Case study: longest univalue path

Jan. 22, 2019

Introduction 

It is another 60 minutes discussion about algorithm longest univalue path. I was an interviewer on interviewing.io and the algorithm is longest univalue path.

Case study

Here is the example we worked on together.

Here is my feedback:

I work on the algorithm with over 20 interviewee right now. I learn one way to approach the problem and it should take me less than 15 minutes to solve it right now.

The fact I learned is the following:

I failed to solve the similar problem in weekly contest 120 distribute coins in binary tree, and I spent over 36 minutes in Jan. 19 2019.

Steps to shorten the time to 15 minutes

Using post order traversal, bottom up. It is a good idea to mark the path using number next to each node, and the number can be solved using recursively.

First step is to work on straight path, not cross path. From any node as a root node to the leaf node longest univalue path.

Second step is to calculate the cross node path.

Feedbacks

Here is the interviewee's feedback:

It took us more than 60 minutes to reach a final solution, and the code is still under investigation. One of ideas to improve for me as an interviewer is to bring the interviewee into discussion how to hack solution in quick and easy way.

The interviewee tried a few ideas but none of them worked. Even though the code passed a few test cases. I ask why it is plus one in one statement, I ask where is the statement to add two path together in the code.