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.

Deletion distance algorithm

January 28, 2018

Introduction

It is very hard for me to learn a dynamic programming solution to solve deletion distance. One thing I have learned is to understand the difference between recursive and dynamic programming. The peer is a latest computer engineering PH.D. from top university, he asked me tough questions. I had hard time to go over the analysis and answer his questions, but I managed to learn and answer correctly.

It is not good to memorize the solution, that is the reason I seek for the advice for each mock interview. This time I had chance to learn from top graduate and understand how important it is to be able to explain the algorithm.

I have to understand the algorithm and be able to defend my analysis. Mathematics is my undergraduate study major, I love to prove something based on theorem.

Analysis and code review 

Here is the transcript I wrote in less than 30 minutes. 

Deletion distance

January 8, 2018

Introduction

Dynamic programming is most challenge solution I feel right now. Also it is very easy to write since I chose to write in bottom-up approach. The recurrence formula is still the same as the recursive solution.

It is another mock interview on January 7, 2018, 8:00 PM. I chose to use dynamic programming to implement the deletion distance. It is the first time I tried to write one in mock interview, most of time I wrote recursive solution instead. I was so excited to have some one watch me and give me constant feedback while I worked on the solution.

Code review

Here is my C# implementation of deletion distance. I spent around 25 minutes to write the algorithm including the analysis of algorithm.