Microsoft Interview Question Software Engineer / Developers
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).
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...
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...
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!
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.
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.
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
That will be o(n2). Each element in one array comparing with another array. But mergesort will be nlog2n
Go to 1st year CS class to learn complexity of binary search. FYI, it's O(logn), so total complexity is O(nlogn).
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)
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
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.
keep two pointers, walk through the 1st to the last. O(n+m). Details omitted
- Anonymous March 17, 2011