Facebook Interview Question
Backend DevelopersCountry: United States
public class FindMaxPathInTree {
public static class Node {
public Node left;
public Node right;
public int data;
public Node(int data) {
super();
this.data = data;
}
}
public static void main(String[] args) {
/*Node node = new Node(9);
node.left = new Node(-2);
node.right = new Node(7);
node.left.left = new Node(5);
node.left.right = new Node(3);
node.left.left.left = new Node(1);
node.left.left.right = new Node(4);
node.left.right = new Node(3);
node.right.left = new Node(2);
node.right.right = new Node(9);
node.right.right.left = new Node(7);
node.right.right.left.left = new Node(2);
node.right.right.left.right = new Node(9);
StringBuilder result = new StringBuilder();*/
Node node = new Node(-1);
node.left = new Node(-2);
node.right = new Node(3);
node.right.right = new Node(-1);
StringBuilder result = new StringBuilder();
findMaxPathInTree(node, new Sum(),result, new StringBuilder());
System.out.println(result.toString());
}
private static class Sum {
int sum;
}
public static int findMaxPathInTree(Node node, Sum sum, StringBuilder maxPath, StringBuilder currPath) {
int currentSum = 0;
if (node == null) {
return 0;
} else if (node.left == null && node.right == null) {
if (sum.sum < node.data) {
sum.sum = node.data;
maxPath.delete(0, maxPath.length());
maxPath.append("" + node.data);
}
currPath.delete(0, currPath.length());
currPath.append("" + node.data);
currentSum = node.data;
} else {
int leftSum = findMaxPathInTree(node.left, sum, maxPath, currPath);
String leftSumPath = currPath.toString();
currPath.delete(0, currPath.length());
int rightSum = findMaxPathInTree(node.right, sum, maxPath, currPath);
String rightSumPath = currPath.reverse().toString();
currPath.delete(0, currPath.length());
// find current sum including left subtree, right subtree, and current node
if (leftSum + node.data > node.data) {
int tempSum = node.data + leftSum;
if (node.data + rightSum > node.data) {
// append all three for finding tempSum
tempSum += rightSum;
if (tempSum > sum.sum) {
sum.sum = tempSum;
maxPath.delete(0, maxPath.length());
maxPath.append("" + leftSumPath + node.data + rightSumPath);
}
if (leftSum > rightSum) {
currPath.append(leftSumPath + node.data);
currentSum = leftSum + node.data;
} else {
currPath.append(rightSumPath + "" + node.data);
currentSum = rightSum + node.data;
}
} else {
currentSum = leftSum + node.data;
currPath.append("" + leftSumPath + "" + node.data);
}
}
else if (rightSum + node.data > node.data) {
int tempSum = node.data + rightSum;
if (node.data + leftSum > node.data) {
// append all three for finding tempSum
tempSum += leftSum;
if (tempSum > sum.sum) {
sum.sum = tempSum;
maxPath.delete(0, maxPath.length());
maxPath.append("" + leftSumPath + node.data + rightSumPath);
}
if (leftSum > rightSum) {
currPath.append(leftSumPath + node.data);
currentSum = leftSum + node.data;
} else {
currPath.append(rightSumPath + "" + node.data);
currentSum = rightSum + node.data;
}
} else {
currentSum = rightSum + node.data;
currPath.append("" + rightSumPath + "" + node.data);
}
} else {
if (node.data > sum.sum) {
maxPath.delete(0, maxPath.length());
maxPath.append("" + node.data);
currPath.append("" + node.data);
currentSum = node.data;
}
}
}
return currentSum;
}
}
#include <iostream>
#include <vector>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
left_ = right_ = NULL;
}
int val_;
Node *left_, *right_;
};
class Path {
public:
Path()
{
sum_ = numeric_limits<int>::min();
}
int sum_;
vector<Node *> path_;
};
Path MaxSumPath(Node *n, Path &out)
{
if (!n) {
return Path();
}
Path l = MaxSumPath(n->left_, out);
Path r = MaxSumPath(n->right_, out);
int sum = n->val_;
if (l.sum_ > 0) {
sum += l.sum_;
}
if (r.sum_ > 0) {
sum += r.sum_;
}
if (sum > out.sum_) {
out.sum_ = sum;
out.path_.clear();
if (l.sum_ > 0) {
out.path_.insert(out.path_.end(), l.path_.begin(), l.path_.end());
}
out.path_.push_back(n);
if (r.sum_ > 0) {
for (int i = r.path_.size() - 1; i >= 0; --i) {
out.path_.push_back(r.path_[i]);
}
}
}
Path p = l.sum_ > r.sum_ ? l : r;
if (p.sum_ < 0) {
p = Path();
}
p.sum_ = (p.sum_ == numeric_limits<int>::min()) ? n->val_ : p.sum_ + n->val_;
p.path_.push_back(n);
return p;
}
int main()
{
/*
(1)
/
(2)
/ \
(3) (4)
/ /
(6) (7)
/ \
(5) (8)
*/
Node n1(1);
Node n2(2);
Node n3(3);
Node n4(4);
Node n5(5);
Node n6(6);
Node n7(7);
Node n8(8);
n1.left_ = &n2;
n2.left_ = &n3;
n2.right_ = &n4;
n3.left_ = &n6;
n4.left_ = &n7;
n7.left_ = &n5;
n7.right_ = &n8;
Path path;
MaxSumPath(&n1, path);
cout << path.sum_ << ": ";
for (Node *n : path.path_) {
cout << n->val_ << "->";
}
cout << "\n";
}
My PHP Solution :
<?php
function findLongestPath($root,&$longest){
$valueFromLeft = ($root->left) ? findLongestPath($root->left,$longest) : 0;
$valueFromRight = ($root->right) ? findLongestPath($root->right,$longest) : 0;
$longest = max($longest,$valueFromLeft + $valueFromRight + $root->value,$valueFromRight + $root->value,$valueFromLeft+ $root->value,$root->value);
return max($valueFromLeft + $root->value , $valueFromRight + $root->value);
}
class Tree{
var $value;
var $left;
var $right;
}
$node1 = new Tree();
$node1->value=-10;
$node1->left = new Tree();
$node1->left->value=-1;
$node1->right = new Tree();
$node1->right->value=5;
$node1->left->right = new Tree();
$node1->left->right->value=-2;
$long=0;
findLongestPath($node1,$long);
echo $long;
?>
Some python code, O(n) runtime:
#class Node(object):
#
# def __init__(self, val):
# self.val = val
# self.r = None
# self.l = None
def biggest(n, curr_sum=0, path=''):
if n is None:
return curr_sum, path
return max(biggest(n.r, curr_sum + n.val, path + "{}-".format(n.val)),
biggest(n.l, curr_sum + n.val, path + "{}-".format(n.val)),
key=lambda a: a[0])
def biggest_sum_path(n):
result = biggest(n)
print("Path - {}, Sum - {}".format(result[1][:-1], result[0]))
Scala
object MaxPathSum extends App {
case class Node(weight: Int, left: Option[Node] = None, right: Option[Node] = None) {
// Return the max path within this tree and the current max path for the path containing this node
def maxPath: (Int, Int) = {
val (leftMax, leftPath) = left.map(_.maxPath).getOrElse((0,0))
val (rightMax, rightPath) = right.map(_.maxPath).getOrElse((0,0))
val path = List(leftPath + weight, rightPath + weight, weight).max
val max = List(leftMax, rightMax, path).max
(max, path)
}
}
val tree =
Node(-1, Some(Node(2,
Some(Node(-5)),
Some(Node(3,
None,
Some(Node(6)))))),
Some(Node(-5,
Some(Node(1)),
Some(Node(8))))
)
println(tree.maxPath._1)
}
recursive definition should do it in a tree, in a generic graph it would be NP-hard.
- Chris December 02, 2017