Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

//Use two reference pointers to store the maximum sum and the node that exposes the maximum sum in max and maxNode respectively
int maxSum(struct node *root, struct node **maxNode, int *max)
{
if (!root) return 0;
// If the node is leaf node, compare its value and return the value of that node
if(!root->left && !root->right)
{       
      if (node->val > max)
              { *max = root->value; max = &root; }
      return root->val;
}
// Calculate the sum of the current node
int cmax = root->value + max(root->left, maxNode, max) + max(root->right, maxNode, max);
if (cmax > max)
              { *max = root->value; max = &root; } //Update the reference pointers 
return cmax;
}

- Dragon March 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

seems like you didn't update the maxNode

- CreepyMan March 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

class A {
   static class Result {
      int value;
      Node node;
   } 
   
   int sumOfTree(Node root, Result max) {
      if (root == null) {
         return 0;
      }
      int leftR = sumOfTree(root.left, max);
      int rightR = sumOfTree(root.right, max);
      int sum = leftR + rightR + root.value;
      if (sum > max.value) {
         max.value = sum;
         max.node = root;
      } 
      return sum;
   }
   
   public static void main(String[] args) {
      Node root = ...; //create a tree
      Result max = new Result(Integer.MIN, root);
      new A().sumOfTree(root, max);
      max.value; //max value
      max.node; //max node
   }
}

- Larry March 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can't create instance of static Class??? Approach looks fine

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

Dangerous!!! Null handlers missing

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

and the function is always returning the sum calculated whether it is greater or smaller than the current max

- Anonymous April 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

1. Static class can be instantiated.
2. Only need handle root == null.
3. Return sum to calculate sumOfTree. Max is stored in max instance.

- Larry April 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

Do post-order traversation(left-right-parent). During traversation save the parent bode with max sum (left sum + rigth sum). Time: O(N)

- m@}{ March 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is correct, post order will calculate child sum and then go to parent. but the issue is we need to return node*, with this approach we will have to change all the parent nodes to sum of child nodes, not sure if allowed to do so .

- aaman.singh85 October 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Do post-order traversation(left-right-parent). During traversation save the parent node with max sum (left sum + rigth sum). Time: O(N)

- m@}{ March 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The question says to return the Node itself while most solutions are returning the sum of this Node, so I guess the question was probably edited. Here is my recursive version to returning the Node.

The recursive method does 2 things: (1) set the sum of current node and (2) return the largest-sum Node under the current node.

static Node largestSum(Node n) {
  if(n == null)
    return null;

  Node leftLargest = largestSum(n.left);
  Node rightLargest = largestSum(n.right);
  n.sum += (n.left != null ? n.left.sum : 0);
  n.sum += (n.right != null ? n.right.sum : 0);

  Node largest = n;
  if(n.left != null && leftLargest.sum > largest.sum)
    largest = leftLargest;
  if(n.right != null && rightLargest.sum > largest.sum)
    largest = rightLargest;

  return largest;
}

- Sunny December 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good solution. Just that we need to make an assumption: the class Node should have the field "sum".
Also we can create a tree and update the sum of a node whenever we insert a new node in its subtree.

- Setila June 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

start summing up value from leaf to root and while summing these value keep track of node largest sum up value. and passing this value to parents node.


int Max (node *root)
{

static node tmp=NULL ;
static int check=INT_MIN

if(!root)
return 0;

if(root->left ==NULL && root->right==NULL)
return root->data;

int L=Max(root->left);
int R =Max(root->right);

if( (root->data + L +R) >check)
{
tmp=root; //store the node with max value;
}

return (root->data +L +R) ;
}

tmp node will have largest sum up value.


//tmp node can be pass as a reference node also




}

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

Nice code, but the function need to return the node with largest subtree value

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

Scala version. Returns SearchResult with tree node and sum of its direct child values. Because it is binary tree there is no need to search on the left if the right node is present.

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

  def findNodeWithBiggestSum(t:Option[Tree[Int]]):Option[SearchResult] = {
    def _compare(t1:Option[SearchResult], t2:Option[SearchResult]):Option[SearchResult] = {
      if (t1.isEmpty) return t2
      if (t2.isEmpty) return t1
      //Both not empty
      if (t1.get.sum > t2.get.sum) t1 else t2
    }
    def _computeResult(t:Option[Tree[Int]]):Option[SearchResult] = t match {
      case None=>None
      case Some(tree)=>
        val leftValue = zeroIfNone(tree.left)
        val rightValue = zeroIfNone(tree.right)
        Some(SearchResult(tree, leftValue + rightValue))
    }
    def _find(t:Option[Tree[Int]], soFar:Option[SearchResult]):Option[SearchResult] = t match {
      case None=>soFar
      case Some(t)=> t.right match {
          case None => _compare(_computeResult(Some(t)), _find(t.left, soFar))
          case Some(rightTree)=>
            _compare(_computeResult(Some(t)), _find(t.right, soFar))
      }
    }
    _find(t, None)
  }

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

It's not binary search tree.

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

package SubTreeLargestSumUp;

public class BTNode {
	public BTNode left;
	public BTNode right;
	public int value;
	public int sumUp;
	
	public BTNode(BTNode l, BTNode r, int v, int s){
		left = l;
		right = r;
		value = v;
		sumUp = s;
	}
}
package SubTreeLargestSumUp;

public class BTNode {
	public BTNode left;
	public BTNode right;
	public int value;
	public int sumUp;
	
	public BTNode(BTNode l, BTNode r, int v, int s){
		left = l;
		right = r;
		value = v;
		sumUp = s;
	}
}

package SubTreeLargestSumUp;

public class DFS {
	BTNode r = new BTNode(null, null, 0, Integer.MIN_VALUE);
	
	
	
    public static void main(String [] args){
    	BTNode a = new BTNode(null, null, 4, Integer.MIN_VALUE);
    	BTNode b = new BTNode(null, null, 5, Integer.MIN_VALUE);
    	BTNode c = new BTNode(null, null, -1, Integer.MIN_VALUE);
    	BTNode d = new BTNode(null, null, 7, Integer.MIN_VALUE);
    	BTNode e = new BTNode(c, d, 3, Integer.MIN_VALUE);
    	BTNode f = new BTNode(a, b, 2, Integer.MIN_VALUE);
    	BTNode g = new BTNode(e, f, 1, Integer.MIN_VALUE);
    	DFS dfs = new DFS();
    	dfs.sumUp(g);
    	System.out.print(dfs.DFS(g).value);
    }
	
	
	public int sumUp(BTNode n){
  	  if (n.left == null && n.right == null)
  		  return n.sumUp = n.value;
  	  else if (n.left == null)
  		  return n.sumUp = n.value + sumUp(n.right);
  	  else if (n.right == null)
  		  return n.sumUp = n.value + sumUp(n.left);
  	  else return n.sumUp = n.value + + sumUp(n.left) + + sumUp(n.right);
    }
	
	public BTNode DFS(BTNode n){
		if (n.left != null)
			DFS(n.left);
		if (n.right != null)
			DFS(n.right);
		if (n.sumUp > r.sumUp) r = n;
		return r;
	}
	
}

- Giuss March 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package SubTreeLargestSumUp;

public class BTNode {
	public BTNode left;
	public BTNode right;
	public int value;
	public int sumUp;
	
	public BTNode(BTNode l, BTNode r, int v, int s){
		left = l;
		right = r;
		value = v;
		sumUp = s;
	}
}
package SubTreeLargestSumUp;

public class BTNode {
	public BTNode left;
	public BTNode right;
	public int value;
	public int sumUp;
	
	public BTNode(BTNode l, BTNode r, int v, int s){
		left = l;
		right = r;
		value = v;
		sumUp = s;
	}
}

package SubTreeLargestSumUp;

public class DFS {
	BTNode r = new BTNode(null, null, 0, Integer.MIN_VALUE);
	
	
	
    public static void main(String [] args){
    	BTNode a = new BTNode(null, null, 4, Integer.MIN_VALUE);
    	BTNode b = new BTNode(null, null, 5, Integer.MIN_VALUE);
    	BTNode c = new BTNode(null, null, -1, Integer.MIN_VALUE);
    	BTNode d = new BTNode(null, null, 7, Integer.MIN_VALUE);
    	BTNode e = new BTNode(c, d, 3, Integer.MIN_VALUE);
    	BTNode f = new BTNode(a, b, 2, Integer.MIN_VALUE);
    	BTNode g = new BTNode(e, f, 1, Integer.MIN_VALUE);
    	DFS dfs = new DFS();
    	dfs.sumUp(g);
    	System.out.print(dfs.DFS(g).value);
    }
	
	
	public int sumUp(BTNode n){
  	  if (n.left == null && n.right == null)
  		  return n.sumUp = n.value;
  	  else if (n.left == null)
  		  return n.sumUp = n.value + sumUp(n.right);
  	  else if (n.right == null)
  		  return n.sumUp = n.value + sumUp(n.left);
  	  else return n.sumUp = n.value + + sumUp(n.left) + + sumUp(n.right);
    }
	
	public BTNode DFS(BTNode n){
		if (n.left != null)
			DFS(n.left);
		if (n.right != null)
			DFS(n.right);
		if (n.sumUp > r.sumUp) r = n;
		return r;
	}
	
}

- Giuss March 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is variable "r" in the function {public BTNode DFS(BTNode n)}

- Abhi March 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

R points to the max node; declared at the top.

- Gkondal May 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int largestvaluesum(struct node *root,struct node **maxvaluenode)
{int maxsum;
if(root==NULL)
return 0;
int lsum=largestvaluesum(root->left,maxvaluenode);
int rsum=largestvaluesum(root->right,maxvaluenode);
if(maxsum<=max(lsum,rsum)+root->data)
{maxsum=max(lsum,rsum)+root->data;
*maxvaluenode=root;
}
return maxsum;
}

- codinglearner March 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This changes the data in a node to the recursive sum of its children's data.

NODE* max;
visited = NULL;
do
{
	while( p != NULL )
		stack.push(p);
		p = p->left;
	
	while( !stack.empty() )
	{
		temp = stack.top();
		if( temp->right == NULL || temp->right == visited )
			stack.pop();
			temp->data += (temp->left)?temp->left->data:0;
			temp->data += (temp->right)?temp->right->data:0;
			if( max == NULL )	max = temp;
			else if( max->data < temp->data )	max = temp;
			visited = temp;
			continue;
	
		if( temp->right != NULL )
			p = temp->right;
			break;
	}
}while( p != NULL || !stack.empty() );

- y2km11 March 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int subTreeWithMaxSum(node *root)
{
	if(!root)
		return 0;
	if(!root->left && !root->right)
		return root->data;
	int lSum = subTreeWithMaxSum(root->left);
	int rSum = subTreeWithMaxSum(root->right);
	return max(root->data, max(root->data+lSum+rSum, max(root->data+lSum, root->data+rSum)));
}

- Anonymous March 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry this is wrong... i thought to return sub tree with max sum...

Its not possible to return node, because you need to maintain 2 values one with intermediate data which is the solution and one to return to next top level.... so at a time its not possible to return 2 values from a function

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

yeah, return the int value is easier.... return node is a tricky one

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

Please have a look

node * maxSumSubtree( node * head, int &sumSubTree, int &maxSumSubtree)
{
if(head == NULL)
{
sumSubTree = 0;
maxSumSubtree =0;
return NULL
}

int leftSumSubTree = 0;
int rightSumSubTree = 0;
int maxLeftSumSubTree = 0;
int maxRightSumSubTree = 0;

node *leftMaxSumSubtree = NULL;
node *rightMaxSumSubtree = NULL;

leftMaxSumSubtree = maxSumSubtree(head->left, leftSumSubTree, maxLeftSumSubTree);
rightMaxSumSubtree = maxSumSubtree(head->right, rightSumSubTree, maxRightSumSubTree);

sumSubTree = head->data + leftSumSubTree +rightSumSubTree;

if(sumSubTree => maxRightSumSubTree && sumSubTree => maxLeftSumSubTree)
{
maxSumSubtree = sumSubTree;
return head;
}
else if(maxRightSumSubTree >= sumSubTree  && maxRightSumSubTree >= maxLeftSumSubTree)
{
maxSumSubtree = maxRightSumSubTree;
return rightMaxSumSubtree;
}
else
{
maxSumSubtree = maxLeftSumSubTree;
return leftMaxSumSubtree;
}
}

- Wayne March 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. breadth first traversal the tree, push nodes into a stack.
2. while stack is not NULL, pop the top element in the stack, and add it's value with values of its child nodes. update the max value as well as the result node.

Am I right?

- StartFromNeg1 March 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public static TreeNode FindMaxSubtree(TreeNode node,Hashtable<TreeNode,Integer> sum)
	{
		if(node == null)
			return null;
		
		TreeNode leftMaxNode = FindMaxSubtree(node.LeftChild, sum);
		TreeNode rightMaxNode = FindMaxSubtree(node.RightChild, sum);
		
		int nodeSum = node.Data + (node.LeftChild == null? 0 : sum.get(node.LeftChild)) 
					  + (node.RightChild == null? 0 : sum.get(node.RightChild)) ;		
		sum.put(node, nodeSum);
		
		TreeNode maxNode = node;
		int max = nodeSum;
		
		if(leftMaxNode != null && sum.get(leftMaxNode) > max)
		{
			maxNode = leftMaxNode;
			max = sum.get(leftMaxNode);
		}
		
		if(rightMaxNode != null && sum.get(rightMaxNode) > max)
		{
			maxNode = rightMaxNode;
			max = sum.get(rightMaxNode);
		}		
		
		return maxNode;
	}

- alala March 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct node * func(struct node *ptr)
{
if(ptr==NULL)
return NULL;
else
{
struct node *le,*re;
le=(struct node *)func(ptr->left);
re=(struct node *)func(ptr->right);
if(le!=NULL&&re!=NULL)
ptr->info=le->info+re->info+ptr->info;
else if(re==NULL&&le==NULL)
ptr->info=ptr->info;
else if(le==NULL)
ptr->info=re->info+ptr->info;
else if(re==NULL)
ptr->info=le->info+ptr->info;

return ptr;
}
}

- beginner March 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The code replace the value of the node with the sum of sub-tree, but didn't record the max-sum node. maybe can record it using a static variable

- philwang April 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Store temp maxSumNode and initialize it to root
// Also maintain an extra field sum in every Node apart from value and next

public Node largestSumNode( Node root ){
sumOfNode(maxSumNode = root);
return maxSumNode;
}

private int sumOfNode( Node node ){
if( node != null ){
node.sum = node.value + sumOfNode(node.left) + sumOfNode(node.right);
if( node.sum >= maxSumNode.sum )
maxSumNode = node;
return node.sum;
}
return 0;
}

- Prateek Mandloi March 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct maxSumAndNode{
int maxSum ;
struct node *maxNode ;
};



struct maxSumAndNode rootNodeWithLargestSumUpValue(struct node *node, int maximum, struct node *ret)
{
int tempSum ;
struct maxSumAndNode st1,st2;


if(node == NULL){
struct maxSumAndNode result;
result.maxSum = maximum ;
result.maxNode = ret;

return result;
}

else
{
if((tempSum = printSum(node) )> maximum)
{
maximum = tempSum ;
st1 = rootNodeWithLargestSumUpValue(node->left , maximum, node);
st2 = rootNodeWithLargestSumUpValue(node->right , maximum , node);
if(st1.maxSum > st2.maxSum)
{
return st1;
}
else
{
return st2;
}

}
else
{
maximum = maximum ;
st1= rootNodeWithLargestSumUpValue(node->left , maximum, ret);
st2 = rootNodeWithLargestSumUpValue(node->right , maximum , ret);
if(st1.maxSum > st2.maxSum)
{
return st1;
}
else
{
return st2;
}
}

}
}

- naveen kumar May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct maxSumAndNode{
int maxSum ;
struct node *maxNode ;
};



struct maxSumAndNode rootNodeWithLargestSumUpValue(struct node *node, int maximum, struct node *ret)
{
int tempSum ;
struct maxSumAndNode st1,st2;


if(node == NULL){
struct maxSumAndNode result;
result.maxSum = maximum ;
result.maxNode = ret;

return result;
}

else
{
if((tempSum = printSum(node) )> maximum)
{
maximum = tempSum ;
st1 = rootNodeWithLargestSumUpValue(node->left , maximum, node);
st2 = rootNodeWithLargestSumUpValue(node->right , maximum , node);
if(st1.maxSum > st2.maxSum)
{
return st1;
}
else
{
return st2;
}

}
else
{
maximum = maximum ;
st1= rootNodeWithLargestSumUpValue(node->left , maximum, ret);
st2 = rootNodeWithLargestSumUpValue(node->right , maximum , ret);
if(st1.maxSum > st2.maxSum)
{
return st1;
}
else
{
return st2;
}
}

}
}

- naveen kumar May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

stTree* MaxSubtreeSum(stTree* pTree,int& MaxSum,stTree*& pMaxNode)
{
if(pTree == NULL)
return pMaxNode;

int TempSum = SubTreeSum(pTree);
if(TempSum > MaxSum)
{
MaxSum = TempSum;
pMaxNode = pTree;
}
MaxSubtreeSum(pTree->left,MaxSum,pMaxNode);
MaxSubtreeSum(pTree->right,MaxSum,pMaxNode);
return pMaxNode;
}

int SubTreeSum(stTree* pTree)
{
if(pTree == NULL)
return 0;

return (pTree->data + SubTreeSum(pTree->left) + SubTreeSum(pTree->right));
}

- rishikantku June 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will it not be always a root node???
Please correct me if i am wrong

- rishikantku June 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

only if all values positive :)

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

can we return node without modifying the node values of without using a separate sum function.. this code is returning correct node but am modifying every node's value with its sum-up value..

tree* LargestSumNode(tree *p, int l, int r)
{
    static int max = 0;
    static tree *max_node = NULL;
    
    if(!p) return max_node;
    
    if(!p->left && !p->right)
    {
        if(p->data > max)
        {
          max = p->data;
          max_node = p;
        }
    }
    
    LargestSumNode(p->left, l, r);
    l = p->left ? p->left->data : 0;
    
    LargestSumNode(p->right, l, r);
    r = p->right ? p->right->data : 0;
    
    if(p->data + l + r > max)
    {
        max = p->data + l + r;
        max_node = p;
    }
    p->data = p->data + l + r;
    
    return max_node;
}

- Silent September 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

TREE isMax(TREE root)
{
	if(root==NULL)return 0;
	static int maxsum = 0;	
	static TREE newroot = NULL;
	int ls = sum(root->left);
	int rs = sum(root->right);
	if(ls + rs + root->info > maxsum)
	{
		maxsum = ls + rs + root->info;
		newroot = root;
		cout<<"\n New max sum = "<<maxsum;
		cout<<"\n new root = "<<newroot->info;
	}
	
isMax(root->left);
isMax(root->right);

return newroot;
}
int sum(TREE root)
{
	if(root==NULL)
	return 0;
	else
	return (sum(root->left) + root->info + sum(root->right));

}

- _123 July 13, 2012 | 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