## Microsoft Interview Question Software Engineer / Developers

• 0

We have two unique sorted arrays. Need to find common elements from these arrays.

I have followed merge sort and get the common elements. Is there any efficient approch?

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

keep two pointers, walk through the 1st to the last. O(n+m). Details omitted

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

+1, utilize the fact that the two arrays are SORTED.

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

Take two pointers pointing to the two arrays. Now compare the values, if(*p1>*p2) p2++; else p1++
if both are equal, print the value. Traversing in this fashion the complexity will be O(n+m).

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

this is a wrong approach... i can prove this with my example arrays...
1 3 4 8 and 2 1 1 4... here the unique elements are 1 and 4.

1 3 4 8 and 2 1 1 4
^ ^
2 is greater so increment the first pointer

1 3 4 8 and 2 1 1 4
^ ^
3 is greater increment the second pointer

1 3 4 8 and 2 1 1 4
^ ^
again 3 is greater, so increment the second pointer aggain

1 3 4 8 and 2 1 1 4
^ ^
again 3 is greater increment the second pointer

1 3 4 8 and 2 1 1 4
^ ^
now 4 is greater so increment the first pointer

1 3 4 8 and 2 1 1 4
^ ^
both are equal so insert 4 in the new array. increment the first array.

1 3 4 8 and 2 1 1 4
^ ^
all elements in both arrays are traversed in the order of O(n+m). but only one unique value is found. ie '4' but and the unique value '1' could not be found...

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

this is a wrong approach... i can prove this with my example arrays...
1 3 4 8 and 2 1 1 4... here the unique elements are 1 and 4.

``````1 3 4 8 and 2 1 1 4
^           ^
2 is greater so increment the first pointer

1 3 4 8 and 2 1 1 4
^         ^
3 is greater increment the second pointer

1 3 4 8 and 2 1 1 4
^           ^
again 3 is greater, so increment the second pointer aggain

1 3 4 8 and 2 1 1 4
^             ^
again 3 is greater increment the second pointer

1 3 4 8 and 2 1 1 4
^             ^
now 4 is greater so increment the first pointer

1 3 4 8 and 2 1 1 4
^               ^
both are equal so insert 4 in the new array. increment the first array.

1 3 4 8 and 2 1 1 4
^             ^``````

all elements in both arrays are traversed in the order of O(n+m). but only one unique value is found. ie '4' but and the unique value '1' could not be found...

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

I have no idea what just happened. The question is:

"We have two unique sorted arrays. Need to find common elements from these arrays."

Your arrays are neither sorted nor do you find the common elements from these arrays.

The order O (n + m) solution is the most efficient. You have to see each no. at least once!

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

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

In your example, the array is not sorted but the question is for sorted array. So i think the algorithm i proposed should work fine.

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

Well, without further details, it is hard to say O(N+M) better than O(min(NlogM, MlogN)). i.e. if N is too much smaller than M, the latter would work better.

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

I believe interviewer would prefer an O(N+M) solution. The reason is as there is no specification, we can assume each of the sorted array is of similar size, i.e. M = O(N). Which implies total complexity O(N), which is superior to O(N logN).

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

pick one element from one array and Use binay search on another one
YOu can also optimize the binay search as the 1st array is sorted

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

That will be o(n2). Each element in one array comparing with another array. But mergesort will be nlog2n

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

Go to 1st year CS class to learn complexity of binary search. FYI, it's O(logn), so total complexity is O(nlogn).

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

@N.M. what an idiot.. :) u should go back to some higher secondary school coz these things u should have learnt there itself.. complexity of binary search.. lolz.. :) :)

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

We need to find out common elements from sorted array

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

what does "unique" mean here? If it means there is no duplicate element in EACH of the two arrays, then the solution of O(m + n) is available if we can use additional memory.

Solution of O(m + n)
1. merge the two arrays into one ordered big array.
2. scan through the big array to find any duplicate elements (because it is sorted, just check any pair of two elements)

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

``````int i = 0;
int j = 0;
while (i < n && j < m) {
if (a[i] == b[j]) {
cout << a[i] << " ";
i++;
j++;
} else if (a[i] < b[j]) {
i++;
} else {
j++;
}
}``````

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

Ans is simple & clear:

you have two sorted array of unique elemets
a1 = {1, 3, 5, 6}
a2 = {3, 4, 6}

take two indexes ia1 & ia2 pointing to a1[0] & a2[0] respectively

compare both elements pointing by index
if(a1[ia1] == a2[ia2])
{
/* found common element a1[0] */
}
else
if(a1[ia1] < a2[ia2])
{
ia1++; /* increment to compare with next element */
}
else
{
ia2++ /* increment index of second array*/
}
}

perform above steps until any one array is exhausted

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

How about improving little more on the O(MlogN) solution.
When we do a binary search on the second element of the array, we can use the information from first element's search. So if a1 was found (or not found) at index i(or the last index that was checked for a1) we know that a2 would be between [i,n]. Similarly for next search use information, and we go on decreasing N for every search we do.

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

Just a different thought..
If u can use additional Memory, we can store elements of first array in Hash and then iterate through 2nd array and check if its present in Hash.

Name:

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

### Books

is a comprehensive book walking you through 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.