Amazon Interview Question
Country: United States
Interview Type: In-Person
@REAMS.AL it's just normal tree traversal. just like we do in preOrder / inOrder Traversal. sum(variable) keep adding the root data as we move to left node until reaches the leaf node. When we reach to left most node, sum(variable) will have the sum of all left node value (included root value) and then move to right to explore other possibility. The moment it reaches to leaf node, if s < sum then update s(variable) and decreament the sum by current root->data.
I have a solution but the run time is horrible (n^3 I think, correct me if wrong), I thought of a couple ways to optimize but they are complicated. If anybody knows something with better run time please post.
int findMax(Node * root)
{
if (!root) return 0;
return root->value + std::max(findMax(root->left), findMax(root->right));
}
void printMaximalPath(Node * root)
{
std::cout << root->value << std::endl;
int maxLeft = findMax(root->left);
int maxRight = findMax(root->right);
if (maxLeft < maxRight)
printPath(root->right);
else if (maxRight < maxLeft)
printPath(root->left);
else
return; //Leaf node reached
}
yeah here's my updated solution that is order (n + n). The maximum paths are stored in the node itself, could just as easily be stored in another data structure.
long findMax(node * root)
{
callCount++;
//
if (!root) return 0;
long maxLValue = 0;
if (root->maxLeft != -1)
{
maxLValue = root->maxLeft;
}
else
{
root->maxLeft = findMax(root->left);
maxLValue = root->maxLeft;
}
long maxRValue = 0;
if (root->maxRight != -1)
{
maxRValue = root->maxRight;
}
else
{
root->maxRight = findMax(root->right);
maxRValue = root->maxRight;
}
return ((long) root->data) + std::max(maxLValue, maxRValue);
}
void printMaximalPath(node * root) //this is an order N algoritm as well
{
std::cout << root->data << std::endl;
long maxLeft = findMax(root->left); //order N call first time, 0(1) for all other calls
long maxRight = findMax(root->right);
if (maxLeft < maxRight)
printMaximalPath(root->right);
else if (maxRight < maxLeft)
printMaximalPath(root->left);
else
return; //Leaf node reached
}
int global_max=0;
ArrayList<TreeNode> global_max_path=null;
void findMaxPath (TreeNode t, int sum, ArrayList<TreeNode> path)
{
if(t == null)
{
if(sum > global_max)
{
global_max=sum;
global_max_path = path;
}
}
else
{
ArrayList<TreeNode> left_path = new ArrayList<TreeNode>(path);
findMaxPath(t.left,sum+t.data,path.add(t));
ArrayList<TreeNode> right_path = new ArrayList<TreeNode>(path);
findMaxPath(t.right,sum+t.data,path.add(t));
}
}
findMaxPath(t,0,new ArrayList<TreeNode>());
does it mean the sum of values on the path is maximum or path to the node with max value
def dfsMax(bt, n="root", path=[], maxPath=[], maxData=None):
#Init
if n=="root":
n=bt.root
if maxData==None:
maxData=n.data
if n==None:
return maxPath
path.append(n)
#Update Max Path
if n.data >maxData:
maxPath = list(path)
maxPathL=dfsMax(bt, n.left, path, maxPath, maxData)
maxPathR=dfsMax(bt, n.right, path, maxPath, maxData)
path.pop(-1)
if len(maxPathL)==0:
return maxPathR
if len(maxPathR)==0:
return maxPathL
if (maxPathL[-1].data>maxPathR[-1].data):
return maxPathL
else:
return maxPathR
first find the max sum in tree and then search for path for max sum in the tree.
below c++ function will give you the result.
global variable: vector <int> v, int s=0 and int sum=0;
- Ratn October 14, 2012