Amazon Interview Question
Systems Design EngineersCountry: India
Interview Type: Phone Interview
This solution fails for the cases where the maximum path starts from a node and ends with another node which is not a leaf. Like in this example:
5
/ \
2 -4
/ \ /
-1 -3 -2
The returned answer is 6 where it should be 7 (2 --> 5).
This solution fails for the cases where the maximum path starts from a node and ends with another node which is not a leaf. Like in this example:
5
/ \
2 -4
/ \ /
-1 -3 -2
The returned answer is 6 where it should be 7 (2 --> 5).
/* C code */
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
/* To begin with, pass pointer to root node */
int MaxPathSum (Node *node) {
int leftSubtreeSum, rightSubtreeSum;
/* NULL check */
if (node == NULL) return 0;
/* Leaf node check */
if (node->left == NULL && node->right == NULL)
return node->data;
leftSubtreeSum = MaxPathSum (node->left);
rightSubtreeSum = MaxPathSum (node->left);
if ( leftSubtreeSum > rightSubtreeSum )
return leftSubtreeSum + node->data;
else
/* else is redundant. You don't need an else.
* You can directly use the return below without else.
*/
return rightSubtreeSum + node->data;
}
Very nice solution.
may be we could change last few lines to make it work for- path starting from any node and ending at any node:
if ( leftSubtreeSum > rightSubtreeSum )
return (leftSubtreeSum + node->data) > leftSubtreeSum ? (leftSubtreeSum + node->data) : leftSubtreeSum ;
else
return (rightSubtreeSum + node->data) > rightSubtreeSum ? (rightSubtreeSum + node->data) : rightSubtreeSum ;
one more condition is missing here... both left and right are negative values and root is positive value or negative value greater than left and right then we should take only root value
left = root->data + root->left->data;
right = root->data + root->right->data;
leftright = root->data + root->right->data + root->left->data;
d = root->data;
if(d > left && d > right && d > leftright)
return d;
I second algos point. You can try passing an array as an argument so that you can push the nodes that sum to the values and atlast try to print the nodes in the array.
we can simply run BFS and count how many times we do enqueue. This will take O(|V|). The same as DFS.
/* Begin with sum as 0 and max as root->info*/
int maxPathSum(Node root, int sum, int max)
{
if(root == NULL)
return max;
int newSum;
int newMax;
if(sum<0)
newSum = root->info;
else
newSum = root->info + sum;
int lMax,rMax;
if(newSum > max)
newMax = newSum;
else
newMax = max;
int lMax = maxPathSum(root->left, newSum, newMax);
int rMax = maxPathSum(root->right,newSum, newMax);
if(lMax > rmax)
return lMax;
else
return rMax;
}
tested, it works well
int maxPathSum(BTREE *root)
{
int lMaxSum=0, rMaxSum=0;
if(root == NULL)
return 0;
//if this is a leaf, then return o
if(root->left == NULL && root->right == NULL)
return 0;
if(root->left != NULL)
{
lMaxSum = maxPathSum(root->left);
}
if(root->right != NULL)
{
rMaxSum = maxPathSum(root->right);
}
if(root->parent != NULL)
{
if(lMaxSum > rMaxSum)
{
return lMaxSum + root->data;
}else
{
return rMaxSum + root->data;
}
}else if(root->parent == NULL)
{
if(root->left != NULL && root->right != NULL)
{
return lMaxSum+rMaxSum+root->data;
}else if(root->left == NULL)
{
return rMaxSum;
}else if(root->right == NULL)
{
return lMaxSum;
}
}
}
This is a fairly tough problem, but it can be attacked recursively. For any root node, there are up to five paths/values to consider. You have up to two "maximum" paths on the left side, one of which is disconnected from the root node (potentially) and one of which is connected. Then you have the same on the right side. Then you have the value of the root node itself.
Given 5 subpaths, there are 32 ways to combine them, but not all of those combinations form valid paths themselves. So you can prune some combinations as obviously invalid, due to either having overlapping values or not being connectable.
The question doesn't clarify that the binary tree is actually a sort tree--i.e. all elements to the left of the root node are less than the root node--but if you did know that property, you could prune even further.
This might not adhere to all constraints, but can be solved using the solution below.
The solution can be achieved in linear time using recursion. The idea is to find the max sum in left and right sub trees for a node and return the largest of those numbers along with the path to that node. The root of the tree will finally compare the max numbers in its left and right sub trees and returns the larger of those two numbers along with the path.
linearspacetime[dot]blogspot[dot][com]
public void MaxSumPath(Node<int> node, ref int maxSum, int sum, List<Node<int>> path, List<Node<int>> resultPath)
{
if (node == null)
{
if (sum > maxSum)
{
resultPath.Clear();
foreach (var n in path)
{
resultPath.Add(n);
}
maxSum = sum;
}
return;
}
path.Add(node);
MaxSumPath(node.Left, ref maxSum, sum + node.Value, path, resultPath);
MaxSumPath(node.Right, ref maxSum, sum + node.Value, path, resultPath);
path.Remove(node);
}
Given that someone half-retarded wrote the problem statement: can someone (preferably someone capable of expressing coherent thoughts in English) re-word it so that it can be understood in English?
similar as finding the diameter of the tree, recursively find out the max sum of the path in the left or right subtree and max sum of the path from the left child or right child
max = max(val + (left_max_from_root > 0 ? left_max_from_root : 0) + (right_max_from_root > 0 ? right_max_from_root : 0),
left_max,
right_max)
max_from_root = max(val, left_max_from_root + val, right_max_from_root + val)
class MaxSum
{
public int max; //max sum of the path in the tree (not necessary includind the root)
public int maxFromRoot; //max sum of the path from the root (not necessary to the leaf node)
public MaxSum(int max, int maxFromRoot)
{
this.max = max;
this.maxFromRoot = maxFromRoot;
}
}
public MaxSum maxSum(TreeNode root)
{
if(root == null) return new MaxSum(0, 0);
MaxSum leftSum = maxSum(root.left);
MaxSum rightSum = maxSum(root.right);
int maxFromRoot = Math.max(root.val, Math.max(leftSum.maxFromRoot + root.val, rightSum.maxFromRoot + root.val));
int max = root.val +
(leftSum.maxFromRoot > 0 ? leftSum.maxFromRoot : 0) +
(rightSum.maxFromRoot > 0 ? rightSum.maxFromRoot : 0);
max = Math.max(max, Math.max(leftSum.max, rightSum.max));
return new MaxSum(max, maxFromRoot);
}
In tested it for many cases and It works true:)
public static int max_sum = Integer.MIN_VALUE;
public static void find_max_sum(Node root,ArrayList<Node> list){
if(root == null) return;
list.add(root);
int sum = 0;
for(Node c : list){
sum+=(int)c.data;
if(sum > max_sum){
max_sum = sum;
}
}
find_max_sum(root.left, list);
find_max_sum(root.right,list);
list.remove(root);
}
public static void main(String[] args) throws Exception {
Node n1 = new Node(5);
Node n2 = new Node(2);
Node n3 = new Node(-4);
Node n4 = new Node(-1);
Node n5 = new Node(-3);
Node n6 = new Node(-2);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
find_max_sum(n1, new ArrayList<Node>());
System.out.println(max_sum);
}
- Anonymous November 05, 2012