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.

Island count

March 25, 2018

Introduction

It is my mock interview algorithm called Island count. I was so excited to work with a peer who is from Israel this morning 10:00 AM. The peer told me that it is better to write an iterative solution.

Code review

I had to follow the advise from the peer, and then I decided to write a queue to apply breadth first search to visit neighbors, mark visited.

Here is my C# code passing all test cases.

The instruction to play mock interview nicely

I have worked on this algorithm so many times. I know how to train myself one more time nice and easy, get more experience how to write readable code, practice one more time to explain the algorithm and talk about ideas with a peer.

First few minutes, I will write down the matrix using example 5 x 5 matrix, and go over row by row from left to right starting from position (0, 0). If I find the first one, I will mark it visited, and then use DFS/ BFS to visit all neighbors as elements in the same island. I will increment island count variable one. I will mark the first island using char 'A', next island using 'B', likewise. I will apply the same analysis twice, using -1 to mark first two islands A and B, and then just quickly apply C, D, E, F for the rest of islands.

After that, I will ask the peer's advice to choose DFS or BFS. Give him/ her a choice, and follow  the advice. I am willing to write any solution, but I do not want to stick on one solution, I like to practice any solution if need.

This time the peer told me that I should not use recursive function, it is written to write iterative solution in mock interview platform for interviewer. So I have to follow the advice, decide to write the iterative solution.

I thought about using for loops, and then decided to write a queue. Since it is the only way I can apply BFS without using recursive function, otherwise I cannot handle the neighbors just using loops. Data structure queue is definitely needed.

Beautiful code

It is not tough for me to write readable code using Queue, and apply BFS algorithm. I have practiced similar algorithm so many times last 12 months.

I learn how to write readable code last 18 months.

Give credit to the code reviewer, here is the link.

Here is the blog about my past practice. I need to get organized and then I can review what each my past practice and see how good I am getting.