Manhantan 2 - Booking woman in tech

May 14, 2018

Introduction

It is so good to review my practice on the algorithm called Manhantan 2 more than 13 months ago. Hackerrank has all my submissions of the algorithm. I was so glad to know that I can solve the algorithm quickly using dynamic programming solution.

I spent over 30 minutes to write the solution, and then debugged the code and fixed a few issues. But I still missed some constraints, I could not come out the idea to all the algorithm pass all test cases. I need to write down keywords in the problem statement.

Dynamic programming solution

Here is C# code I wrote using dynamic programming solution.

I still like to write down a few lessons I learned through the practice.

1. Line 117 the function name is not matching the work. It should be called FindMaxCandiesFromLeftTopToBottomRight.

2. base case line 129, I added the statement before debugging the code.

3. The three loops (line 132, line 134, line 140) is kind of interesting. I came out the idea when I visited the restroom.

I tried to come out the idea to prune the algorithm, minimumToDestination variable is used to help the third loop.

I made mistake on missing line 167, after the debugging, I found out that my result is always 2. So I need to add line 169, but then my result is bigger so I fixed bug to write one statement ( line 167 ). And then I fixed the issue on line 124, I added 1 to the variable timeToLive.

Funny notes but harding work spirit

I like to read my own comment written more than 13 months ago. I was very hard working, but I need to learn how to write dynamic programming solution. I like to copy the notes here.

" The idea is to start from top left node, always go right or down, and then track the  sum and max value; Because the size of matrix is 100 * 100, queue will cause out-of-memory, use stack, DFS search, try to use recursive solution if possible 200 depth at most, 100 + 100 try to get some points first, and then get the idea - 2:35pm - 7pm, now it is 7:53pm, what is the possible reason to get wrong answer? ".

I could not keep laughing, I was so glad that I moved on mock interview starting last April, 2017. At that time, I wrote broken English with a few Grammar errors here.

Because the size of matrix is 100 * 100, queue will cause out-of-memory, use stack, DFS search, try to use recursive solution if possible 200 depth at most,