Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

It's doable in O(N) but not easy. Look up the paper "Selection in X + Y and matrices with sorted rows and columns* ".

- lasthope December 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is the right answer.

- xiaoxipan December 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But this requires the computation of the elements of the matrix A and that itself has an order of growth n^2. So how is this a O(n) solution for the complete solution?

- Venkatram Pramod December 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 5 vote

I don't think above is the right answer, though I haven't got it either, because the above solution can not work in the following case:
a[]: 1 2 3
b[]: 1 4 7

- uuuouou December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

The time complexity lower bound of this problem is O(klgk) rather than O(n).
With a min-heap, we can solve it with O(klgk) time complexity and O(k) space complexity.
I'll show you the code later.

- henryadam December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think I have same idea, though not in O(k) space complexity. Problem is that k is in range of 1 to n^2, so the time complexity goes to O(n^2 lgn^2).....

- Alexey December 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Alexy.
1. when k is up to n^2, actually you need to sort all these n^2 numbers. Since no appropriate linear sorting algorithm can be applied here, the lower bound of a comparison sorting algorithm' time complexity is O(n^2lgn^2)=O(n^2lgn). Theorectically, you can't do it better.

2. Although k is a variable no greater than n^2, O(n^2lgn) is only the upper bound for O(klgk). So O(klgk) is more accurate than O(n^2lgn).

- henryadam December 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

B.T.W. I just want to clarify the question: do we need k minimum numbers or just the kth number? If only need the kth, we can achieve O(n^2) time complexity by taking "median of medians" algorithm. If we need k mininum numbers, the lower bound of time complexity is O(klgk).

- henryadam December 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here's the code. Most of the code is a min_heap implementation.

#include <iostream>
using namespace std;

typedef struct {
	int i;
	int j;
	int sum;
} HeapElem;

void Swap(HeapElem* a, HeapElem* b) {
	HeapElem t = *a;
	*a = *b;
	*b = t;
}

class MinHeap {
 public:
	MinHeap(int capacity): capacity__(capacity), heap_size__(0) {
		heap_array__ = new HeapElem[capacity];
	};
	~MinHeap() {
		delete[] heap_array__;
	};

	bool Insert(HeapElem e);
	bool ExtractMin(HeapElem* e);
	void PrintHeap();

 private:
	int LeftChild(int id) { return 2*id + 1; }
	int RightChild(int id) { return 2*id + 2; }
	int Parent(int id) {
		if ( id == 0 ) return -1;
		else return (id-1) / 2;
	}

	HeapElem* heap_array__;
	int capacity__;
	int heap_size__;
};

void MinHeap::PrintHeap() {
	cout << "==============================" << endl;
	cout << "heap_size:" << heap_size__ << endl;
	for (int m = 0; m < heap_size__; ++m) {
		cout << "elem[" << m <<"]={" << heap_array__[m].i << "," << heap_array__[m].j << "," << heap_array__[m].sum << "}" << endl;
	}
	cout << "==============================" << endl;
}

bool MinHeap::Insert(HeapElem e) {
	if (heap_size__ == capacity__)
		return false;
	// cout << "Insert elem:{" << e.i << "," << e.j << "," << e.sum << "}" << endl;
	heap_array__[heap_size__++] = e;
	int p = heap_size__-1;
	while (p != 0 && heap_array__[Parent(p)].sum > heap_array__[p].sum) {
		int q = Parent(p);
		Swap(&(heap_array__[p]), &(heap_array__[q]));
		p = q;
	}
	// PrintHeap();
	return true;
}

bool MinHeap::ExtractMin(HeapElem* e){
	if (heap_size__ <= 0)
		return false;
	*e = heap_array__[0];
	// cout << "Exact MinElem={" << e->i << "," << e->j <<"," << e->sum << "}" << endl;
	heap_array__[0] = heap_array__[--heap_size__];
	int p = 0;
	while(p < heap_size__) {
		int left = LeftChild(p);
		if (left >= heap_size__)
			break;
		int min = left;
		int right = RightChild(p);
		if (right < heap_size__ && heap_array__[right].sum < heap_array__[left].sum)
			min = right;	
		if (heap_array__[min].sum < heap_array__[p].sum) {
			Swap(&(heap_array__[min]), &(heap_array__[p]));
			p = min;
		} else {
			break;
		}
	}
	// PrintHeap();
	return true;
}

bool FindKthMin(int* a, int* b, int n, int k, int* v) {
	if (k <= 0 || k > n*n) {
		cerr << "k is invalid" << endl;
		return false;
	}
	MinHeap heap(k);
	HeapElem e = {0, 0, a[0]+b[0]};
	heap.Insert(e);
	HeapElem t1; 
	for(int m = 0; m < k; ++m) {
		heap.ExtractMin(&t1);
		cout << "a[" << t1.i << "]+b[" << t1.j << "]=" << a[t1.i] << "+"<< b[t1.j] << "=" << t1.sum << endl;
		if (t1.j+1 < n) {
			HeapElem t2 = {t1.i, t1.j+1, a[t1.i]+b[t1.j+1]};
			heap.Insert(t2);
		}
		if (t1.j == 0 && t1.i+1 < n) {
		  HeapElem t3 = {t1.i+1, t1.j, a[t1.i+1]+b[t1.j]};
			heap.Insert(t3);
		}
	}
	*v = t1.sum;
	cout << k << "th min value is " << *v <<endl;
	return true;
}

int main () {
	int v;

	int a[] = {1,2,3};
	int b[] = {1,4,7};
	cout << "Test 0" << endl;
	FindKthMin(a, b, 3, 9, &v);

	int a1[] = {  1,   50,  100, 1000, 6000, 6002, 6004, 6006, 6008, 6010 };
	int b1[] = {100,  200,  300, 2000, 3000, 4000, 5000, 6000, 7000, 8000 };
	cout << "Test 1" << endl;
	FindKthMin(a1, b1, 10, 100, &v);

	int a2[] = { 1, 6, 7, 9, 10, 14 };
	int b2[] = { 2, 3, 5, 8, 11, 16 };
	cout << "Test 2" << endl;
	FindKthMin(a2, b2, 6, 36, &v);

	int a3[] = { 1, 30, 35 };
	int b3[] = { 5,  6, 50 };
	cout << "Test 3" << endl;
	FindKthMin(a3, b3, 3, 9, &v);

	int a4[] = { 1,  2,  3,  4,  5,  7,  8,  9, 10, 11};
	int b4[] = { 1, 20, 30, 40, 50, 60, 70, 80, 90,100};
	cout << "Test 4" << endl;
	FindKthMin(a4, b4, 10, 100, &v);

	int a5[] = {3,4,5,6,13,19};
	int b5[] = {1,2,5,9,10,11};
	cout << "Test 5" << endl;
	FindKthMin(a5, b5, 6, 36, &v);

	int a6[] = {0, 1, 3, 5};
	int b6[] = {1, 2, 4, 7};
	cout << "Test 6" << endl;
	FindKthMin(a6, b6, 4, 16, &v);

	return 0;
}

- henryadam December 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Finally I realized that in c++ we can take priority_queue in stl as a heap, thus we would not bother implementing a heap from scratch.

- henryadam December 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

package careercup;

public class KthMinSum {
public static Integer[] find(int k, int[] a, int[] b) {
final Integer[] _result = new Integer[k];

int q = (int) Math.sqrt(k);

for (int i = 0; i < q; i++) {
for (int j = 0; j < q; j++) {
_result[i * q + j] = a[i] + b[j];
}
}

int left = 0;
int right = 0;

for (int i = q * q; i < k; i++) {
_result[i] = (a[q] + b[left]) < (b[q] + a[right]) ? (a[q] + b[left++]) : (b[q] + a[right++]);
}

return _result;
}
}

- Paul N. December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry to tell you that this method does not work. For example, a = {1,5,7,35,42}, b = {6,8,9,35,37}, K=3, the expected result is {7,9,10}, but this method returns {7,9,11}

- lzhou3957 August 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm trying to submit working code for returning first K min sums, but unfortunately system does not allow for me to do it :(

- Paul N. December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ooops, please remove duplicated answers ;)

- Paul N. December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 6 vote

The way I implemented this takes O(K log(K)) time if I use a heap, or O(K^2) if I use a naive sorted array.

Here is the key idea: Obviously, the first pair is A[0] and B[0]. Furthermore, the first pair where we take index "i" from array "A" is indeed (A[i], B[0]). So we can initialize a list of "K" pairs of (A[i], B[0]) for "i = 0, 1, ..., K- 1".

Assume this list is sorted (or Heap with Extract Min). Take first Pair out say, (A[0], B[0]). NOTE: If the next pair leading to K-minimum sum includes (A[0]) it must be (A[0], B[1]). So we simply put the pair (A[0], B[1]) inside. In general, when you extract the pair (A[i], B[j]), you must Insert (A[i], B[j + 1]) back in.

Insertion and Extraction takes O(K) time if you use a simple sorted array, and O(log(K)) if you use a Heap. Overall, it takes, O(K Log(K)) = O(K^2).

Here is what I used for class Pair:

class Pair {
ind ind_A, ind_B;
public Pair(int a, b) { 
	ind_A = a; ind_B = b
}
public boolean IsLessThan(Pair other) {
	return (A[ind_A] + B[ind_B]) < (A[other.ind_A] + B[other.ind_B]);
}

Here is the code for the main for-loop

public void Solve(int K) {         
        pairs = new Heap(A.length);
        for (int i = 0; i < A.length; i++)
            pairs.Insert(new Pair(i, 0));            
        // Now begin
        for (int k = 0; k < K; k++) {
            Pair p = pairs.ExtractMin();   
            System.out.println(p);
            p.ind_B++;
            pairs.Insert(p);
        }
    }

Here is a sample test:

public static void main(String[] args) {
        // TODO code application logic here        
        int[] a = {1, 5, 6, 7, 8, 20, 21, 22};
        int[] b = {1, 4, 5, 10, 15, 16, 17, 18};
        MinSumArray ms = new MinSumArray(a, b);
        ms.Solve(6);
    }

Output:

A[0] + B[0] = 1 + 1 = 2
A[0] + B[1] = 1 + 4 = 5
A[1] + B[0] = 5 + 1 = 6
A[0] + B[2] = 1 + 5 = 6
A[2] + B[0] = 6 + 1 = 7
A[3] + B[0] = 7 + 1 = 8

- Ehsan December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

My answer is almost the same with yours, but with slight difference.
That is, you initialize a list of "K" pairs of (A[i], B[0]) for "i = 0, 1, ..., K- 1", thus form a min heap naturally.
But I insert (A[i], B[0]) to the heap only when (A[i-1], B[0]) is extracted from the heap.See my code.

- henryadam December 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_kth(a, b, k):
    a_count, b_count = 0, 0
    is_last_b = False

    while a_count * b_count < k:
        if a[a_count] < b[b_count]:
            a_count += 1
            is_last_b = False
        else:
            b_count += 1
            is_last_b = True

    if is_last_b:
        return a[a_count - (a_count * b_count - k) - 1], b[b_count - 1]
    else:
        return a[a_count - 1], b[b_count - (a_count * b_count - k) - 1]

- vasyl.stanislavchuk December 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Interesting problem that kept me busy some time but the trick is that arrays are sorted so, given a[0]+b[0] is for sure the first number that is to be produced, what are the next possible sums, well:
- S1 = a[a_i+1] + b[b_i];
- S2 = a[a_i+1] + b[0];
- S3 = a[a_i] + b[b_i+1];
- S4 = a[0] + b[b_i+1];

as you want to iterate over each arrays always checking the sum result of the other first array element when you increment either A index or B index. The smallest sum of the above for is the next one given that you:
- discard any sum smaller than the previous generated sum
- does not go beyond array boundaries

resulting code passing all the test series in this page is:

#include <stdio.h>

void print_Kth_min(int a[], int b[], int K, int N)
{
	int a_i = 0, b_i = 0;
	int count = 0;
	int sum = 0;

	sum = a[a_i] + b[b_i];
	printf("[%d]+[%d] %d\n", a_i, b_i, sum);

	while (count < K) {

		/* Create the 4 possible next sum */
		int S1 = a[a_i+1] + b[b_i];
		int S2 = a[a_i+1] + b[0];
		int S3 = a[a_i]   + b[b_i+1];
		int S4 = a[0]     + b[b_i+1];

		/*
		  Select the smallest one ensuring that:
		  - it needs to be bigger than latest generated sum (otherwise it has been made up already)
		  - does not goes beyond the array boundaries
		*/

		if ((S1 >= sum) && (a_i+1 < N) &&
				((S2 < sum ? 1 : S1 <= S2)) &&
				((S3 < sum ? 1 : S1 <= S3)) &&
				((S4 < sum ? 1 : S1 <= S4))) {
			a_i++;
		} else if ((S2 >= sum) && (a_i+1 < N) &&
				((S1 < sum ? 1 : S2 <= S1)) &&
				((S3 < sum ? 1 : S2 <= S3)) &&
				((S4 < sum ? 1 : S2 <= S4))) {
			a_i++; b_i = 0;
		} else if ((S3 >= sum) && (b_i+1 < N) &&
				((S1 < sum ? 1 : S3 <= S1)) &&
				((S2 < sum ? 1 : S3 <= S2)) &&
				((S4 < sum ? 1 : S3 <= S4))) {
			b_i++;
		} else if ((S4 >= sum) && (b_i+1 < N) &&
				((S1 < sum ? 1 : S4 <= S1)) &&
				((S2 < sum ? 1 : S4 <= S2)) &&
				((S3 < sum ? 1 : S4 <= S3))) {
			b_i++; a_i = 0;
		} else {
			/* We've reached array's limits and need to finish  iterating the one not reached yet */
			if (a_i+1 == N) {
				if (b_i+1 == N) {
					/* K is greater than values we can make up */
					return;
				} else {
					b_i++;
				}
			} else {
				a_i++;
			}
		}
		sum = a[a_i] + b[b_i];
		printf("[%d]+[%d] %d\n", a_i, b_i, sum);
		count ++;
	}
}

int main(int argc, char *argv[])
{

	int a1[] = {  1,   50,  100, 1000, 6000, 6002, 6004, 6006, 6008, 6010 };
	int b1[] = {100,  200,  300, 2000, 3000, 4000, 5000, 6000, 7000, 8000 };

	printf("Test 1\n");
	print_Kth_min(a1, b1, 50, 10);

	int a2[] = { 1, 6, 7, 9, 10, 14 };
	int b2[] = { 2, 3, 5, 8, 11, 16 };

	printf("Test 2\n");
	print_Kth_min(a2, b2, 30, 6);

	int a3[] = { 1, 30, 35 };
	int b3[] = { 5,  6, 50 };

	printf("Test 3\n");
	print_Kth_min(a3, b3, 10, 3);

	int a4[] = { 1,  2,  3,  4,  5,  7,  8,  9, 10, 11};
	int b4[] = { 1, 20, 30, 40, 50, 60, 70, 80, 90,100};

	printf("Test 4\n");
	print_Kth_min(a4, b4, 100, 10);

	return 0;
}

- thierrys December 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider the following input:
a = [ 1, 3, 4, 10 ]
b = [ 2, 3, 8, 9]
First pair is {1,2} .
Iteration 1 selects S3 {1,3} // b_i++
Iteration 2 selects S2 {2,3} // a_i++, b_i=0
Iteration 3 selects S1 {4,2} // a_i++
Iteration 4 selects S3 {4,3} // a_i++
Note that {3,3} is missed and can't be found later since sum has now grown to 7. The {3,3} pair had to be selected at iteration 3 as S3, but there was no criterion to prefer it over S1 as they both yield the same sum. More logic of this type can be added, but the basic truth is there are more than 4 different options at every step. There are actually N options (worst case) as demonstrated by the min-heap based solutions. The pairs sit in a matrix, each row has a cursor running from min to max (two cursors a,b are not enough) and in each step one "row" is selected as having the minimal value. If you don't use a min-heap and just go thru the cursors top-to-bottom, then you can have the following optimization: all the cursors we have not checked yet AND point to columns bigger-equal than ours must have higher-equal values, so can be skipped. Anyway, using min-heap is simpler and faster.

- shin December 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are write if was focused on making it simple but turns out that in case you have multiple time the same number it even gets into a locking situation:

int a8[] = {1, 2, 2, 2};
	int b8[] = {1, 2, 3, 4};

does not produce at all the expected result !!

- thierrys December 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about the following solution, it will run as long as we don't request K to be more then the number of all the possible combinations

public static ArrayList<Integer> firstKMin(int[] A, int[] B, int k) {

		ArrayList<Integer> list = new ArrayList<Integer>();
		
		int firstA=0;
		int nextA=1;
		int firstB=0;
		int nextB=1;

		list.add(A[firstA]+B[firstB]);
		int count=1;

		while(count<k) {
			if(A[firstA]+B[nextB] < B[firstB]+A[nextA]) {
				list.add(A[firstA]+B[nextB]);
				nextB++;
				if(nextB >= B.length) {
					firstA++;
					nextB=0;
				}
			} else {
				list.add(B[firstB]+A[nextA]);
				nextA++;
				if(nextA >= A.length) {
					firstB++;
					nextA=0;
				}
			
			}
			count++;					
		}
		
		return list;	
	}

- YD December 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry, it does not work out. Example, a={1,5,7,35,42}, b={6,8,9,35,37}, K=10, then we expect result as {7,9,10,11,13,13,14,15,16,26}. However, your proposal returns [7, 9, 10, 11, 13, 36, 38, 11, 13, 14].

- lzhou3957 August 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Finally I worked out it! It can pass all the test cases before! Here is the code:

static void nextIdx(const std::vector<int> & r1,
             const std::vector<int> & r2,
             const std::vector<int> & idx1,
             const std::vector<int> & idx2,
             int & i,
             int & j,
             int min_i,
             int min_j)
{
    if(j > 0){
        int rr = r1[i] + r2[j];
        for(int ii = min_i;ii < int(r1.size());++ii){
            int jj = idx1[ii] + 1;
            if(jj < j && rr > r1[ii] + r2[jj]){
                i = ii;
                j = jj;
                rr = r1[i] + r2[j];
            }
            if(!jj)
                break;
        }
    }
    if(i > 0){
        int rr = r1[i] + r2[j];
        for(int jj = min_j;jj < int(r2.size());++jj){
            int ii = idx2[jj] + 1;
            if(ii < i && rr > r1[ii] + r2[jj]){
                i = ii;
                j = jj;
                rr = r1[i] + r2[j];
            }
            if(!ii)
                break;
        }
    }
}

//find k-th min in O(N)
int kthMin(const std::vector<int> & r1, const std::vector<int> & r2, int k)
{
    assert(1 <= k && k <= int(r1.size() * r2.size()));
    assert(!r1.empty() && !r2.empty());
    std::vector<int> idx1(r1.size(), -1);
    std::vector<int> idx2(r2.size(), -1);
    int ret;
    for(int i = 0, j = 0, n = 1;i < int(r1.size()) && j < int(r2.size());++n){
        ret = r1[i] + r2[j];
        if(n == k)
            break;
        idx1[i] = j;
        idx2[j] = i;
        if(i == r1.size() - 1){
            assert(j < int(r2.size()) - 1);
            i = idx2[++j] + 1;
            if(i > 0)
                nextIdx(r1, r2, idx1, idx2, i, j, r1.size(), j + 1);
        }else if(j == r2.size() - 1){
            assert(i < int(r1.size()) - 1);
            j = idx1[++i] + 1;
            if(j > 0)
                nextIdx(r1, r2, idx1, idx2, i, j, i + 1, r2.size());
        }else if(r1[i + 1] < r2[j + 1]){
            int jj = j;
            j = idx1[++i] + 1;
            nextIdx(r1, r2, idx1, idx2, i, j, i + 1, jj + 1);
        }else{
            int ii = i;
            i = idx2[++j] + 1;
            nextIdx(r1, r2, idx1, idx2, i, j, ii + 1, j + 1);
        }
    }
    return ret;
}

And with the all test cases:

//O(N * N)
int kthMinSlow(const std::vector<int> & r1, const std::vector<int> & r2, int k)
{
    assert(1 <= k && k <= int(r1.size() * r2.size()));
    std::vector<int> v;
    for(int i = 0;i < k && i < int(r1.size());++i)
        for(int j = 0;j < k && j < int(r2.size());++j)
            v.push_back(r1[i] + r2[j]);
    std::sort(v.begin(), v.end());
    assert(int(v.size()) >= k);
    return v[k - 1];
}


void test(const int v1[], const int v2[], int N)
{
    assert(N > 0);
    std::vector<int> r1(v1, v1 + N);
    std::vector<int> r2(v2, v2 + N);
    //test
    std::vector<int> t1;
    for(int k = 1;k <= int(r1.size() * r2.size());++k){
        t1.push_back(kthMinSlow(r1, r2, k));
        //std::cout<<t1.back()<<", ";
    }
    //std::cout<<"\n";

    std::vector<int> t2;
    for(int k = 1;k <= int(r1.size() * r2.size());++k){
        t2.push_back(kthMin(r1, r2, k));
        //std::cout<<t2.back()<<", ";
    }
    //std::cout<<"\n";
    if(t1 != t2)
        std::cerr<<"test FAILED\n";
}

int main()
{
    {
        const int v1[] = {0, 1, 3, 5};
        const int v2[] = {1, 2, 4, 7};
        test(v1, v2, sizeof v1 / sizeof v1[0]);
    }{
        const int v1[] = {1, 2, 3,4,5,7,8,9,10,11};
        const int v2[] = {1,20,30,40,50,60,70,80,90,100};
        test(v1, v2, sizeof v1 / sizeof v1[0]);
    }{
        const int v1[] = {1, 30, 35};
        const int v2[] = {5,6,50};
        test(v1, v2, sizeof v1 / sizeof v1[0]);
    }{
        const int v1[] = {1, 6, 7, 9, 10, 14};
        const int v2[] = {2, 3, 5, 8, 11, 16};
        test(v1, v2, sizeof v1 / sizeof v1[0]);
    }{
        const int v1[] = {1, 2, 2, 2};
        const int v2[] = {1, 2, 3, 4};
        test(v1, v2, sizeof v1 / sizeof v1[0]);
    }{
        const int v1[] = {1, 3, 4, 10};
        const int v2[] = {2, 3, 8, 9};
        test(v1, v2, sizeof v1 / sizeof v1[0]);
    }{
        const int v1[] = {1,   50,  100, 1000, 6000, 6002, 6004, 6006, 6008, 6010};
        const int v2[] = {100,  200,  300, 2000, 3000, 4000, 5000, 6000, 7000, 8000};
        test(v1, v2, sizeof v1 / sizeof v1[0]);
    }{
        const int v1[] = {1, 5, 6, 7, 8, 20, 21, 22};
        const int v2[] = {1, 4, 5, 10, 15, 16, 17, 18};
        test(v1, v2, sizeof v1 / sizeof v1[0]);
    }{
        const int v1[] = {100,200,300,400};
        const int v2[] = {1,2,3,4};
        test(v1, v2, sizeof v1 / sizeof v1[0]);
    }{
        const int v1[] = {1, 2, 3};
        const int v2[] = {1, 4, 7};
        test(v1, v2, sizeof v1 / sizeof v1[0]);
    }{
        const int v1[] = {1,   50,  100, 1000, 6000, 6002, 6004, 6006, 6008, 6010};
        const int v2[] = {100,  200,  300, 2000, 3000, 4000, 5000, 6000, 7000, 8000};
        test(v1, v2, sizeof v1 / sizeof v1[0]);
    }{
        const int v1[] = {3,4,5,6,13,19};
        const int v2[] = {1,2,5,9,10,11};
        test(v1, v2, sizeof v1 / sizeof v1[0]);
    }
}

- DoZerg December 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think it's O(N). Obviously your function nexIdx() is not O(1).

- henryadam December 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is actually a *hard* problem, worth publishing a paper on (if you do it in O(K)).

- Anonymous December 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have to admit that the algorithm is not straightly O(N). But I think there might be a way to prove that, in the worst case, nextIdx() could be in a limited complexity. Maybe I will think about it later.

- DoZerg December 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This complexity is O(K^2 log(K)). You are not using some of the information about A and B. We know that A and B are sorted, which implies that you only need the first "K" elements. But that is not all that is implied.
If the first "K" elements of A and B are not sorted, then the list of numbers A[i] + B[j] could form (K^2)! different types of orderings. Then, your algorithm might have been optimal since the complexity is that of sorting.

For this problem we know that A and B are sorted. An O(K log(K)) algorithm actually exists). I guess even an O(K) algorithm might exist but as Anonymous said, if it does, it looks very hard to be found.

** Nevermind, I only saw the second algorithm which you already mentioned is O(N*N)

Also for the first algorithm, in the main loop you are increasing either "i" or "j" by 1 in each iteration. Then each time you also call "nextIdx" which has a for loop running for (N - i) or (N - j) iterations. So the complexity seems to be O(K N).

- Ehsan December 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaxSumsOf2SortedArrays {

	
	public MaxSumsOf2SortedArrays() {
		a = new int[]{0, 1, 3, 5};
		b = new int[]{1, 2, 4, 7};
	}
	int[] a;int[] b;

	void findMax(int K){
		int a1=0;int a2=1;
		int b1=0;int b2=1;
		int count = 0;
		System.out.println(a[0]+b[0]);
		while(count<K && count<=a.length*b.length){
			count++;
			
			int aSum = a[a1]+b[a2];
			int bSum = b[b1]+a[b2];
			if(aSum<=bSum){
				System.out.println(aSum + "--"+a[a1]+"+"+b[a2]);
				a2++;
				if(a2==b.length){
					a1++;
					a2=a1;
				}
				
			}
			else{
				System.out.println(bSum+ "--"+b[b1]+"+"+a[b2]);
				b2++;
				if(b2==a.length){
					b1++;
					b2=b1;
				}
					
			}
		}
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MaxSumsOf2SortedArrays m = new MaxSumsOf2SortedArrays();
		m.findMax(100);
		
	}
}

- Anonymous December 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaxSumsOf2SortedArrays {


public MaxSumsOf2SortedArrays() {
a = new int[]{0, 1, 3, 5};
b = new int[]{1, 2, 4, 7};
}
int[] a;int[] b;

void findMax(int K){
int a1=0;int a2=1;
int b1=0;int b2=1;
int count = 0;
System.out.println(a[0]+b[0]);
while(count<K && count<=a.length*b.length){
count++;

int aSum = a[a1]+b[a2];
int bSum = b[b1]+a[b2];
if(aSum<=bSum){
System.out.println(aSum + "--"+a[a1]+"+"+b[a2]);
a2++;
if(a2==b.length){
a1++;
a2=a1;
}

}
else{
System.out.println(bSum+ "--"+b[b1]+"+"+a[b2]);
b2++;
if(b2==a.length){
b1++;
b2=b1;
}

}
}

}

public static void main(String[] args) {
// TODO Auto-generated method stub
MaxSumsOf2SortedArrays m = new MaxSumsOf2SortedArrays();
m.findMax(100);

}
}

- Dwai December 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) algorithm was proposed from this paper www dot cse dot yorku dot ca/~andy/pubs/X+Y.pdf, however it doesn't fit for an interview.

- xiaoxipan December 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class KthMinSumFromTwoArrays {
	public static void main(String[] args){
		int[] a = new int[]{1,5,9,15,20};
		int[] b = new int[]{3,4,7,10,12};
		
		KthMinSumFromTwoArrays obj = new KthMinSumFromTwoArrays();
		
		for(int i = 1; i<=9; i++){
			System.out.println(obj.findNthMinSum(a, b, i));	
		}
	}
	
	private int whichIsMin(int first, int second, int third){
		int min = Math.min(first, second);
		if(min == first){
			min = Math.min(first, third);
			if(min == first){
				return 1;
			} else {
				return 3;
			}
		} else {
			min = Math.min(second, third);
			if(min == second){
				return 2;
			} else {
				return 3;
			}
		}
	}
	
	private int findNthMinSum(int[] a, int[] b, int n){
		if(n == 1){
			return a[0]+b[0];
		}
		int aLimit = a.length;
		int bLimit = b.length;
		
		int firstA = 0;
		int firstB = 0;
		
		int secondA = 1;
		int secondB = 0;
		
		int thirdA = 2;
		int thirdB = 0;
		
		int nThMin = 0;
		
		while(n > 0){
			int firstSum = Integer.MAX_VALUE;
			int secondSum = Integer.MAX_VALUE;
			int thirdSum = Integer.MAX_VALUE;
			
			if(firstA < aLimit && firstB < bLimit){
				firstSum = a[firstA]+b[firstB];
			}
			
			if(secondA < aLimit && secondB < bLimit){
				secondSum = a[secondA]+b[secondB];
			}
			
			if(thirdA < aLimit && thirdA < bLimit){
				thirdSum = a[thirdA]+b[thirdB];
			}
			
			int whichIsMin = whichIsMin(firstSum, secondSum, thirdSum);
			
			switch(whichIsMin){
			case 1:
				nThMin = a[firstA]+b[firstB];
				firstB++;
				if(firstB == bLimit){
					firstA = secondA;
					secondA = thirdA;
					thirdA++;
					firstB = secondB;
					secondB = thirdB;
					thirdB = 0;
				}
				break;
			case 2:
				nThMin = a[secondA]+b[secondB];
				secondB++;
				break;
			case 3:
				nThMin = a[thirdA]+b[thirdB];
				thirdB++;
				break;
			}
			n--;
		}
		return nThMin;		
	}
}

- Anonymous December 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

KlogK will be too slow in case if K ~ n^2;
It will be approximately N^2log(N^2)
I can solve it in exactly N^2 :)
just write out every pair a[i] + b[j], and find k-th; in C++ it is builtin function nth_element(); other have to implement nth order median statistics

- Askhat January 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Minimum value will be a[0] + b[j] or a[i] + b[0]

so the answer is

int[] firstKMin(int k, int[] a, int b []){
int i = 1;
int j = 1;
int index = 1; 
int[] answer = new int[k];
// This is special case
answer[0] = a[0] + b[0];
while(i < N && j < N){
x = a[i]   + b[0];
	y = a[0] + b[j];
	if(x < y){
		answer[index] = x;
		i++;
}else{
	answer[index] = y;
	j++;
}
	c++;
}
if(index < k){
	if(i == N){
		for(int l = j; l < N; l++){
			answer[index] = a[0] + b[l];
			index++;
}	
}
if(j == N){
		for(int l = i; l < N; l++){
			answer[index] = a[i] + b[0];
			index++;
}
}
}
return answer;
}

- kuroobi January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Minimum value will be a[0] + b[j] or a[i] + b[0]
Note#
a[0] + b[0] is the special case, we need to be careful for
this case.
k > N case is also special case.

so the answer is

int[] firstKMin(int k, int[] a, int b []){
int i = 1;
int j = 1;
int index = 1; 
if( K >= 2N){
	// invalid input
	retrun null;
}
int[] answer = new int[k];
// This is special case
answer[0] = a[0] + b[0];
while(i < N && j < N){
x = a[i]   + b[0];
	y = a[0] + b[j];
	if(x < y){
		answer[index] = x;
		i++;
}else{
	answer[index] = y;
	j++;
}
	c++;
}
if(index < k){
	if(i == N){
		for(int l = j; l < N; l++){
			answer[index] = a[0] + b[l];
			index++;
}	
}
if(j == N){
		for(int l = i; l < N; l++){
			answer[index] = a[i] + b[0];
			index++;
}
}
}

return answer;
}

- kuroobi January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A (klog k) Soluton

import java.util.*;
class node{
	int aX;
	int bX;
	node(int aX, int bX)
	{
		this.aX=aX;
		this.bX=bX;
	}
	
}
public class kthMin {

	static node kthMin(int[] arrA, int[] arrB,int k)
	{
		//Declaration/Intialization section
		Queue<node> maxHeap=new PriorityQueue<node>(1,new Comparator<node>(){
			public int compare(node A, node B)
			{
				return (B.aX+B.bX)-(A.aX+A.bX);
			}
		});
		
		//Logic section
		for(int i=0;i < k && i < arrA.length;i++)
			for(int j=0; j < k && j < arrB.length;j++)
				if(maxHeap.size() < k)
					maxHeap.add(new node(arrA[i],arrB[j]));
				else{
					if(maxHeap.peek().aX+maxHeap.peek().bX > arrA[i]+arrB[j])
					{
						maxHeap.poll();
						maxHeap.add(new node(arrA[i],arrB[j]));
					}
				}
		return maxHeap.peek();
	}
	public static void main(String[] args) {
		int[] arrA={ 1,  2,  3,  4,  5,  7,  8,  9, 10, 11};
		int[] arrB={ 1, 2, 30, 40, 50, 60, 70, 80, 90,100};
		node n=kthMin(arrA,arrB,6);
		System.out.print(n.aX+" "+ n.bX);

	}

}

- Dinesh June 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not simply add the two arrays together (O(n)) and then run quickselect (O(n)) on the resulting array? If we're just selecting the Kth min then thats fine, we'd get the element we need, if we're providing the list of mins up to K then, anything to the left of the returned element from quick select will be the min. If we need to know the elements of each array that composed these then perhaps we could sort an array of a datatype which contains the requisite information.

- cool_funster August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Apply Bucket Sort on first K elements only for both the sorted array.

Iterate through the bucket from 1 -- k to get the kth mean.

Assumption: Memory is not an issue and bucket array can be very high.

- anshuman101 February 24, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Since both are sorted array,The first element of both the array will be minimum. So the sum a[0]+b[0] will be less than any of other a[i]+b[j]

so the answer is straight

A[0] + B[0]

- mitesh.pant December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

k = 1: a[0] + b[0]
k = 2: min(a[0] + b[1], a[1] + b[0])
k = 3: max(a[0] + b[1], a[1] + b[0])
k = 4: a[1] + b[1]
...
k = 3n-1: min(a[n-1] + b[n], a[n-1] + b[n])
k = 3n: max(a[n-1] + b[n], a[n-1] + b[n])
k = 3n + 1: a[n] + b[n]
k = 3

- Anonymous December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is the code that was implemented based on the above generalization.

public class KthMinimum {
	public static int findKthMin(int[] A, int[] B, int K) {

		// Get square root of previous and next perfect squares of K
		// Example: If K=8 then low = 2 (sqrt of 4) and high =3 (sqrt of 9)
		int low = (int) Math.floor(Math.sqrt(K));
		int high = (int) Math.ceil(Math.sqrt(K));

		// If K is a perfect square (like 1, 4, 9)
		if (low == high) {
			low--;
			return A[low] + B[low];
		}
		int max = (int) Math.pow(high, 2);
		int offset = (int) Math.ceil((Math.pow(high, 2) - K) / 2);

		high--;
		low = high - offset;
		if ((max % 2 == 0 && K % 2 == 0) || (max % 2 != 0 && K % 2 != 0)) {
			return Math.min(A[high] + B[low], A[low] + B[high]);
		} else {
			return Math.max(A[high] + B[low], A[low] + B[high]);
		}
	}

	public static void main(String[] args) {
		int a[] = { 1, 6, 7, 9, 10, 14 };
		int b[] = { 2, 3, 5, 8, 11, 16 };

		System.out.println(findKthMin(a, b, 32));
	}
}

- ganni December 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Please tell me how wrong I am:

public ArrayList<Integer> getKthMin(int k, int[] a, int[] b){
	ArrayList<Integer> answer = new ArrayList<>();
	int i = 0;
	int j = 0;
	while((i + j) < k)
	{
		answer.add(a[i] + b[j])
		if(a[i] <= b[j])
			i++;
		else if(a[i] > b[j])
			j++;
	}
	return answer;
	
}

- Nick December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nick, This will not work.
consider a: 1, 30, 35
b: 5,6,50
your code will return
k=1: 1+5=6 ok
k=2: 30+5=35 (not ok as the real answer is 1+6 =7)

- mahesh December 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public int findKthMin(int[] A, int[] B, int K)
{
	int indexA = 0;
	int indexB = 0;
	int count = 1;

	while (count < K)
	{
		int sum1 = A[indexA + 1] + B[indexB];
		int sum2 = A[indexA] + B[indexB + 1];
		
		if (sum1 > sum2)
		{
			indexA++;
		}
		else
		{
			indexB++;
		}
	}
	return A[indexA] + B[indexB];
}

- naman December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is correct way.... any use-case invalidating this solution ?

- alex December 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider the example:
a: 1, 30, 35
b: 5,6,50

k = 1 : 1 + 5
k = 2 : 1 + 6
k = 3 : correct ans: (30 + 5) your algo: (30 + 6)

- naveen December 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you do not need to calculate sums inside the loop. Just keep track of the indexes.

public int findKthMin(int[] A, int[] B, int K)
{
	int indexA = 0;
	int indexB = 0;
	char min;
	int count = 0;
	int *pMin = null;
	int *pMinLast = null;

	while (count < k)
	{
	   pMinLast = pMin;
	   if (A[indexA] < B[indexB])
	   {
		pMin = &A[IndexA];
		indexA++;
	   }
	   else
	   {
		pMin = &B[IndexB];
		indexB++;
	   }
	}
	
	return *pMin + *pMinLast;
}

- Mak December 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't work, it skips some numbers.
For example, if the sequence of mins goes like that:
a[0] + b[1]
a[1] + b[1]
a[0] + b[2]
We need to go backwards sometimes.

If consider a matrix where each cell contains summation of array elements, then next min is a cell adjacent to ANY explored cell not only current cell... hopefully that make sense

- Anonymous December 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Got it finally:
(1)do merge process, record each item is from a[] or b[].
(2)find the Kth smallest pair(remember a pair must be one from a[], the other from b[]).

time complexity: O(N)
space complexity: O(N)

As I'm more familiar with C++, following is my C++ code with annotation:

#include <cstdlib>
#include <utility>
#include <algorithm>
using namespace std;

pair<int,int> getKthSmallestPair(const int a[], const int b[], int N, int K)
{
    //only exist N*N pairs of a[i]+b[j]
    if(K <= 0 || K > N*N) return make_pair(-1, -1);
    
    //alloc memory for the merged array flags
    int total = N << 1;
    bool* isFromA = new bool[total];
    
    //do merge process, record whether the item is from a[] or not
    int i = 0, j = 0, k = 0;
    for(; i < N && j < N; ++k){
        if(a[i] > b[j]){
             isFromA[k] = false;
             ++j;
         }
         else{
             isFromA[k] = true;
             ++i;
         }
    }
    for(; i < N; ++i, ++k){
        isFromA[k] = true;
    }
    for(; j < N; ++j, ++k){
        isFromA[k] = false;
    }
    
    //find the Kth smallest pair of a[i] + b[j]
    i = j = -1;
    //step 1: find the certain i or j of the Kth pair
    int itemsOfA = 0, itemsOfB = 0;
    for(k = 0; k < total; ++k){
        if(isFromA[k]){
            ++itemsOfA;
            if(itemsOfA * itemsOfB >= K){
                i = itemsOfA - 1;
                break;
            }
        }
        else{
            ++itemsOfB;
            if(itemsOfA * itemsOfB >= K){
                j = itemsOfB - 1;
                break;
            }    
        }
    }
    //step 2: find the matched j or i in the Kth pair
    int dis = itemsOfA * itemsOfB - K + 1;
    if(i == -1){//b[j] has been found in step 1, whose index is k in the merged array
        for(--k; k >= 0; --k){
            if(isFromA[k]){
                --itemsOfA;
                if(--dis == 0){
                    i = itemsOfA;
                    break;
                }
            }
        }
    }
    else{//a[i] has been found in step 1, whose index is k in the merged array
        for(--k; k >= 0; --k){
            if(!isFromA[k]){
                --itemsOfB;
                if(--dis == 0){
                    j = itemsOfB;
                    break;
                }
            }
        }
    }
    
    //free memory and return indexes
    delete[] isFromA;
    return make_pair(i, j);
}

int main()
{
    int a[] = {1, 2, 3};
    int b[] = {1, 4, 7};
    
    pair<int,int> res;
    for(int i = 1; i <= 9; ++i){
        res = getKthSmallestPair(a, b, 3, i);
        printf("%dth smallest pair is a[%d] + b[%d]\n", i, res.first, res.second);
    }
    puts("\nafter switch a[] and b[]:\n");
    for(int i = 1; i <= 9; ++i){
        res = getKthSmallestPair(b, a, 3, i);
        printf("%dth smallest pair is a[%d] + b[%d]\n", i, res.first, res.second);
    }
    
    return 0;
}

- uuuouou December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think your answer is wrong. Your program can not pass the following test data.
int a[] = {0, 1, 3, 5};
int b[] = {1, 2, 4, 7};

- ecnuwbwang December 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are right. The above solution is not correct. I'm Sorry.

- uuuouou December 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public int kthMinimum(int a[], int b[], int k){
ArrayList<Integer> temp = new ArrayList<Integer>();
for(int i=0; i<a.length-1; i++){
for(int j=0; j<b.length-1; j++){
temp.add(a[i]+b[j]);
}
}
Collections.sort(temp);
return temp.get(k);
}

- Saad December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

k=0;j=0;i=0;
while(k<K)//K is the K mentioned in the question
{

sum= a[i]+b[j]; //calculate sum with current i and j, it will be the next smallest
k++;
//now we need to know whether to increment i or j
//This will depend on (a[i]+b[j+1]) and (a[i+1]+b[j])

if  ( a[i]+b[j+1] < a[i+1]+b[j]  )  //incrementing index of b takes us to the next smallest sum
     j++;
else
     i++

}
 
return sum;

- mahesh December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

dont keep computing sums inside the loop. Just need to keep track of which is the kth min and (k+1)th min number in combined array.

public int findKthMin(int[] A, int[] B, int K)
{
	int indexA = 0;
	int indexB = 0;
	int *pMin = null;
	int *pMinLast = null;

	while ((indexA+indexB) <= k + 1)
	{
	   pMinLast = pMin;
	   if (A[indexA] < B[indexB])
	   {
		pMin = &A[IndexA];
		indexA++;
	   }
	   else
	   {
		pMin = &B[IndexB];
		indexB++;
	   }
	}
	
	return *pMin + *pMinLast;
}

- Anonymous December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry but i am not sure you code works in the following case:
a[] = {100,200,300,400}
b[] = {1,2,3,4}
k = 1
the result should be 100+1 neither pMin nor PMinLast will point to a.

- hen December 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

public class KthMinSum {
    public static Integer[] find(int k, int[] a, int[] b) {
        final Integer[] _result = new Integer[k];

        int q = (int) Math.sqrt(k);

        for (int i = 0; i < q; i++) {
            for (int j = 0; j < q; j++) {
                _result[i * q + j] = a[i] + b[j];
            }
        }

        int left = 0;
        int right = 0;

        for (int i = q * q; i < k; i++) {
            _result[i] = (a[q] + b[left]) < (b[q] + a[right]) ? (a[q] + b[left++]) : (b[q] + a[right++]);
        }

        return _result;
    }
}

- Paul N. December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Like Alexey mentioned below, this doesn't work. Downvoting so it doesnt show up as top voted result (which it currently does)

"a = new int[] { 1, 2, 3,4,5,7,8,9,10 };
b = new int[]{1,20,30,40,50,60,70,80,90,100};
doesnt work

Also, k can be up to n^2, so the first double loop can take n^2

- Alexey on December 18, 2013 | Flag"

- whatevva' December 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

package careercup;

public class KthMinSum {
    public static Integer[] find(int k, int[] a, int[] b) {
        final Integer[] _result = new Integer[k];

        int q = (int) Math.sqrt(k);

        for (int i = 0; i < q; i++) {
            for (int j = 0; j < q; j++) {
                _result[i * q + j] = a[i] + b[j];
            }
        }

        int left = 0;
        int right = 0;

        for (int i = q * q; i < k; i++) {
            _result[i] = (a[q] + b[left]) < (b[q] + a[right]) ? (a[q] + b[left++]) : (b[q] + a[right++]);
        }

        return _result;
    }
}

- Paul N. December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

a = new int[] { 1, 2, 3,4,5,7,8,9,10 };
b = new int[]{1,20,30,40,50,60,70,80,90,100};
doesnt work

Also, k can be up to n^2, so the first double loop can take n^2

- Alexey December 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks for review. That was big fail ;)

> Also, k can be up to n^2, so the first double loop can take n^2

in original problem need to return first K elements, not just Kth element which was described as PS, that's why at least need to fill K elements. So algorithm's expected complexity is O(K). If K is equal to max value n^2, do you know any algorithm which fill n^2 elements in O(N)?

- Paul December 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

static int kthMinimum(int index1, int index2, int curr, int k)
	{
		if(curr == k)
		{
			return array1[index1] + array2[index2];
		}
		
		int n1 =  array1[index1 + 1] + array2[index2];
		int n2 =  array1[index1] + array2[index2 + 1];
		
		if(n1<n2)
		{
			curr++;
			if(curr == k)
				return n1;
				
			curr ++;
			if(curr == k)
				return n2;
		}
		else
		{
			curr++;
			if(curr == k)
				return n2;
				
			curr ++;
			if(curr == k)
				return n1;
		}
		return kthMinimum(index1 + 1, index2 + 1, curr+1,k);
	}

- hmm December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int findKthSum(int A[], int B[], int N, int K)
{
	ASSERT(N*N > K); // we must have K pairs

	// lets say A[a] and B[b] is Kth lowest sum
	// we must have ((a-1) * b < K) and  (a * (b-1) < K)
	
	// merge sort
	int a = 1; // this is elements used from A.
	int b = 1; // this is elements used from B.
	bool lastFromA = false;
	while (a * b < K)
	{
	   if (A[a-1] < A[b-1])
	   {
		a++;
		lastFromA = true;
	   }
	   else
	   {
		b++;
		lastFromA = false;
	   }
	}
	
	if (a*b == K) return A[a-1]+B[b-1];
	
	
	// so far we have used up a-1 elements from A, and b-1 elements from B. and have found (a-1)*(b-1)th lowest.
	// we also have one of the correct index (nextFromA). just find the other one.
	if (lastFromA)
	{
	    b = K - (a-1)*b;
	}
	else
	{
	    a = K - (b-1)*a;
	}
	// our answer is A[a] + B[b]
	return A[a] + B[b];
}

- Anonymous December 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

slight correction: last line should read

// our answer is A[a-1] + B[b-1]
	return A[a-1] + B[b-1];

- Anonymous December 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

like merge sort, increase pointers from a and b. You do not need to calculate the min values, you just count the min values while increasing the pointers. And when you exceed the desired k, you can calculate a[i] + b[j] for the kth min.

private static int kthMin(int[] a, int[] b, int k){
		
		int i = 0 ; 
		int j = 0 ;
		int numOfMin = 1;
		
		while(i < a.length -1 && j < b.length - 1) {
			
			
			if(a[i+1] <= b[j+1]) {
				i++;
				numOfMin += (j+1);
				if(numOfMin >= k) return a[i] + b[j- numOfMin + k];
				
			}
			else { 
				j++;
				numOfMin += (i+1);
				if(numOfMin >= k) return a[i- numOfMin + k] + b[j];
			}
			
		}
		
		return 0;
	}

- Arth December 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ooops, it does not work for

int a[] = {0, 1, 3, 5};
	int b[] = {1, 2, 4, 7};

- Arth December 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(n) algorithm:
suppose you have initial minimum:
a[i]+b[j]
To find next minimum you need to test the following 4-6 pairs and find the pair
with minimum sum that is greater than the current one. Rinse-repeat K times.

Code:

public static int getMin(int[]a, int[]b, int k){
		if(a.length!=b.length || a.length*a.length < k){
			return Integer.MIN_VALUE;
		} else {
			int newmin=a[0]+b[0]; // this is the result holder, initialized to satisfy Java
			for(int cura=0, curb=0, i=0; i<k; i++ ){
				int curmin = a[cura] + b[curb]; // current minimum
				newmin = curmin; 
				int newa =cura, newb=curb;
				int testa, testb, testsum;
				boolean gotcandidate = false;
				// Test a[cura-1]+b[curb+1] pair
				if(curb<b.length-1 && cura>0){
					testa=cura-1;
					testb=curb+1;
					testsum=a[testa] + b[testb];
					// if this pair's value is greater than current minimum we got candidate
					if(testsum>curmin){ 
						newmin=testsum;
						newa=testa;
						newb=testb;
						gotcandidate=true;
					}
				}
			    // Test a[cura+1]+b[curb-1] pair
				if(cura<a.length-1 && curb>0){
					testa=cura+1;
					testb=curb-1;
					testsum=a[testa] + b[testb];
					// we got new candidate if
					// this sum is greater than current minimum 
					// AND
					// we haven't got candidate yet OR this sum is less than the current candidate
					// i.e. current minimum > this test > current candidate
					if(testsum>curmin && (!gotcandidate || testsum<newmin)){
						newmin=testsum;
						newa=testa;
						newb=testb;
						gotcandidate=true;
					}
				}
				
	 		   // Test a[cura]+b[curb+1] 
				// if curb+1 is out of bound then test
				// a[cura+1]+b[0] instead
				if(curb<b.length-1){
					testa=cura;
					testb=curb+1;
				} else {
					testb=0;
					testa=cura+1;
				}
				testsum=a[testa] + b[testb];
				// we got new candidate if
				// this sum is greater than current minimum 
				// AND
				// we haven't got candidate yet OR this sum is less than the current candidate
				// i.e. current minimum > this test > current candidate
				if(testsum>curmin && (!gotcandidate || testsum<newmin)){
					newmin=testsum;
					newa=testa;
					newb=testb;
					gotcandidate=true;
				}
			    // Test a[cura+1]+b[curb]
				// if cura+1 is out of bound then test
				// a[0]+b[curb+1] instead
				if(cura<a.length-1){
					testa=cura+1;
					testb=curb;
				} else {
					testa=0;
					testb=curb+1;
				}
				testsum=a[testa] + b[testb];
				// we got new candidate if
				// this sum is greater than current minimum 
				// AND
				// we haven't got candidate yet OR this sum is less than the current candidate
				// i.e. current minimum > this test > current candidate

				if(testsum>curmin && (!gotcandidate || testsum<newmin)){
					newmin=testsum;
					newa=testa;
					newb=testb;
					gotcandidate=true;
				}
		
				if(!gotcandidate){
					System.out.println("Couldn't figure out next step for " + cura + ":" + curb);
					return -1;
				} else {
					// advance a and b indexes
					// to the newly found minimum
					cura=newa;
					curb=newb;
				}
				
			}
			return newmin;
		}
	}

- CalmMan December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oops, forgot to write up pairs in explanations

Here goes:
current min is a[i]+b[j];
next min will be amongs
a[i-1]+b[j+1] // test only if i>0
a[i+1]+b[j-1] // test only if j>0
a[i]+b[j+1] // if j+1 is out of bound test a[i+1]+b[0] instead
a[i+1]+b[j] // if i+1 is out of bound test a[0]+b[j+1] instead

amongst these candidates your next minimum is the smallest one which is
greater than the current minimum.

a:     i-1 i i+1
 b:     j-1 j j+1

- Anonymous December 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't work with these inputs:

A: (1,4,20,24)
B: (1,21,22,25)

1st min: 1+1
2nd min: 4+1
3rd min: 1+20
4th min should be 1+21 but with your method it doesn't check the i=0 in this step.

- kaveh.vakili March 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Minimum value will be a[0] + b[j] or a[i] + b[0]

so the answer is

int[] firstKMin(int k, int[] a, int b []){
int i = 1;
int j = 1;
int index = 1; 
int[] answer = new int[k];
// This is special case
answer[0] = a[0] + b[0];
while(i < N && j < N){
x = a[i]   + b[0];
	y = a[0] + b[j];
	if(x < y){
		answer[index] = x;
		i++;
}else{
	answer[index] = y;
	j++;
}
	c++;
}
if(index < k){
	if(i == N){
		for(int l = j; l < N; l++){
			answer[index] = a[0] + b[l];
			index++;
}	
}
if(j == N){
		for(int l = i; l < N; l++){
			answer[index] = a[i] + b[0];
			index++;
}
}
}
return answer;
}

- kuroobi January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Since both are sorted array,The first element of both the array will be minimum. So the sum a[0]+b[0] will be less than any of other a[i]+b[j]

so the answer is straight

A[0] + B[0]

- Anonymous December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think your solution ignores the "first K" part, which sounds like a k-th order statistic.

- Anonymous December 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Can we reuse the same array's elements to compute multiple sums? I mean for this ex and K = 4:
a[]: 1 2 3
b[]: 1 4 7
The correct answer is 1+1, 2 + 1, 3+1, 1+4 ?

- thelineofcode December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am sure it is..

- naveen December 18, 2013 | Flag


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