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.