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

- ChrisK December 14, 2016 | Flag Reply
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);

}

- Avinash Kumar December 14, 2016 | Flag Reply
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]};
		}

- Vidhya December 31, 2016 | Flag Reply
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]))

- ketaki November 27, 2017 | Flag Reply
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]))
}}

- Anonymous November 27, 2017 | Flag Reply
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])

- keta.thatte November 27, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More