## Google Interview Question for Java Developers

• 0

Country: United States

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

``````int max =0;

private static int[] maximumEvenSum(TreeNode node){
if(node == null)
return new int[]{0, 0};
if(node.left == null && node.right == null){
if(node.val % 2 == 0){
max = Math.max(max, node.val);
return new int[]{0, node.val};
} else{
return new int[]{node.val, 0};
}
}
int[] left = maximumEvenSum(node.left);
int[] right = maximumEvenSum(node.right);
int even = 0;
int odd = 0;
if(node.val % 2 ==  0){
even = Math.max(Math.max(left[1] + node.val, right[1] + node.val) , node.val);
odd = Math.max(Math.max(left[0] + node.val, right[0] + node.val) , 0);
if(even%2 == 0)
max = Math.max(even, max);
if((left[0] + node.val + right[0]) % 2 == 0)
max = Math.max(left[0] + node.val + right[0], max);
if((left[1] + node.val + right[1]) % 2 == 0)
max = Math.max(left[1] + node.val + right[1], max);
} else{
even = Math.max(Math.max(left[0] + node.val, right[0] + node.val), 0);
odd = Math.max(Math.max(left[1] + node.val, right[1] + node.val) , node.val);
if(even%2 == 0)
max = Math.max(even, max);
if((left[0] + node.val + right[1]) % 2 == 0)
max = Math.max(left[0] + node.val + right[1], max);
if((left[1] + node.val + right[0]) % 2 == 0)
max = Math.max(left[1] + node.val + right[0], max);
}
left[1] = even;
left[0] = odd;
return left;
}``````

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

My idea is to keep track of max even sum and max odd sum of the paths going through a particular node. O(N) time, O(log N) space (in case of a balanced tree).

``````#include <iostream>
#include <vector>

using namespace std;

class Node {
public:
Node(int val)
{
val_ = val;
left_ = right_ = NULL;
}
int val_;
Node *left_, *right_;
};

class Sums {
public:
Sums(int even, int odd)
{
e_ = even;
o_ = odd;
}
int e_;
int o_;
};

Sums MaxSums(Node *n, int &max_e_sum)
{
Sums out(0, 0);
if (n) {
Sums l_max_sums = MaxSums(n->left_, max_e_sum);
Sums r_max_sums = MaxSums(n->right_, max_e_sum);

vector<int> sums = {
l_max_sums.e_ + n->val_,
l_max_sums.o_ + n->val_,
r_max_sums.e_ + n->val_,
r_max_sums.o_ + n->val_,
l_max_sums.e_ + r_max_sums.e_ + n->val_,
l_max_sums.e_ + r_max_sums.o_ + n->val_,
l_max_sums.o_ + r_max_sums.e_ + n->val_,
l_max_sums.o_ + r_max_sums.o_ + n->val_
};

for (int i = 0; i < 4; ++i) {
int sum = sums[i];
if (sum % 2 == 0) {
out.e_ = max(out.e_, sum);
max_e_sum = max(max_e_sum, out.e_);
} else {
out.o_ = max(out.o_, sum);
}
}

for (int i = 4; i < sums.size(); ++i) {
int sum = sums[i];
if (sum % 2 == 0) {
max_e_sum = max(max_e_sum, sum);
}
}
}

return out;
}

int main()
{
/*
10
/    \
2      5
/  \      \
1   101    13
*/
Node n10(10), n2(2), n5(5), n1(1), n101(101), n13(13);
n10.left_ = &n2;
n10.right_ = &n5;
n2.left_ = &n1;
n2.right_ = &n101;
n5.right_ = &n13;

int max_e_sum = 0;
MaxSums(&n10, max_e_sum);
cout << max_e_sum << "\n";
}``````

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

``````pair<int,int> maxarray(node * root, node * ref){
if(root==NULL) return pair<int,int>(0,0);
// general case
pair<int,int> fromleft = maxarray(root->left,ref) + root->value;
pair<int,int> fromright = maxarray(root->right,ref) + root->value;
int myself = root->value;
// root case
if(root==ref){
vector<int> ret;
ret.push_back(fromleft.first+fromright.first+root->value);
ret.push_back(fromleft.first+fromright.second+root->value);
ret.push_back(fromleft.second+fromright.first+root->value);
ret.push_back(fromleft.second+fromright.first+root->value);
return pair<int,int>(0,findmax(ret,1));
}
// find even most and odd most from these
vector<int> odds;
vector<int> evens;
return pair<int,int>(findmax(odds,0),findmax(evens,0));``````

}

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

int max =0;

private static int[] maximumEvenSum(TreeNode node){
if(node == null)
return new int[]{0, 0};
if(node.left == null && node.right == null){
if(node.val % 2 == 0){
max = Math.max(max, node.val);
return new int[]{0, node.val};
} else{
return new int[]{node.val, 0};
}
}
int[] left = maximumEvenSum(node.left);
int[] right = maximumEvenSum(node.right);
int even = 0;
int odd = 0;
if(node.val % 2 == 0){
even = Math.max(Math.max(left[1] + node.val, right[1] + node.val) , node.val);
odd = Math.max(Math.max(left[0] + node.val, right[0] + node.val) , 0);
if(even%2 == 0)
max = Math.max(even, max);
if((left[0] + node.val + right[0]) % 2 == 0)
max = Math.max(left[0] + node.val + right[0], max);
if((left[1] + node.val + right[1]) % 2 == 0)
max = Math.max(left[1] + node.val + right[1], max);
} else{
even = Math.max(Math.max(left[0] + node.val, right[0] + node.val), 0);
odd = Math.max(Math.max(left[1] + node.val, right[1] + node.val) , node.val);
if(even%2 == 0)
max = Math.max(even, max);
if((left[0] + node.val + right[1]) % 2 == 0)
max = Math.max(left[0] + node.val + right[1], max);
if((left[1] + node.val + right[0]) % 2 == 0)
max = Math.max(left[1] + node.val + right[0], max);
}
left[1] = even;
left[0] = odd;
return left;
}

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

``````It should be post order traversal with below way of cal

If leaf
=>Item: odd
.      Return ( 0, value)
=> item : even
.      Return ( value, 0)

If not leaf
=> item even
// through both child's creating max subtree
.    max = MAX ( max, MAX(left.even+ right.even, left.odd+ right.odd) + value)

return (
even-> MAX ( MAX ( left.even, right.even) + value, value),
odd ->( left.odd, right.odd) + value )
)

=> item odd
// through both child's creating max subtree
.    max = MAX ( max, left.odd +  right.odd + value)

return (
even-> ( left.odd, right.odd) + value),
odd -> MAX ( left.even, right.eve) + value, value )
)

if any situation the value at odd position is even, then put 0 instead
Like tree
6 here even sum is not possible (6+2 = even, 6+4= even, 2+4+6 = even) not possible odd sum( 10,0)
2  4

Same for even.``````

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

Logic drive from simple math;
odd + odd = even
odd + even = odd
even + even = even
0 + even = even
0 + odd = odd

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.