Bloomberg LP Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

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.

``````int maxLevelSum(Node *root)
{
queue<Node*> q;
q.push(root);
q.push(nullptr);
int level = 0;
int sums[2]{0, 0};
while(q.size() > 0)
{
Node *current = q.front(); q.pop();
if(current == nullptr)
{
level ^= 1;
if(q.size() > 0) q.push(nullptr);
continue;
}
sums[level] += current->value;
if(current->left != nullptr) q.push(current->left);
if(current->right != nullptr) q.push(current->right);
}
return max(sums[0], sums[1]);
}``````

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

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

}

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

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

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

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

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

{{
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]))
}}

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

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

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.