Microsoft Interview Question for Junior programmers


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

- lalka October 10, 2017 | Flag Reply
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;
}

- sandak October 10, 2017 | Flag Reply
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;
}

- PenChief October 11, 2017 | Flag Reply
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;
    }
  }

- Anonymous October 11, 2017 | Flag Reply
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;
    }
  }

- sudip.innovates October 11, 2017 | Flag Reply
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;
}

- ChrisK October 12, 2017 | Flag Reply
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));

- Anonymous October 12, 2017 | Flag Reply
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.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;
    }
}

- Makarand October 15, 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