## Amazon Interview Question for Development Support Engineers

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

/*
* Given two sorted integer arrays A and B of size n and m respectively, find
* the kth smallest element in the union of A and B in O(lg(n)+lg(m)) time....
*/

#include <iostream>

using namespace std;

int kthMin(int a[], int n, int b[], int m, int k)
{
if (n+m < k)
return 0;

int ua;
int la;
int ub;
int lb;
int ia;
int ib;

la = 0;
lb = 0;
ua = n-1;
ub = m-1;

ia = k/2-1;
if (ia > ua)
{
ia = ua;
}
ib = k-ia-2;
if (ib > ub)
{
ib = ub;
}
ia = k-ib-2;

while ((ia+1 < n && a[ia+1]<b[ib]) || (ib+1<m && b[ib+1]<a[ia]))
{
if (a[ua] < b[lb])
{
if (n<k) return b[k-n-1];
else return a[k-1];
}
if (b[ub] < a[la])
{
if (m<k) return a[k-m-1];
else return b[k-1];
}

if (ia+1 < n && a[ia+1]<b[ib])
{
la = ia;
ub = ib;
ia = int((ua+la)/2.0+0.5);
ib = k-ia-2;
if (ib > ub)
{
ib = ub;
}
ia = k-ib-2;
} else
{
lb = ib;
ua = ia;
ib = int((lb+ub)/2.0+0.5);
ia = k-ib-2;
if (ia > ua)
{
ia = ua;
}
ib = k-ia-2;
}
}

if (a[ia] > b[ib])
return a[ia];
else
return b[ib];
}

int main()
{
int n = 9;
int a[] = {2, 4, 6, 8, 10, 12, 14, 16, 18};
int m = 9;
int b[] = {1, 3, 5, 7, 9, 11, 13, 15, 17};
int k = 9;
/*
int n = 9;
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int m = 9;
int b[] = {10, 11, 12, 13, 14, 15, 16, 17, 18};
int k = 1;
*/
/*
int n = 9;
int a[] = {1, 2, 3, 4, 5, 15, 16, 17, 18};
int m = 9;
int b[] = {6, 7, 8, 9, 10, 11, 12, 13, 14};
int k = 16;
*/

cout << kthMin(a, n, b, m, k);

return 0;
}

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

Could you please explain the algo. Its difficult to decipher a long code here.

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

Here's the high-level idea for a special case. Suppose that m = n = 2^p + 1 and that we're looking for the median (lower or upper; it doesn't matter). If p = 0, then use brute force (O(1)). Otherwise, compare the median a of A with the median b of B. If a <= b, then the smallest 2^p elements of A and the largest 2^p elements of B contain no medians. The case a >= b is symmetric. Recur with p one smaller, for a total running time of O(1).

To recover the general case, observe that by implicitly padding A and B with the right number of elements -infinity and infinity we can reduce the problem of finding the kth element in arbitrarily sized arrays to the above case without an increase in running time.

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

#include<stdio.h>

int main ()
{
int a[]={1,10,12,13,14};
int b[]={9,11,15,16,17};
int k =5; //the 5th smallest no
int i = k-1;
int j = k-1;
while(i+1+j+1>k)
{
if(a[i]<=b[j])
{
j--;
}
else
{
i--;
}
}
if(j<i)
cout<<a[i];
else
cout<<b[j];
}

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

i think the last condition should be

if(a[i] < b[j] )
cout << a[i];
else
cout << b[j];

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

If k > 5 we get index out of bounds for a[i] and b[j]

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

Are you kidding me? Do you have any idea what O(lg(n)+lg(m)) means?

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

(Y)

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

Here is a thought use a min heap of size k and have 2 pointers positioned at the start of 2 arrays, say i pointing to A[0] and j pointing to B[0] then...

``````int numberOfElementsInHeap = 0;
int kthSmallestElement = -1;
while(true) {
if(A[i] < B[j]) {
insert A[i] into the min heap
kthSmallestElement = A[i]
i = i + 1;
numberOfElementInHeap++;
}else {
insert B[j] into the min heap
kthSmallestElement = B[j]
j = j + 1;
numberOfElementInHeap++;
}
if(numberOfElementInHeap == K) {
return kthSmallestElement;
}
}``````

The heap above jsut serves the purpose of conforming with the qus requirements log(n) + log(m). We are obtaining the kth smallest element in the loop itself.

Please comment if above looks corrrect?

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

If we use heap of size k, and keep track of highest element in k, then we're done in O(k).
Actually this what u're doing here, but complexity in not lg(n)+lg(m).

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

Hm, depending on the value of K, we may need to insert all elements from both arrays into this heap (say if we need the last element in the combined array), but even then the complexity becomes log(n) + log(m). Not quiet what we want, BUMMER.

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

aquila.25, your solution is O(m+n) in the worst case. Not a log answer.

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

This is what I am thinking:

Given two array A, B
case 1: if a[0] < b[0] && a[n-1] < b[0], then
a. if(k>n) return b[k-n-1];
else return a[n-k-1];
b. reverse case for array b similar to case 1.

case 2: if case 1 does not hold then,
1. if(a[0] < b[0])
search in array starting from a[n/2] and b[0]
else
search in array starting from a[0] and b[n/2]

In this manner every search with divide the problem in to half and keep count if the number kth smallest or not.

Let me know if this flies....

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

//|A| = m
int A[] = new int[] { 1, 10, 12, 13, 14, 29, 38, 76 };
//|B| = n
int B[] = new int[] { 9, 11, 15, 16, 17, 18, 19, 20 };

int k = 8;

TreeMap tree = new TreeMap();

//insert array A into the tree, with time: O(log m)
for (int i = 0; i < A.length; i++) {
Integer value = new Integer(A[i]);
tree.put(value, value);
}

//insert array B into the tree, with time: O(log n)
for (int i = 0; i < B.length; i++) {
Integer value = new Integer(B[i]);
tree.put(value, value);
}

//get the k the value, with time: O(k)
Integer kthValue = null;
int count = 0;
Iterator itor = tree.keySet().iterator();
while(itor.hasNext()){
Integer value = (Integer) itor.next();
count++;
if(count==k){
kthValue = value;
}
}

//total time = O(log m) + O(log n) + O(k)
// = O(log m) + O(log n) //when k is small.
// = O(log m + log n)

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

I think we can use binary search for this problem. First, find both the middle of two array, mid_N and mid_M. if mid_N is the smaller part, and K > N/2, we can dump the first half of the array N, vice versa. Every time we can dump half of one array. The we can do it in O(logM+logN)

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

sounds easy - but show me how in more specific terms :)

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

``````Algo(A, 1, n, B, 1, m)
{
i = 1+n/2;
j = 1+m/2;

if(i+j == k)
return max(A[i], B[j]);
else
if(i+j > k) //Search in left sub arrays
return Algo(A, 1, i, B, 1, j, k);
else{	//i+j > k
if(A[i] < B[j]) //Eliminate A's left half
return Algo(A, i+1, n, B, 1, j, k-i);
else 	//Eliminate B's left half
return Algo(A, 1, i, B, j+1, m, k-j);
}
}``````

Boundary conditions may be checked properly.

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

i have one:

FindMedian(A,B,n,m)
assume A, B, and n> m, and find the kth.
////compare A[n/2] and B[m/2]
if A[n/2] < B[m/2], means the median is to the bigger of A and smaller of B.
next search A[n/2+m/2/2] and B[m/2-m/2/2]
if A[n/2] > B[m/2], means the median is to the smaller of A and larger of B.
next search A[n/2-m/2/2] and B[m/2+m/2/2]
since every step we are narrowing by half of the smaller array, the total should take O(lgm)

if u can find median, u can find kth, by going median then median of one half of median and so on.

the first median works on entire arrays, and takes O(lgm+lgn), because in the general case u don't know which is bigger.

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.