Amazon Interview Question for Software Engineer / Developers


Team: AWSP
Country: United States
Interview Type: Phone Interview




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

This is what I came up with the help of Interviewer

private Node SumTree(Node root)
        {
            if (root == null) return null;

            if (root.left == null && root.right == null)
                return new Node(0);

            Node left = SumTree(root.left);
            Node right = SumTree(root.right);

            int sum = left.key + right.key + root.left.key + root.right.key;

            Node newroot = new Node(sum);
            newroot.left = left;
            newroot.right = right;

            return newroot;

        }

- sk February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have also end up with same solution using Scala

case class Tree[+T](val value:T, val left:Option[Tree[T]], val right:Option[Tree[T]])

  def zeroIfNone(t:Option[Tree[Int]]):Int = t match {
    case None=>0
    case Some(t)=>t.value
  }
  
  def sum(t:Option[Tree[Int]]):Option[Tree[Int]] = t match {
    case None => None
    case Some(t) => {
        val newValue = zeroIfNone(t.left) + zeroIfNone(t.right)
        Some(Tree(newValue, sum(t.left), sum(t.right)))
    }
  }

- IvanoBulo February 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have also end up with same solution using Scala

case class Tree[+T](val value:T, val left:Option[Tree[T]], val right:Option[Tree[T]])

  def zeroIfNone(t:Option[Tree[Int]]):Int = t match {
    case None=>0
    case Some(t)=>t.value
  }
  
  def sum(t:Option[Tree[Int]]):Option[Tree[Int]] = t match {
    case None => None
    case Some(t) => {
        val newValue = zeroIfNone(t.left) + zeroIfNone(t.right)
        Some(Tree(newValue, sum(t.left), sum(t.right)))
    }
  }

- IvanoBulo February 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Scala is so confusing, why would anyone ever want to use this language??

- amritaansh123 February 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wrong code. You will get seg fault.
Here is a working code:
Node createReqTree(Node root){
if(root == NULL)
return NULL;

Node l=createReqTree(root->left);
Node r=createReqTree(root->right);

int total= ((l==NULL)?0:l->value) + ((r==NULL)?0:r->value);
total+= ((root->left == NULL) ? 0:root->left->value) + ((root->right == NULL)?0:root->right->value);
Node n = createNode(total);
n->left=l;
n->right=r;

return n;

}

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

I am not sure, if below solution is appropriate or not? Please correct me if anything wrong.

Steps:
1. First build BST with Preorder values.
2. Then do a Postorder traversal and update root as (root + (left + right)) and mark left and right as 0.
3. follow the step 2 till end of Post order.

- Sidhartha February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am not sure, if below solution is appropriate or not? Please correct me if anything wrong.

Steps:
1. First build BST with Preorder values.
2. Then do a Postorder traversal and update root as (root + (left + right)) and mark left and right as 0.
3. follow the step 2 till end of Post order.

- Sidhartha February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int sumDescendant(struct node* Node)
{
	if(Node == NULL)
		return 0;

	int cache = Node->data;
	Node->data = sumDescendant(Node->left) + sumDescendant(Node->right);
	return (cache + Node->data);
}

Step1: Return 0 when a Node is NULL (this is useful in assigning 0 to leaf nodes)
Step 2: Cache Node's current data since we would need to use this cached data as well later.
Step 3: Calculate the new value of the node's data by summing up its childern values
Step 4: Return cached + node's current data to the parent

- Jester February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seems like the focus should be on constructing the new tree and not on reconstructing the original tree from just the preorder traversal. It's just not possible to arrive at a unique tree with just that.
Node[1] would hold the new root for a non-null tree.

public Node[] sum(Node root) {
		if(root == null) {
			return null;
		}
		Node newRoot = new Node(0);
		Node sum = new Node(0);
		if(root.getLeft() != null || root.getRight() != null) {
			Node[] leftSum = sum(root.getLeft());
			Node[] rightSum = sum(root.getRight());
			sum = add(leftSum, rightSum);
			newRoot.setData(sum.getData());
			if(leftSum != null) {
				newRoot.setLeft(leftSum[1]);
			}
			if(rightSum != null) {
				newRoot.setRight(rightSum[1]);
			}
		}
		return new Node[] { root, newRoot };
	}

	private Node add(Node[] left, Node[] right) {
		int lSum = left == null ? 0 : left[0].getData();
		int rSum = right == null ? 0 : right[0].getData();
		return new Node(lSum + rSum);
	}

- smffap February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can more form than one binary trees for a given preorder traversal. That means there could be more than one solution preorder sequences. For eg, for the given preorder traversal if you form a binary tree with all left pointers NULL, then the solution sequence is (320, 270, 240, 230, 190, 130, 0) not (270, 50, 0, 0, 130, 0, 0) as mentioned in the question . This is also is the easiest solution sequence that can be formed - cumulative sum.

Can the original poster confirm that he is not missing something?

- y2km11 February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

curious too

- wow February 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1st.. if its a complete tree then there is only on possibility....

2nd we need sum of their descendents (sub tree) which not include the value of node, if it is like so, we are either gonna increase the size of resultant tree by one level or leaf never gonna 0,

please comment.

- Sanjay Kumar February 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Create a copy of original tree.
2. Do a postOrder Traversal with tree->data = tree->Left->data + tree->right->data .
3. Do a postOrder Traversal again passing the old and new tree as arguments and
now newtree->data = newtree->data - oldtree->data;

- Anonymous February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Create a copy of original tree.
2. Do a postOrder Traversal with tree->data = tree->Left->data + tree->right->data .
3. Do a postOrder Traversal again passing the old and new tree as arguments and
now newtree->data = newtree->data - oldtree->data;

- Anonymous February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here in the same traversal new node is created using new left and right subtrees using post order recursive alg

Node * postOrder(Node* oldNodeCurrent)
{
    int leftVal = 0, rightVal = 0;
    If (oldNodeCurrent == NULL)
        return NULL;
    Node *leftN = postOrder(oldNodeCurrent->left);
    Node *rightN = postOrder(oldNodeCurrent->right);
    
   if(leftN != NULL)
       leftVal = leftN->val;
    if(rightN != NULL)
       rightVal = right->val;
    Node* current = new Node(leftVal + rightVal,leftN,rightN);
   
    return current;
}

- RN February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

need to add the old left node value and the old right node value to the return node value.

- pinkiee March 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here in the same traversal new node is created using new left and right subtrees using post order recursive alg

Node * postOrder(Node* oldNodeCurrent)
{
    int leftVal = 0, rightVal = 0;
    If (oldNodeCurrent == NULL)
        return NULL;
    Node *leftN = postOrder(oldNodeCurrent->left);
    Node *rightN = postOrder(oldNodeCurrent->right);
    
   if(leftN != NULL)
       leftVal = leftN->val;
    if(rightN != NULL)
       rightVal = right->val;
    Node* current = new Node(leftVal + rightVal,leftN,rightN);
   
    return current;
}

- RN February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

simple function can do the work.. transverse through the original tree ..

node * func1(node *root) {
node* root1=new node;
root1->value=0;
root1->value=sum(root);
if (root->left!=NULL)
root1->left=finc1(root->left);
if (root->right!=NULL)
root1->right=finc1(root->right);
return(root1);
}

- Sanjay Kumar February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the above solution is O(nlogn)
below is the solution in the O(N)

node * func1(node *root) {
node* root1=new node;
root1->value=0;
if (root->left!=NULL)
root1->left=finc1(root->left);
if (root->right!=NULL)
root1->right=finc1(root->right);
if(root->left==NULL && root->right==NULL)
root1->value=0;
else if(root->left!=NULL && root->right==NULL)
root1->value=root1->left+root->left;
else if(root->left==NULL && root->right!=NULL)
root1->value=root1->right+root->right;
else
root1->value=root1->right+root->right+root1->left+root->left;

return(root1);
}

- Sanjay Kumar February 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

why O(nlogn) ?Could you explain that? i think the two are both O(n)...

- Anonymous February 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i see ... damn ...i didn't see that sum(root)

- Anonymous February 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is what I came up with the help of Interviewer

private Node SumTree(Node root)
        {
            if (root == null) return null;

            if (root.left == null && root.right == null)
                return new Node(0);

            Node left = SumTree(root.left);
            Node right = SumTree(root.right);

            int sum = left.key + right.key + root.left.key + root.right.key;

            Node newroot = new Node(sum);
            newroot.left = left;
            newroot.right = right;

            return newroot;

        }

- sk February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution

#include <stdlib.h>

int create_sum_tree(TreeNode* node, TreeNode** sumTreeNode) {
    if (node == NULL)
        return 0;
    *sumTreeNode = calloc(1, sizeof(TreeNode));
    (*sumTreeNode)->data = create_sum_tree(node->left, &((*sumTreeNode)->left)) +
                                         create_sum_tree(node->right, &((*sumTreeNode)->right));

    return node->data + (*sumTreeNode)->data;
}

- sanil February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution

#include <stdlib.h>

int create_sum_tree(TreeNode* node, TreeNode** sumTreeNode) {
    if (node == NULL)
        return 0;
    *sumTreeNode = calloc(1, sizeof(TreeNode));
    (*sumTreeNode)->data = create_sum_tree(node->left, &((*sumTreeNode)->left)) +
                                         create_sum_tree(node->right, &((*sumTreeNode)->right));

    return node->data + (*sumTreeNode)->data;
}

- sanil February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is the complexity ?

- sorabh February 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming a trivial three element list-based representation of a BST tree, here is a complete example.

scheme <<END
(define (sumtree tree)
	(define (process tree)
		(if (list? tree)
			(let ((left (process (cadr tree))) (right (process (caddr tree))))
				(let ((sum (+ (car left) (car right))))
					(list 
						(+ (car tree) sum)
						(list sum (cadr left) (cadr right)))))
			(list tree 0)))
	(cadr (process tree)))
	
(sumtree '(50 (30 40 10) (60 55 75)))
END

- vQ February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming a trivial three element list-based representation of a BST tree, here is a complete example.

scheme <<END
(define (sumtree tree)
	(define (process tree)
		(if (list? tree)
			(let ((left (process (cadr tree))) (right (process (caddr tree))))
				(let ((sum (+ (car left) (car right))))
					(list 
						(+ (car tree) sum)
						(list sum (cadr left) (cadr right)))))
			(list tree 0)))
	(cadr (process tree)))
	
(sumtree '(50 (30 40 10) (60 55 75)))
END

- vQ February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int sumUpTree(BinaryTree root)
	{
		if(root == null)
		{
			return 0;
		}
		else
		{
			int left = sumUpTree(root.left);
			int right = sumUpTree(root.right);
			int cacheData = root.data;
			root.data = left + right;
			return cacheData+left + right;
		}
	}

- hello world February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int subtree_sum(NODEPTR root,int sum){
    if(root == NULL)
        return 0;
    sum = 0;
    int temp;
    sum += subtree_sum(root->left,sum);
    sum += subtree_sum(root->right,sum);
    temp = root->data;
    root->data = sum;
    return(temp + sum);
    }

- vagrawal13 July 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* trees_programs::newtree(node* n)
{ node*n1=0;
node*n2=0;
if(n==0)
return NULL;

n1=newtree(n->left);
n2=newtree(n->rite);
node* nd=new node(0);
if(n==root)
{
root2=nd; // root of new tree
}
nd->left=n1;
nd->rite=n2;
nd->data=0;
if(n->left==0&&n->rite==0)
{
nd->data=0;
nd->left=0;
nd->rite=0;
}
if(n->left!=0)
nd->data+=n->left->data;
if(n->rite!=0)
nd->data+=n->rite->data;
if(n1!=0)
nd->data+=n1->data;
if(n2!=0)
nd->data+=n2->data;
return nd;







}

- aaman.singh85 October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

AWESOME....it works

- nn April 24, 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