## Microsoft Interview Question for Dev Leads Dev Leads

Country: India
Interview Type: In-Person

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

it can be done in log(n) time using binary search.
Do binary search in both arrays simultaneously, starting with lo1 = lo2 = 0 and hi1=hi2 = n;
At each step, chuck out a portion of each array.

``````public static int findNthRankElement(int[] a1, int[] a2, int n){
// double binary search
int lo1 = 0, lo2 = 0, hi1 = n, hi2 = n;
while (lo1 < hi1 && lo2 < hi2){
int mid1 = lo1 + (hi1 - lo1)/2;
int mid2 = lo2 + (hi2 - lo2)/2;

if (a1[mid1] < a2[mid2]) {
lo1 = mid1+1;
hi2 = mid2-1;
} else if (a1[mid1] > a2[mid2]) {
hi1 = mid1-1;
lo2 = mid2+1;
} else {
return a1[mid1];
}

//System.out.println(lo1 + " " + hi1 + " - " + lo2 + " " + hi2);
}
return (lo1 >= 0 && lo1 < a1.length) ? a1[lo1] :
(hi1 >= 0 && hi1 < a1.length) ? a1[hi1] :
(lo2 >= 0 && lo2 < a2.length) ? a2[lo2] :
a2[hi2] ;
}``````

The funky return statement is because i couldn't be bother to figure out which one to return (btw this function return the actual element rather than it's rank)

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

This method does not work
1) if the lengths of the given arrays are not equal
2) if the arrays lengths is less than k

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

Doing binary search.
Complexity: O(log N), where N is the size of array data

``````int getNth(int a[], int size_a,
int b[], int size_b,
int k) {

if(size_a + size_b < k || k <= 0) {
}

int left_a = 0;
int right_a = (k < size_a) ? k : size_a;

do {
// pivots go from 0, 1...N
// 0 - dont include any element from that array
// 1 - first element of the array
// Hence, you will notice that all array references are left shifted by 1

int pivot_a = left_a + (right_a - left_a) / 2;
int pivot_b = k - pivot_a;

// Second array is smaller than "k"
if(pivot_b > size_b) {
left_a = (left_a == size_b) ? size_b + 1 : size_b;
continue;
}

if(pivot_a == 0 && left_a == right_a) {
return b[k-1];
}

if(pivot_b == 0) {
return a[k-1];
}

// We have found the expected element when:
// element pointed by a pivot is less than or equal to all elements of the other array
// Example with k = 5
// 1,3,5,7,9
// 2,4,6,8,10
// when pivot_a = 3 and pivot_b = 2
// (a[pivot_a-1]=5) is less than (b[pivot_b]=6)
// and
// (b[pivot_b-1]=2) is less than (a[pivot_a]=5)

if(pivot_b == size_b || a[pivot_a-1] <= b[pivot_b]) {
if(pivot_a == size_a || b[pivot_b-1] <= a[pivot_a]) {
return (a[pivot_a-1] > b[pivot_b-1]) ? a[pivot_a-1] : b[pivot_b-1];
}
else {
left_a = pivot_a + 1;
}
}
else {
right_a = pivot_a;
}
}
while(1);
}``````

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

What does it mean by nth rank element? Does it mean nth largest/smallest element? Thanks.

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

Simplest method is to use merge() from mergeSort to end up with the combined sorted array, then selection-rank algorithm utilizing partition() from quickSort.
Merge: O(m+n)
Partition: O(lg(m+n)) avg, O(m+n) worst
Overall worst case: O(m+n)

There is also the observation that given some value v1 in array a, the rank of v1 in the combined array is the rank of v1 in array a + the rank of the largest value v2 in array b that is <= v1. Using this, you can recursively chop away regions of both arrays. However the hard part is finding the rank of v2, which itself is O(lgm) avg and O(m) worst case.
Using this technique, the avg case becomes O(lgnlgm), and worst O(mn). It is questionable whether the possible performance increase is worth the complexity and possible much worse performance.

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

Here is the method which i think will work here.

``````A, B are input arrays
FindRank(A, i1,j1, B, i2, j2, N)
if i1=j1 then
q = Apply BS in B[i2..j2] for key A[j1], we use nearest value which is less then A[j1] to find this
return B[i2 + |N-(q-i2+2)|] as response
else if i2=j2 then
q = Apply BS in A[i1..j1] for key B[j2], we use nearest value which is less then B[j2] to find this
return A[i1 + |N-(q-i1+2)|] as response
else
q =  (j1+i1)/2
r = Apply BS in B[i2..j2] for key A[q], we use nearest value which is less then A[q] to find this
if N > (r-i2 + q-i1)
call FindRank(A, q,j1, B, r, j2, N - (r-i2 + q-i1))
else if N < (r-i2 + q-i1)
call FindRank(A, i1,q, B, i2, r, N)
else if N = (r-i2 + q-i1)
return r or q based upon whether A[q] is big or B[r] is big
end
end
end``````

Complexity
Time : O(Log(n)*Log(n))
Space : O(1)

A simpler but O(N) complexity algorithm can be found using two pointer i, j strting from 0, and moving the samller value pointer until i+j < n.

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

how about this? Isn't this simple? Am I missing something?

``````private static int FindNth(int[] arr1, int[] arr2, int n)
{
int i = 0, j = 0, c = 2, target = 0;

while (c < n)
{
if (arr1[i] < arr2[j])
{
i++;
target = i;
}
else
{
j++;
target = j;
}

c++;
}
return arr2[target];
}``````

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

I can only think of a O(n) solution, where n is the rank.

Perform the merge method (as in the merge sort) to move one cursor on each sorted array. When both cursors have moved n times, you found the n-ranked element.

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

Either start from the back of array , or you have to move (a1.length+a2.length -n ) to get the nth rank element.

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

set a pointer i to first array A and j to second array B.
setup a counter to 0

in a loop--
compare A[i] and B[j]

if(A[i] = B[j])
increment counter. if(counter == n) then result = A[i] or B[j]. else increment i and j

if(A[i] < B[j])
increment counter. if(counter == n) then result = A[i]. else increment i

if(B[j] < A[i])
increment counter. if(counter == n) then result = B[j]. else increment j.
--

This will take care of assigning same rank to integers that are equal.
There are some more conditions to take care of

1. i > A size
compare subsequent integers in B and dont increment counter if they are equal. Once you find unequal subsequent integers, increment counter and check if the counter is n. in which case the first integer (smalled one) of the two being compared is the answer.
(same goes with j > B size, which ever runs out first)

2. you ran out of both A and B and counter is still not n, in which case there is no answer

space O(1)
time O(n)

what if the arrays are sorted in desc order or one is ascending the other is descending? the only difference in such cases will be if you are incrementing or decrementing i / j. In any case, i and j need to point to the smallest integer before starting comparisons.

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

``````// v1 and v2 are sorted vectors.
// value in nelem is valid only if return value is true
bool FindNthElement(vector<int>& v1, vector<int>& v2, int& nelem, int rank)
{
bool ret = false;
int n1 = v1.size(), n2 = v2.size();
int size = n1+n2;
int i=0,j=0,k=0, count = 0, temp;

if( (rank <= size) && (rank>0) )
{
while( (k<size) && (count!=rank ) )
{
if( (i<n1) && (j<n2) )
{
if( v1.at(i) <= v2.at(j) )
{
temp = v1.at(i); i++;
}
else
{
temp = v2.at(j); j++;
}
}
else if(i<n1)
{
temp = v1.at(i); i++;
}
else
{
temp = v2.at(j); j++;
}
nelem = temp; count++;
if( count == rank )
{
ret = true;
}
k++;
}
}

return ret;
}

Please let me know if you my code gives a wrong result. :)``````

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.