Microsoft Interview Question Junior programmers
Country: Israel
Interview Type: In-Person
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;
}
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;
}
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;
}
}
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;
}
}
@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;
}
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));
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.add(0);
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;
}
}
public static int levelWithMinSum(Node root) {
Queue<Node> queue = new LinkedList<>();
int maxSum = Integer.MAX_VALUE;
queue.add(root);
queue.add(null);
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;
if(queue.peek()!=null)queue.add(null);
} else {
currentSum += item.value;
if (item.lelfChild != null) {
queue.add(item.lelfChild);
}
if (item.rightChild != null) {
queue.add(item.rightChild);
}
}
}
return maxLevel;
}
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;
LinkedList<BNode> queue = new LinkedList<>();
queue.add(tree.get(root));
int curLevelLength = queue.size();
while (!queue.isEmpty()) {
BNode curElement = queue.pollFirst();
curSum += curElement.id;
// To add child nodes is possible
if (curElement.hasLeft()) {
queue.addLast(curElement.getLeft());
}
if (curElement.hasRight()) {
queue.addLast(curElement.getRight());
}
// 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}
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
Level-by-level printing modification with caching
- lalka October 10, 2017