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(index1<0)
return index;
int left = ClowR;
int leftIndex = bs(A,0,index1,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(index1>=0){
int leftIndex = bs(A,0,index1,left);
if(A[leftIndex]>=left)
nLeft = indexleftIndex;
}
int nRight = 0;
if(index+1<=n1){
int rightIndex = bs(A,index+1,n1,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,n1,C);
int r = max(A[n1]C,CA[0]);
return bsR(A,0,r,C,K,index);
}

anonymous
August 04, 2017 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

anonymous
July 18, 2014 Open Chat in New Window
My solution is n*log(maxSum)*log(m).
 anonymous August 05, 2017Binary search on range (A[0]+B[0],A[n1]+B[m1]).
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)