Amazon Interview Question Development Support Engineers
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.
#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];
}
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?
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).
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.
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....
//|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)
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)
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.
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.
/*
- Anonymous February 11, 2010* 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;
}