Leetcode 72: Edit Distance

July 30, 2017

Introduction

It is such great mocking experience for Julia to work on edit distance algorithm again in 30 minutes this afternoon around 4:00 pm. Since Julia was tired and kind of sleepy, she could not hear the peer because of her speaker was turned off. It took her 5 minutes to find out, both tried to login again. The fact is that if you are tired, your will have some issues to work on the small thing.

It is good to observe that when you are tired, the thing can go out of control once a while. Julia remembered last time that she was very tired and then she worked on week of code 34 over 5 hours and did not score anything. Always get ready for the mocking!

The algorithm is hard to write. Even though it is not the first time to write it. Her last practice is documented here.

Design of Memoization

The peer helped Julia to come out the idea to design the key for memoization. Julia worked on design by going through the simple case, "heat" to "hit",  how to express distance("eat","it") using the key? Julia thought about loud, one way is to concatenate two keys like this "eat it", and she said that "it eat" should be the same as "eat it". Because Julia was too tired, she did not have a good idea. She was given a hint to use the array, use index of string, then she asked the idea using int[2] and define the comparer function.

The peer gave her hint to use jagged array memo[i][j], whereas i and j are the index of start position of substring.

Algorithm practice 

C# practice code is here. The code runs with a test case and the result is correct. The peer reminded Julia line 71 and 72 having an issue. Julia forgot to increment one to the distance. At the end with a test case, the peer applaused  Julia, and it was unbelievable 71 lines of code no bug.

Editorial Notes:

9/22/2017
I practiced again this algorithm through mocking interview, I met a senior developer who has very good managing experience. He asked me the time complexity about brute force solution, I stumbled on the question.

Based on the above experience, I did not learn the algorithm very well in theory. The dynamic programming is not easy to figure out. I need to relate to a simple life experience for this algorithm. I did one later on. Here is the blog link.

July 6 2023

I am working on Meta phone screen in two months, so I have chance to review Edit distance.