## Google Interview Question

you missed 1

else {

sum = A[p.a_index+1] + B[p.b_index+1];

max_heap.put(make_pair(p.a_index+1, p.b_index+1, sum));

}

@mytestaccount2: BIN is right, did you actually try your code? (e.g. A = [ 9, 8, 1], B = [9, 3, 1]). You are always increasing the gap between the two indexes: a_index and b_index, so you will miss the A[1] + B[1] pair. Just look at the code: if a_index < b_index you increment again b_index, and when a_index > b_index you again increment a_index; so except for the initial case a_index = b_index = 0, they'll never be the same.

If i got it correctly then there will be two arrays sorted/unsorted now we need to find out sum of elements which will be kth largest....

If this is right(if unsorted) u might want to sort it and start adding from the end...u know every (i)mod3 th largest sum as A[n]+B[n] is the largest then we've A[n]+B[n-1],A[n-1]+B[n] in between..next 4th biggie is A[n-1]+B[n-1]...go something this way...u already ....but this will not be the question I am sure this one's so darn easy....

what i mean by i mod 3 was for every i(mod3)==0 u've a known largest number...so we might use it :)

I think yoyr concept is not valid.

Check it for:

First Array :10 8 6 4 1

Second Array: 9 6 3 2 1

I am sorry , I am a bit slow here...Could you please explain if you discard your order of sorting(which we are doing ourself and assume ascending) then exactly how is that going to fail...

dude i never said that A[n]+B[n-1],A[n-1]+B[n] will be in any order..I left that to figure out once we know the index i such that k falls in between of out Arithmetic progression of known largest numbers as 1st,4th,7th,10th and so on where 1st largest belongs to A[n]+B[m] , 4th largest will be A[n-1]+B[m-1] , 7th largest will be A[n-2]+B[m-2] and so on...just figure out where K rests in AP..its simple math I guess....but for that we need to reach to the point right...ok...I'll be a bit more descriptive.....

@abhi, what if A and B are as follows?

A: 51, 52, 53

B: 1, 2, 100

The third largest is (51 + 100), not (53 + 2)

Sort both the arrays in descending order O(nlogn) and then the following code snippet

int Kthlargepair(int[] a, int[] b)

{

int aIndex = 0;

int bIndex = 0;

for(int i = 1; i < k; ++i)

{

if(a[aIndex] > b[bIndex])

++aIndex;

else

++bIndex;

}

return a[aIndex] + b[bIndex];

}

The above code is of complexity O(n)

Total complexity: O(nlogn)+O(n) = O(nlogn)

What I can think is of O(n^2)

Maintain a mean heap of size k.For each sum(one element from first array and another from second array),if sum<top_of_the_heap the no need to insert it

else

Remove the top.Insert the sum at the top.Call Min heapify.

At last the top element is the kth largest.

Seems like a young tableau problem, if we decide to sum up all elements in both sorted array.

sort: nlogn

sum: mn

young tableau extraction: klogn

total: mn

this can be reduced if we can come up with some scheme that identifies only those elements which needs to be added (reduced sum complexity to less than "mn")

This problem can solved in O(n * log(max_Value(a) + max_Value(b) )) + O(nlogn) using binary search. First sort both the arrays. Now consider the following query .

How many pairs of numbers are there which have sum >= to the given value. This query can be solved in many ways . There are two algorithms to solve this query . The first one in the best case takes O(logn) and worst case O(nlogn).Another algorithm takes always O(n) time. Once you can answer this query we can use binary search to solve the given problem.

int search(int start, int end,const int &K) {

if(start>end)

return -INF;

int mid = (start+end)>>1;

//func(arg) returns how many pairs are there which have sum >=arg

int no_pairs = func(mid);

if( no_pairs < K ) {

return search(start,mid-1,K);

}

else if( no_pairs > K ) {

return search(mid+1,end,K);

}

else{

return max(mid, search(mid+1,end,K) ) ;

}

}

Working of the above algorithm:

First of all we note that kth maximum is a number b/w min_value(a)+min_value(b) and max_value(a)+max_value(b) . So we do a search in this interval for that kth maximum. By definition kth maximum sum means a value in the sum array and number of elements in that sum array greater than this value is k-1.

Algorithm working: If the number of pairs which have sum>=mid is say Count. if Count

> K then we search in [mid+1,end] . If Count < K then we search in [start,mid-1] . Now if Count ==K then we note that the value mid can be our answer or there can be another integer larger than this and for which Count==K . Suppose your sum array is 1 2 10 15. and K is 2 . Then 3,4,5,...10 values satisfy the condition that number of pairs greater than that value is 2. Now convince yourselves that the answer is maximum among all the values.

It is good exercise to think how we can write the function by name func used in this binary search :)

@Madhav

could you please explain how do you keep track of sum? are you calculating sum based upon partition? Please excuse me but I am finding it hard to understand

You need not calculate the sum array actually. All you need to find how many elements in the sum array will be >= the given value. Can you tell me which part of the solution you did not understand

@Madhav

The part where you try to get a pair of number where you compare it against *some* sum. If you could explain with example, I will get more clear idea.

Thanks in advance

@Madhav

What I dont understand is *All you need to find how many elements in the sum array will be >= the given value* Here what is the given value? Our range is fixed min_value(a)+min_value(b) and max_value(a)+max_value(b)

but when we calculate interim sum, how do we validate its position relative to the kth sum

e.g max-min range is 80-11 and my interim sum is 45 and I am looking for 6th largest sum, how would I know that 45 is larger or smaller than 6th largest sum?

Sort Both Arrays complexity O(nlogn)

e.g.

a1[] = {10 9 6 4 2}

a2[] = {11 9 7 1}

Create another result array r[] sorted using insertion sort & count number of elements in result array

1st Pass:

take 1st element of a1 & a2 sum = 21 insert r[1] (count = 1)

check if k <= count (every time when pass over)

a1[0]+a2[0] = 21

take a1[0]+a2[1] = 19 compare a2[0]+a1[1]=20 (inset 20) r2 = [20] count 2

check if k <= count (every time when pass over)

a2[1]+a1[1] = 18 < 19

insert 19 r3 = 19

check if k <= count (every time when pass over)

compare element is 18 now

now traverse on a1 with each a2 element upto index 1 in above line

a1[0]+a2[0] already there

a1[0]+a2[1] = 19 already checked

a1[1]+a2[0] there

a1[1]+a2[1] =18 checking element

a1[2]+a2[0] = 17 < 18

inser 18 count 4 r4[] =18

check if k <= count (every time when pass over)

so on........

r[] = {21, 20 , 19, 18, 17...}

sorted

kth element is there

1)Sort both array (nlogn)

2)now we have A[n] and B[m] two sorted array.

take iA and iB two index variable

lets create a minimum heap minHeap(max size=k);

n+

for each iA+iB=0 Add A[iA]+A[iB](only one elem in heap till now)

for each iA+iB=1 Add A[iA]+A[iB](only 2 more elem in heap added)

.....

do the same thing till you are able to add elemment in k space heap

suppose

for each iA+iB=x Add A[iA]+A[iB](no element found space in k spaced heap)

after this point every element formed will be lesser than found in last iteration

here minimum value of heap will be the kth element.

ps: the idea is to create virtual young's table and iterate thru each diagonal,till one diagonal miss entry in minheap

Complexity of step 2 will be about K(logK).

Total complexity = nlogn +nlogn + klogk =O(nlogn)

The easies solution i hope...

1) Sort both arrays A[] and B[]

2) result = 0;

for each b in B {

result += countElementsThatAreLessThan(k - b);

}

Where countElementsThatAreLessThan is simple binary search function that finds index of last element in A that is less than given value;

O(nlogn)

I have an idea:

1. sort both A[] and B[];

2. do something like merging them:

a)find p that A[0]->A[p-1]>B[0] and A[p] < B[0];

now we have the biggest (p) elements in both A and B (they are from A);

b)find q that B[0]->B[q-1]>A[p] and B[q] < A[p];

now we have the second biggest (q) elements in both A and B (they are from B);

so these two sets of elements will make the (p*q) biggest SUMs.

3.if(k > p*q),we will do the same to find (k-q*q)th max sum in A[p..n] and B[0..n]

4.if(k < p*q),we could find it in A[0..p-1] and B[0..q-1].They are both sorted and A[p-1] > B[0].In this case, A[0] and B[0] will be make the biggest sum, and A[0..1] and B[0..1] will make the biggest 2*2 sums, and A[0..2] and B[0..2] will make the biggest 3*3...so we can get the position X that X >=sqrt(k) and X <= sqrt(k)+1. (A[X] and B[0..X]) and (B[X] and A[0..X]) will make the (X-1)^2+1 to X^ biggest sums,we can really sort them now

1) Sort both arrays in descending order. O(nlogn)

2) Merger them in descending order O(n)

3) Find biggest n such n*(n-1)/2 is < k. O(?) probably sqrt of 2k+1.

4) add n+1 the element to mergedArray(k- nC2) O(constat)

final order O(n).

Any gotcha in logic?

Thx for clearing that. Well, we can use similar technique even in this case.

1) let the size of a be n, b be m.

total of m*n pairs.

2) find x elements from A, and y elements from B such that these x+y elements are the top most elements in both arrays. ( can be foun O(x+y) inline).. such x*y <= k.

3) there can be atmost x*y combinations with these sets which are bound to be the top most sums.

4) from then on, take x+1th and y+1 element and do (k-xy) additions to figure out kth higest sum. (this step is tricky but can be done in O(k-xy) which is def.ly less >= O(max of x or y).

5) Effective algorithm can be solved in O(nlogn) which is required for sorting.

Sorry, final order in above methos id O(nlogn).

Basically 2 elements can be picked from n numbers in nC2 ways.

if we find max n such nC2 is less than K, any combinational sum of those n numbers is bigger than kth sum. then we pick n+1 elemtn and keep adding from highest number to get nC2+1th number etc.

I don't think there is a sure way to avoid the case that Rahul's algorithm missed. How about the following:

1) Order the two arrays a and b in descending order

2) Starting with a[i] where i=0, add it to b[j] where j = 0 ... n and b[j] > a[i+1] and store the values to a result array, using insertion sort

3) Increment i and repeat (the last element of a will obviously be a special case since there is no i+1)

4) This way, at each "round", the largest number in that round is strictly smaller than the largest number in the previous round so to find kth largest sum, we only need to compute while i < k.

I might be missing something though. Any thoughts?

Sort the array first then do the following

```
int KthlargestSum(int[] a, int[] b)
{
int aIndex = 0;
int bIndex = 0;
Sum = 0;
for(int i = 1; i < k; ++i)
{
if(a[aIndex] > b[bIndex])
{
sum + = a[aIndex]
++aIndex;
}
else
{
sum + = a[bIndex]
++bIndex;
}
}
return sum;
}
```

Time O(nlogn) + O(k) = O(nlogn)

Space O(1)

here's my solution in (nlgn+k) time.

Sort the both arrays.

Start from the end.

Let the arrays be A and B.

at each step maintain two pointer to last element of arrays.

At each point, compare A[last1]+ A[last1-1] , B[last2]+ B[last2-1] and A[last1] +B[last2]

According to largest of them decrease last1 and last2.

this way you'll get Kth largest sum in k steps.

Comment if I am mistaken somewhere.

assuming arrays are sorted ascending order, will this work? ur comments are really appreciated. thx

```
public static int kthLargestSum(int [] a1, int [] a2, int k) {
int maxSum = 0;
int a = a1.length-1;
int b = a2.length -1;
for(int i = 0; i < k; i++) {
maxSum = 0;
if(a1[a] < a2[b]) {
maxSum+=a2[b];
maxSum+=a1[a];
a--;
} else if(a1[a] > a2[b]) {
maxSum+=a1[a];
maxSum+=a2[b];
b--;
} else {
maxSum+=a1[a];
maxSum+=a2[b];
b--;
}
}
return maxSum;
}
```

1. Sort both arrays in descending order

- mytestaccount2 July 29, 2013