## Amazon Interview Question for Interns

Country: India
Interview Type: Phone Interview

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

1. apply reverse inorder
2. keep track of sum of nodes while traversing
3. change the value of roots while traversing

``````public void sumofallgreater(Node root)
{
if(root==null)
return;
sumofallgreater(root.right);
sum+=root.info;
root.info=sum-root.info;

sumofallgreater(root.left);

}``````

-->sum is a static variable

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

Can you please explain me about your algo. I am bit confused. Just tell me with small example.

Thank you.

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

1.see I m traversing right subtree first so we will get traversal in decreasing order.
2.And counter sum will held the sum of traverse elements
like if 5,3,2 is traversed thn sum will have 10.
3. for the current node we will change its value with the sum.
4. and current elements value before updation we will add in sum also bcz we need it further.

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

let me know if u have any problem

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

I don't understand why you have root.info = sum - root.info please advice. Thanks

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

@Nuruddin-
See I m thinking of this problem as the largest node will have zero in updated tree since there is no larger node thn it. SO I m updating it with zero thats why I performed subtraction.

If u want that largest node will contain the vlue of its own in updated tree is well then no need of subtraction.
Let me know if u have any more issues

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

Suppose the tree has only one element,given the above logic,
a

sum+=root.info; ==> sum=a
root.info=sum-root.info;===> root.info=a-a => root.info=0;

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

``````replaceGreater(n, sum)
{
if (n == NIL) return;

replaceGreater(n->right, sum);

x = n->value;
n->value = sum;
sum = sum + x;

replaceGreater(n->left, sum);
}

replaceGreater(root, 0);``````

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

in C

``````int sum = 0;
int old_sum;

void inRevOrder(struct Node* node)
{
if(!node) return;
if(node->right) inRevOrder(node->right);
old_sum = sum;
sum += node->val;
node->val = old_sum;
if(node->left) inRevOrder(node->left);
}``````

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

1) Each node will receive some values from left subtree and from right subtree.
2) That node will change its value with : selfvalue + sum of value received from right subtree
3) That node will return new pair of values to its parent: < sum of left subtree value, node's new value >
I can explain algo with an example:

``````left assume following BST:
41
40			50
39			45		55

node 40 will return <39, 40>
node 50 will return <45, (50+55)> -- <45, 105>
node 41 will receive left pair<39, 40> and right pair <45, 105>
node 41 will change -- 41 + right pair --> 41 + 45 + 105 -->191
node 41 will return <sumofleftpairvalue + newsumeofcurrentnode> -- <(39+40), 192> -- <79,192>

this will continue``````

sudo code:

``````pair<int, int> updateBst (tree *root)
{
if (!root)	return <0,0>
if (leafnode) return <0, root->key>

leftpair = updateBst (root->left)
rightpair = updateBst (root->right)

root->key += rightpair.first + rightpair.second;
return < (leftpair.first+leftpair.second) , root->key>
}``````

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

Reverse Inorder traversal which lists the nodes in descending followed by sum at each node works perfectly well

``````int sum=0;
void descending(myBSTNode focusNode) {
if (focusNode != null) {
descending(focusNode.rightChild);
sum+=focusNode.key;
focusNode.key=sum-focusNode.key;
System.out.println(focusNode.name + " has a key   " + focusNode.key);
descending(focusNode.leftChild);
}

}``````

Output of Reverse Inorder traversal:

Salesman has a key 85
Sales manager has a key 75
Boss has a key 50
Secretary has a key 30
VP has a key 25
Office manager has a key 15

Final Output

Salesman has a key 0
Sales manager has a key 85
Boss has a key 160
Secretary has a key 210
VP has a key 240
Office manager has a key 265

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

Hi Guys, what does 'greater nodes' really means? Nodes which values are great than what it is originally? If so, in a sorted tree situation, only the right sub tree?

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

what do you mean by greater nodes ? Please give detail example of it.

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

``````public class ReplaceBST {

private static List<Integer> list = new LinkedList<Integer>();
private static List<Node>  nodeList = new LinkedList<Node>();

public static void replace(Node root) {
if(root == null) return;

replace(root.left);
replace(root.right);
}

public static void inOrderTreeWalk(Node root) {
if(root == null) return;

inOrderTreeWalk(root.left);
System.out.println(root.value);
inOrderTreeWalk(root.right);
}

public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);

node4.left = node2;
node2.left = node1;
node1.right = node3;
node4.right = node6;
node6.left = node5;
node6.right = node7;

replace(node4);
int cumul = 0;

for(int i = list.size() - 1;i >= 0;i--) {
nodeList.get(i).value = cumul;
cumul += list.get(i);
}

inOrderTreeWalk(node4);

}
}``````

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

``````replace_with_greater_node(self, sum):
if self == None:
return
replace_with_greater_node(self.right, sum)
temp = self.value
sum = sum + temp
self.value = sum

replace_with_greater_node(self.left,sum)``````

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.