## Lime Labs Interview Question for Consultants

• 0

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

sort both arrays and add the first elements from both arrays

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

If I say 4 least sum then u cannot just added top 4 elements of sorted array because say both are sorted then
a+b -> first
a+b OR a + b
so please take all combinations in mind

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

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 ?

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

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).

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

Hi

Thanks for the help.
It would be great if you can elaborate on the solution

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

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).

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

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).

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

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).

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

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).

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

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).

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

Moderators, please, delete unwanted messages and fix the posting form.

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

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

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

WRONG i think

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

You are not checking for all combinations i think

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

oh i see where i am wrong. I will find out a way to correct this one.
Thanks very much.

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

// AA and BB are sorted
for(int x=0;x<=k-1;x++)
{
..for(int y=0;y<=k-1-x;y++)
}
CC=sort(C);
return CC[k];

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

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++;
}

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

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++;
}

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.