Amazon Interview Question
Software Engineer / Developerssort A,B,C, then modifying merge sorted to search for A_i+B_j+C_k. Time O(nlogn) , n is the length of A or B or C
A solution with O(n) complexity.
Create a hash table, that contain all the possible sum combination of any of the 2 list.
A X B
A[1] + B[1....n]
A[2] + B[1....n]
...
...
A[n] + B[1....n]
Its a one time effort with O(n*n).
And it provide lateral access & solution with O(n).
Check if -(C[index]) exists in the hash table then return true.
When you mention a hash table mention the hash key and hash function because hash table is nothing without it.And only with that detail we can determine the worst case complexity of the solution.
for each of n*n element combination from A&B build a binary search tree. Building a tree takes O(N) where N = n*n.
then for each of n elements from C, Do a binary search on the tree which is expected to be O(nLgn) thus the Overall complexity of the solution remains O(n^2)
First sort all of them (O(nlogn) complexity)
A -> ascending
B & C -> descending
Now to make understanding simpler,lets take an example
A=> -4 -1 3 6 7 8 i
B=> 9 7 3 2 1 -5 -6 j
C=> 12 5 2 1 0 -1 -5 k
LOOP { // exit if i+j+k == 3n
1.check if A[i] + B[j] + C[k] ==0,if yes return true;
2. if not then if A[i] + B[j] + C[k] <0
i = i + 1
3. else {
if(A[i] + B[j+1] + C[k] == 0) return true;
if(A[i] + B[j] + C[k+1] == 0) return true;
j = j+1;
k = k+1;
}
END LOOP
The idea is to
=> if sum < 0 ,then value at A should be increased to get zero so i is incremented
=> if sum > 0 ,then B and C should be decreased to get zero so j and k is incremented.
Complexity = sorting + interation
= o(nlogn) + O(3n)
= O(nlogn)
pls note :- Just for sake of understanding,i have taken i,j,k;They can be implemented using ->next in a linked list.
Guys,ur comments are welcome!
This doesn't work, since the "right" elements in B and C may be further than one apart.
It doesnt work in the following scenario (Ideally it should have returned true as A[0] + B[3] + C[1] = 0)
A {0, 1, 2, 4, 5}
B { 4,3,1,-1, -4}
C { 2,1,0,-2,-4}
First loop:
A[0]+B[0]+C[0] = 6 >0
&& A[0]+B[1]+C[0] != 0
&& A[0]+B[0]+C[1] != 0
j=1
k=1
Second Loop:
A[0]+B[1]+C[1] = 4 >0
&& A[0]+B[2]+C[1] != 0
&& A[0]+B[1]+C[2] != 0
j=2
k=2
Third Loop:
A[0]+B[2]+C[2] = 1 >0
&& A[0]+B[3]+C[2] != 0
&& A[0]+B[2]+C[3] != 0
j=3
k=3
Fourth loop:
A[0]+B[3]+C[3] = -3 <0
i=1
Fifth loop:
A[1]+B[3]+C[3] = -2 <0
i=2
sixth loop:
A[2]+B[3]+C[3] = -1 <0
i=3
seventh loop:
A[3]+B[3]+C[3] = 1 >0
&& A[3]+B[4]+C[3] != 0
&& A[3]+B[3]+C[4] != 0
j=4
k=4
eighth loop:
A[3]+B[4]+C[4] = -4 <0
i=4
ninth loop:
A[4]+B[4]+C[4] = -3 <0
i=5 <<Loop Ends>>
My algorithm would do...
minA = lowest element in A (On).
minB = lowest element in B (On)
minC = lowest element in C (On).
if minA + minB + minC > 0 => return false
else return true.
This would be On overall.
I think this would solve the problem. Or am i crazy?
Thanks.
you guys are so funny! I have some rough idea of O(n^2) complexity.
first construct hashtable for numbers in B and C, setup flag indicating which list each number belongs. like this
Hashtable:
key value
number B or C or BC
then iterate each number in A, suppose the value of one number is m
then you need to find the sum of numbers from B and C which sums to -m
do linear search in hashtable. it can be done in O(n) since number value
is the key of hashtable.
you guys are so funny! I have some rough idea of O(n^2) complexity.
first construct hashtable for numbers in B and C, setup flag indicating which list each number belongs. like this
Hashtable:
key value
number B or C or BC
then iterate each number in A, suppose the value of one number is m
then you need to find the sum of numbers from B and C which sums to -m
do linear search in hashtable. it can be done in O(n) since number value
is the key of hashtable.
@arvind646 : ya ur sollution is right really fine using the heap and maiontaining the sum as variable always 3 member be there at the heap and its so easy time coplexity over all that is taking sorting as werll be nlgn a really gud slution means we are taking sme extra space that is constant too means heap will always be of size 3 :)
Suppose C is the smallest array. Sort A and B, and for each element x in C, do the usual algorithm to find x in the implicit 2D array [Sij] where Sij = Ai + Bj.
- Anonymous March 16, 2010No one knows how to do (much) better without some restrictions on the input.