Mock interview: 1080 Insufficient Nodes in Root to Leaf Paths

July 15, 2020

Introduction

The interviewee is Microsoft SDE II with two years experience, his performance on this algorithm is super talent level. It took him less than 20 minutes, and I ran through Leetcode online judge. It passed all test cases.

Case study

Here is the gist including source code. I will write a short case study on Leetcode discuss post.

	import java.io.*;
	import java.util.*;
	class Solution {
	public static void main(String[] args) {
	ArrayList<String> strings = new ArrayList<String>();
	strings.add("Hello, World!");
	strings.add("Welcome to CoderPad.");
	strings.add("This pad is running Java " + Runtime.version().feature());
	for (String string : strings) {
	System.out.println(string);
	}
	}
	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode() {}
	* TreeNode(int val) { this.val = val; }
	* TreeNode(int val, TreeNode left, TreeNode right) {
	* this.val = val;
	* this.left = left;
	* this.right = right;
	* }
	* }
	*/
	/*
	460 -
	null dfsHelper(a 0 - 1)
	/ \
	null null
	*/
	public TreeNode sufficientSubset(TreeNode root, int limit) {
	if (root == null) return root;
	return dfsHelper(root, 0, limit);
	}
	private TreeNode dfsHelper(TreeNode root, int prevTotal, limit) {
	// base case at leaf node
	if (root.left == null && root.right == null) {
	return (prevTotal + root.val < limit) ? null : root;
	}
	// now recursion going left first then right
	if (root.left != null) {
	// creative -
	root.left = dfsHelper(root.left, prevTotal + root.val, limit);
	}
	if (root.right != null) {
	root.right = dfsHelper(root.right, prevTotal + root.val, limit);
	}
	return root.left == null && root.right == null ? null : root;
	}
	}
	/*
	Given the root of a binary tree, consider all root to leaf paths: paths from the root to any leaf. (A leaf is a node with no children.)
	A node is insufficient if every such root to leaf path intersecting this node has sum strictly less than limit.
	Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.
	test case 1:
	1
	/ \
	-99 -99
	limit is 1, return null
	test case 2:
	10
	/ \
	5 10
	limit = 21, return null
	test case 3:
	1i
	/ \
	i 2 -3 i
	/\ /
	inul 1i 4 limit = -1
	return:
	1
	/ \
	2 -3
	\ /
	1 4 limit = -1
	The given tree will have between 1 and 5000 nodes.
	-10^5 <= node.val <= 10^5
	-10^9 <= limit <= 10^9
	public TreeNode sufficientSubset(TreeNode root, int limit) {
	}
	*/

view raw SufficientPathTreeAlgo.java hosted with ❤ by GitHub

Continue

Comparison

It is so challenge for me to accept the truth. The interviewee is SDE II with two years experience. He did share his experience to work on books cracking coding interview and also elements of programming. 

His idea is very creative, and efficient. The recursive function design is to meet the requirement directly. Do not work around the problem. 

The interviewee works on preparation of so many interviews. It is true that they all get so many experience on interviews. The companies are Amazon, Facebook, Tik Tot, Square, Box.