Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

I don't not fully understand the question precisely. What about leaf nodes?
Are you saying only the leaf nodes have values that can vary, and the rest of the tree just ripple sums these up to root?

Anyways, for the restriction, why can't you define your own += using a loop on ++ ?

- S O U N D W A V E March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 4 votes

You can keep the leaf node's value as it is. for all non-leaf nodes, make the value as sum of its left and right subtree with the condition that only increment can be preformed on each node to change its value.

- pavi.8081 March 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 votes

If you knew all this, why would you not friggen save people's time and post it in the original question?

- S O U N D W A V E March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@BigKdotAtTdot : this was damn clear. If not you could have made valid assumptions and given the solution. Don't know what was not clear that made you so confused.

- pavi.8081 March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If it was clear why did you keep changing your original post as people asked you questions and kept posting code that was misled by your ambiguity?

Which Amazon location asked you this? Did you ask them clarifying questions? What did they say exactly? Why aren't these in your post?

- S O U N D W A V E March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@BigKdotAtTdot: Thanks for clearly mentioning. Now I accept there was little confusion in 1st version of question. But confusion was only one. It was about the leaf node (like should it maintain its value or pick 0 from its null children)

Apart from that I think few people also got confused about the sum, which I proactively clarified in question.
Misleading people was not the intention. Apologies! for that if I did that to you.

Now coming to your questions:
1. Which Amazon location asked you this?: India
2. Did you ask them clarifying questions?: Yes I did about leaf nodes but interviewer asked me to make valid assumptions. Hence I made assumptions after taking interviewer's approval.
3. Why aren't these in your post?: They were not because I thought I asked dumb question :(

- pavi.8081 March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Part 1:

int update(Node* node) {
  if (!node)
    return 0;

  if (!node->left && !node->right)
    return node->value;

  node->value = update(node->left);
  node->value += update(node->right);
  return node->value * 2;
}

Part 2:

int update(Node* node, int expect) {
  if (!node)
    return 0;

  if (!node->left && !node->right) {
    node->value = max(node->value, expect);
    return node->value;
  }

  expect = (expect + 1) / 2;
  expect = max(expect, node->value);

  // if left or right is available, choose the corresponding node
  // if both are available, leave expect to the right node
  int left = 0, right = 0;
  if (node->left && node->right) {
    left = update(node->left, node->left->value * 2);
    right = update(node->right, expect - left);
  } else if (node->left) {
    left = update(node->left, expect);
  } else {
    right = update(node->right, expect);
  }

  node->value = left + right;
  return node->value * 2;
}

void update(Node* root) {
  int expect = root->value * 2;
  update(root, expect);
}

- Linfuzki March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is your Part 1: update function is doing? Why are you returning node->value*2?
In your Part 2: update function, why are you doing expect = (expect + 1) / 2?
How does it work? can you please elaborate.

- pavi.8081 March 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Pavi,

Part 1 is for the original question and part 2 is for the follow up question.

For your questions:
- update(node) updates the value of node and its subtree, and returns the sum of the node & its subtree
- as mentioned above, the sum of the node & its subtree is returned; since node already contains the sum of its subtree, the result value would be node->value * 2
- say, if a parent node expects a value of 20, then its child node need only half of it, which is 10, because the subtree of the child node can contribute the other half. On the other hand, if the expected value is odd, e.g. 21, then 21 / 2 is 10, which is not enough to meet 21; the expected value is increased by 1 to deal with that.

Please let me know if it doesn't make sense

- Linfuzki March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The follow question also looks very simple. I don't really see the significance of "expect" variable here. It could have been done without it like this -

public int update(Node node){
	if(node == null){
		return 0;
	}
	int left = 0;
	int right = 0;

	left = update(node.left);
	right = update(node.right)

	node.data = Math.max(node.data, left + right);

	return node.data + left + right;
}

Do you see any issues with this program?

- Prashant April 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please ignore the above program, its obviously incorrect. I didn't read the problem statement correctly.

- Prashant April 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I attached a simple implementation in Java. The idea I used is this:
1- Flood an increment command from root (this is recursive).
2- When a node receives the command, it calls INC (add + 1), calls it for parent and calls it for its children. However, there is a flag to make sure children are called only once.
To get the number of nodes in the tree, this method must be called from the root of the tree.

root.floodInc();
   System.out.println(root.value);

Node:

public class Node {	
	Node left, right, parent;
	int value;
	int key;
	boolean asked_children = false;
	public void inc() {
	    this.value += 1;
	}
	public void floodInc() {
	    this.inc();
	    if (parent != null) {
		parent.floodInc();
	    }
	    if (!asked_children) {
		asked_children = true;
		if (left != null) {
		    left.floodInc();
		}
		if (right != null) {
		    right.floodInc();
		}
	    }
	}
	public Node(int key, int value, Node parent) { 
	    this.parent = parent;
	    this.value = value;
	    this.key = key;
	}
    }

- Ehsan March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Ehsan,
Assuming parent pointer as part of node structure may not be right. Moreover its not mentioned in question to assume it.

Secondly if I assume parent pointer and follow your solution then , as I traced it, It gave wrong answer :(
two suggestions:
1. If you can give a solution without parent pointer then better.
2. If you need parent pointer, then I request you to review and trace your solution once and let me know. Thanks

- pavi.8081 March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi. Thanks for feedback. Having the parent in a node is reasonable otherwise the tree cannot support many operations including balancing and delete. But this is not important here.

Also, please provide me with a test case that the code failed. It works for me here :).

I will first explain the code posted above, then attach a program which does the counting for tree nodes with no parents.

I should say that both algorithms run in O(n^2). I have a feeling faster than n^2 might not exist.

I give you an example. "A" is the root
(A, 0)
(C, 0) (F, 0)
(B, 0) (D, 0) (E, 0) (G, 0)
1) A: by calling A.floodInc(), "A" increases its value and sends the message to C and F. "A" marks ask_children = true" so that it will not ask them again.
(A, 1)
(C, 0) (F, 0)
(B, 0) (D, 0) (E, 0) (G, 0)
2) C, F do the same. But since they have a parent "A", they will also send a floodInc to "A". Then, A will receive the "Inc" command twice. Note that this time, "A" will not ask for Inc from its children due to the ask_children flag.
(A, 3)
(C, 1) (F, 1)
(B, 1) (D, 1) (E, 1) (G, 1)
3) B, D, E, G will do the same. Let's trace B's message
First, it is received at C, so C increases its value
(A, 3)
(C, 2) (F, 1)
(B, 1) (D, 1) (E, 1) (G, 1)
Then C will resend the message to its parent.
(A, 4)
(C, 2) (F, 1)
(B, 1) (D, 1) (E, 1) (G, 1)
The same process happens for D, E, G, ..
(A, 7)
(C, 3) (F, 3)
(B, 1) (D, 1) (E, 1) (G, 1)

Code for no parent case:

public class BSTSimple {
    private static BSTSimple dummy;
    public static void main(String[] args) {
        dummy = new BSTSimple();        
        int[] arr = {8, 4, 12, 2 , 1, 14, 11, 18};
        Node root = null;
        for (int i = 0; i < arr.length; i++) {
            Node n = insert(root, arr[i]);
            if (root == null) {
                root = n;
            }
        }
        while (incValue(root));
        System.out.println(root.value);
        System.out.println(root.left.value);
    }
    public class Node {
        public Node left, right;
        public int key;
        public int value;
        public boolean counted = false;
        public Node(int key, int value) {
            this.key = key; this.value = value; 
        }

    }
    public static boolean incValue(Node n) {        
       if (n.left == null && n.right == null) {
           if (n.counted) {
               return false;
           }
           n.value += 1;
           n.counted = true;
           return true;
       }       
       if (n.left != null) {
           while(incValue(n.left)) {
               n.value++;
               return true;
           }
       }
       if (n.right != null) {
           while(incValue(n.right)) {
               n.value++;
               return true;
           }
       }
       if (n.left != null || n.right != null) {
           if (!n.counted) {
              n.counted = true;
              n.value++;
              return true;
           }
       }
       return false;
    }
    
    public static Node insert(Node root, int key) {
        if (root == null) {
            root = dummy.new Node(key, 0);
            return root;
        }
        else {
            Node node = root;
            while (node.key != key) {
                if (node.key > key) {
                    if (node.left == null) {
                        node.left = dummy.new Node(key, 0);                        
                    }
                    node = node.left;
                }
                else {
                    if (node.right == null) {
                        node.right = dummy.new Node(key, 0);
                    }
                    node = node.right;
                }
                
            }
            return node;
        }                
    }
}

- Ehsan March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Ehsan,
Thanks for the elaborate explanation. But as I understand it, I think you have misunderstood the question.
Question is not about counting total number of nodes in left and right sub-trees and setting that as value of the root node.
Here, Question is to set node's value as sum of node values in left and rt subtrees.
For example:
let tree be:

20
     5             6
null   3    null null

the resultant tree becomes:

9
     3             6
null   3    null null

Please refer to "Further clarifications." section in the Question.

I hope I understood it right. Please let me know if I am wrong

- pavi.8081 March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the idea is to just use increment (++) then we can first assign the maximum of the two child nodes and then increment times the minimum of the two child nodes to get to the sum. Complexity should be O(N + max-min) where N is the total number of nodes; max is the maximum value of all of the leaf nodes and min the minimum value.

public int sumNodes(Node n) {
		if (n==null) {
		  return 0;
		} else if (n.left==null && n.right == null) {  
		  return n.value; //leaf already set to its value
		} else { 		 
		  int leftValue = sumNodes(n.left);
		  int rightValue = sumNodes(n.right) ;
	  	  n.value = Math.max(leftValue, rightValue);

		  //increment here:
		  for(int i = 0; i < Math.min(leftValue,rightValue); i++, n.value++); 

		  return n.value;
		}	
	}

- Guy March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

HI Guy: As per my understanding when you are writing this statement:

n.value = Math.max(leftValue, rightValue);

I can think of an example say if node's value is 20 and its left and right child node's values are 3 and 4 respectively. So, when you execute above statement, its actually reducing the value of the node and not increasing it.
If its so then its against the rule mentioned in question. your take?

- pavi.8081 March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Pavi: my understanding is that only leaf nodes have values. All other nodes get their value by adding up the values of their two children. You can only use the increment (++) or the assignment statement to change values.

Yes, it is difficult without interacting with the source of the requirements. Whatever the requirements, it's a fun little exercise.

- Guy March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

As per my understanding question is to replace the node with the sum of there left and right child .

above solution is good but we have to add in pace of

n.value = Math.max(leftValue, rightValue);

int temp=n.value;
n.value= leftValue+rightValu
return temp+n.value;
--------------------------------------------

- RamJane March 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can someone explain the steps in plain english ? we all can write code, its about finding best algo

- monu March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void bt_root_equal2_sum_left_right(node **root)
{
        if(*root==NULL) return;
        int sum = get_sum((*root)->left)+get_sum((*root)->right);
        if((*root)->data < sum)
        {
                (*root)->dat = sum;
        }
        bt_root_equal2_sum_left_right(&(*root)->left);
        bt_root_equal2_sum_left_right(&(*root)->right);
}

int get_sum(node *root)
{
        if(root==NULL) return 0;
        return root->data+get_sum(root->left)+get_sum(root->right);
}

- amit: try this.. March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

"You can make assumption that leaf nodes retain their original value and does not change. "
I understand this statement as following: leaf nodes don't satisfy the sum of subtrees condition, because otherwise all nodes would be 0, but I am allowed to increment their value just like other nodes.

I would first observe that once leaves are set up, the tree is fixed. But depending on your choice of leaves it might be impossible to construct the tree, based on the constraint.

Does the number of changes I make or the sum of increments I make hurt my score? If not find the maximum value, make all leaves max+1 and then ripple the sums up to the root.

If yes I am not sure how to get the optimal solution but for each node check the sum of the nodes of its subtree. You don't need to set values for the intermediate nodes for this, simply multiply the relative depths of each leaf's value.
If sum > value: It's OK, you should increment the value.
If sum < value: You should increment one of the leaves.
Take action only when all nodes satisfy the first condition, if any of them doesn't, then increment a leaf node and check again.

In this solution I am not utilizing swaps.

- Eralp Bayraktar March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

SummationTree(Node node){
	if(node == null)
		return 0;
	
	int totalSum = SummationTree(node.left) + SummationTree(node.right);
	int nodeValue = node.value; 
	if( totalSubTreeSum > nodeValue )
		node.value = totalSubTreeSum;
	return totalSubTreeSum + nodeValue;
}

- struggler March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm: We recursively call the function for left and right subtree. This method will update the root's value if the sum of the nodes of the left subtree and the right subtree nodes is greater than the root's value. The function returns back the total sum of root, left subtree nodes and the right subtree node's value.

int toSumTree(struct node *root)
{
int leftSum,rightSum,n=root->data;
if(root->left!=NULL) leftSum=toSumTree(root->left);
if(root->right!=NULL) rightSum=toSumTree(root->right);
if(root->left!=NULL && root->right!=NULL)
{
if(n<leftSum+rightSum)
{
root->data=leftSum+rightSum;
}
return n+leftSum+rightSum;
}

else if(root->left!=NULL && root->right==NULL)
{
if(n<leftSum)
{
root->data=leftSum;
}
return n+leftSum;
}

else if(root->left==NULL && root->right!=NULL)
{
if(n< rightSum)
{
root->data=rightSum;
}
return n+rightSum;
}

return n;
}

- Isha March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive approach:

int sumOfNode(Node *node)
{
if(node == null)
{
	return 0;
}

int left=0,right=0;

left = sumOfNode(node->left);
right = sumOfNode(node->right);

sum = left + right;

if(node -> info < sum)
{
	node -> info = sum;
}
else
{
	sum = node -> info;
}

return sum;

}

- PKT March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void stepDown (Node root) {

if ( root == null ) 
return;

Node LC = root.left;
Node RC = root.right;
boolean l1 = false;
boolean l2 = false;

if ( LC != null ) {
	l1 = checkIsLeaf (LC);
	}
if ( RC != null ) {
	l2 = checkIsLeaf (RC);
	}


if ( l1 == false )
	stepDown (LC);

if ( l2 == false )
	stepDown (RC);

root.info = LC.info + RC.info;
return;

}

boolean checkIsLeaf (Node root) {

	if ( root == null )
		return false;
 
	else if ( root.left == null && root.right == null )
		return true;
	else
		return false;
}

- sivaram.hari299 March 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we have to do post order traversal
and set node value as

private int PostOrderTrav(Node node)
{
	if(node == null)
		return 0;

int LeftVal = PostOrderTrav(node.Left);
int rightVal = PostOrderTrav(node.Right);


node.Value = Math.Max(node.Value , LeftVal+rightVal)
return node.Value
}

- Mohit March 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

an elegant solution is given at geeksforgeeks.org/convert-an-arbitrary-binary-tree-to-a-tree-that-holds-children-sum-property/

- pulkit March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The recursive approach is the best one.

public void sumTree(){
	
		System.out.println(sumTreeCalc(root));
		
	}
	
	
	public int sumTreeCalc(LinkedNode n){
		
		int k=0;
		if(n.right==null && n.left==null)
			k=-1;
		else if (n.left==null)
			k=sumTreeCalc(n.right)+n.right.val;
		else if (n.right==null)
			k=sumTreeCalc(n.left)+n.left.val;
		else
			k=sumTreeCalc(n.right)+n.right.val+sumTreeCalc(n.left)+n.left.val;
		
		if(k!=-1)
		{
			n.val=k;
			return k;
		}else
			return 0;
		
	}

- saurin7 July 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public int changeTree(node root){
 		if (root==null)return;
		int left=changeTree(root.left);
		int right=changeTree(root.right);
		return root.data=left+right;

}

If node value can only be incremented then I am not sure how to set it to lower value, unless we change the tree, i mean add some constant number to each node.

- OTR March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Check your code carefullly. First of all, how can you return nothing in the base case?
Secondly, think about leaf nodes.

- S O U N D W A V E March 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You should be rather returning 2*root.data

- shivamk March 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use postorder traversal and increment sum according to below cases .

public void childrenSum(Node root)
{
	/*
	 * Post order traversal
	 */
	
	int leftSum=0,rightSum=0;
	
	/*
	 * if root is null or leaf node
	 */
	if(root==null||(root.left==null && root.right==null))
		return ;
		
	childrenSum(root.left);
	childrenSum(root.right);
	
	if(root.left!=null)
		leftSum=root.left.data;
	
	if(root.right!=null)
		rightSum=root.right.data;
	
	int diff=leftSum+rightSum-root.data;
	/*
	 * 3 cases rises if only increment allowed 
	 * 1.diff==0 , no change required
	 * 2.diff>0 ,root.data=root.data+diff
	 * 3.diff<0 , add diff to left sub tree or right sub tree 
	 * 
	 * 
	 */
	
	if(diff>0)
		root.data=root.data+diff;
	else if(diff<0)
	{
		incrementSum(root,-diff);//now diff is +
	}		
	
}

private void incrementSum(Node root, int diff) {
	// TODO Auto-generated method stub
	
	if(root.left!=null)
	{
		root.left.data=root.left.data+diff;
		incrementSum(root.left, diff);
	}
	else if(root.right!=null)
	{
		root.right.data=root.right.data+diff;
		incrementSum(root.right, diff);
	}
			
}

- braj March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think you are doing the right thing.
In case of diff < 0, you are increasing the value of node to sum of its subtrees, but in this process you are also increasing the value of nodes' of left and right subtree. Am I right?
If I am then this is not what is expected out of the solution.

- pavi.8081 March 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Pavi, you don't even know what the question is, so stop wasting people's time.

- S O U N D W A V E March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@BigKdotAtTdot : Hey stop making absurd comments and spamming this thread. What made you write this: "you don't even know what the question". can you please explain?
Moreover I have not held your ears to force you waste your time. you are free to abandon and not respond to this question.
And there is no need to be rude! instead of making vague comments you could have precisely mentioned what's confusing you.

- pavi.8081 March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Cut and paste this code into your editor to get the answer

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct tree
{
	tree *left;
	tree *right;
	int data;
}tree_t;
tree_t *makeNode(int data)
{
	tree_t *n=(tree_t *)malloc(sizeof(tree_t));
	n->left=n->right=NULL;
	n->data=data;
	return n;
}
int increment(tree_t *n)
{
	if(n==NULL)
		return 0;
	if(n->left==NULL&&n->right==NULL)
		return n->data;
	n->data=increment(n->left);
	n->data=n->data+increment(n->right);
	return n->data;
}
void printTree(tree_t *n)
{
	if(n==NULL)
		return;
	printf(" %d \n",n->data);
	printTree(n->left);
	printTree(n->right);
}
int main()
{
	tree_t *node;
	node=makeNode(20);
	node->left=makeNode(6);
	node->right=makeNode(2);
	node->left->left=makeNode(2);
	node->left->right=makeNode(3);
	printTree(node);
	increment(node);
	printf("\n");
	printTree(node);
}

- vgeek March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@vgeek: I tried your solution. But its making a node's value equal to sum of its left and right child nodes.
Whereas In the question, its required to make the node's value as sum of its left and right subtree.
Where the sum of its left and right subtree means that sum of all nodes in left subtree + sum of all nodes in right subtree

- pavi.8081 March 09, 2014 | Flag


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