## Amazon Interview Question for Java Developers

• 1
of 1 vote

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

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

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?

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

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.

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

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

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

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

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

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

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

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

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

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){
}else if (i > k){
result =treeSumUtil(r1.left,r2,k);
}else
result =treeSumUtil(r1,r2.right,k);
return result;
}
}``````

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

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.

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

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);``````

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?

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

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.

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;``````

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

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

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;
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 = root.val > theOther.val ? theOther : root;
res = res == 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.

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.

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

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

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

}``````

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.

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

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);
}``````

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.

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.

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);
}``````

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.

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.

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