Bloomberg LP Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Use spiral level order traversal technique.
Take two sum varialbe oddSum and evenSum and two stacks s1 and s2.
Take one boolean variable evenLevel.
java code is below:
public int maxAmountRob(BTNode<T> node) {
if (node == null) {
return;
}
Stack<BTNode<T>> stack1 = new Stack<>();
Stack<BTNode<T>> stack2 = new Stack<>();
stack2.push(node);
boolean levelFlag = false;
int oddSum=0;
int evenSum=0;
while (!(stack1.isEmpty() && stack2.isEmpty())) {
BTNode<T> currentNode;
if (levelFlag) {
while (!stack1.isEmpty()) {
currentNode= stack1.pop();
oddSum+=currentNode.getData();
if(currentNode.getLeft() != null){
stack2.push(currentNode.getLeft());
}
if(currentNode.getRight() != null){
stack2.push(currentNode.getRight());
}
}
levelFlag = false;
} else {
while (!stack2.isEmpty()) {
currentNode= stack2.pop();
evenSum+=currentNode.getData();
if(currentNode.getRight() != null){
stack1.push(currentNode.getRight());
}
if(currentNode.getLeft() != null){
stack1.push(currentNode.getLeft());
}
}
levelFlag = true;
}
}
return Math.max(oddSum,evenSum);
}
I used normal post-order traversal with a method parameter indicating the level.
public static int maxLevelSum(TreeNode root){
int[] sums = getSums(root, 0);
return Math.max(sums[0], sums[1]);
}
public static int[] getSums(TreeNode node, int level){
int[] res1 = new int[2];
int[] res2 = new int[2];
if (node.left != null)
res1 = getSums(node.left, level+1);
if (node.right != null)
res2 = getSums(node.right, level+1);
if (level %2 ==0){
return new int[]{res1[0]+res2[0], res1[1]+res2[1]+ node.val};
}
else{
return new int[]{res1[0]+res2[0] + node.val, res1[1]+res2[1]};
}
Python Solution:
def maxLevelSum(root,EvenOrOdd,sumation):
if root == None:
return max(sumation[0],sumation[1])
else:
if EvenOrOdd == True:
sumation[0] += root.val
else:
sumation[1]+= root.val
maxLevelSum(root.left,not EvenOrOdd,sumation)
maxLevelSum(root.right,not EvenOrOdd,sumation)
return max(sumation[0],sumation[1])
print(maxLevelSum(tr,True,[0,0]))
{{
def maxLevelSum(root,EvenOrOdd,sumation):
if root == None:
return max(sumation[0],sumation[1])
else:
if EvenOrOdd == True:
sumation[0] += root.val
else:
sumation[1]+= root.val
maxLevelSum(root.left,not EvenOrOdd,sumation)
maxLevelSum(root.right,not EvenOrOdd,sumation)
return max(sumation[0],sumation[1])
print(maxLevelSum(root,True,[0,0]))
}}
def maxLevelSum(root,EvenOrOdd,sumation):
if root == None:
return max(sumation[0],sumation[1])
else:
if EvenOrOdd == True:
sumation[0] += root.val
else:
sumation[1]+= root.val
maxLevelSum(root.left,not EvenOrOdd,sumation)
maxLevelSum(root.right,not EvenOrOdd,sumation)
return max(sumation[0],sumation[1])
I assume it's a level order traversal where you build two sums, one of even levels and one of odd. levels
I used a nullptr as a marker element to seperate levels in the queue, tiny trick is to ensure the termination
works.
- Chris December 14, 2016