## Amazon SunGard Interview Question for Software Engineer / Developers

Team: Elastic Mapreduce
Country: United States
Interview Type: Phone Interview

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

Do a post order traversal and decide the sum of the subtree and the best sum seen so far and return it to the parent. --- O(n)

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

Hi,

I have an O(n) algo for this. Please check it. In this, I make inorder traversal and keep on saving the max sum and the corresponding node till now in 2 variables.

``````int get_max_sum_node(node *root, node **max_sum_node)
{
static int max = 0;

if(root != NULL)
{
int sum = 0;

sum += get_max_sum_node(root -> left, max_sum_node);
sum += root -> data;
sum += get_max_sum_node(root -> right, max_sum_node);

if(sum > max)
{
max = sum;
*max_sum_node = root;
}

return sum;
}
return 0;
}``````

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

This is post order as you are calculating sum (& calc max update) at the end and not in btw.

Also consider a corner case where all nodes are -ve, your algo returns 0. You need to do (root->left != NULL) or checking max_sum_node value etc

I think you don't need max variable as you are anyway having **max_sum_node.

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

here is one good solution,

puddleofriddles.blogspot.com/2012/01/write-program-to-find-sub-tree-in.html

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

tree contains negative values?

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

yes, It may contains negative values

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

Obviously , else root will have the max value and leaf nodes min value. !!

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

Considering tree has got negative values else otherwise max will be the tree itself.

Define one HashMap<TreeNode,Integer> to store sum of node.This is to make sure we dont calculate the sum of one subtree more than once.

static int SumNode(TreeNode node){
int sum = 0;
if(node == null)
return 0;
else{
if(map.containsKey(node))
return map.get(node);
else{
sum = node.data + SumNode(node.left) + SumNode(node.right);
map.put(node,sum);
return sum;
}
}
}

static int MaxSum(TreeNode root){
if(root == null)
return 0;
else
return Math.max(SumNode(root),Math.max(MaxSum(root.left),MaxSum(root.right)));
}

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

You are consuming O(n) space in form of hashmap just to ensure that you don't calculate sum of a sub-tree twice. You could to a pre-order traversal.

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

Please give a code if you think it can be done without O(n) space

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

@Manan:You are returning the max sum.The question asks for the tree with the max sum.

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

I don't know who is this.. but I completely agree with this solution..
You are returning the max sum and node address.

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

What about just recursively traversing the tree while giving a pointer to pointer to Node and a reference to the max value?

``````Node* maxSubtree(Node* r) {
int max = -oo;
Node* maxNode = NULL;
f(r, max, &maxNode);
return maxNode;
}
int f(Node* r, int& max, Node** maxNode) {
if(r==NULL) return 0;
int sum = f(r->left, max, maxNode) + f(r->right, max, maxNode) + r->data;
if(sum>max) {
max = sum;
*maxNode = r;
}
return sum;
}``````

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

Above code works just perfect. But I have a doubt if we have to always include the leaf node in the sub tree?
Can we have a sub tree without including the leaf nodes of the main tree.

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

If I understand your question, no. By definition of a tree, I think we need to include all the children (including leaves) of a given node if want to consider it as a tree.

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

@crdmp :
Shouldn't the code be:

``````Node* maxSubtree(Node* r) {
int max = -oo;
Node* maxNode = NULL;
f(r, &max, &maxNode);//Change
return maxNode;
}
int f(Node* r, int *max, Node** maxNode) {//Change
if(r==NULL) return 0;
int sum = f(r->left, max, maxNode) + f(r->right, max, maxNode) + r->data;
if(sum> *max) {//Change
*max = sum;//Change
*maxNode = r;
}
return sum;
}``````

Check the lines with the comment: "//Change"

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

If the root of subtree is smaller or equal to 0, then the summation of its left subtree must be negative, so its right subtree has the larger summation than it. This pattern should save at least half of computation.

Then we traverse down to its right subtree.

If the root is larger than 0, then add the summation of its left subtree and itself, if it is negative, it's the same to the previous situation so we recursively investigate its right subtree. Otherwise, this tree has the maximum summation.

Not quite sure, anyone find bugs?

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

Running time is best case: lg(n)---only max node is positive; worse-cars: n/2, calculate summation of left subtree.

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

Hi, It is need not be a BST.
It is just balanced binary tree.

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

yes this need not be BST.... it can be any tree....

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

Then it's just a depth-first traverse like crdmp showed.

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

{If the root of subtree is smaller or equal to 0, then the summation of its left subtree must be negative}
Why is this? It could also be that the right subtree might be negative.E.g. Root is -4, left is 8 and right is 4.(A tree with 3 nodes).With your approach you say the right child is the max tree but it it has 4 < 8

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

my bad...I assumed it is a BST

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

@Manan: Your algorithm is brute force and its O(n^2) time and O(n) space.

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

how the complexity is O(n2) in his algo ..

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

``````public class TreeSum {
public static class Node {
int value;
Node left;
Node right;

public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}

public static class Result{
Node node;
int max;
int sum;

public Result(Node node, int max, int sum) {
this.node = node;
this.max = max;
this.sum = sum;
}
}

public static Result findMaximum(Node root) {
if (root == null) {
return new Result(root, 0, 0);
} else {
Result left = findMaximum(root.left);
Result right = findMaximum(root.right);
int sum = left.sum + right.sum + root.value;
int max = sum;
Node node = root;
if (max < left.max) {
max = left.max;
node = left.node;
}

if (max < right.max) {
max = right.max;
node = right.node;
}
return new Result(node, max, sum);
}
}
}``````

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.