Amazon Interview Question
Java DevelopersCountry: India
Interview Type: In-Person
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?
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.
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)
I don't think your inorder traversals are correct. Example
if (p->right) then we want the leftmost child of p->right
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).
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;
}
}
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.
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);
Q: why is there no space consideration that comes from recusing N times to get to the pair?
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;
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.
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.
#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;
}
}
}
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.
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.
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.
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);
}
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.
Same as searching the sum of 2 numbers in an array. Instead of having 2 pointers: start and end, we have 2 tree iterators.
- Miguel Oliveira January 26, 2015