Case study: hard level algorithm my post ranks top 7

Oct. 9, 2019

Introduction

It is the time for me to review my achievements. I did not get really big progress in terms of problem solving in 2019. I did get back into stock market, and put my 401 K and IRA back into stock market this April, and I went to onsite interview from Fortinet in May, and then prepared onsite for Amazon and Facebook in August, I had phone screen from Docusign in September. I learn slowly to adapt the challenge to advance myself. Today I like to talk about something new, my post ranks top 7 - a hard level algorithm.

Case study

I did not notice that I wrote a post, since I did not add it to my github repository Leetcode page six month ago.

Here is the image to show my ranking.

Here is the link.

How to write an excellent post?

I think that it is not difficult to write an excellent post. The algorithm I studied is so easy to understand, since I put together some comment to make it so straightforward.

And also I did spend time to save a graph from weekly contest lead board, and then wrote down my observation.

It is so important for me to learn how to document good learning process for other players.

Being a good mentor, helper, or player, I strive to document my practice, my learning, and then I have chance to meet more people in the world. I do believe that it takes so much time for me to learn and master one algorithm. I also certainly like to see people advance skills quickly. I always like to be one of players, share and learn, learn and then share.

Find minimum cost from top left corner to bottom right corner

May 13, 2018

Introduction

It is the algorithm to find the minimum cost from a matrix top left corner to bottom right corner.

Transcript

Here is my work in the mock interview. The interviewer told me that I should write the code after the mock interview, give him to review the code for next mock interview.

My next mock interview will be in Tuesday.

Mock interview 

Learning algorithm is such great experience. It is so much fun to work with a young graduate student around twenty five years old. He was very kind and also very encouraging. I spent first 5 to 10 minutes to think and communicate with the interviewer depth first search, compared to breadth first search. And then he kept asking me how you can improve the algorithm compared to depth first search. He did more than two times.

I finally came out the idea to use dynamic programming algorithm. Even though I have practice Deletion distance algorithm over 20 minutes last 12 months. But I still miss some dots to come to dynamic programming algorithm.

Arguments

I like to write down a few words about my analysis using depth first search is not optimal.

First, the algorithm is to find the minimum cost. There is no need to find actual path. Using depth first search of course takes extra effort to find path from source to destination.

The question is to ask minimum cost. I should quickly related to deletion distance.

I will do some research and figure out how I can come out dynamic programming algorithm without hints by the interviewer.

I have weakness to come out dynamic programming solution at the first place today.

Assignment

The interviewer told me to show him the code I write and he will give me some review next mock interview.

Follow up 

May 14, 2018
It is the algorithm called Leetcode 64: Minimum Path Sum.

I was asked if I worked on the problem before. I said that I did not. But actually I thought about the hackerrank contest I worked on similar algorithm. So I search all contests I played from oldest to latest one, I found the algorithm and blog called Manhantan 2.

I am so glad to learn that my last practice in the contest. I was so glad to see my hard work, and here is my C# algorithm written based on dynamic programming. The solution still has bugs with score 33.

Linear scan the array

Dec. 25, 2017

Introduction

I had a mock interview at 12:00 PM. I wrote a linear scan algorithm and finished the algorithm in 22 minutes. The peer asked me if I solved the problem before, and then I explained to the peer that I solved similar algorithm, there are two famous algorithms related to linear scan algorithm, test how good you can write a for/ while loop. One is called Leetcode can plant flower, one is called hackerrank Bear and gene.

Code review

The C# code is here.

Leetcode 33: Search in Rotated Sorted Array

Sept. 16, 2017

Introduction

It is the wonderful learning opportunity for me to practice the algorithm again last night at 10:00 pm. I chose to write the idea I thought about and read about, but I had not written it before. The experience told me that binary search basically is also like a depth first search, the most important is to work on base case.

The more detail is like this, I spent first 15 minutes to exchange ideas with the peer, and then only 13 minutes left, I need to write some code, and I chose to write a binary search combining normal binary search in sorted array and shift array binary search. My argument is that the normal one is just special case of shifted array binary search. The iterative solution is hard to avoid duplicate logic and coding. I just could not believe that I made it the first writing without any bug or grammar error.


Leetcode 33 is a medium algorithm, I wrote down the algorithm in less than 13 minutes, and most important thing I did is to move base case "middle value" (line 29 - 32) to the first thing inside the while loop, moved those 4 lines out of if block from line 36 to 46.

Tip to share 

I got the complaint about my practice of binary search tree. The peer told me that the most important part is to work on middle value in the binary search tree. Focus on middle value, do not consider start value at all.

Algorithm practice 

C# code practice is here. 

Rookie in recursive function design

May 29, 2017

Introduction

It is the great experience to teach myself how to write a correct recursive function to implement a depth first search algorithm. Julia spent over hours to teach herself, how to track a route in depth first search over one hour.

In order to figure out the issue, Julia wrote a depth first search algorithm using stack to help herself. She compared to the version using stack to the one using recursive function. She found out that the issue she had, she did not need to use memoization, she needed a memo to mark visited node to avoid dead loop.

Code practice 

C# code with dead loop, stack overflow issue. Mocking code is here. 

C# code to write a stack to implement Depth First Search (DFS). Code is here. 

C# code to write a recursive function. Code is here. 

A cheerful heart is medicine. Smile to my own mistake, next time I will ace the recursive function. Coding is done by a human, crafting takes practice!

Recursive - HARD TO TELL

Argument:

Use non-recursive depth first search algorithm to help the design. Using an explicit stack, it is much easy to follow. Write pseudo code, figure out base case, the design to avoid dead loop, cycle issue, memoization issue, structure the algorithm first. And then use it as the helper of recursive function design.

Recursive function is short and efficient to implement DFS, but error-prone. It is not straightforward. Practice this way to help yourself.

Use stack to help

Every mistake is valuable

I should say that memoization is extra, next step. Need to work on basic recursive function boundary check first. One thing is to test the code with the sample test cases, slowly and carefully, mark the test case for each line of code using comment.

To be a good tester all the time. Read your own code and go over it, with test cases. Julia, you got the tip from mocking experience.

Backtracking algorithm: rat in maze

Sept. 10, 2015

  Study again the back tracking algorithm using recursive solution, rat in maze, a classical problem. Made a few of mistakes through the practice, one is how to use two dimension array, another one is that "not all return path returns value", not so confident that "return false" at the end of function.

  重温二年前做过的算法题, Rat in Maze, 为自己惭愧! 二年前的练习, 没有任何的参考网页信息, 也没有算法讨论, 尝试改进. 感觉到自己的差距, 这次练习, 着重强调把算法能背出来. 一步一步写出来, 发现几个错误. 二维数组不熟悉, 耽误了十几分钟; 另外, 就是, "return false" 在递归函数最后一句, 先是忘了. 总之, 这个经典题目, 十分钟写不出来; 需要二个数组, 边界条件检测, 一点印象没有.

  Here are my favorite blogs about this problem:

1. http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/

2. http://algorithms.tutorialhorizon.com/backtracking-rat-in-a-maze-puzzle/

3. https://www.cs.bu.edu/teaching/alg/maze/


  Julia's C# pratice:

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

  And then, try to find more discussion about this problem, came cross blogs to challenge my analysis skills. 搜一下Google, 找到一个很有深度的网页, 看了以后, 体验一下代码, 感觉比自己的水平高了几个档次.

  http://blogs.msdn.com/b/mattwar/archive/2005/02/03/366498.aspx

  http://blogs.msdn.com/b/mattwar/archive/2005/02/11/371274.aspx

  More code to read and then play:

http://www.evercrest.com/ext/CheeseAppropriator.cs

  and C# practice:

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

January 10, 2016
Review the algorithm

Follow up 

April 27, 2017