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
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.
No comments:
Post a Comment