Showing posts sorted by date for query find largest smaller BST key. Sort by relevance Show all posts
Showing posts sorted by date for query find largest smaller BST key. Sort by relevance Show all posts

Monday, May 21, 2018

Good programmer needs friends

May 21, 2018

Introduction


I could not believe that I got contacted by a few friends I made over mock interview practice last 12 months this long weekend. The work they did for me are touching my heart.

I am more open and confident. I first purchased my video course on udemy.com and also I purchased grokking system design interview course.

I still remembered that one of UCLA students gave me mock interview comment, stubborn, do not take hint less than six months ago. I worked on the algorithm called Largest smaller key in BST. 


Most challenge work 


Today I also like to write down for a small research topic called most challenge work I have done. If it is not challenge enough, I will find another one. I will try a few times until it is really challenge one. 

I had a holiday break today, and then I invited my friend to chat with me. I was trying to relax and have some reading work to do before I work on my home work from my coach. I did not do very well on my last mock interview, I practiced over ten times on word count engine algorithm. The coach gave me similar question, but he likes me to show very good coding as well with optimal space complexity. 

I do believe there are a lot of benefit to join one community or another one in order to help to build a good career in software industry. But I do think there is something missing in normal business practice. I also try to experience and tell that. Do your current job very well. Make your current employer happy. 

Counter argument is that if you can get a job with double salary why you choose to work on the less one. But in reality, only less than six percent will be selected after phone screen and onsite screening. Most of us are still working on daily job as usual. 

Another thing is how to embrace the hard work. I do see my weakness to solve simple and medium algorithm, since I like to solve advanced ones or hard level on Hackerrank, I notice that it is easy to get excited and continuously try to solve one, 10 hours to solve one algorithm scoring one with score zero. No complaint and also I was so happy to have pushed myself so hard on submitting all kinds of ideas against online judge of Hackerrank. 

I have worked with my coach last past week, I understood that he must have put hundreds of hours to complete Leetcode over 600 algorithms. I could not do it for all kinds of reason. I also like to get reality what weakness I have once a while. 


Try to answer this way



My most challenge work I like to do is to make my current job very easy and relax. 

It is not easy for several reasons right now. I have to learn so many things but I like to get good at foundations which are computer science data structure and algorithm.



Find best coach 


I practice so many mock interviews and meet a lot of people. One day I was so amazed that the peer performed so well since I could not fail him after I gave more than four algorithms. After more than 90 minutes talk, I knew that I may find a coach for myself.  


After more than four months, I contacted the graduate student and ask his help to be a coach and hitting partner to practice algorithm and data structure. The coach has practice over 600 Leetcode algorithms. 


Work with the coach


It is not easy to work with the coach and come out the good result in three weeks short time. We have to work together enough time before we can trust the coach and player relationship will work very well.


Why it is most challenge work? 


First I have to understand why I need a coach. I learn it from tennis sports last few years. 

By observing how professional tennis players prepare for China open in Beijing, I learn how professional tennis players develop relationship with each other and also with coaches and hitting partner, personal assistants. 

I need a coach this time for three weeks preparation. Why I need a coach? I try to get more educated and well-prepared. I like to beat the odds against 80% with more dedicated training. 

My coach can help me think about more in terms of algorithm and data structure. And I like to find out my weakness and learn something from the coach's experience. 


Tuesday, December 19, 2017

Leetcode 20: Valid Parentheses (II)

Dec. 19, 2017


Introduction


It is very hard challenge to plan what to study and what to review in this holiday season. Specially I will have a holiday break in the last week of December.

On Dec. 18, 2017, I practiced the mock interview, and then the peer worked on the valid bracket algorithm. The peer is a young undergraduate student who just started his computer science degree in university of Washington, top ranking computer science. The peer just started this year.

What advice can I give to the peer? I was asked by the peer.

I knew that it takes some time to develop the mock interview skill. But it is good to take the hint, and also follow the peer's idea. I was stubborn before on one mock interview when I met a computer science undergraduate from UCLA, and I learned the lesson on this algorithm called the largest smaller key in BST. I explained the idea to follow the hint to the peer.

Addition to mock interview 


It is a good idea to extend the algorithm for the mock interview algorithm. For bracket match algorithm, there are a few algorithms from Leetcode. I reviewed one of them called Leetcode 20: Valid Parentheses, and then I like to write down my review one by one.

Here is the blog I chose to study in January 2016, I also created a gist for the blog. The blog author wrote 170 blogs in Chinese, and he wrote very well. And also I found out that the blog Ethan Li 的技术专栏was written in 2015, now the peer works for snapchat, a facebook company.

I did great job for myself today, find 170 blogs to read related to algorithm, analysis and very nice readable code. It is hard for me to keep learning new algorithm while taking mock interview every week day 10:00 PM. It is better for me to read a lot of coding blogs, and reduce time on wechat related to social stuff.

I will choose five algorithm written by the engineer, and then write a blog for each algorithm.

Sunday, December 10, 2017

Binary search tree search from root to leaf node

Dec. 10, 2017

Introduction


It is the great learning experience for me to do mock interview tonight at 10:00 PM. I met an architecture tonight, the peer showed me how to write correct code first, and then reminded me to write optimal code as well. The search in binary search tree can turn left and then turn right and then turn left, but invariant is that the path is from root to leaf node, and the answer is always found until the leaf node is reached.

Code study


I practiced this algorithm so many times, last time I wrote a blog about the experience one month ago. Here is the blog.

Today I solved the problem with the help of the peer.

There are two bounds to work on. One is the lower bound value which is smaller than given value, and then the other one is upper bound which is smaller than given value. In order to find the upper bound, we are looking for the first value which is bigger than given value first, and then find a smaller value until one is found. Then we are sure that we are find the upper bound value.

In my previous practices, the upper bound value should be searched in two directions, go right to find bigger value, and then go left to find smaller value.

Feedback is encouraging


Follow up 


Dec. 13 ,2017

Finally I have time to come out a test case to illustrate the search, and the steps are left and right and left and right and left.

Here is the binary search tree, given value 7, the largest smaller BST key should be 6. How to find the node with value 6?

Start from root node with value 10, and then visit every node in the above tree, and visit the leaf node with value 6, and the answer is 6.

Monday, November 6, 2017

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. 

Sunday, September 3, 2017

Being an interviewer: Find largest smaller binary search tree key

September 3, 2017

Introduction


It is the great learning experience to watch a 2nd undergraduate student to perform the algorithm. The peer did very well on the analysis, but the execution of the algorithm is kind of weak. I need to step in and ask a good question about the iterative solution.

Evaluation 


This is the first time I show my evaluation as an interviewer. It is such a great activity that I meet a new person and also help the peer to learn an algorithm.

I still remembered that back to 2006 I applied the instructor job in united states, I was afraid to write and speak out, and I did send out over 20 applications.

Now it is so natural to watch how an undergraduate learns the algorithm through various channels outside the university. And I am glad to be part of the process.

I like to learn an algorithm similar to Leetcode 230: Kth smallest element in BST. Also I like to build experience around the algorithm with great reward experience to be part of mocking interview.

Here is the review I got after the mocking interview:


Actionable Item



After the mocking interview, I felt that the peer is not very competitive player. But I learned through his analysis, his calmness and his idea to continue to search right node for bigger value in order to get largest one is very clear and correct. 

I felt pressured that second year undergraduate student will master the algorithm in such a quick pace, how I should do in order to compete? Just be their friends. 

Next time I should copy the peer's code, and analyze the code later.