Amazon Interview Question for Java Developers


Country: India
Interview Type: In-Person




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

Same as searching the sum of 2 numbers in an array. Instead of having 2 pointers: start and end, we have 2 tree iterators.

if tree_size < 2
  // no answer
  return null

start = tree.begin(); // smallest element
end = tree.rbegin(); // last element - largest
while start != end
   if start->value + end->value == target
      return start, end
   if start->value + end->value > target
      end--
   else
      start++

// no pair sums up to target
return null

- Miguel Oliveira January 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It seems each ++/ or -- operation on the iterator takes O(logn) so the total time complexity is O(log(n)*n) instead of O(n). Could you please verify that?

- alexyuisme February 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In this case, we need to look to the overall algorithm complexity and not a single ++/-- complexity. Since the problem statement does not guarantee the BST is balanced, *one* ++ or -- operation can take O(n) in the worst case.

However, the amortized time of ++/-- operations is O(1). This is because the iterators will traverse each tree edge twice: 1 - going to a child, 2 - go back to the parent. A tree has N-1 edges, thus O(2*(n-1)) is O(n) *total* time.

Hence, the algorithm takes O(n) total time.

- Miguel Oliveira February 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I implemented binary search tree iterator and reverse iterator in this pseudo-code. I still need to put a check of p->parent == null.

Logic is the same as finding two value sum in an array.

// find next node in in-order traversal from left to right
next_l(node p):
	if (p->right) {
		p = p->right;
		while (p->left) {
			p = p->left;
		}
		return p;
	}

	if (p->parent->left == p)
		return p->parent;

	do {	
		p = p->parent;
	} while (p->parent->left != p);

	return p->parent;

// find next node in in-order traversal from right to left
next_r(node q):
	if (p->left) {
		p = p->left;
		while (p->right) {
			p = p->right;
		}
		return p;
	}

	if (p->parent->right == p)
		return p->parent;

	do {	
		p = p->parent;
	} while (p->parent->right != p);

	return p->parent;


findNodes(arg k):

p = root;
q = root;

while (p->left) {
	p = p->left;
}
while (q->right) {
	q = q->right;
}

int sum = p->item + q->item;

while (p != q and sum != k) {
	if (sum > k) {
		q = next_r(q);
	}
	else {
		p = next_l(p);
	}
	sum = p->item + q->item;
}

if (p == q) return false

return (p, q)

- Victor January 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think your inorder traversals are correct. Example
if (p->right) then we want the leftmost child of p->right

- Miguel Oliveira January 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, you are right. Thanks for pointing out. Will fix it

- Victor January 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Time complexity of above algorithm is not O(n), as each inorder successor or predecessor operation has complexity of O(log n) and there can be n such operations, so complexity will be O(n log n).

- rit February 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The successor/predecessor actually take O(n) time because the tree is not guaranteed balanced. However, the amortized time over the N operations is O(1). Hence the overall O(n).

- Miguel Oliveira February 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Keep two pointers for the root and (either left or right of the root)
2. Calculate the sum of the two nodes(i).
3. If i == k return the result
Else If i > k, move the pointer1 to the left
Else i > k, move the pointer2 to the right.

public List<Node> treeSum(Node root,int k){

	if(root == null || (root.left == null && root.right == null))
		return null;
	else if(root.left != null){
		return treeSumUtil(root.left,root,k);
	}else if (root.right !=null){
		return treeSumUtil(root,root.right,k);
	}

}    
public List<Node> treeSumUtil(Node r1, Node r2, int k){
	if(r1== null || r2 == null)
		return null;
	else{
		List<Node> result;
		int i=r1.data + r1.data;
		if( i == k){
			result= new LinkedList<Node,Node>();
			result.add(r1);
			result.add(r2);
		}else if (i > k){
			result =treeSumUtil(r1.left,r2,k);
		}else
			result =treeSumUtil(r1,r2.right,k);
		return result;
	}	
}

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

It seems like this solution doesn't check when the sum is on the children nodes. For example,
7
/ \
3 10
/ \
1 4

if I am looking for the sum of 5, the solution seems not to work.

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

The solution does not enable the right pointer to point to any node on the left of root and the left pointer to point to any node on the right of root. This is enabled when we begin the left pointer from the smallest element and the right pointer from the largest element.

Hence, I think we need to add another condition wherein

if (i > k && r1.left==null){
  result = treeSumUtil(r1,r2.left,k);

Similarly,

if (i < k && r2.right==null){
  result = treeSumUtil(r1.right,r2,k);

- Prakash February 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Q: why is there no space consideration that comes from recusing N times to get to the pair?

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

You actually don't need to recurse. You can iterate over nodes in in-order traversal in O(1) space. Check the first two solutions in this page.

- Victor January 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another solution I can think of is

1. Inorder traversal
2. find two sum as you have a sorted array.
a. have two indices, one at the front, one at the end
b.

while (front < end ) {
	if (arr[front]+arr[end] == n) return arr[front];
	else if (arr[front]+arr[end] > n) end--;
	else front++; 
}
return null;

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

inorder traversal and saving the result will have space complexity of O(n)

- tihor February 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time O(n * logn) space O(logn) (recursion stack size)

private TreeNode[] res = new TreeNode[2];
public void bstTwoSum(TreeNode root, int target) {
        // assume root.val is one of the 2 numbers:
	if (root.val < target) {
		int tar = target - root.val;
		if (tar == root.val) return;  // if root.val = target/2 we won't find the other node
		TreeNode theOther = search(tar, root);
		if (theOther != null) {
			res[0] = root.val > theOther.val ? theOther : root;
			res[1] = res[0] == root ? theOther : root;
		} else {
			// root is not one of the numbers, try it's both subtrees
			bstTwoSum(root.left, target);
			bstTwoSum(root.right, target);
		}
	} else {
		// if current value not less then target value, two numbers must all be in left sub tree.
		bstTwoSum(root.left, target);
	}

Note: search(int val, TreeNode root) do binary tree search for val, in BST rooted at root, takes O(logn) time.

- John.hzs1988 January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

In worst case your solution takes O(nlogn) time not O(logn*logn). Suppose that your else

else {
			// root is not one of the numbers, try it's both subtrees
			bstTwoSum(root.left, target);
			bstTwoSum(root.right, target);
		}

happens each time. Thus you will travers all over the tree that has n nodes.

- denys.o.p January 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for pointing that out. You are right. Will modify my solution.

- John.hzs1988 January 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "stdafx.h"
#include <map>
using namespace System;
using namespace std;

struct Node
{
	Node* left;
	Node* right;
	int data;
};

Node* findSmallerRoot(Node* root, int k)
{
	Node* subroot = root;
	
	while (subroot && subroot->data > k)
	{
		
		subroot = subroot->left;
	}
	return subroot;
}


bool FindPair(std::pair<Node*, Node*>& out,Node* root, int k)
{
	if (root == NULL || (root->left == NULL && root->right == NULL))
	{
		return false;
	}
	Node* subroot = root;
	if (subroot->data > k)
	{
		subroot = findSmallerRoot(subroot, k);
		if (!subroot)
		{
			return false;
		}
	}
	Node* big = NULL;
	Node* small = NULL;
	if (subroot->data > k / 2)
	{

		big = subroot;
		small = subroot->left;
	}
	else
	{
		big = subroot->right;
		small = subroot;
	}
	bool result = false;
	while (big && small)
	{
		int sum = big->data + small->data;
		if (sum == k)
		{
			out = std::pair <Node*, Node*>(big, small);
			result = true;
			return result;
		}
		if (sum > k)
		{
			if (small->left)
			{
				small = small->left;
			}
			else if (big->left && big->left!=small)
			{
				big = big->left;
			}
			else
			{
				return false;
			}
			continue;
		}
		else
		{
			if (big->right)
			{
				big = big->right;
			}
			else if (small->right && small->right!=big)
			{
				small = small->right;
			}
			else
			{
				return false;
			}
			continue;
		}
	}
		
}

- Aditya Vemuri January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You have two solutions:
1. You are allowed to change the Tree: Convert to DLL (o(1) memory), now do SUM2 on Array.
2. You are not allowed to change, do InOrder, Reverse-InOrder, iterative, withoutStack.
At each iteration, loop out of InOrder and reverseInOrder, if condition is met, break, if not, loop back in.

- Anonymous February 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Convert bst to DLL inplace in O(n), than get the initial and final pointer in the DLL and do like finding sum in array!!!

- prateek February 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Take left most node, left, Take right most node, right
2. if ( left.data + right.data == sum) {
            return left, right; 
    else if (left.data + right.data > sum) {
            right = inOrderPredecessor (root, right);
    } else {
            left = inOrderSuccessor(root, left);
    }

- Anonymous February 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do it by inorder and reverse order traversal. Like we do in an array, we move after comparing sum of values at start and end indices with K. Similarly, we move one step in inorder traversal if value is smaller in comparison to K or we move in reverse inorder if the value is greater.

- Anonymous April 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do it by inorder and reverse order traversal. Like we do in an array, we move after comparing sum of values at start and end indices with K. Similarly, we move one step in inorder traversal if value is smaller in comparison to K or we move in reverse inorder if the value is greater.

- yeah April 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String getNodesWithSum(Integer sum) { 
		List<Integer> inOrderList = traverseInOrder();
	
		int start = 0; 
		int end = inOrderList.size() -1 ;
		
		while(end > start){ 
			System.out.println("Comparing index : " + start + " & " + end);
			if(inOrderList.get(start) + inOrderList.get(end) == sum){
					return "Two nodes with sum = " + sum
							+ " are : " + inOrderList.get(start) 
							+ " and " + inOrderList.get(end);
			}else if(inOrderList.get(start) + inOrderList.get(end) > sum){
					end--; 
			}else{
					start++;
			}
		}
		return ("No nodes with sum = " + sum);
	}

- madz February 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1. Convert tree to doubly linklist . [this is poss in in O(1) memory]
2. Keep one pointer is at begining and other at the end.
3. Now treat like array and find if there is any pair which sum to k. [if start+end is higher than k then move end to previous else if start+ end sum is lower than k then move start foward else display current pair]
4. conver doubly linklist to tree.

- Tester January 29, 2015 | 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