## Amazon Interview Question

Country: United States

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

The problem itself is tricky, it says constant space but doesn't require it to be storage efficient.

The solution is:

int maxValue = tree.getMaxValue() // by keeping visiting right most branch

int[] array = new int[maxValue] // not storage efficient
for each node value in the tree, set array[value] = 1 // O(n)

for each node value in the tree, check whether array[K-value] exists. If exists, print the pair. // O(n)

Thus the solution is O(n) and the storage is a constant value depending the largest node value.

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

well ...........
excellent thought though.... can put the interviewer in a tough spot :)

There is one way to do this ( but there's a catch , only problem is , we cannot maintain the structure of the tree)

Step 1. - > Convert the Binary tree to a doubly linked list O(n) time
# Search in google for this solution
Step 2 . -> Now you can to your array thing here, but with pointers , one from left
and one from right

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

Hi CrackyCode :-)

the linked list is not constant in storage perspective ~ but the solution you proposed is O(n) in time.

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

I think crackCoder means to use left, right pointer of a tree node as pre, next pointer in a list node. Then we just need to do simple 2 sum.

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

If I am not mistaken, I think we could use a HashSet here to save the space wasted in indices that are array[i] != 1

Another observation. Please correct me if I'm understanding something wrong here -

If duplicates are NOT allowed in the BST
-------------------------------------------------------
If size of array is S, then S = n + c where n is the number of nodes and c is some constant integer such that c>=0.

Space complexity is O(S) = O(n+c) = O(n).

If duplicates are allowed in the BST
------------------------------------------------
If size of array is S, then S = n + c where n is the number of nodes and c is some constant integer such that c>(-1*n). Worst case space complexity happens when c>=0 in which case it is O(n)

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

This is really a nice solution but not a constant space one. maxValue can be different in different tree and this will mean different space requirements and not a constant space requirement. For a solutions to be constant space one, it should always use the same space irrespective of number of tree elements, its minimum and maximum elements.

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

1) convert the given BST into an sorted array A with in-order traverse,
2) two index (i=0, j=arraysize-1)
3) loop over:
3.a) if A[i]+A[j]>k => j--;
3.b) if A[i]+A[j]<k => i++;
3.c) output (i,j)

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

well, it's not constant space.

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

ok, if we can modify the input BST, we can first convert it into a double linked list, and do the same. the time complexity will be O(n), and space O(1)

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

I would say this cannot be done in O(n). It is necessary that we examine each element and look for existence of its pairs that sums to k. It would take O(n) just to go through each element. In my view, the best possible is O(nlog n)

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

It can be done in O(n) provided space..

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

and how is that done?

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

1. Hash each element of BST
2. now traverse BST and lookup hash for element with value (sum-node_val)

this requires constant space + can be done in O(n)

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

delete not good.

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

Why do we need a sorted array in this case?

``````left = findSmallestValue(); // O(logN)
right = findLargestValue(); // O(logN)
while (left <= right) {
if (left + right == k) output(left,right); // if there are duplicates, need to handle all pairs
else if (left + right < k) left = successor(left);
else right = predecessor(right);
}``````

This algorithm practically runs in-order traversal twice. O(n)

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

Getting predecessor isn't constant ( no parent pointer )
this comes to O(logn)^2 ?

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

In-order traversal of BST sorts data in ascending order
as A B C D E F G if you
1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.

and you can sort it in deciding order
G F E D C B A if you
1. Traverse the right subtree.
2. Visit the root.
3. Traverse the left subtree.

it can be done without recursion
so you can imagine we've got a sorted array A B C D E F G and we have pointers/reference at head and tail, and we can use them to traverse across 'virtual' array to find pair of nodes whose sum is equal to a given number k

time complexity is O(n) and space complexity is O(1)

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

Improving on zouzhile's idea,
1 we can create an array A of size k
2. Initialise the array with null
2. Do an inorder traversal of the tree (O(n))till a node with value k or greater than k arrives. And setting the array A[node.value] = 1 (or a pointer to the node using perhaps a hashmap)
3. Traverse the array and for each A[i]!=null, find if A[k-i] is null. If not null then, then we have a pair and from this pair of indices of A, we can get the nodes.
Runtime is O(n) and space is constant with respect to k.

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.