## Amazon Interview Question for SDE-2s

• 0

Team: Kindle
Country: India
Interview Type: Written Test

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

``````int switchWithGreater(Node *root, int sum){
if (root == NULL) return sum;
int val = root->value;
sum = switchWithGreater(root->right, sum);
root->value=sum;
sum+=val;
sum=switchWithGreater(root->left, sum);
return sum;
;``````

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

``````public void replaceNodeBySumOfGreaterChildren(TreeNode root) {
// Do PreOrder traversal and invoke tree-sum for each node.
// Order is import so that updated value of a node, does not affect values of other nodes.
// So we can use only In order or PreOrder, but not PostOrder
if (root == null)
return;

root.data = getTreeSum(root.rChild);
replaceNodeBySumOfGreaterChildren(root.lChild);
replaceNodeBySumOfGreaterChildren(root.rChild);

}

public int getTreeSum(TreeNode root) {
if (root == null)
return 0;
return root.data + getTreeSum(root.lChild) + getTreeSum(root.rChild);
}``````

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

Am I missing something in question?
As per my understanding a BST is given and a particular node (whose value is k, say) is given. Now firstly we have to find sum of all nodes whose value is greater than k. Once we have the sum, now each node value of BST should be replaced with 'root->data+sum'.
If that is the problem, then none of the above solutions listed above are helpful?

I must be missing something grave.

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

``````public class Data{
int sumSoFar;

public Data(int s){
sumSoFar = s;
}
}

class Node{
int value;
Node left;
Node right;
}

updateHelp(n,new Data(0));
}

private void updateHelp(Node n, Data d){
if(n == null){
return;
}
updateHelp(n.right,d);
n.val += d.sumSoFar;
d.sumSoFar = val;
updateHelp(n.left, d);
}``````

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

Is the resultant tree also a binary search tree? As per the statement in question I assume it wont be BST. Could you please clarify bit more on this.

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

Visit each node and replace its value with the sum of node values to the right of it.

``````public class Solution {

public void replaceInPlaceWithValuesGreaterThanSelf(TreeNode root){
if(root == null)
return;
replaceWithSumOfNodesGreaterThanitself(root.left);
replaceWithSumOfNodesGreaterThanitself(root);
replaceWithSumOfNodesGreaterThanitself(root.right);

}

private TreeNode replaceWithSumOfNodesGreaterThanitself(TreeNode root){

if(root.right==null)
return root;

root.data=sumOfChilds(root.right);

return root;
}

private int sumOfChilds(TreeNode root){

if(root == null)
return 0;
return root.data+sumOfChilds(root.left)+sumOfChilds(root.right);

}

}

class TreeNode{
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data){
this.data = data;
this.left = null;
this.right =null;
}
}``````

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

``````class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val

def replace_with_greater(root, sum_val):
if not root:
return sum_val
val = root.val
sum_val = replace_with_greater(root.right, sum_val)
root.val = max(root.val, sum_val)
sum_val += val
sum_val = replace_with_greater(root.left, sum_val)
return sum_val``````

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

Here's a recursive solution. The idea is that for each Node n, we can set that Nodes value as the sum of nodes larger than it that come before it in a preorder traversal plus the sum of the right subtree of that node, plus its value. Hence we can have our function's return value yield subtree sizes, and use a parameter sum_above to pass in the sum we've seen so far larger than the current value. Thus we can compute the solution recursively in linear time and constant space:

``````int replaceNodes(TreeNode*& root, int sum_above) {
if (root == 0) {
return 0;
}
int sum_right = replaceNodes(root->right, sum_above);
int sum_left = replaceNodes(root->left, sum_right + sum_above + root->data);
int temp = root->data;
root->data = sum_right + sum_above + temp;
return sum_right + sum_left + temp;``````

}

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

Start from the right most node, that will remain as is, since it is the largest node. Then as you move back up, add the sum from the right side to the value, and send the sum to the left (since all the values on the left will be less than all on right).

``````void updateWithSum(Node root) {
updateWithSum(root, 0);
}

int updateWithSum(Node root, int sumSoFar) {
if (root == null) {
return sumSoFar;
}

root.value += updateWithSum(root.right, sumSoFar);
int sumFromLeft = updateWithSum(root.left, root.Value);

return sumFromLeft;
}``````

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

Its a simple solution.
Do reverse inorder iteration and keep a track of sum. For every node add the value of the sum so far.

``````public void reverseInOrder(TreeNode root, int sum) {
if (root == null) {
return;
}
reverseInOrder(root.right, sum);
sum += root.val;
root.val = sum;
reverseInOrder(root.left, sum);
}``````

Do they ask such easy questions for SDE-2?

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.