It is a good journey

Dec. 25, 2017

Introduction

It is the good journey for me to take first 6 interviews as the interviewer, and I got first 6 rating with full score 5 as an interviewer. In order to do that, I had to be super patient to the beginner of mock interview, and extend the algorithm to challenge the strong player. To overcome technical difficulty on mock interview platform, I used two times to get audio outside mock interview platform, 2.5 hours using wechat with a Chinese, one hour using Microsoft skype with a professional.

Let us take easy, and look at the performance below. Da Da Da, I made it as I chose to be, an advanced interviewer.

Extended algorithm

Here is the leetcode link for the extended algorithm for mock interview on 10:00 PM Dec. 26, 2017.

What I like to do is to write down my talk as an interviewer to help the peer, give the hint and encouragement to solve the problem.

I like to use this talk to encourage myself to be a lazy programmer, and always delegate the task and do as little as possible in terms of writing code.


Before I write the story let us look at the binary search tree, and talk about a few test cases first.

Test case 1: Given value 25, how to find the successor null?

Test case 2: Given value 14, how to find the successor 20?

Assume that I am very lazy, try to solve as little as possible, find a most simple task first for the algorithm. 

Given the node is the same as the root node. What is the successor? 

It should be the root node's right subtree's minimum node. It does not matter if the root node has right child or not. We can just delegate the task to the right child, using one recursive call. 

In other words, we are saying that the left subtree all nodes in the tree are smaller than given value, it is impossible to find root node's successor in left subtree. The root node itself cannot be the candidate. 

Next step, what if we relax the condition, root node's value is not bigger than given node's value? We apply the same logic. 

Now go to next test case. Given value 14, how to find the successor 20? 

Since the root node's value is bigger than given node's value, the root node can be the successor or after the successor in the list of nodes based on inorder traversal. 

Let us delegate the task to its left child, ask the return of successor. If the successor is not existed in the left subtree, then root node is the successor. 

Follow up 

Dec. 26, 2017 9:59 AM

Actually the extend algorithm is a binary search algorithm. To search binary search tree inorder successor given two nodes, root node and given node, what we need to do is to handle base case. 

If the root node is null, then return null. The most challenge part is when to return root node as a successor. Given the above tree, root node is 20, only when given node is 14, the successor is root node 20. How can we tell that it is 20?

Get connected

Give some feedback about mock platform. Maybe there are too many traffic for video and audio, my peer asked me if it is always like this. I told him that I did a few time, get audio no video from wechat or facebook or skype. 

Special case of Leetcode 230: Kth Smallest Element in a BST

Nov. 6, 2017

Introduction

It is the hard level algorithm called Kth smallest element in BST. When k value is one, the problem can be called to find largest smaller element in a binary search tree given the number.

It is very good discussion with the peer how to write an iterative solution. I did write down the code using C# and then I have to figure out how to get good rating from the peer.

Here is the C# practice code. I added main function after the mock interview.

Code review 

Here is the evaluation I got. I need to learn how to work with the peer, and follow the hint better.

Follow up 

Nov. 7, 2017
I found a bug in my code, the null pointer exception on line 35:
while(currentNode.right.key < num)


Here is the fix, C# code is here. currentNode.right == null is added to line 41. ( * bug fix No. 1*)

Nov. 10, 2017 11:44 PM

I finally figured out the thing I did wrong in my last mock interview. The code I wrote in Nov. 6 is wrong, and also the fix of bug on Nov. 7 ( * bug fix No. 1*) is also wrong. I finally understood that I was too stubborn and did not take the advice in mock interview.


Also the above code will not work for the following binary search tree:

Given the value 11, largest smaller BST key's value should be 10, but the solution will return 8 instead. Also the above code has null pointer run time exception on line 36, currentNode's right child may be null pointer, need to put a guard clause to check currentNode.right != null.


Nov. 10, 2017
11:19 PM
I had 10:00 pm mock interview, the peer worked on the algorithm. I had chance to find my problem based on the following test case. Great thanks for the peer, who is very patient, and think about the test case carefully.

Given number 11, the largest smaller BST key is 10. How to find node with value 10?   

First, start from root node with value 19, 19 is bigger than 10, so go to its left child. Left child value is 8 and it is smaller than 11, then set the value to look for (denote as LargestValue) as 8. And go to its right child to search. The node's value is 11 which is not smaller than 11, then go to left child 10, and set LargestValue = 10. Node 10 is leaf node without any child. 10 is the answer. 

In other words, find smaller one, go right; find bigger one, then go left. Until the traverse reaches the leaf node. Left, right, left. 

Woman's CodeSprint 2 - Minimum Loss - after the contest (series 2 of 10)

Nov. 20, 2016

Julia worked on the algorithm in the contest, and then solved the algorithm with full score - 35.

Here is the problem statement:

https://www.hackerrank.com/contests/womens-codesprint-2/challenges/minimum-loss

Julia's C# solution:

https://gist.github.com/jianminchen/af474846d81b96f4e70fc1a5866dca15

The ideas used in the algorithm:

Use bucket sort similar idea to go through each bucket, compare to previous if the current is less than minimum loss 

or not. Each bucket keeps the two value - max/ min value.

Study all other submissions using C++, Java, C#, JavaScript:

Actionable Items:

1. Read the code line by line, word by word; train myself to understand the code, by reading, by association 

with C#.

2. Study TreeSet - Java - class - memorize all the API, compared to C# Hashset

https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

My favorite Java code:
https://gist.github.com/jianminchen/3fce12eff5838fa10bff0792547d0779

A small research - TreeSet in Java is implemented as Binary search Tree?
http://stackoverflow.com/questions/4430809/making-binary-search-tree

Find the best solution written in Java:

Discussion of Time Complexity:

1. Brute force solution - O(n^2), choose any two year to compare the price. Will time-out!

2. Using Binary search - therefore, it is easy to find the minimum price, O(nlogn)
Maintain a binary search tree!

Study this C# solution using Binary search tree:

https://gist.github.com/jianminchen/c910f5d1f37309c70b489e6c75b0678c

line 16, 25 are Julia's favorite code - 

Very classical solution using binary search tree, and very clever solution.

Memorize the solution. Warm up the solution sometimes in the future.

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.