Amazon Interview Question
Software Engineer / DevelopersTeam: payments team
Country: India
Interview Type: In-Person
0(n^2)
convert the bst into array, then solve for a+b=k-c, for each c in the array.( need to do it for every
c and not (a+b)) .
Convert the BST to array as said..and perform below operation.
for(int i=0;i<a.length;i++){
for(int j =i+1;j<a.length;j++){
for(int k =j+1;k<a.length;k++){
if(a[i]+a[j]+a[k]==Q){
System.out.println(""+a[i]+"--"+a[j]+"--"+a[k]+"");
}
}
}
}
The algo you gave here is of complexity o(n^3)....instead my approach gives u complexity of o(n^2 logn)..and that's what interviewers are looking for...
Ok changed it to get O(N^2) change above code, removed thrird loop code to after
for(int j =i+1;j<a.length;j++) line..
int k = j+1;
if (k < a.length) {
if (a[i] + a[j] == Q - a[k]) {
System.out.println("" + a[i] + "--" + a[j] + "--"+ a[k] + "");
}
}
1) inorder traversal to get the array into assending order
Then the following code -
import sys
from array import *
a= array('i', [1,2,3,4,5,6,9])
size = 7
i=0
k=20
while 1:
if(i + 3 > size):
print "No match found"
sys.exit(0)
sum = a[i] + a[i+1] + a[i+2]
#print sum
if (sum == k):
print "starting index is " + str(i)
sys.exit(0)
i = i+1
First do inorder traversal to get a sorted array. Now, for every element, c in array, do following : find pairs a, b such that a+b = k-c in remaining array by using a HashMap technique. Traverse remaining array and for each element, insert it in HashMap using following rules.
(1)If an element (a) is already present as key that when combined with it(b) gives k-c, then insert it as value to that key.
(2)Otherwise, insert it as key with value as INT_MIN or INT_MAX or INFINITY.
Now, the entries in the hashmap with proper values will give required pairs(key, value). Combining these with c gives triplets needed. Do this for every possible c.
void findANYThreeNodesWithSumK(node* head, node* sumarr[], int num, int K) {
if (head == NULL)
return;
findANYThreeNodesWithSumK(head->left, sumarr, num, K);
findANYThreeNodesWithSumK(head->right, sumarr, num, K);
sumarr[num] = head;
findANYThreeNodesWithSumK(head->left, sumarr, num+1, K-head->data);
findANYThreeNodesWithSumK(head->right, sumarr, num+1, K-head->data);
if (K == 0 && num == 3) {
//print all the nodes in sumarr
num = 0;
//flush sumarr so that it can continue further
}
}
Steps :
1. Inorder traversal of BST gives array elements in sorted order O(N)
2. When traversing BST to find the sorted order find the largest element that is lower than K. (Operation doesn't take time done as a part of step 1)
3. Problem reduces to a modification of the maximum sub-array problem
In average it could be even better than O(n^2):
- Anonymous November 04, 20121- first hash list by the value
2- sequentially go through the list and subtract the value (let's call it 'c') from the k. and then search for the pairs of the numbers who sum up to (k-c) -> because it is hashed so you can start from first item in the list and check for the other pair in constant time
overall time complexity in worst case is o(n^2) but in real we expect less than that