Amazon Interview Question for Software Engineer / Developers


Team: payments team
Country: India
Interview Type: In-Person




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

In average it could be even better than O(n^2):
1- 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

- Anonymous November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)) .

- huha November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why not convert BST to doubly linked list and do it the same way , this will save space as well

- Geek December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

O(n^2 Logn)

1. Convert the BST to a sorted array using inorder traversal
2. run 2 for loops, i & j and for each i,j find a number using Binary search such that number
= k - (input[i]+input[j]).

- pratikrd November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]+"");
			}
		}	
	}
}

- Naveen November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- pratikrd November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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] + "");
  }
}

- Naveen November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But this code wont find all the combinations

- Andi November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- rags November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- ashu1.220791 November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
	}
}

- praveen November 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@praveen Your code doesn't consider case in which one of the node is head and second is in left sub-tree and third is in right sub-tree.

- nikkiani1991 November 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- amit December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Store the output of the inorder traversal it will give sorted array. Now apply algorithm of three sum problem by slight modification where arr[i]+arr[j]+arr[k]=K.

- khunima April 05, 2014 | Flag Reply


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