## Microsoft Interview Question

Software Engineer in Testsint 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;

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++;

}

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)

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

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

- algooz April 23, 2008