## Lime Labs Interview Question for Consultants

• 0
of 0 votes

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
of 0 votes

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+b -> first
a+b OR a + b
so please take all combinations in mind

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

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
of 0 votes

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
of 0 votes

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
of 0 votes

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
of 0 votes

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
of 0 votes

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
of 0 votes

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
of 0 votes

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
of 0 votes

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
of 0 votes

WRONG i think

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

You are not checking for all combinations i think

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

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
of 0 votes

how about this way:

// AA and BB are sorted
for(int x=0;x<=k-1;x++)
{
..for(int y=0;y<=k-1-x;y++)
....C.add(AA[x]+BB[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++;
}

Add a Comment
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.

Learn More

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

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More