Microsoft Interview Question Software Engineer / Developers




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

- Anonymous on March 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- airfang613 on March 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- Happytobeofservice on March 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- Anonymous on March 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- Anonymous on March 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- souravghosh.btbg on March 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What a moron you are! FIRST READ QUESTION, THEN ANSWER.

- @anonymous on March 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Happytobeofservice on March 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Lyons on March 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- anon on March 19, 2011 | Flag
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

- Anonymous on March 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- N.M on March 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- @N.M. on March 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.. :) :)

- hello on June 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We need to find out common elements from sorted array

- N.M. on March 17, 2011 | Flag Reply
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)

- Anonymous on March 21, 2011 | Flag Reply
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++;
    }
}

- Anonymous on March 21, 2011 | Flag Reply
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

- Rahul TeddyMeddy on March 23, 2011 | Flag Reply
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.

- DaleSingh on May 03, 2011 | Flag Reply
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.

- KEEG on June 20, 2011 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More