Amazon Interview Question for SDE-2s


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

- elkon March 12, 2017 | Flag Reply
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);
	}

- AmitG March 15, 2017 | Flag Reply
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.

- Andro March 21, 2017 | Flag Reply
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;
}

public Node updateSum(Node n){
	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);
}

- divm01986 March 12, 2017 | Flag Reply
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.

- montu March 13, 2017 | Flag Reply
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;
	}
}

- PPD March 13, 2017 | Flag Reply
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

- montu March 20, 2017 | Flag Reply
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;

}

- trevorvanloon April 07, 2017 | Flag Reply
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;
}

- ajawaid191 April 14, 2017 | Flag Reply
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?

- Max Steel March 17, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More