Amazon Interview Question
Developer Program EngineersCountry: United States
Interview Type: Phone Interview
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}?
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.....
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)
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.
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?
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?
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.
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)+")";
}
}
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
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?
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.
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).
+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.
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
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
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)
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.
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
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);
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;
}
}
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.
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' ?
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;
}
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};
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;
}
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]
thanks for your grateful idea, I am very grateful. I will implement your idea and let you know.
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!
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();
}
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)
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"
good idea, and I am very lazy, could you implement for us? so many people are eager to get a right solution.
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.
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
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;
}
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;
}
}
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 :)
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 ?
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..
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;
}
}
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...
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] (!))...
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);
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.
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.
- gen-y-s January 16, 2013The 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)