anonymous
BAN USER- 3of 3 votes
AnswersGiven two sorted arrays A and B. Find the first K pairs (a, b) from A and B which have the smallest sum of a & b. Supposed K is small compared to |A| x |B|
- anonymous in United States
For example:
A = [1, 2, 3, 6, 10]
B = [1, 4, 5, 7]
K = 5
Result [(1,1), (1,4), (1,5), (2,1), (3,1)]| Report Duplicate | Flag | PURGE
Google Intern - 1of 1 vote
AnswersGiven a sorted distinct array of integers and a key K. C closest elements to K are in range [L,R] inclusive, L<=R. Return L as the left index of C closest elements to K.
- anonymous in United States
For example:
A = [1, 2, 5, 8, 9, 13]. K = 8 and C = 4. The result L = 3 because 4 closest elements to 8 are [5, 8, 9, 13]| Report Duplicate | Flag | PURGE
Google Intern Algorithm
An suboptimal/optimal solution in O((log(n))^2) is:
1. Find position of K by using binary search in log(n) time
2. Do a nested binary search inside binary search to find L.
Binary search for radius (low_radius, high_radius) around key K:
- Binary search for number of elements on the left of K
- Binary search for number of elements on the right of K
- Total = number elements from left + number of elements from right + 1
If total >= C we binary search on (low_radius, mid_radius), otherwise we binary search on (mid_radius+1, high_radius).
Full code:
int bs(int A[],int low,int high,int value){
if(low==high)
return low;
int mid = (low+high)/2;
if(A[mid]>=value)
return bs(A,low,mid,value);
return bs(A,mid+1,high,value);
}
int bsR(int A[],int lowR,int highR,int C,int K,int index){
if(lowR == highR){
if(index-1<0)
return index;
int left = C-lowR;
int leftIndex = bs(A,0,index-1,left);
if(A[leftIndex]>=left)
return leftIndex;
return index;
}
int midR = (lowR+highR)/2;
int right = C + midR;
int left = C - midR;
int nLeft = 0;
if(index-1>=0){
int leftIndex = bs(A,0,index-1,left);
if(A[leftIndex]>=left)
nLeft = index-leftIndex;
}
int nRight = 0;
if(index+1<=n-1){
int rightIndex = bs(A,index+1,n-1,right+1);
if(A[rightIndex]<=right){
nRight = rightIndex - index;
}
else{
if(rightIndex>index+1){
nRight = rightIndex - 1 - index;
}
}
}
int n = 1 + nLeft + nRight;
if(n>=K)
return bsR(A,lowR,midR,C,K,index);
return bsR(A,midR+1,highR,C,K,index);
}
int kClosest(int A[],int n,int C,int K){
int index = bs(A,0,n-1,C);
int r = max(A[n-1]-C,C-A[0]);
return bsR(A,0,r,C,K,index);
}
M is 10K servers, N is 1 billion integers each server has. The complexity to find the median is O(N*M*log(M)/2) = O(N*M*log(M)). The memory usage is O(M).
1. Sort each server takes O(Nlog(N))
2. Use an array A (size M) to store the first elements from each server.
3.
count = 1
ret = 0
while(count<N*M/2){
3.1 find the minimum element m at index from the array A takes O(log M)
3.2 ret = m
3.3 A[index] = getNextElement(index) from the index_th server takes O(1)
//getNextElement(index) return the next element from the index_th server, if
//if it exceeds the max size of the index_th server, then return INF value
3.4 increase count by 1
}
3.5 ret is result we want
My solution is n*log(maxSum)*log(m).
- anonymous August 05, 2017Binary search on range (A[0]+B[0],A[n-1]+B[m-1]).
We get the mid_sum = (low + high)/2
total = 0
For each element a in A, use second binary search to find number of elements in B which <= mid_sum - a, add that number to total.
If low == high, then return the pairs from above loop.
if(total >= K) binary search on (low, mid_sum), otherwise binary search on (mid_sum+1, high)