Amazon Interview Question for Developer Program Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
5
of 7 vote

Think of a k by k matrix where each element at (i,j) is the sum of item i from the first array and item j from second array. The row and coluns of this matrix are in increasing order.
The idea is to have a pointer for each row in the matrix indicating the next element to consider from the row. We take the smallest element from all rows, and move the pointer for the row we took the item from forward.
This can be implemented using a heap of size k, which is initialized with the element of the first column of the matrix. We perform k steps where we pop the min element from the heap and replace it with the next element from its row in the matrix.
Complexity: time O(k log k), space O(k)

- gen-y-s January 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are we assuming no duplicates? Could you walk through an example of this, for instance, if A = {1,1,1, 2} and B = {1,1,1, 2}?

- Will_In_Seattle January 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here's an example:
A={0,3,7}
B={0,5,10}

Matrix of C where C[i,j]=A[i]+B[j]:

0  5 10  
 3  8 13
 7 12 17

We start with C[0,0] (which is 0) and then we consider C[0,1] (to the right of C[0,0]) which is 5 and C[1,0] (the first cell in the next row) which is 3 so we choose the C[1,0] because it's the smaller one.
Since we chose C[1,0] we now consider the next item in the same row C[1,1] which is 8, and also the first item from the next row C[2,0] which is 7 (note that we adding the next row to the consideration when we choose the first element from the previous row). So we choose 5 (C[0,1]) since it's the smallest of 5, 7 ,8, and now we add the next item from the same row to the consideration which is 10 (C[0,2]). Now we again choose between 7,8, and 10 and so on.....

- gen-y-s January 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here's the algorithm implemented in Python.
It handles duplicates, as well as different size arrays and any k-th sum: k!=len(A)!=len(B)
Complexity is O(k log k) time, O(k) space

import heapq

def kth_sum(l1, l2, k):
  if k==0 or k>len(l1)*len(l2):
    return "error"
  h=[(l1[0]+l2[0], 0, 0)]
  for c in range(0, k):
    (v, x, y)=h[0]
    print str(v)+" "+str((x,y))
    if y==0 and x+1<len(l1):
      heapq.heappush(h, (l1[x+1]+l2[0], x+1, 0))
    if y+1<len(l2):
      heapq.heapreplace(h, (l1[x]+l2[y+1], x, y+1))
    else:
      heapq.heappop(h)
  return v

def main():
  l1=[1, 6, 10]
  l2=[2, 5, 7]
  print l1
  print l2
  kth_sum(l1, l2, 5)

- gen-y-s January 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if you turn it into c or c++, We will appreciate it very much.

- yingsun1228 January 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The advantage of python is that it has a heap module, and also I used a tuple type of the form (val, i, j) to represent matrix cells which contain the value and its coordinates in the matrix. This is required to determine the next element to be added to the heap, when an element is popped from the heap.
So in C++ you would have to define a class to represent a matrix cell, and use library providing heap data structure.

- gen-y-s January 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ok, I know that, and I should add a new rule to my topic.

- yingsun1228 January 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'd like an explanation for my earlier example, or perhaps with {1,1,2}, {1,1,3}. I don't think it works, does it?

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

Also will this matrix solution work if the arrays start with a different element? E.g. A={ 1, 3, 5} and B= { 2, 4, 5} What value would you be in [0,0] of the matrix?

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

For A=[1,1,2] B=[1,1,3] The sum matrix C will be:

2 2 4
2 2 4
3 3 5

We initialize the heap with C[0,0]=2
First Iteration: We pop C[0,0]=2 from heap and push C[0,1]=2 and C[1,0]=2 onto the heap.
Second Iteration: pop C[0,1]=2, push C[0,2]=4.
Third iteration: pop C[1,0]=2, push C[1,1]=2 and C[2,0]=3.
Fourth Iteration: pop C[1,1]=2, push C[1,2]=4
Fifth Iteration: pop C[2,0]=3, push C[2,1]=3
Sixth Iteration: pop C[2,1]=3, push C[2,2]=5
Seveth Iteration: pop C[0,2]=4
Eighth Iteration: pop C[1,2]=4
Nineth Iteration: pop C[2,2]=5

Or you could just run the program and see for yourself.

- gen-y-s January 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here's the solution in java:

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;

class Kth_Sum {

  static class Cell implements Comparable
  {
    public int val;
    public int row;
    public int col;
    public Cell(int val, int row, int col)
    {
      this.val=val;
      this.row=row;
      this.col=col;
    }
    public int compareTo(Object o)
    {
      Cell other = (Cell)o;
      int c = Integer.compare(this.val, other.val);
      if (c==0)
      {
        c = Integer.compare(this.row, other.row);
        if (c==0)
          c = Integer.compare(this.col, other.col);
      }
      return c;
    }
    public String toString()
    {
      return Integer.toString(this.val)+" ("+Integer.toString(this.row)+", "+Integer.toString(this.col)+")";
    }
  }

- gen-y-s January 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;

class Kth_Sum {

  static class Cell implements Comparable
  {
    public int val;
    public int row;
    public int col;
    public Cell(int val, int row, int col)
    {
      this.val=val;
      this.row=row;
      this.col=col;
    }
    public int compareTo(Object o)
    {
      Cell other = (Cell)o;
      int c = Integer.compare(this.val, other.val);
      if (c==0)
      {
        c = Integer.compare(this.row, other.row);
        if (c==0)
          c = Integer.compare(this.col, other.col);
      }
      return c;
    }
    public String toString()
    {
      return Integer.toString(this.val)+" ("+Integer.toString(this.row)+", "+Integer.toString(this.col)+")";
    }
  }

  public static void main(String[] args)
  {
    ArrayList l1 = new ArrayList();
    l1.add(1);
    l1.add(2);
    l1.add(4);
    ArrayList l2 = new ArrayList();
    l2.add(0);
    l2.add(5);
    l2.add(7);
    kth_sum(l1,l2,9);
  }

  public static Cell kth_sum(List<Integer> l1, List<Integer> l2, int k)
  {
    PriorityQueue<Cell> queue = new PriorityQueue<Cell>();
    if (k>l1.size()*l2.size())
      return null;
    Cell c=null;
    queue.add(new Cell((l1.get(0)+l2.get(0)),0,0));
    for(int i=0; i<k; i++)
    {
      c=queue.poll();
      if (c==null)
        break;
      System.out.println(c);
      if (c.col==0 && c.row+1<l1.size())
        queue.add(new Cell((l1.get(c.row+1)+l2.get(c.col)),c.row+1,c.col));
      if (c.col+1<l2.size())
        queue.add(new Cell((l1.get(c.row)+l2.get(c.col+1)),c.row,c.col+1));
    }
    return c;
  }
}

- gen-y-s January 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 awesome

- sreeram January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ gen-y-s
I'm about "Complexity: time O(k log k), space O(k)"...
To build the matrix you need k^2 operations and to store the matrix you need O(k^2) additional space, don't you?

- Aleksey.M January 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

Wrong Solution.
The complexity is O(k*k) instead of claimed O(k log k).

The flaw is that Matrix is created in O(k*k) time.

- Bevan February 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

No it's O(K log K)
The main loop will iterate K times.
Each loop iteration performs a one remove operation and up to 2 insert operations into the heap. These operation take O(log H) time where H is the size of the heap. The max size of the heap is K (since it will grow by at most one in each iteration), so each iteration takes O(log K) time. Therefore overall time is O(K log K).

- gen-y-s February 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

+1 @Bevan
Complexity is O(k*k) and not O(k log k) .

@gen-y-s The remove and insert operations are to be done on the matrix rows.. You are correct that complexity of finding the kth smallest combination is O(k log k) but to be able to run your algorithm the input needs to be created and that WOULD take O(k* k) time.

- Second Attempt March 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

check this link... nicely explained

The best solution, but non-trivial, O(lg m + lg n):
Although the above solution is an improvement both in run time and space complexity, it only works well for small values of k, and thus is still in linear run time. Could we improve the run time further?

The above logarithmic complexity gives us one important hint. Binary search is a great example of achieving logarithmic complexity by halving its search space in each iteration. Therefore, to achieve the complexity of O(lg m + lg n), we must halved the search space of A and B in each iteration.

We try to approach this tricky problem by comparing middle elements of A and B, which we identify as Ai and Bj. If Ai is between Bj and Bj-1, we have just found the i+j+1 smallest element. Why? Therefore, if we choose i and j such that i+j = k-1, we are able to find the k-th smallest element. This is an important invariant that we must maintain for the correctness of this algorithm.

Summarizing the above,
Maintaining the invariant
i + j = k – 1,

If Bj-1 < Ai < Bj, then Ai must be the k-th smallest,
or else if Ai-1 < Bj < Ai, then Bj must be the k-th smallest.

If one of the above conditions are satisfied, we are done. If not, we will use i and j as the pivot index to subdivide the arrays. But how? Which portion should we discard? How about Ai and Bj itself?

We make an observation that when Ai < Bj, then it must be true that Ai < Bj-1. On the other hand, if Bj < Ai, then Bj < Ai-1. Why?

Using the above relationship, it becomes clear that when Ai < Bj, Ai and its lower portion could never be the k-th smallest element. So do Bj and its upper portion. Therefore, we could conveniently discard Ai with its lower portion and Bj with its upper portion.

If you are still not convince why the above argument is true, try drawing blocks representing elements in A and B. Try visualize inserting blocks of A up to Ai in front of Bj-1. You could easily see that no elements in the inserted blocks would ever be the k-th smallest. For the latter, you might want to keep the invariant i + j = k – 1 in mind to reason why Bj and its upper portion could never be the k-th smallest.

On the other hand, the case for Ai > Bj is just the other way around. Easy.

Below is the code and I have inserted lots of assertion (highly recommended programming style by the way) to help you understand the code. Note that the below code is an example of tail recursion, so you could technically convert it to an iterative method in a straightforward manner. However, I would leave it as it is, since this is how I derive the solution and it seemed more natural to be expressed in a recursive manner.

Another side note is regarding the choices of i and j. The below code would subdivide both arrays using its array sizes as weights. The reason is it might be able to guess the k-th element quicker (as long as the A and B is not differed in an extreme way; ie, all elements in A are smaller than B). If you are wondering, yes, you could choose i to be A’s middle. In theory, you could choose any values for i and j as long as the invariant i+j = k-1 is satisfied.

leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html

- dev January 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@dev ... the questions is not about union of two array. Its about to find k-th smallest combinations(i.e. summation) of 2 num, one from each array.

- SRB January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

i didn't get the question

- Y January 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I change the expression, could help me to get this question.

- yingsun1228 January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am not sure how k comes in to the picture as since the array is in ascending order, the least value of (a[i] + b[j]) would be when i = 0 and j = 0

- Y January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

no, you did not get the idea, sorry for my bad english, I mean the counts of conbination of ai+bj is k, not only one. k-th means the count is k.

- yingsun1228 January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If I am getting question right, you mean that of all the K*K pairs generated by both arrays, where one element is from array A and other element is from array B, we have to find Kth smallest pair.
---------------------------------
(Make maxheap of size K.)

For each pair generated by arrays,calculate a + b,
If a + b is less than top of maxheap then replace it with top and heapify.
else ignore it.
At the end, top of the maxheap will give kth smallest a+b. If you want you can also store index numbers of elements.

Time Complexity - O(n*n logn)
Space Complexity - O(k)

- Nitin Gupta January 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

thank you, you get the main idea and the right resolution, but the time of this solution is a little long. And sorry for that I have not got the best anwser yet and we both waiting for other people's idea. Thank you.

- yingsun1228 January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh really sorry, I forgot the condition 0 <= i <= j <= k

We can use this condition to reduce time complexity.
Will update the code later.

Thanks

Sorry for inconvinience

- Nitin Gupta January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can someone clarify the question properly with an example?

- anish[1] January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if a[]={1,2,3}; b[]={4,7,10} the result should be 5, 6,7;
if a[]={1,2,5}; b[]={4,6,9} the result should be 5,6,7;

I will build an BST with sums calculated with all pairs, and iterate this tree in in-order sequence.
time is o(k^2); space is o(k);

- Bin January 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Bin, it is also a very grateful idea. And can you put your codes here, and we can analysis your idea clearly.

- yingsun1228 January 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

With this class you can get the sum of the smallest kth element or the combination that composes it.

public class MinimumKth {
    private int[] a;
    private int[] b;
    
    public MinimumKth(int[] a, int[] b){
	this.a = a;
	this.b = b;
    }
    
    public int smallestSum(int kth) {
	int[] toSum = smallestCombination(kth); 
	return toSum[0] + toSum[1];
    }
	    
    public int[] smallestCombination(int kth) {
	int[] smallest = new int[2];
	for(int j=0; j <= kth; j++) {
           smallest[1] = b[j];
           for(int i=0; i <= j; i++) {
              smallest[0] = a[i];   
	   } 
	}
	return smallest;
    }
}

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

I think your solution is wrong.
Lets suppose
a[] = {1,9,15}
b[] = {2,5,7}

Here K = 3

So answer should be (1, 7)

While your solution will return (15,7), if I am not wrong.

- Nitin Gupta January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

First of all, Is that a valid input ? Isn't the minimum element of array 'b' should be greater than the maximum element of array 'a' ?

- Dattathreya January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is perfectly correct and valid input.

Your condition is mentioned anywhere in the question. I am not making any assumption as far as question is concerned.

- Anonymous January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] find(int[] a, int[] b) {
        if (a == null || b == null || a.length != b.length) return null;
        
        int k=a.length;
        
        if (k==0) return null;
        
        int i=0;
        int j=0;
        
        int[] r = new int[k];
        int h = 0;
        
        r[h++]=a[i] + b[j];
        System.out.println(a[i]+"+"+b[j]);
        
        while (h<k) {
            if (a[i+1]+b[j] > a[i]+b[j+1]) {
                j++;
            } else {
                i++;
            }
            r[h++]=a[i] + b[j];
            System.out.println(a[i]+"+"+b[j]);
        }
        
        return r;
    }

- Illya January 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks for your code and idea, but it will turn out to be wrong when a and b like this:a[] = {1, 3, 6}; b[] = {2, 5, 6};

- yingsun1228 January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, you are right. Here is final version:

public static int[] find(int[] a, int[] b) {
        if (a == null || b == null || a.length != b.length) return null;
        int k=a.length;
        if (k==0) return null;
        
        int i=0, j=0;
        int[] r = new int[k];
        r[i+j]=a[i] + b[j];
        
        while (i+j<k-1) {
            if (i==k || a[i+1]+b[0] > a[0]+b[j+1]) {
                j++;
                r[i+j]=a[0] + b[j];
            } else {
                i++;
                r[i+j]=a[i] + b[0];
            }
        }
        
        return r;
    }

- Illya January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No. This one is not correct too. Sorry.

- Illya January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

that's nothing, and I am very grateful for you idea.

- yingsun1228 January 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in O(1). we can see that for any index x, a[x]+b[x] will be greater that all a[i]+b[j] where 0<i<x and 0<j<x. so to find kth largest, we need to find x such that (x-1)squared <k<xsquared. after that kth smallest will be smaller of a[k]+b[0] and b[k]+a[0]

- Gopal January 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks for your grateful idea, I am very grateful. I will implement your idea and let you know.

- yingsun1228 January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you implement your idea for me? I am not quite understanding what you mean.

- yingsun1228 January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this solution may not work .. i missed those numbers which, although on greater index than x ,can give smaller sums when added to numbers on index <x. will think over and try to fix this scenario

- newStart January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This comment has been deleted.

- Administrator January 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

do you test it and what is the result: it works well?

- yingsun1228 January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The above code wouldn't work if we are trying to find out the 4th smallest sum for arrays {1,2,6} and {2,3,8}. The actual answer is 5 but the code would report 8 instead!

- fengsui January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thank you all the same.

- yingsun1228 January 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry, I still do not understand the question. Can you please write an example clearly?

- Kary January 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int k_smallest_combinations(int A1[], int A2[], int l1, int l2, int k){
    Min_Heap heap(l1);//l1 is size of heap
    int count=1;
    for(int i=0; i<l1; i++){
        sum = A1[i] + A2[0];
	heap.insert(sum, i, 0);
    }
    while(count<k){
        int row = heap.root.row();
        int column= heap.root.column();
        sum = A1[row] + A2[column+1];
        heap.insert(sum, row, column +1);
	count++;
    }
    return heap.root.data();
}

- SRB January 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's the solution I gave implemented in python.
It works even for input lists of different sizes (e.g. one list with "m" elements and a second list with "n" elements) and any k-th largest sum:

import heapq

def kth_sum(l1, l2, k):
  if k==0 or k>len(l1)*len(l2):
    return "error"
  h=[(l1[0]+l2[0], 0, 0)]
  for c in range(0, k):
    (v, x, y)=h[0]
    print str(v)+" "+str((x,y))
    if y==0 and x+1<len(l1):
      heapq.heappush(h, (l1[x+1]+l2[0], x+1, 0))
    if y+1<len(l2):
      heapq.heapreplace(h, (l1[x]+l2[y+1], x, y+1))
    else:
      heapq.heappop(h)
  return v

def main():
  l1=[1, 6, 10]
  l2=[2, 5, 7]
  print l1
  print l2
  kth_sum(l1, l2, 5)

- gen-y-s January 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think having an index bookkeeper array for both of the input arrays would result a linear algorithm.
Take the given example.
A: {1, 3, 6}
B: {4, 5, 6}
index_A:{0, 0, 0} // indicating the next index of its potential pair in the opposite array.
index_B:{0, 0, 0} // same.

Each time the comparing two combinations would be taken
from index_A and index_B:
{index_A[i], index_B[j+1]} and {index_A[i+1], index_B[j]}


Step 1: get min{(A[0], B[0]), (A[0], B[0]) }
get A[0] and B[0]. and update the index array to be:
index_A:{1, 0, 0}
index_B:{1, 0, 0}
Step 2: get min{(A[0], B[1]), (A[1]), B[0])} // the index pair are the crossing pair of the index array
here we have min{(1, 5), (3, 4)}, since (1, 5) wins, we need to update the index array to be:
index_A:{2, 0, 0}
index_B:{1, 0, 0}
Step 3: get min{A[0], B[2]), (A[1], B[0)}; // the index pair are the crossing pair of the index array
we have min{(1, 6), (3, 4)}, it can be either. we pick (1, 6), and update the index array to be:
index_A:{3, 0, 0} //here we have the potential pair of the first element of A to be 3, this indicates
//this element is out of game.
index_B:{1, 0, 0}
continue
until we find the k-th combination at step "k"

- Helloworld January 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good idea, and I am very lazy, could you implement for us? so many people are eager to get a right solution.

- yingsun1228 January 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution doesn't work if A={1,30,60}
Also why did you increase both indexes in the first step but only one index in the second step ?
In any case, the solution is wrong because there could be more than two options to consider for the next pair. In contrived example that was used, the order of pairs is very simple, that's the only reason it works for that case.

- gen-y-s January 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hope I am not mistaken. but if the two arrays A,B are in ascending order, why not compare the first element of the two then the smallest k combonations will be the frist element added with elements of the other array?

int * f ( int [ ] A, int[ ] B, int k){
     int min,* other_array;       
      if( A[0]>B[0])  {min=B[0]; other_array=A;}
      else {min=A[0]; other_array=B;}
int i;
 for(i=0;i<k;i++) other_array[i]+=min;   
         return other_array;
}

The question istself describes this algorithm with an example, it can't be so simple but I can' interpret the question other wise

- EthOmus January 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check this complexity will be k

int main(){
    int a[]={0,3,7};
    int b[]={0,5,10};
    int aSize = 3,bSize = 3;
    int x=0,y=0,i=0,j=0,k=9; // suppose k=9
    while(x!=aSize && y!=bSize && k>0){
        i=x+1;j=y+1;
        cout<<a[x]<<","<<b[y]<<endl;
        k++;
        while(i!=aSize && j!=bSize && k>0){
            if(a[x]+b[j]<b[y]+a[i]){
                cout<<a[x]<<","<<b[j]<<endl;
                j++;
            }
            else{
                cout<<b[y]<<","<<a[i]<<endl;
                i++;
            }
            k--;
        }
        while(i!=aSize&&k>0){
                cout<<b[y]<<","<<a[i]<<endl;
                i++;
                k--;
        }

        while(j!=bSize&&k>0){
                cout<<a[x]<<","<<b[j]<<endl;
                j++;
                k--;
        }
        x++;
        y++;
    }
    return 0;
}

- Crazy Tesla January 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Test{

public static void main(String args[]){
int[] a = {1,2,3,4,5,6};
int[] b = {-1,2,4,12,13,15};

int[] k = findK(a, b);


for(int c : k){
System.out.println(c + " ");
}
}


public static int[] findK(int[] a, int[] b)
{
if(a == null || b == null || a.length != b.length)
return null;


int[] result = new int[a.length];
int i = 1;
int j = 1;

for(int k = 1; k < result.length; k++){
int sumWithA = a[0] + b[j];
int sumWithB = b[0] + a[i];

if(sumWithA <= sumWithB){
result[k] = sumWithA;
j++;
}else{
result[k] = sumWithB;
i++;
}

}
return result;


}
}

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

I forget to add
result[0] = a[0] + b[0];

- qiqiatosu January 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Start from ptr1 at A[0], and ptr2 at B[0].

If ptr1 is at A[i] and ptr2 is at B[j], increase ptr1 by one if A[i+1] + B[j] < A[i] + B[j+1], else increase ptr2 by one, recording the min at each step.

That is it. Kind of like merge sort, accept you are not merging or sorting :)

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

Oh, and it is O(n).

- memo January 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

suppose you increase ptr1 to A[1], and afterwards you want increase ptr2 to B[1]. But you also need to decrease ptr1 back to A[0] right ? In merge sort you never move the pointers backwards, got it ?

- gen-y-s January 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yea, you are right. But one of the pointers can stay, and the other can do a binary search to find the next value. So, you can have ptr1 fixed, ptr2 binary search, and then vice versa. Between those 2, you take the min. That, though, is O(nlogn).

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

Can we do it like this:

First generate all the A[i] + B[j] combinations as suggested in the question. And then build a max heap.
Now remove the top (K*K - K) elements from the heap....and every time you remove, heapify the heap...So at the end, you will get the Kth smallest element at the top.

Hope it helps..

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

I'd use the priority to help computation.
Everytime pop an answer with index pair(i,j) (which is the smallest sum now), and add the (i,j+1) and (i+1,j) pair into the heap.

import java.util.LinkedList;
import java.util.PriorityQueue;


class PairSum implements Comparable<PairSum>{
    public int value1;
    public int value2;
    public int sum;
    public int index1;
    public int index2;
    public PairSum(int _value1, int _value2, int _index1, int _index2){
        value1 = _value1;
        value2 = _value2;
        sum = value1 + value2;
        index1 = _index1;
        index2 = _index2;
    }
    
    public int compareTo(PairSum another){
        if(this.sum < another.sum)
            return -1;
        else if(this.sum == another.sum)
            return 0;
        else
            return 1;
    }
    
    public String toString(){
        String res = "[ " + value1 + "," + value2 + " " + sum + " ]";
        return res;
    }
}

public class SortSum{
    
    
    public static LinkedList<PairSum> sortSum(int[] array1, int[] array2){
        LinkedList<PairSum> res = new LinkedList<PairSum>();
        PriorityQueue<PairSum> heap = new PriorityQueue<PairSum>();
        
        heap.offer(new PairSum(array1[0],array2[0],0,0));
        while(heap.size() != 0){
            PairSum popped = heap.poll();
            res.add(popped);
            int i = popped.index1;
            int j = popped.index2;
            if( (i < array1.length) && (j < array2.length - 1)){
                heap.offer(new PairSum(array1[i], array2[j+1], i, j + 1));
            }    
            
            if( (i < array1.length - 1) && (j < array2.length)){
                heap.offer(new PairSum(array1[i+1], array2[j], i+1, j));
            }
        }
        
        return res;
    }
    
    public static void main(String[] args){
        
        int[] array1 = {1,3,6};
        int[] array2 = {4,5,6};
        
      
        System.out.println(SortSum.sortSum(array1, array2));
        
        return;
    }
}

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

I think we can solve this problem in linear time as follows:

Since we know that the arrays are sorted, so we can assume that the first element(smallest emelent) of an array will give us the min combination when combined with any element of second array. So, we bookmark these 2 elements of both arrrays.

int i = 0; j =0;

1. Print A[0] and B[0], of course..this is the min combination so far.
2. If (A[0] + B[j+1] < A[i+1] + B[0]), then print A[0]+B[j+1] and j++;
3. If (A[i+1] + B[0] < A[0] +B[j+1]), then print A[i+1] + B[0] and i++;
4. Else .... both are equal, print A[0] + B[j+1] and A[i+1] + B[0] and i++, j++

repeat 1,2,3,4 K time...you wil get the result..I have tested on some test case...Reply if it works for you...

- A January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Unfortunately, it doesn't work. See {1,5,6} and {2,3,8}.
Pairs are: (a[0],b[0]), (a[0],b[1]), (a[1],b[0] (!))...

- Aleksey.M January 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Aleksey: It works well for this input as well...recheck

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

it does not work for {1 2 10 19} and {2 4 15 18}

- sz2376@columbia.edu November 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

scala> Array(1,2,3).zip(Array(4,5,6)).map(e => e._1 + e._2)
res16: Array[Int] = Array(5, 7, 9)

- rbsomeg February 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

if my understanding is right, we can have two pointers and move forward gradually. if list1[i + 1] > list2[j+1] then we pick up j to increase by one since we need a new combo.

def kthsum(ll, lr, k):
	i,j = 0,0
	sum = ll[i] + lr[j];
	k -= 1;
	while k != 0:
		if i + 1 < len(ll) and j + 1 < len(lr):
			if ll[i+1] < lr[j+1]:
				i += 1;
			else:
				j += 1;
		elif i + 1 >= len(ll) and j + 1 < len(lr):
			j += 1;
		elif i + 1 < len(lr) and j + 1 >= len(lr):
			i += 1;
		else:
			break;
		k -= 1;
	if k != 0:
		return None;
	return i,j;

if __name__ == "__main__":
	lst1 = [1,2,6];
	lst2 = [2,3,8];
	print kthsum(lst1,lst2, 3);

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

ok...its wrong. sorry. :(

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

public static void main(String args[]){

int[] a = {1, 3, 6};
int[] b = {4, 5, 6};
int k;
for(int i=0;i<a.length;i++){
for(int j=0;j<b.length;j++){

k = a[i]+b[j];
System.out.println(a[i] + "+" + b[j] + "=" + k);


}
}

- Sathishwaran January 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes, thanks for your explanations, and i will try your idea.

- yingsun1228 January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You may have up to k items to choose from to be the next item (the smallest one). In your example, after you chose (a0, b1) then you have to choose from (a1,b0), (a1, b1), or (a0, b2).
To choose between multiple elements you will need log(k) time and you have to do this k times.

Also, I already gave the full solution.

- gen-y-s January 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you paste your code here, thanks.

- yingsun1228 January 17, 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