summing pieces - dynamic programming

June 20, 2018

Introduction

Life is not easy for a software programmer.  Since it is hard to master data structure and algorithm. Technology is updating so fast, I try to make my work very easy for me to handle.

I notice that I need to get organize and check in all algorithms I wrote into github. I came cross one algorithm, one editorial note, one hackerrank profile. It inspired me so much.

Here is the algorithm called summing piece. I wrote complicated code in the contest.

Here is the editorial note with some math, my favorite part.

I plan to write a dynamic programming solution for the algorithm.

careless whisper

June 4, 2018

Introduction

I had mock interview this morning with my coach, 8:00 AM. This is our goodbye meeting. I talked to my coach that the dynamic programming solution is hard to come out in the first five minutes. I just named this algorithm as careless whisper. I did hear the word coming out my mouth when I discussed with the peer yesterday, using dynamic programming.

Algorithm is called to find maximum flower. Given a matrix with cells three options: empty, wall, flower, find maximum flowers cell.

Let us say that two dimension grid contains empty cell (S) or flower (F) or wall (W). A person standing in a cell can see north, south, east and west. But all flowers behind wall are invisible. Find the cell with maximum visibility.

S   F   S  F
W S   F  S
F  W  S  F
S  F   F  W
S  F   W S

output: 3

Algorithm practice

Here is my C# algorithm.

I do not have time to put those four functions into one function, avoid code duplication. 

Follow up

June 20, 2018

The friend just shared with me the discussion panel on this algorithm. 

Discussion of maximum visible is here. 

Follow up 

March 5, 2019

I asked the algorithm in mock interview on interviewing.io. I learned from the interviewee that the algorithm can be simplified by checking left/ upper two directions only.



March 6, 2019

I spent time to work on the example again. It cannot be simplified. 

Leetcode 91: Decode ways

May 29, 2018

Introduction

It is my eighth mock interview from my coach starting from 8:00 AM to 9:40AM on May 29, 2018. He asked me to work on Leetcode 91: Decode ways.

Mock interview

Here is code I wrote in the mock interview.

Follow up

I wrote the C# code and then tried to pass online judge. I made a mistake to put 0 which should be '0' on line 80.

Coach's advice

Please consider to define the array using extra one space. Let the first element of the array be empty, therefore in your solution line 80 index >= 1 can be removed.

Follow up 

May 2, 2019

I chose one of online mock interview on Leetcode.com and had chance to practice the algorithm one more time.

I spent 30 minutes to write and used debugger to help me to fix a few bugs in order to pass online judge.

Here are highlights:

91 Decode ways
I came cross three bugs and I had to use debugger to help me to figure out
1. mix char with integer, s[i] - '0' is to convert to integer
2. all results are zero, forget to increment one for the start
3. apply step 1 for all instances, miss a few place
4. missing edge case, tenth digit should exclude 0, 3 to 9. 0 is not considered by mistake.
5. missing edge case, 00 is not valid

And the code written is here to look up.

Find the least number of perfect square numbers sum equal to given number

May 15, 2018

Introduction

It is the second algorithm in my mock interview today. I like to show my transcript here and plan to write a C# solution when I have a few minutes.

Follow up 

Here is my C# code. I made a mistake and then I fixed the bug.

Do I make things too easy?

May 15, 2018

Introduction

It is so much laughing today since I had chance to review my own code written more than 12 months ago. Is that true every 12 months you advance your programming skills? Since I learn how to come out dynamic programming solution without any headache, I found out my practice over 6 hours in the contest was so such a good thing to laugh about.

I am self-learner on algorithm problem solving. I am pushing myself to top of world level? I could not believe that I wrote so many lines of code, I documented it. The blog serves the purpose to teach me that good code is to write short, very clean code compared to the long complicated functions.

Code comparison

Here is the solution I played with stack with so many things, including extra comment up to 400 lines of code. I did it more than 13 months ago.

Laughing moment. Laughing...

I wrote simple code today. So simple and I could not laugh one more time. The code still has bugs, but I will sort out the constraints in the problem statement.

Dynamic programming solution is here written on May 15, 2018.

Keep writing some code every day and write some coding blog every day.

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.

Being an interviewee: Deletion distance

April 21, 2018

Introduction

It is 10:00 PM mock interview and I had to work on deletion distance algorithm. The peer asked me if I worked on the problem before, since I did very fast. I finished the analysis in less than 10 minutes, I went over the test case "heat" and "hit", and built up a dynamic programming table from scratch. I certainly told the peer that I worked on the algorithm more than 10 times, each time there is a new issue coming out.

I started to code and passed my test case and all test cases on the platform. And then I had a chat with the peer. The peer had very good leadership skills, he showed me how to explain things crystal clean, pay attention to the intonation, kind of like exaggeration.

I told the peer that people complained to me speaking too fast, my sister with over 30 years teaching experience complained to me that I was not in the same channel, sometimes I let my mind shift away. I do not answer people's question directly, rambling, or change the topic without any conscious. I am still working on it.

Sometimes I notice that I do not focus on one thing, do multiple things in the same time. In terms of mock interview, I have to respect the peer, stop playing wechat or checking my email or my blog while the peer is coding.

The peer is very considerate and supportive, he said that it may happen to him as well.

Mock interview

Here is my analysis and C# code.

Leetcode 312: Burst balloons

April 6, 2018

Introduction

It is a hard level algorithm, so I like to work on the algorithm over ten times. I like to spend time to read this blog written in Chinese, and then try to understand better about the algorithm.

Here is the gist I created for blog study.

My favorite algorithm

It is the first time I read this analysis in Chinese. I could not believe that the analysis is such a good one.

I have to learn how to break into two subproblems and also two of them are independent.

Algorithm study: 95 algorithm videos (II)

April 20, 2018

Introduction

It is hard level algorithm called Leetcode 312: Burst Balloons. And the video is 20 minutes, I spent the time to watch the video, staying at home for one day vacation. I enjoyed the learning of the algorithm.

It is interesting for me to learn the dynamic programming through the video. I like to evaluate the author and see how good he is. I know that he is working for Facebook.

Leetcode 312: Burst Balloons

I like to talk about a screenshot and discuss the layout of dynamic programming algorithm presented by basksetwangcoding.

First step, I need to define state for the dynamic programming algorithm.

Next step, I need to define initialization step.

Third step, I need to define the function, problem and subproblem how to connect each other.

[left][right] = Max(i: [left + 1, right - 1])

For each subproblem, coin[i] * coin[left] * coin[right] + [left][i] + [i][right - 1]

Fourth step, I need to define result: [0][n - 1]

I need to put together a simple example to explain the solution to the peer. Here it is the example:

  1    2    3    4   5   6   7  8  9

Algorithm practice

Here is my C# practice.

Algorithm study: 95 algorithm videos (I)

April 6, 2018

Introduction

It is a hard level algorithm called Leetcode 312: Burst Balloons in Leetcode.com. I like to study the algorithm again by watching the teaching video here.

I could not believe that I finally have time to write code for the algorithm on April 25, 2018.

Leetcode 312: Burst Balloons Algorithm practice

I started to work on the algorithm on April 24, 2018. I have to learn the algorithm by working on a simple test case [3, 1, 5, 8] with the maximum value 167 based on Leetcode 312 problem statement. What I did is to write C# code based on the idea based on the video provided by a facebook engineer.

I calmed down and thought about how to write this dynamic programming solution, I told myself that I should take the time to think and do not rush, read other people's source code.

Basic ideas are simple. Define the base cases first, and then bottom up build the dynamic programming table.

I spent more than 40 minutes to write down the code on the paper. I put the code in Visual studio and debug the code. Apply the test case [3, 1, 5, 8]. But the code does not work, the value is much bigger than 167. Actually it is 218.

Here is my C# practice with some bugs. I need to figure out my problem in the algorithm. 

I could not believe that I could not count the correct number. The number is too big. In theory, it should be the error from the base case, the logic of recurrence is simple and I copied from the facebook engineer presented in the above video. But I need to train myself on this bug finding process. 

Find the bug

It is time for me to read discussion panel of Leetcode 312, I read a few of them, but the dynamic programming idea is different. So I continued to google and read a few blogs. One of blogs is very good since the blogger works for Microsoft.

But I still could not apply my case. The dynamic programming method in those blogs are inclusive, not exclusive.

Questioning the base case

Finally I started to question my base case, what is the value dp[i, i+1], in other words, keep ith and (i + 1)th balloon, then there is no balloon to burst. My answer is numbers[i] * numbers[i + 1], that is too much. So I changed to one. I ran the code still not the correct. So I finally know that it should be 0.

Although it takes me a lot of hours to learn the algorithm, but I think that I do right thing for myself.

Here is my C# code to pass Leetcode 312 online judge.

How to be a good interviewer?

April 1, 2018

Introduction

I like to do a small research how to be a good interviewer. I learn to be an interviewer by myself, I got a bad feedback when I mock interviewed a person anonymously no video from Singapore with over 6 years experience a few days ago. I gave the algorithm called Leetcode 152: Maximum subarray product. Because I did not want to give all hints out to solve the problem, the interviewee wrote an idea with so buggy code using checking negative elements. At the end of 45 minutes, both of us did not learn anything. The interviewee did not learn anything from the mock interview, I also got bad feedback.

So in order to make mock interview learning experience, I choose to give out all hints and sometimes I make it a tutoring session.

Deletion distance

On March 31, 2018, I gave the peer a mock interview using deletion distance. So I decided to step in and worked on the algorithm together, discussed how to approach the dynamic programming algorithm together.

Being interviewer: Deletion distance

March 29, 2018

Introduction

It is the dynamic programming algorithm called deletion distance. I had a 12:00 PM mock interview. I had chance to discuss with the peer how to solve the problem by playing with dynamic programming table.

How to build a dynamic programming table?

Here are a few things we discussed.

1. How to define rows and columns?
2. Add "" string for row and column
3. First time I found out that I need to add extra row/ column to identify current char to work on.
Line 19 is extra row added to show current char to work on, first char next to line 23 to line 26 is the extra column added to show current char to work on in another string.

4. I worked on the first row and first column, and then I did write line 29 to line 33 to explain the recurrence formula.

5. I asked the peer to work on the second row. He worked on second row and third row, he made a mistake to calculate distance("fro", "do"). And then I asked him to check diagonal value dist("fr","d") = 3.

We then had discussion how to prove that the minimum distance is the diagonal value when the current char is the same as the other string's current char.

The proof is from line 25 to line 36. I explained that the matrix or dynamic programming two dimension table from left to right, top to down, it is not descending order. So it is easy to prove that based on the fact.

Giving advice

I also wrote some advice for senior developers to pick up algorithm and data structure in general, specially on deletion distance algorithm:

Do not feel frustrated. I also make a lot of mistakes and practice a lot of times on this algorithm. Practice more. Learn one thing a time.

I do not need to find out how good you can write code. Try to play with setting up a two dimensional table first, and then write code based on the steps. It may take a few times. Once you get a lot of practice, dynamic programming should be very mathematical, use a template, it is easy to write the code.

Leetcode 152: Maximum product subarray

March 27, 2018

Introduction

I like to work on this algorithm Leetcode 152: Maximum product subarray, and I find that it is similar to the algorithm I practice so many times called float numbers and operators.

Algorithm practice as an interviewer

I chose the algorithm to interview the peer in mock interview. The peer is very talent programmer, he had a facebook onsite last December, and he prepares for Google onsite. what I found out is that he needs some hint to come out dynamic programming solution, but his coding ability is very strong, and also the analysis ability.

Here is the transcript.

Knight's tour

March 15, 2018

Introduction

It is very classical dynamic programming called Knight's tour. The problem statement is here on stackoverflow.com.

The most important thing is to know that we only need to count the number of phone numbers, but we do not need to know what numbers for each phone number. The second tip is to know that there are 10 numbers for each step at most.

Algorithm practice

Here is my C# algorithm.

My problem is that it takes me too long to come out the idea and write a solution. I need to make it fit into 20 minutes, 6 to 8 minutes to come out the idea, and I should be able to write the algorithm in less than 10 minutes.

Thinking process

We all know that most important is thinking process. Of course I had long thinking process this time. I drew something on paper, and I took time to think and play with the example.

What I like to do it to make some presentable notes here and document my thinking process. Good thinking process is the gold, the coding part is easy specially for dynamic programming algorithm.

1   2    3

4   5    6

7   8    9

    0

We can tell that 1 can reach 6 and 8. Please check next row and then next column. we denote that knights[1] = new int[]{6, 8}.
Same applies to each number in the first row, next row.

One thing I have to pay attention is number 6, there are 3 numbers to reach, row above, row below, column before, knights[6] = new int[]{0, 1, 7}.

Let us call it first play.

Next play is to work on a graph using those numbers as node, and then connections as edges. It is directed graph as well. Originally in my practice, my drawing is kind of messy. In the following, I try to simplify and make the drawing more readable.

For example, knights[1] = new int[]{6, 8}, I will draw like the following:


0   1    2    3    4   5     6    7    8    9

     ----------------------->

    ------------------------------->


And then we need to add knights[0] = new int[] { 4, 6},

0   1    2     3      4     5    6    7    8    9

------------------->

------------------------------>

We can use depth first search, but time complexity is too high using depth first search. We do not care the path detail. There are so many paths, all we care about the total number of paths.

Once I decide to use a table to store all intermediate result. I have ideas to solve the problem using polynomial time.

Suppose that we start from number 1, and then go over 4 steps and see how many results we can generate.


3              1       3    4     2
2    2   1       1            1
1    0   0   0  0  0 0  1 0  1   0
0    0   1   0  0  0 0  0 0  0   0
-------------------------------------------------
     0   1   2  3  4 5  6  7  8   9

688. Knight Probability in Chessboard

March 10, 2018

Introduction

Dynamic programming algorithm is more advanced compared to recursive function, depth first search algorithm. I like to write down some note to document my practice, time spent is longer than three hours.

Algorithm practice

I did read one blog to document the analysis of the algorithm with the code, so I went over analysis word by word, and organized the idea first and put into the gist. But I could not understand the algorithm.

So I continued to search more blogs to read, and then I found one with the graph to explain three dimension dynamic programming. I understood the idea to apply dynamic programming algorithm.

Next I worked on code from discussion panel and then converted to the C# code. But it still took me more than one hour, I had to debug the code and pass the failed test case.

It is so interesting to learn the algorithm by going over the steps. It is not difficult but it took me a few hours. I think that it should take less than one hour in total.

Here is the gist I created for understanding the dynamic programming algorithm after I read a few coding blog and one discussion on Leetcode.com.

Here is the code to implement in two dimension array instead of 3 dimension, since we do not need to save all intermediate steps.

Here is the C# code to pass all test cases on Leetcode online judge 688.

Leetcode 91: Decode ways

March 4, 2018

Introduction

It is so surprising that I can solve the decode ways to apply dynamic programming techniques. The conversation is like this. The peer asked me if I can solve the problem since he was asked in one of mock interview and then he failed to solve the problem since the idea of two pointer technique is not working. He was told to solve it using dynamic programming.

Dynamic programming is so much fun and I can quickly solve the algorithm after 12 months continuous practice on the same algorithm over and over again, and also learn from each peer when they work on those algorithms. After I failed several times on constructing the dynamic programming lookup table in two dimension, I finally build a template for myself to follow.

Two most favorite dynamic programming algorithms are deletion distance and regular expression matching. Usually what I like to do is to construct a look up table, work on base case first, and then figure out recursive formula. Detail can also look up here.

Algorithm practice

Here is the transcript I worked on in mock interview with a peer together. It is such great experience to share with the peer. I believe that once I have practiced dynamic programming algorithm on mock interview platform last 12 months so many times, I just apply the technique and find that it is not hard to figure out anymore. Here is the link to look up my practice on Leetcode 10: regular expression match hard level algorithm, including the blogs I worked as an interviewer as well.

What I did is to work on test case 1238712, build up a dynamic programming lookup table. And then go through from the left to right and find the answer 6 for the test case 1238712.

We had discussion together over 20 minutes on this dynamic programming lookup table, after we carefully went over the detail, I was told that the result is correct. The peer also went over to build the table by himself after I demoed how to construct it step by step.

One fact is that the peer shared with me the solution first, but I did not have to read the code the peer shared with me at all.  I just told him to build a lookup table, work on a simple test case first.

Teaching and learning is so much fun since the peer is very busy and short of time. He has to prepare two interviews for top 10 software companies in less than one month. I am glad to learn from his experience as well.

One algorithm a time.

My personal advice

The peer told me that he only did one round of mock interview, after he finished all 30 question he stopped. He does not build strength if he keeps working on new algorithm.

Compared to the peer one round mock interview experience, I have more than 6 rounds. But what I found out is that I work on the same 30 algorithm over and over again. Even though I have to work on those dynamic programming algorithms over and over again, I worked on Leetcode 10: regular expression matching more than 30 times with various peers, I also kind of picking up a lot of things through those practice, from recursive function to dynamic programming, various languages from ruby programming to C++, Java and C#.

Deletion distance

Feb. 28, 2018

Introduction

I had a mock interview on Feb. 27, 2018 10:00 PM. I wrote deletion distance algorithm again.

Code review

Here is the C# code.

Longest arithmetic progression

Feb. 18, 2018

Introduction

It is the most difficult dynamic programming algorithm I have worked on before. I just could not believe that we do not have a lot of blogs and articles to talk about it. I was thinking about posting one on stackexchange.com in short future.

One thing I like to look into is how the startup company in Sillicon Valley chooses algorithm for the phone screen, what kind of talent is at the top of the free market now these days?

I do know how tough it is to survive a 20 minutes mock interview using this algorithm.

Plan to work on the solution. Here is the link.

Algorithm practice

Here is the C# code practice I had recently. I did find a blog with test cases. After I went through the test case, I understood the algorithm and how it works.

Actionable Items

I like to read the papers related to the algorithm, and see if I can understand the paper one day. Here is the link.

Here is the post on stackoverflow. And the answer I voted is here.

Deletion distance dynamic programming

Feb. 12, 2018

Introduction

It is BC family day and I booked 10:00 AM mock interview. I wondered last night who will practice mock interview in the day time of Monday. I was wondering if I should work on something else, go out to play tennis, walk around the park, go shopping of fresh fruit and vegetables.

I started to work with the peer on the algorithm called Sudoku Solver. It is so much fun to work with the peer on this algorithm. I did one a few days ago on the engineer in silicon valley area, and I like the peer quick thinking and also very good communication skills. Specially when the peer asked me if everything looks good on my side.

My mock interview

I had to solve deletion distance using dynamic programming. What I did is to go over the example first, and then I explained how to solve the problem row by row.

Here is C# code. The peer advised me to optimize the space to O(m + n) instead of O(m * n).

Here is the graph I drew and then I worked with the example to explain the algorithm. I found out that I have more time to explain the algorithm using the graph and walk through the example slowly to explain the algorithm, in case there is any question from the peer, I can stop and then explain more.

I also start to learn that the coding part is less challenge compared to explanation of the algorithm.

Swift means sweet

Feb. 11, 2018

Introduction

Swift language is chosen by young generation programmers and they like to work on ios app etc. I was explained by the peer through the mock interview. I rated that the peer is one of top performer in my last 160 peers last eleven months.

It is my decision to start a new round of mock interview using ID: beet after I finished the round using ID: apple. I also chose to interview using Swift language, since I practiced one time with a peer using Go, I like to learn new things and stay out of my comfortable zone this round.

This is the first time over 160 mock interview that I met a peer who used Swift in the mock interview. As a matter of fact, he was the first person who asked me to give him time to look at his algorithm before I started to code my algorithm Leetcode 10: regular expression matching.

And also the peer shared his Swift code of Leetcode 10 after I performed my algorithm. And then the peer told me that he solved the problem differently, and I asked him to explain it to me. And then I had chance to learn Swift language from him, and also I had chance to ask question on the implementation. I learned to ask questions and identify the recursion zero time, one time or more than one time in the code. I was so surprised that I just learned a new way to solve the problem. It is an iterative way, and it is to go over pattern string and perfect solution. I really enjoyed the learning.

Swift code

It is kind of sweet for me to learn a new language. I learn starting from my most favorite algorithm. I just could not believe that the teaching and learning can happen so quickly.

Here is the swift code. I added comments to highlight the b* pattern repetition zero time, one time or more than one time.