## Microsoft Interview Question for Software Engineer in Tests

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

This problem is from Cormen chap 9 - prob 9.3-8
Let X[1..n] and Y[1..n] be two sorted arrays each containing n numbers already in sorted order.
Algorithm is as follows

``````TWO-ARRAY-MEDIAN(X,Y)
n = length[X] // n also equals length[Y]
median = FIND-MEDIAN(X,Y,n,1,n)
if (median == NOT-FOUND)
then median = FIND-MEDIAN(Y,X,n,1,n)
return median

FIND-MEDIAN(A,B,n,low,high)
if(low > high)
return NOT-FOUND
else
{
k = (low+high)/2
if(k == n && A[n] <= B[1]
return A[n]
else if(k<n && B[n-k] <= A[k] <= B[n-k+1]
return A[k]
else if(A[k]> B[n-k+1]
return FIND-MEDIAN(A,B,n,low,k-1)
else
return FIND-MEDIAN(A,B,n,k+1,high)
}``````

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

int find_median(int *a, int a_lower, int a_upper, int *b, int b_lower, int b_upper, int size)
{
if(a_lower == a_upper && b_lower == b_upper)
{
// we have only one element in both the array
return (a[a_upper] < b[b_upper])?a[a_upper]:b[b_upper];
}

int median_a = a[a_lower+size/2];
int median_b = b[b_lower+size/2];

// Case 1 : If both the medians are equal
if(median_a == median_b)
return median_a;
//
// Case 2 : if m1>m2 then median must exist in arr1[a1, a2,…m1] and arr2[b1, b2,…m2….bM]

if(median_a > median_b)
return find_median(a, a_lower, a_upper-size/2, b, b_lower+size/2, b_upper,(size+1)/2 );
else if (median_a < median_b)
return find_median(a, a_lower+(size/2), a_upper, b, b_lower, b_upper-size/2, (size+1)/2);

return -1;

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

@Ganesh

I think your code will not work for

A[]={1,3,5,17,19}
B[]={10,11,12,13,14}

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

Can't it be using merge sort logic???

A[0:n-1];
B[0:m-1];

mid = (n+m)/2;
idx = 0;
for(i=0,j=0; i<n && j <m;)
{
if(A[i] <= B[j])
{
midE = A[i];
i++;
}
else
{
midE = B[j];
j++;
}
if(idx == mid)
return midE;
idx++;
}

for(;i<n;i++)
{
midE = A[i];
if(idx == mid)
return midE;
idx++;
}

for(;j<n;j++)
{
midE = B[j];
if(idx == mid)
return midE;
idx++;
}

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

O(log n)....compare the middle elements of the arrays....depending on which element is bigger....take the upper half of one array n lower half of the other....go on till we have 1 element.....thts the median....in case of even number of elements...there can be 2 medians....

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

a median is described as the number separating the higher half of a sample from the lower half.

if the length of the array is odd, the centre element is the median. If it is even, the two centre elements are the medians!

Right?

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

A related problem i feel find the median of BST in O(logn)

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

kjflkdjsfkdjfsjdkdlsjfdsjj

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

Say A= {1 2 4 6 8 9}
B= {2 5 7 10 11}

Median = {1 2 2 4 5 6 7 8 9 10 11} = 6

int nMedianIndex = (6 + 5) / 2 = 6 or ( 5 in case of zero based index) This means that the median should be the 5th index if all are in one array, sorted.
int nCountindex = 0

do{
1) Compare each element of the two arrays. if element in first array > elelmet in second array, increase second array index
2) Compare each element of the two arrays. if element in second array > elelmet in first array, increase first array index
3) Compare each element of the two arrays. if element in first array = elelmet in second array, increase both indices
4) nCountIndex+=1;
} while (nCountIndex <=nMedianIndex)

return nCOutnIndex.

Complexity: O(n) & O(1)

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

That's incorrect

Test case: A = {1, 2, 3, 4, 5, 6} B = {1, 2, 3, 4, 5, 6}
Median according to the logic above : 6

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

3) Compare each element of the two arrays. if element in first array = elelmet in second array, increase both indices

this one should be changed. Incrase array 1's index only.

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.