Case study: 979. Distribute coins in binary tree

Jan. 31, 2019

Introduction

It is my mock interview lasting 100 minutes from 10:00 PM to 11:40 PM PST. I was so surprised since the interviewee is in eastern time zone, and start time is 1:00 AM EST. I like to write a case study on the mock interview

Case study

It is my favorite algorithm. I like to learn more about the algorithm through the mock interview. The interviewee has good education, very good communication skills, new graduate from top university, good job experience; I need to learn how to help and exchange ideas, make myself more helpful to contribute ideas.

We had very good discussion to explore the problem in depth after he solved the problem, tested the code with a test case.

I also review JavaScript programming language.

Here are interview in detail:
1. The discussion, ideas we discussed
2. JavaScript code with a test case
3. The discussion after the mock interview

I will come back with more detail.

	// JavaScript source code
	/**
	* Definition for a binary tree node.
	* function TreeNode(val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	*/
	/**
	* @param {TreeNode} root
	* @return {number}
	*/
	var distributeCoins = function(root) {
	let totalMoves = 0
	function getCoinsNeeded(node) {
	let leftCoinsNeeded = 0
	if(node.left) leftCoinsNeeded = getCoinsNeeded(node.left)
	let rightCoinsNeeded = 0
	if(node.right) rightCoinsNeeded = getCoinsNeeded(node.right)
	totalMoves += Math.abs(leftCoinsNeeded) + Math.abs(rightCoinsNeeded)
	return node.val + leftCoinsNeeded + rightCoinsNeeded - 1
	}
	getCoinsNeeded(root)
	return totalMoves
	};
	let Node = function(val) {
	this.val = val
	this.left = this.right = null
	}
	let A = new Node(1)
	let B = new Node(0)
	let C = new Node(0)
	let D = new Node(3)
	A.left = B
	A.right = C
	B.right = D
	console.log(distributeCoins(A))

view raw leetcode979DistributeCoinsBetweenBinarytree.js hosted with ❤ by GitHub

Here is more...

	//post order
	leftMoves = getMoves(left) // 1
	rightMoves = getMoves(right) // -1
	ownMoves = node.val === 0? -1 : node.val // wrong
	totalMoves = Math.abs(leftMoves) + Math.abs(rightMoves) // each node will be visted once - //moves from each edge
	return ownMoves + leftMoves + rightMoves // definition of recursive function
	Example 4:
	4
	/-2 -1\
	0 0
	\ -1
	0 -1 - should be the coins needed to move - recursive function +, -
	total moves -> absolution
	3 0 0 1
	1 2
	-> coins move -> piggyback -> node value calculation first
	take two steps:
	for example:
	left child - math.abs(child.val - 1)
	right child - math.abs(child.val - 1)
	how many coins we need to move
	determine the value of root node -> ?
	1 + 1 + new root value = root.val + left.val + right.val
	new root.val
	The above steps can be in recursive function - post order traversal

view raw Leetcode 979 Distribute coins between binary tree hosted with ❤ by GitHub

One thing both of us learned in the discussion is how to calculate each edge in the tree once. We count the traffic to transfer coins through each edge. We like to count each edge once, the pseudo code above will count some edge more than once.

Interviewee feedback

Interviewer feedback

More discussion

I shared my experience in the contest of 120, I had problems to come out the optimal solution. Where to start? I thought about finding a node with zero coin first, and then I need to find a node with extra coins in the tree, but in order to get minimum coins, I cannot just find any node with extra coins. This makes the problem hard to solve.

Secondly, I have math undergraduate degree. I know that we have to prove that the optimal solution using post order bottom up is minimum value. How to prove it?

We had discussion and that is the reason we took extra time to explore those topics.