## Facebook Interview Question for Backend Developers

Country: United States

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

recursive definition should do it in a tree, in a generic graph it would be NP-hard.

``````int max_path_rec(Node* root, int& max_path)
{
if (root == nullptr) return numeric_limits<int>::min();
int left_branch = max(0, max_path_rec(root->left_, max_path));
int right_branch = max(0, max_path_rec(root->right_, max_path));
max_path = max(max_path, root->value_ + left_branch + right_branch);
return root->value_ + max(left_branch, right_branch);
}

int max_path(Node* root)
{
int mpath = numeric_limits<int>::min();
max_path_rec(root, mpath);
return mpath;
}``````

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

``````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;

}
}``````

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

``````#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";
}``````

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

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;

?>``````

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

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]))``````

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

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)
}``````

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.