## Microsoft Microsoft Interview Question for Software Engineer in Tests

Team: Office
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 5 vote

Say the two arrays are: a[] of size n and b[] of size m.
Declare another array c[] of size m+n
Compare a[i] with b[j], put the smaller value into c[k]
keep incrementing the index of the array whose element is smaller and put it into c[k++]
keep continuing this unless one of the arrays is used.
Now since the other array is sorted already, simply copy all the remaining elements into c[].

Comment hidden because of low score. Click to expand.
2

I think you also have to consider the case their a[i]=b[j], where then you would simply make the next entry of c=a[i] and then at the end, you would need to count the number of null entries in the array, make a new array of the appropriate size, and copy the entries over.

Comment hidden because of low score. Click to expand.
0

@SL: the note about a[i] == b[j] is correct, because otherwise you'll end up with duplicates on the merge resultn, and then the result size could be less and n + m.

Comment hidden because of low score. Click to expand.
2

Yes.. I happened to miss that condition out..
Here is the code after incorporating the condition for equality:

``````package com.career.cup;

class MergeWithoutDuplicates {

static int[] getMergedArrayWithoutDuplicates(int[] firstArray, int[] secondArray)
{
int firstArraySize=firstArray.length;
int secondArraySize=secondArray.length;
int i=0,j=0,k=0;
int[] resArray=new int[firstArraySize+secondArraySize];
while(i<firstArraySize && j<secondArraySize)
{
if(firstArray[i]==secondArray[j])
{
resArray[k++]=firstArray[i++];
j++;
}

else if(firstArray[i]<secondArray[j])
resArray[k++]=firstArray[i++];

else
resArray[k++]=secondArray[j++];

}

while(i<firstArraySize)
resArray[k++]=firstArray[i++];

while(j<secondArraySize)
resArray[k++]=secondArray[j++];

return resArray;
}

public static void main(String[] args)
{
int[] firstArray={1,2,6,9,10,27};
int[] secondArray={2,8,10,89};
for(int resIndividualElement: getMergedArrayWithoutDuplicates(firstArray,secondArray))
{
System.out.println(resIndividualElement);
}
}
}``````

This solution works fine but since we created an array of size (m+n) and when there are duplicates, we dont use some of these slots in the result array we are returning which are initialized to 0. Can someone please suggest how we could avoid this without having to create a whole new array only to accommodate the size.

Comment hidden because of low score. Click to expand.
0

One thing you might have missed it here, Suppose we have arrays like
int[] a ={1,5,6,7,9,12,17};
int[] b = {2,3,4,7,10,11,12,18,22};
the way u have mentioned, we will get something like
{1,2,3,5,4,6,7,9,10,11,12}

But , this contradicts the assumption, i.e result should be sorted.

Correct me if i am wrong .

Comment hidden because of low score. Click to expand.
0

@sushant001:kindly check ur ans the result by using above algo will be {1,2,3,4,5,6,7,9,10,11,12,17,18,22} bcoz while cmpring 3 and 5 index of b will be incrmnted and nw it will pt to 4 since 4 is also less than 5 than 4 will be oinserted into new array and now agn index of b will be incremented and it will point to 7 i hope u got it

Comment hidden because of low score. Click to expand.
-1
of 1 vote

[1,2,3]
[3,3,3,4,4,4]

Comment hidden because of low score. Click to expand.
0

Question says that both input arrays are sets.
[3,3,3,4,4,4] is not a valid set.

Comment hidden because of low score. Click to expand.
4
of 4 vote

``````void Merge(int * a, int m, int * b, int n, vector<int>& c)
{
int p = 0; int q = 0;
while (p < m && q < n)
{
if (a[p] < b[q])
{
c.push_back(a[p++]);
}
else if (a[p] > b[q])
{
c.push_back(b[q++]);
}else
{
c.push_back(a[p++]);
q++;
}
}
while (p < m)
{
c.push_back(a[p++]);
}
while (q < n)
{
c.push_back(b[q++]);
}
}``````

Comment hidden because of low score. Click to expand.
0

Good solution.

With the STL vector there isn't the problem of the find the size of the merged set, and the effect the vector reallocation on the time complexity is negligible.

But in this case it's worth to note that the resulting container's type is not the same of the inputs'.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Use binary search tree is the most efficient way to solve this problem.
In Java, we have TreeSet.
You could also implement your own binary tree and add data into this tree.

``````import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class MergeSet {

Set<Integer> resultSet = new TreeSet<Integer>();
for(int i=0;i<set1.size();i++){
int value = set1.get(i);
if(value > 0){
}
}

for(int i=0;i<set2.size();i++){
int value = set2.get(i);
if(value > 0){
}
}
return resultSet;
}

public static void main(String[] args){
Set<Integer> result = mergeSets(set1,set2);
System.out.println(result);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is a complement of this one: 15273751

Comment hidden because of low score. Click to expand.
0
of 0 vote

Somewhat similar to 15290749

Comment hidden because of low score. Click to expand.
0

how about maintaining a simple BST. or a TreeSet in java

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is the runtime for this O(n) ? n being size of the larger of the two sorted lists?

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can just merge both the arrays and sort it and put it in a hashset.

public static void main(String[] args)
{
int[] a ={1,5,6,7,9,12,17};
int[] b = {2,3,4,7,10,11,12,18,22};
int[]c=new int[a.length+b.length];
for(int i=0;i<=a.length-1;i++)
{
c[i]=a[i];
}
for(int i=a.length,j=0;i<=c.length-1;i++,j++)
{
c[i]=b[j];
}
Arrays.sort(c);
HashSet<Integer> hset=new HashSet<>();
for(int num:c)
{
}
System.out.println(hset);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.LinkedHashSet;
import java.util.Set;

public class MergeSortedArrays {

public static void main(String[] args) {
int[] a= {1,2,6,9,10,27};
int[] b= {2,8,10,89};
int[] result=merge(a,b);
for(int i : result)
{
}
System.out.println(set);

}
public static int[] merge(int[] a,int[] b)
{
int m=0;int n=0;
int k=a.length+b.length;
int[] c=new int[k];
int j=0;
while(m<a.length && n<b.length)
{
c[j++] = a[m]<=b[n] ? a[m++] :b[n++];
}
while(m<a.length)
{
c[j++]=a[m++];
}
while(n<b.length)
{
c[j++]=b[n++];
}
return c;
}

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.