## Google Interview Question for Software Engineer Interns

Country: United States
Interview Type: Phone Interview

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

Use dynamic programming, find max sum for each node and remember the value.
let 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

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

Is that the min path from first node to last level? Are all numbers positive?

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

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.

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

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

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

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];
}

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

prev = curr;
}

return curr[0].Path;
}``````

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

Use bfs

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

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

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

Check the adjacent nodes to the node you are currently on and go to the max adjacent node and do this for every node you land on. As one person said, it would require bfs. Don't know why people are making it so complicated.

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

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

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

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

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

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

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

``````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<>();
n1.children = children;

children = new ArrayList<>();
n2a.children = children;

children = new ArrayList<>();
n2b.children = children;

children = new ArrayList<>();
n3a.children = children;

children = new ArrayList<>();
n3b.children = children;

children = new ArrayList<>();
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;

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

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

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.

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

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

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.