Lime Labs Interview Question Consultants
Please test it.
If I say 4 least sum then u cannot just added top 4 elements of sorted array because say both are sorted then
a[0]+b[0] -> first
a[0]+b[1] OR a[1] + b[0]
so please take all combinations in mind
A brute force approach would be sort both arrays n log n, then create a min heap, and push all possible combination of first k elements in both arrays, which is k square. If k << n, the complexity is still O(n log n).
Are you looking for a better solution than this ?
One improvement I can add: it is possible to find k first elements in n element array in O(n*k) complexity using algorithm for k-order statistics, so if k<<n it is better. Overall complexity thus is O(n*k + k*k).
Finding k smallest elements from N can be done in O(N). Finding k smallest from k*k elements can be done in O(k*k).
Overall is O(N + k*k).
Finding k smallest elements from N can be done in O(N). Finding k smallest from k*k elements can be done in O(k*k).
Overall is O(N + k*k).
Finding k smallest elements from N can be done in O(N). Finding k smallest from k*k elements can be done in O(k*k).
Overall is O(N + k*k).
Finding k smallest elements from N can be done in O(N). Finding k smallest from k*k elements can be done in O(k*k).
Overall is O(N + k*k).
Finding k smallest elements from N can be done in O(N). Finding k smallest from k*k elements can be done in O(k*k).
Overall is O(N + k*k).
Will this work?
AA=sort(A);
BB=sort(B);
pA=0;
pB=0;
count=1;
while(1)
{
....x=AA(pA)+BB(pB+1);
....y=AA(pA+1)+BB(pB);
....if(x<=y)
....{
........pB++;
....}
....if(y<x)
....{
........pA++;
....}
....count++;
....if(count==k)
........return AA[pA]+BB[pB]
}
should be O(nlogn+k)
please correct me if there is something wrong or i misunderstood the question
oh i see where i am wrong. I will find out a way to correct this one.
Thanks very much.
This problem appeared before...
Assume the two original arrays are (a0, a1, ...an) and (b0, b1, ... bm) sorted in ascending order. Let's consider the n by m array with (i, j) holding the sum ai + bj. The smallest obviously is (0,0), however the candidates for next smallest could be either (0,1) or (1, 0). In general assuming that you already picked k-1 smallest sums then the candidates for the next smallest will be on the “boundary” of these k-1 cells in the 2d array. Keep a heap for these boundary points and then select the next smallest from the heap. The size of the heap can be kept small (<k) so maintaining the heap (and picking the next smallest) at each step is log(k). Therefore we have a k*log(k) algorithm.
Pseudo code:
i = 0;
nextSmallest = sum(0,0);
While( i < k)
{
Add the two boundary cells of S =(x, y) , {(x + 1,y), (x, y+1)} to the heap H;
s = H.min()
i++;
}
This problem appeared before...
Assume the two original arrays are (a0, a1, ...an) and (b0, b1, ... bm) sorted in ascending order. Let's consider the n by m array with (i, j) holding the sum ai + bj. The smallest obviously is (0,0), however the candidates for next smallest could be either (0,1) or (1, 0). In general assuming that you already picked k-1 smallest sums then the candidates for the next smallest will be on the “boundary” of these k-1 cells in the 2d array. Keep a heap for these boundary points and then select the next smallest from the heap. The size of the heap can be kept small (<k) so maintaining the heap (and picking the next smallest) at each step is log(k). Therefore we have a k*log(k) algorithm.
Pseudo code:
i = 0;
nextSmallest = sum(0,0);
While( i < k)
{
Add the two boundary cells of S =(x, y) , {(x + 1,y), (x, y+1)} to the heap H;
s = H.min()
i++;
}
sort both arrays and add the first elements from both arrays
- chennavarri October 14, 2010