Mock interview experience

March 1, 2016

  Julia likes to document her first mock interview using C# on March 28, 2016. She got this question to be interviewed: BST Successor Search.

  Given a node n in a binary search tree, explain and code the most efficient way to find the successor of n.

Analyze the run time complexity of your solution.

How did Julia work out the problem with the help from the interviewer? 

Julia was nervous, so she did not think too much. Ask to discuss the successor. What is the successor? 

Then, she was told that a tree

   4

3   5

4' successor is 5, and 3's successor is 4. 

Julia should work on some test cases, and make complete understanding of algorithm first. 

But, she did not. 

She was told to write some code about it. Julia then asked to start from root node, and then, was told that Node class:

Class Node{

   Node left; 

   Node right; 

   Node parent; 

   int value; 

}

So, the function has to take argument node n - any node in the tree, instead of root node. 

code with bugs - work on simple BST: 

 4

3   5

4' successor is 5, and 3's successor is 4. 

https://github.com/jianminchen/AlgorithmsPractice/blob/master/BSTSuccessor_Step1.cs

And then, here are the conversations:
Interviewer: There will be more than 1 cases failing;
show a tree
       4
   2
       3

  3's successor is 4, not null. 2 is left child of 4, and then 3 is right child of 2. Go up to parents.

Julia: So, if we work on the following tree, will all bugs be fixed? 

                    4

              2          6

            1   3      5    7

Interviewer: 3's successor is 4, and 4's successor is 5, not 6. 
Julia: Ok, let me add two more functions to help. 

For node 3, the successor of 3 is 4.  // to fix bug, add function checkRelationship while retrieving grand parents. 
For node 4, the successor of 4 is 6. // to fix bug, add function called getLeftMostNode()

https://github.com/jianminchen/AlgorithmsPractice/blob/master/BST_Successor_Step2.cs


The interviewer asked Julia cleaned up the code, removed unnecessary variables, put return statement in while loop. 

At the end, the interviewer told that Julia was the best one; he interviewed 7 other people, maybe using the same question. Julia was so excited, motivated after hearing the feedback. Julia, she did write very clear, readable code, with logic perfect through mock interview. 

And then, Julia was asked the run time analysis. The balanced search tree, the run time is O(logN), but if it is not balanced, can be up to N. 

But, lessons learned:
1. Always work on test cases, discuss algorithm, make sure both agrees, then, start to write code; 
2. Work on simple test case, and then, extend the algorithm to fit the complicate case. 
3. Start from simple case, write code to make it work on simple case. 
    And then, discuss bugs, and fix the bugs with more functions. 
    It took 28 minutes to finish most of coding. 
4. Julia was too nervous, she could not think about successor clearly at the beginning. So, she asked to have some discussion about successor. Interviewer showed her one simple example. 


    Surprisingly, write in two steps, make the coding so easy.