Google Interview Question Software Engineer Interns
Country: United States
Interview Type: Phone Interview
Do a level order traversal and add the numbers from top to bottom (If a node occurs multiple times, then keep the maximum number there).
The max number of a leaf node in this process will be the maximum sum.
1st itr: 3
2nd itr: 12 ->7
3rd itr:13 -> 20 {20, 15} -> 9
4th itr: 17 -> 25 {25, 20} -> 28 {28, 17}-> 11.
Maximum number is 28.
Another idea could treat the pyramid as a heap-structure, insert the duplicate child twice to resolve the parent-location problem. then do a traversal from leaf to root to find the max-total:
import math
class DAGHeap:
def __init__(self, aVals):
self.vals = aVals
self.vals.insert(0, -1)
self.length = len(self.vals)
print(self.vals)
def parent(self, i):
return int(i/2)
def countT(self, j):
if j == 0:
return 0
else:
return self.vals[j] + self.countT(self.parent(j))
def countMax(self):
pmax = 0
for i in range(self.length-1, math.floor(self.length/2), -1):
currentMax = self.vals[i] + self.countT(self.parent(i))
if pmax < currentMax:
pmax = currentMax
print('Maximum Path Cost: ', pmax)
a = [1 , 20 ,21 ,9, 12,12, 6, 71, 22,22,5, 5, 7]
b = [3,9,4,1,8,8,2,4,5,5,8,8,2]
myDAG = DAGHeap(a)
myDAG.countMax()
myDAG = DAGHeap(b)
myDAG.countMax()
Sample output:
[-1, 1, 20, 21, 9, 12, 12, 6, 71, 22, 22, 5, 5, 7]
Maximum Path Cost: 101
[-1, 3, 9, 4, 1, 8, 8, 2, 4, 5, 5, 8, 8, 2]
Maximum Path Cost: 28
I'm not familiar with DAG instead I use an array representation, but the same idea can be used with a Tree or DAG.
private class PathHelper
{
public int Value = 0;
public List<int> Path = new List<int>();
}
public List<int> FindMaxPath(int[][] values)
{
int n = values.Length;
PathHelper[] prev = new PathHelper[n];
PathHelper[] curr = null;
for (int i = 0; i < n; i++)
{
prev[i] = new PathHelper();
prev[i].Value = values[n - 1][i];
prev[i].Path.Add(values[n - 1][i]);
}
for (int i = n - 2; i >= 0; i--)
{
int m = values[i].Length;
curr = new PathHelper[m];
for (int j = 0; j < m; j++)
{
curr[j] = new PathHelper();
var max = (prev[j].Value > prev[j + 1].Value) ? prev[j] : prev[j + 1];
curr[j].Value = values[i][j] + max.Value;
curr[j].Path.Add(values[i][j]);
curr[j].Path.AddRange(max.Path);
}
prev = curr;
}
return curr[0].Path;
}
We can keep track of max Child using map which has been used to calculate max sum and return max Sum. and then call print path on the map:
below is the working code :
struct Node{
int data;
Node *lc=NULL; Node *rc=NULL;
Node(int x) : data(x){}
};
int findPath(Node * root,std::map<Node *,Node *> &maxChild){
if(root->lc==NULL && root->rc==NULL){
return root->data;
}
else{
int maxS;
int suml=root->data+findPath(root->lc,maxChild);
int sumr=root->data+findPath(root->rc,maxChild);
if(suml>sumr){
maxChild[root]=root->lc;
maxS=suml;
}
else{
maxChild[root]=root->rc;
maxS=sumr;
}
return maxS;
}
}
void printPath(std::map<Node *,Node *>& maxChild,Node * root){
while(true){
std::cout<<root->data<<" ";
root=maxChild[root];
if(maxChild.find(root)==maxChild.end()){
std::cout<<root->data<<" \n ";
break;
}
}
}
class Tree:
def __init__(self, data, children=[]):
self.data = data
self.children = children
def max_path(tree):
d_node = {}
max_val = max_path_helper(tree, d_node, {}, set())
return find_path(tree, d_node), max_val
def max_path_helper(tree, d_node, d_val, done):
if tree == None:
return 0
if (tree not in done):
best_next = None
best_val = 0
for child in tree.children:
val = max_path_helper(child, d_node, d_val, done)
if val > best_val:
best_val = val
best_next = child
d_node[tree] = best_next
d_val[tree] = tree.data + best_val
done.add(tree)
return d_val[tree]
def find_path(tree, d):
path = []
curr = tree
while curr in d:
path.append(curr.data)
curr = d[curr]
return path
# Quick test
second_eight = Tree(8)
five = Tree(5)
first_eight = Tree(8)
first_eight.children = [five, second_eight]
two = Tree(2)
two.children = [second_eight, Tree(2)]
dag = Tree(3, \
[Tree(9, \
[Tree(1, \
[Tree(4), Tree(5)]), \
first_eight]), \
Tree(4, \
[first_eight, \
two])])
print(max_path(dag))
Use tree data structure for pyramid. Finding the path with the maximal sum is relatively easy because its sub-problem can be found as its sum to itself plus its left and right children. Details: cpluspluslearning-petert.blogspot.co.uk/2016/03/bts-find-path-with-maximal-sum-in.html
using namespace Pyramid;
void TestPyramidTree()
{
{
const std::vector<int> input;
assert(Pyramid::ValidInput(input) == 0);
const std::vector<int> input1 = { 1 };
assert(Pyramid::ValidInput(input1) == 1);
const std::vector<int> input2 = { 1, 2, 3 };
assert(Pyramid::ValidInput(input2) == 2);
const std::vector<int> input3 = { 1, 2, 3, 4, 5, 6 };
assert(Pyramid::ValidInput(input3) == 3);
const std::vector<int> input4 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
assert(Pyramid::ValidInput(input4) == 4);
const std::vector<int> input5 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
assert(Pyramid::ValidInput(input5) == 5);
}
{
const std::vector<int> input1 = { 1, 0 };
assert(Pyramid::ValidInput(input1) == 0);
const std::vector<int> input2 = { 1, 2, 3, 0 };
assert(Pyramid::ValidInput(input2) == 0);
const std::vector<int> input3 = { 1, 2, 3, 4, 5, 6, 0 };
assert(Pyramid::ValidInput(input3) == 0);
const std::vector<int> input4 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0 };
assert(Pyramid::ValidInput(input4) == 0);
const std::vector<int> input5 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0 };
assert(Pyramid::ValidInput(input5) == 0);
}
{
PyramidTree<int> pyramid;
try {
pyramid.GetDepth();
assert(false);
}
catch (const PyramixException &e) {
assert(std::string(e.what()) == "Pyramid not constructed yet");
}
try {
pyramid.FindMaxSum();
assert(false);
}
catch (const PyramixException &e) {
assert(std::string(e.what()) == "Pyramid not constructed yet");
}
try {
pyramid.FindMaxSumAndPath();
assert(false);
}
catch (const PyramixException &e) {
assert(std::string(e.what()) == "Pyramid not constructed yet");
}
try {
pyramid.ConstructPyramid({1, 2, 3, 4});
assert(false);
}
catch (const PyramixException &e) {
assert(std::string(e.what()) == "Construction failure - invalid input");
}
try {
pyramid.FindMaxSum();
assert(false);
}
catch (const PyramixException &e) {
assert(std::string(e.what()) == "Pyramid not constructed yet");
}
try {
pyramid.FindMaxSumAndPath();
assert(false);
}
catch (const PyramixException &e) {
assert(std::string(e.what()) == "Pyramid not constructed yet");
}
pyramid.ConstructPyramid({ 1, 2, 3 });
assert(pyramid.GetDepth() == 2);
assert(pyramid.FindMaxSum() == 4);
auto path = pyramid.FindMaxSumAndPath();
assert(path.sum == 4);
assert(path.path == std::vector<int>({1, 3}));
pyramid.ConstructPyramid({ 1, 2, 3, 4, 5, 6 });
assert(pyramid.GetDepth() == 3);
assert(pyramid.FindMaxSum() == 10);
path = pyramid.FindMaxSumAndPath();
assert(path.sum == 10);
assert(path.path == std::vector<int>({ 1, 3, 6 }));
pyramid.ConstructPyramid({ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
assert(pyramid.GetDepth() == 4);
assert(pyramid.FindMaxSum() == 20);
path = pyramid.FindMaxSumAndPath();
assert(path.sum == 20);
assert(path.path == std::vector<int>({ 1, 3, 6, 10 }));
pyramid.ConstructPyramid({ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 });
assert(pyramid.GetDepth() == 5);
assert(pyramid.FindMaxSum() == 35);
path = pyramid.FindMaxSumAndPath();
assert(path.sum == 35);
assert(path.path == std::vector<int>({ 1, 3, 6, 10, 15 }));
}
}
Instead of using tree data structure a simple array works as well. The number of each level and its children node is deterministic as long as the pyramid is given. Finding the path with maximal path can be solved with sub-problem of its children node as well. Details: cpluspluslearning-petert.blogspot.co.uk/2016/03/find-path-with-maximal-sum-in-pyramid-ii.html
Test
void TestPyramidArray()
{
{
PyramidArray<int> pyramid;
try {
pyramid.GetDepth();
assert(false);
}
catch (const PyramixException &e) {
assert(std::string(e.what()) == "Pyramid not constructed yet");
}
try {
pyramid.FindMaxSum();
assert(false);
}
catch (const PyramixException &e) {
assert(std::string(e.what()) == "Pyramid not constructed yet");
}
try {
pyramid.FindMaxSumAndPath();
assert(false);
}
catch (const PyramixException &e) {
assert(std::string(e.what()) == "Pyramid not constructed yet");
}
try {
pyramid.ConstructPyramid({ 1, 2, 3, 4 });
assert(false);
}
catch (const PyramixException &e) {
assert(std::string(e.what()) == "Construction failure - invalid input");
}
try {
pyramid.FindMaxSum();
assert(false);
}
catch (const PyramixException &e) {
assert(std::string(e.what()) == "Pyramid not constructed yet");
}
try {
pyramid.FindMaxSumAndPath();
assert(false);
}
catch (const PyramixException &e) {
assert(std::string(e.what()) == "Pyramid not constructed yet");
}
pyramid.ConstructPyramid({ 1, 2, 3 });
assert(pyramid.GetDepth() == 2);
assert(pyramid.FindMaxSum() == 4);
auto path = pyramid.FindMaxSumAndPath();
assert(path.sum == 4);
assert(path.path == std::vector<int>({ 1, 3 }));
pyramid.ConstructPyramid({ 1, 2, 3, 4, 5, 6 });
assert(pyramid.GetDepth() == 3);
assert(pyramid.FindMaxSum() == 10);
path = pyramid.FindMaxSumAndPath();
assert(path.sum == 10);
assert(path.path == std::vector<int>({ 1, 3, 6 }));
pyramid.ConstructPyramid({ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
assert(pyramid.GetDepth() == 4);
assert(pyramid.FindMaxSum() == 20);
path = pyramid.FindMaxSumAndPath();
assert(path.sum == 20);
assert(path.path == std::vector<int>({ 1, 3, 6, 10 }));
pyramid.ConstructPyramid({ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 });
assert(pyramid.GetDepth() == 5);
assert(pyramid.FindMaxSum() == 35);
path = pyramid.FindMaxSumAndPath();
assert(path.sum == 35);
assert(path.path == std::vector<int>({ 1, 3, 6, 10, 15 }));
}
}
public class DirectedGraphMaxPath {
public static void main(String[] args) {
NodeDAG n1 = new NodeDAG(3);
NodeDAG n2a = new NodeDAG(9);
NodeDAG n2b = new NodeDAG(4);
NodeDAG n3a = new NodeDAG(1);
NodeDAG n3b = new NodeDAG(8);
NodeDAG n3c = new NodeDAG(2);
NodeDAG n4a = new NodeDAG(4);
NodeDAG n4b = new NodeDAG(5);
NodeDAG n4c = new NodeDAG(8);
NodeDAG n4d = new NodeDAG(2);
List<NodeDAG> children = new ArrayList<>();
children.add(n2a);
children.add(n2b);
n1.children = children;
children = new ArrayList<>();
children.add(n3a);
children.add(n3b);
n2a.children = children;
children = new ArrayList<>();
children.add(n3b);
children.add(n3c);
n2b.children = children;
children = new ArrayList<>();
children.add(n4a);
children.add(n4b);
n3a.children = children;
children = new ArrayList<>();
children.add(n4b);
children.add(n4c);
n3b.children = children;
children = new ArrayList<>();
children.add(n4c);
children.add(n4d);
n3c.children = children;
solveMaxPath(n1);
}
public static void solveMaxPath(NodeDAG root) {
if (root == null) {
return;
}
int sum = 0;
int maxSum = 0;
List<NodeDAG> path = new ArrayList<>();
MaxPathSum mp = new MaxPathSum();
findMaxPath(root, sum, maxSum, path, mp);
printPath(mp.maxPath);
}
private static void printPath(List<NodeDAG> maxPath) {
for (NodeDAG nodeDAG : maxPath) {
System.out.print(nodeDAG.v + " ");
}
}
private static void findMaxPath(NodeDAG root, int sum, Integer maxSum, List<NodeDAG> path, MaxPathSum maxPathSum) {
if (root == null) {
return;
}
sum += root.v;
path.add(root);
if (sum > maxPathSum.max) {
maxPathSum.max = sum;
maxPathSum.maxPath = path;
}
if (root.children != null && !root.children.isEmpty()) {
for (NodeDAG nodeDAG : root.children) {
findMaxPath(nodeDAG, sum, maxSum, new ArrayList<NodeDAG>(path), maxPathSum);
}
}
}
}
class MaxPathSum {
int max;
List<NodeDAG> maxPath;
public MaxPathSum() {
this.max = 0;
this.maxPath = new ArrayList<>();
}
}
class NodeDAG {
int v;
List<NodeDAG> children;
public NodeDAG(int v) {
super();
this.v = v;
}
@Override
public String toString() {
return new Integer(v).toString();
}
}
The Dynamic programming solution offered has some limitations when the nodes are labeled with negative integers. If the nodes are negative then one solution might be to
change the sign of the nodes and search for the path with minimum value. As we have reversed the sign of the nodes, the path with least sum is infact the path with the maximum value of the original data.
public static int maxPath(Tree root){
HashMap<Tree, Integer> cache = new HashMap<Tree, Integer>();
return maxPath(root, cache);
}
public static int maxPath(Tree root, HashMap<Tree, Integer> cache){
if(root == null)
return 0;
if(cache.containsKey(root))
return cache.get(root);
int a = root.x + maxPath(root.l);
int b = root.x + maxPath(root.r);
cache.put(root, Math.max(a, b));
return Math.max(a, b);
}
Use dynamic programming, find max sum for each node and remember the value.
- runwithfullspeed February 19, 2016let MS(n) be the max sum for node n, then:
MS(n) = max(MS(child of n)) + value(n),
if n is leaf, NS(n) = value(n)
time complexity is depth of the tree * max_width of the tree