## Microsoft Interview Question for Junior programmers

• 0

Country: Israel
Interview Type: In-Person

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

Level-by-level printing modification with caching

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

``````class Node {
public int value;
public Node right;
public Node left;
}

int minLevel(Node root) {
if (root == null) return -1;
List<int> levelsums = calcLevelSums(root); // O(n)
retun levelWithMinSum(levelsums) + 1; // wc - O(n)
}

ist<int> calcLevelSums(Node root) {
List<int> levelSums = new ArrayList();

List<Tuple<int, Node>> nodesToProcess = new ArrayList();
nodesToProcess.put(new Tuple(0, root));

// extremely not balanced tree - O(n)
// balanced tree -
// leaves n/2, with reallocation: 1 + 2 + 4 + ... + n = 1 * (2 ^ log(n) - 1) / 2 = n
while (!nodesToProcess.isEmpty()) {
Tuple<int, Node> curr = nodesToProcess.delete(nodesToProcess.size()-1);
int level = curr.getX();
Node node = curr.getY();

int sum = levelSums.get(level) + node.value;
levelSums.set(level, sum);

if (node.left != null) {
nodesToProcess.put(new Tuple(level+1, node.left));
}
if (node.right != null) {
nodesToProcess.put(new Tuple(level+1, node.right));
}
}

return levelSums;
}

int levelWithMinSum(List<int> list) {
if (list == null || list.size() == 0) {
return Integer.MIN_VALUE;
}

int minInd = 0;
for (int i = 0; i < list.size(); i++) {
if (list.get(i) < list.get(minInd)) {
minInd = i;
}
}
return minInd;
}``````

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

We use BFS to scan the tree. We only need to keep track of the following:
- Current level being scanned
- Current level sum so far
- Min level found so far
- Min sum found so far

This solution has O(N) complexity with minimum space

``````#include "CommonHeader.h"

struct Node {
int value;
std::vector<Node*> children;
Node(int v, Node* parent = nullptr)
: value(v)
{
if(parent) {
parent->children.push_back(this);
}
}
};

std::pair<int, int> getMinSumLevel(Node* root)
{
std::queue<std::pair<Node*, int> > q; // node:level
q.push({ root, 1 });

int curlevel = 1;
int minLevel = 1;
int minSumSoFar = INT_MAX;
int curlevelSum = 0;
while(!q.empty()) {
Node* n = q.front().first;
int level = q.front().second;
q.pop();

if(curlevel != level) {
// we completed this level
if(curlevelSum < minSumSoFar) {
minSumSoFar = curlevelSum;
minLevel = curlevel;
}
curlevel = level;
curlevelSum = 0;
}
curlevelSum += n->value;
std::for_each(n->children.begin(), n->children.end(), [&](Node* child) { q.push({ child, curlevel + 1 }); });
}
return { minLevel, minSumSoFar };
}

void test_min_level_sum()
{
Node n01(50);
Node n11(6, &n01), n12(2, &n01);
Node n21(30, &n11), n22(80, &n11), n23(7, &n12);

std::pair<int, int> res = getMinSumLevel(&n01);
std::cout << "Level is: " << res.first << ", Sum: " << res.second << std::endl;
}``````

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

O(n + lg(n))
n ->getting the sum level wise
lg(n) - > getting the lowest sum level

Space - lg(n)

Interested in knowing if there are any better approaches....

``````public static void main(String[] args){

T N6 = new T(7, null, null);
T N5 = new T(80, null, null);
T N4 = new T(30, null, null);
T N3 = new T(2, N6, null);
T N2 = new T(6, N4, N5);
T N1 = new T(50, N2, N3);

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
max(N1, 1, map);
int level = 0;
int minsum = N1.val;
for(Map.Entry<Integer, Integer> entry: map.entrySet()){
int lvl = entry.getKey();
int sum = entry.getValue();
if(sum > 0 && sum < minsum){
minsum = sum;
level = lvl;
}
}
System.out.println("Level " + level  + " with sum = " + minsum);
}

public static void max(T node, int l, Map<Integer, Integer> map){
if(node == null)
return;

T left = node.left;
T right = node.right;

max(left, l+1, map);
max(right, l+1, map);

int sum = 0;
if(map.get(l) == null)
map.put(l, 0);
else
sum = map.get(l);

if(left != null){
sum += left.val;
map.put(l, sum);
}
if(right != null){
sum += right.val;
map.put(l, sum);
}

}

static class T{
int val;
T left;
T right;
int height;

public T(int val, T left, T right){
this.val = val;
this.left = left;
this.right = right;
}
}``````

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

Complexity - O(n + lg(n))
Space - lg(n)

Interested in some other better approaches...

``````public static void main(String[] args){

T N6 = new T(7, null, null);
T N5 = new T(80, null, null);
T N4 = new T(30, null, null);
T N3 = new T(2, N6, null);
T N2 = new T(6, N4, N5);
T N1 = new T(50, N2, N3);

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
max(N1, 1, map);
int level = 0;
int minsum = N1.val;
for(Map.Entry<Integer, Integer> entry: map.entrySet()){
int lvl = entry.getKey();
int sum = entry.getValue();
if(sum > 0 && sum < minsum){
minsum = sum;
level = lvl;
}
}
System.out.println("Level " + level  + " with sum = " + minsum);
}

public static void max(T node, int l, Map<Integer, Integer> map){
if(node == null)
return;

T left = node.left;
T right = node.right;

max(left, l+1, map);
max(right, l+1, map);

int sum = 0;
if(map.get(l) == null)
map.put(l, 0);
else
sum = map.get(l);

if(left != null){
sum += left.val;
map.put(l, sum);
}
if(right != null){
sum += right.val;
map.put(l, sum);
}

}

static class T{
int val;
T left;
T right;
int height;

public T(int val, T left, T right){
this.val = val;
this.left = left;
this.right = right;
}
}``````

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

@studip.innovates: I think you can place the summing up into the recursion at the start, thus you don't need to do it for left and right redundantly (not absolutely sure about Java syntax) which is neater.

``````public static void max(T node, int l, Map<Integer, Integer> map)
{
if(node == null) return;
Integer sum = map.get(l);
map.put(l, sum == null ? node.value : node.value + sum);
max(node.left, l+1, map);
max(node.right, l+1, map);
}``````

alternatively you can use a vector instead of a hashmap, but hashmap is more convenient to use here... vector would be faster, constant, same O(n) time complexity

alternative, do it without recursion, to spare the final step of stepping through the map/vector. note the different space requirements, the recursive code has (O(h), whereas the non-recursive and queue based solution has O(n), where n is the number of elements, and h is the height of the tree.

``````int minLevelSum(Node *root)
{
if(root == nullptr) return 0; // avoid endless loop below
size_t level = 1; // root is level 1 as "defined" in the question
int levelSum = 0; // current level's sum
int minLevelSum = numeric_limits<int>::max();
int minLevelSumLevel = 0;
deque<Node*> q({root, nullptr}); // just a queue, where null marks end of current level

while(true) { // last node is always nullptr
Node* node = q.back();
q.pop_back();
if(node == nullptr) {
if(levelSum < minLevelSum) {
minLevelSum = levelSum;
minLevelSumLevel = level;
}
if(q.empty()) break; // last level, stop here
q.push_front(nullptr); // levelseperator for next level
levelSum = 0; // start new level, sum  = 0
level ++;
} else {
levelSum += node->value_;
if(node->left_ != nullptr) q.push_front(node->left_);
if(node->right_ != nullptr) q.push_front(node->right_);
}
}
return minLevelSumLevel;
}``````

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

ES6 O(n) time and O(log n) space solution, assuming the binary tree is kind of balanced.

``````function helper(node, level, sumByLevel){
if (!node){
return;
}
if (!sumByLevel.has(level)){
sumByLevel.set(level, 0);
}
const levelSum = sumByLevel.get(level);
sumByLevel.set(level, levelSum + node.val);
helper(node.left, level + 1, sumByLevel);
helper(node.right, level + 1, sumByLevel);
}

function minSubLevel(root){
const sumByLevel = new Map();
helper(root, 1, sumByLevel);
let minSum = Number.MAX_SAFE_INTEGER;
let minLevel = null;
sumByLevel.forEach((sum, level) => {
if (sum < minSum){
minSum = sum;
minLevel = level;
}
});
return minLevel;
}

const root = {
val: 50,
left: {
val: 6,
left: {
val: 30,
left: null,
right: null
},
right: {
val: 80,
left: null,
right: null
}
},
right: {
val: 2,
left: {
val: 7,
left: null,
right: null
},
right: null
}
}

console.log(minSubLevel(root));``````

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

``````import java.util.ArrayList;
import java.util.List;

/*
Recursively descend into the tree. Pass a collector argument
that will store the sum for each level. Then find the minimum
level
*/
public class MinLevelSum {
public static void main(String[] args) {
Node n50 = new Node(50);
Node n6 = new Node(6);
Node n2 = new Node(2);
Node n30 = new Node(30);
Node n80 = new Node(80);
Node n7 = new Node(7);
//
n50.left = n6;
n50.right = n2;
n6.left = n30;
n6.right = n80;
n2.left = n7;

MinLevelSum work = new MinLevelSum();
List<Integer> list = new ArrayList<>();
work.findLevelSums(n50, 0, list);
System.out.printf("Min level= " + work.findMinLevelSum(list));
}

private static class Node {
Node left = null, right = null;
int data;

Node(int d) {
this.data = d;
}
}

void findLevelSums(Node n, int level, List<Integer> list) {
if (n == null) return;
while (list.size() - 1 < level)
list.set(level, list.get(level) + n.data);
findLevelSums(n.left, level + 1, list);
findLevelSums(n.right, level + 1, list);
}

int findMinLevelSum(List<Integer> list) {
int minLevel = -1, min = Integer.MAX_VALUE;
for (int i = 0; i < list.size(); i++)
if (min > list.get(i))
minLevel = i;
return minLevel;
}
}``````

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

``````public static int levelWithMinSum(Node root) {

int maxSum = Integer.MAX_VALUE;
int currentLevel = 0;
int maxLevel = 0;
int currentSum = 0;
while (!queue.isEmpty()) {
Node item = queue.poll();
if (item == null) {
currentLevel++;
if (currentSum < maxSum) {
maxSum = currentSum;
maxLevel=currentLevel;
}
currentSum = 0;
} else {

currentSum += item.value;

if (item.lelfChild != null) {
}
if (item.rightChild != null) {
}

}
}

return maxLevel;
}``````

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

My couple of cents in Java:

``````public class LevelWithMinimumSumOfBT {

static class Level {
private int levelId;
private long sumOfItems;

public Level(int levelId, long sumOfItems) {
this.levelId = levelId;
this.sumOfItems = sumOfItems;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder("Level: {");
sb.append("id = ").append(levelId);
sb.append(", sum = ").append(sumOfItems);
sb.append('}');
return sb.toString();
}
}

static class BNode {
private int id;
private BNode left = null;
private BNode right = null;

public BNode(int id) {
this.id = id;
}

public void setLeft(BNode left) {
this.left = left;
}

public BNode getLeft() {
return left;
}

public boolean hasLeft() {
return left != null;
}

public void setRight(BNode right) {
this.right = right;
}

public BNode getRight() {
return right;
}

public boolean hasRight() {
return right != null;
}
}

static Level getLevelWithMinimumSum(Map<Integer, BNode> tree, int root) {
long curSum = 0L;
long lowerSum = Long.MAX_VALUE;
int curLevel = 0;
int lowerLevel = -1;

int curLevelLength = queue.size();

while (!queue.isEmpty()) {
BNode curElement = queue.pollFirst();
curSum += curElement.id;

// To add child nodes is possible
if (curElement.hasLeft()) {
}

if (curElement.hasRight()) {
}

// To check is it end of the level or not
curLevelLength--;
if (curLevelLength == 0) {
curLevel++;
if (curSum < lowerSum) {
lowerSum = curSum;
lowerLevel = curLevel;
}
curSum = 0;
curLevelLength = queue.size();
}
}

return new Level(lowerLevel, lowerSum);
}
}``````

I did not include the main method in the snippet, but example of the launch is:

``````6
50
50 6 l
50 2 r
6 30 l
6 80 r
2 7 l
Level: {id = 2, sum = 8}``````

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

Simple Python solution

``````def minLevelSum(root):
q = Queue()
q.put(root)
minSum = float('inf')
curLevel, minLevel = 0, 0
while q.qsize():
tempList = []

for _ in range(0, q.qsize()):
curr = q.get()
tempList.append(curr.data)
if curr.left: q.put(curr.left)
if curr.right: q.put(curr.right)

if sum(tempList) < minSum:
minSum = sum(tempList)
minLevel = curLevel

curLevel += 1
return minLevel``````

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.