Find height of tree - My third mock interview given by my coach

May 17, 2018

Introduction

It is my third mock interview this 8:00 AM. I had very good learning experience in mock interview. I started to learn how to communicate better to work with my coach. He also started to think about helping me to work hard to find bugs in my code.

Mock interview

Here is my transcript. I will write C# code with some test cases, and also try to use recursive function to get node's level of tree for each node starting from 0 as root node.

Coach's advice

Through the mock interview, I was told that there are several issues on my iterative solution. I made a few mistakes. And then I was told to think recursively. If the current node depends on parent's node in terms of height calculation, then it is better to write a recursive solution.

Here is recursive solution I wrote after the mock interview.

I still could not believe that I made a few mistakes, and even I used Visual Studio debugger to help me to troubleshoot the issue. I missed the line 115 to assign value to heightIds[index].

Iterative solution is hard to think

I spent over 30 minutes to write and debug the code, I had to fix my thinking process ending up nothing is calculated. I missed the base case when the node has parent with value -1, then the node's height is one.

Here is iterative solution in C#.

From the performance of this algorithm in the mock interview, I learned the lesson to write an iterative solution correctly is not easy at all. So many bugs and even I write using Visual studio I keep finding issues.

A few places to be corrected after the mock interview:

1. base case: line 126 - line 128
2. line 139, I like to break the list iteration as soon as possible. Make sure that only uncalculated nodes are visited.

I think that the solution may also be broken the time complexity O(N). It is hard to write iterate a solution.

Lesson learned

Think recursively, think memorization. Try to cut time to O(N) linear time.