Leetcode: Edit Distance - 30 minutes talk

Oct. 20, 2017

Introduction

It is very interesting to spend time with my relative, a 22 year old in the city of Yichun. He is a computer science graduate from top universities in 2016, and he plans to take graduate admission test for a computer science master degree at the end of 2017.

30 minutes talk 

I am very open to the new idea. What I have to do is to continue to support my nephew for Canada sponsor application and then also help him to build a career in computer science field. 

It is very good for my nephew to get some skills to help his parents to manage a restaurant. I also prefer to encourage him to get more education instead of working in industry to work for some one else. 

I did spent 30 minutes to test his coding skills, and practiced my lecturing skills during my vacation, this is the second chat. He was getting better, I still had no idea how he learns and what is his learning style.  

Here are my notes I wrote on a piece of paper about the algorithm. The algorithm is documented in detail here. 

Highlights of talk 

I spent a few minutes to explain the possible deletion distance between two words "heat" and "hit". The minimum deletion distance is 3, including deletion of two chars ('e' and 'a') in the word "heat" and one deletion of chars ('i') in the word "hit".

The naive deletion distance 5 can be implemented by deletion of 3 chars in "heat" from second char to last char, and deletion of chars in "hit" from second char to last char.

I used two words "abc" and "defg" and explained the deletion distance of two words. The possible choice to delete a char each time is 2, and there are 7 choices, so it is 2⁷.

Actionable Item

Teaching was fun even though my nephew is a rookie in algorithm and data structure, he did not ask any question and surfed wechat while I was talking. He told me to continue and I was not sure if he understood the algorithm or not.

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 dynamic programming

Feb. 6, 2018

Introduction

I still have difficult time once a while in terms of solving dynamic programming solution. The underneath recursive design of dynamic programming takes more time to practice.  I had a mock interview last weekend and the peer showed me his way to solve the deletion distance.

It is such nice learning experience from the peer. The code is written in Java and the link is here.

Most of important is that the peer showed me how he proved that recurrence formula is correct. Here is the transcript of the analysis.

Follow up 

I asked the peer in mock interview and then we discussed the formula why distance("heat","hit") = distance("hea", "hit").

Here is the discussion:

 //$dog and $frop,
  //$hit, i =   3 $heat, j = 4
  //f[$hit][$heat] = f[$hi][$hea]
  (f[$hit][$hea] + 1)
  (f[$hi][$heat] + 1)
  (f[$hi][$hea]  <- minimum
    min(f[$h][$hea], $f[$hi][$he]) + 1
  )


Let me write down the explanation given by the peer on March 12, 2018. First let me read his explanation and then figure out his reasoning.

First the peer thinks that it is better to add extra char to stand for empty string "", using '$' char.

There are 3 choices to determine the deletion distance between two string "$hit" and "$heat". There are three choices, in other words, here is the expression:

f[$hit][$heat] = Math.Min(f[$hi][$hea], f[$hit][$hea] + 1, f[$hi][$heat] + 1),

We should be able tell that minimum one is f[$hi][$hea].

Follow up 

July 9, 2018

The peer contacted me to ask practice together. I was so surprised since he won ICPC regional contest in 2012. It is the first time I have a peer to practice together with highly competitive skills in contest.

I just quickly looked up his review back in Feb. 3, 2018 6:00 PM. What I did is to check date connected on linkedin, and then found the mock interview round login, and then looked up algorithm. And then I found the blog, and mock interview feedback.

Algorithm learning small talk

May 4, 2017

Introduction

It is very interesting to read the article called "when pressure and off-court life overcome talent and results". The article link is here.

It is more exciting to practice coding and attend contest in the weekends. Julia enjoys the contest and also likes to push herself to join the community and share what she can do. Here is the blog to show her ask code review on a hard level algorithm in Hackerrank world codesprint 10 recently.

Julia had a mocking experience tonight, she had a big surprise about learning a dynamic programming algorithm.

The problem is a very ordinary solution using dynamic programming, recursive solution.

The deletion distance of two strings is the minimum number of characters you need to delete in the two strings in order to get the same string. For instance, the deletion distance between "meat" and "mit" is 3:

• By deleting 'e' and 'a' in "meat", and 'i' in "mit", we get the string "mt" in both cases.
• We cannot get the same string from both strings by deleting 2 letters or fewer.

Less means more 

How to analyse the above algorithm? 

Use frog and dog as an example, we have two words, we like to linear scan two strings from left to right, all starts from the beginning. First chars of two strings are 'f' and 'd'. If they are equal, then both pointers go to next one. Otherwise, we have to move one of pointers. Both cases should be counted. In other words, 'd' is deleted, then continue to work on two strings: "og" and "frog"; or 'f' is deleted, then continue to work on two string: "dog" and "rog". 

So far, the analysis is perfect. We cannot sort the string, because the order is important and has to be kept. The count of char does not help much. The brute force solution is not good since it will be O(n²), actually it is hard to find a brute force solution.

In other words, recursive function can be written in the following recurrence formula:

CalculateDeletionDistance(s₁, s₂) = CalculateDeletionDistance(s₁.substring(1, length1 - 1), s2.substring(1, length2 - 1)) if s₁[0] == s₂[0];

Make it short, CalculateDeletionDistance is shorted as CDD, s₁₁ is the substring of s₁, s₂₁ is the substring of s₂.

CDD(s₁, s₂) = CDD(s₁₁, s₂₁) if s₁[0] == s₂[0],
CDD(s₁, s₂) = 1 + Math.Min(CDD(s₁, s₂₁), CDD(s₁₁, s₂)) if s₁[0] != s₂[0]

Basically the recursive function is depth first search, base case should be calculated the deletion distance. And then in order to save time, it is better using bottom-up solution, called dynamic programming method.

Edit Distance Algorithm

Previous practice on Leetcode 72 is here. Spend 20 minutes to review lecture note from standford again. Also plan to spend 30 minutes to review Leetcode discussion, link is here.

Julia was wondering if the dynamic programming is also solvable using DFS algorithm.

Actionable Items

Plan to read the article on topcoder: Dynamic Programming - From novice to expert, the link is here.

Read the facebook engineering manager - Yi Huang's linkedin profile.

Take some notes from the recommendation:

Understand to build a hobby - writing code, solve problems on topcoders:

"Numerous times we turn to each other to discuss algorithm and optimization problems and every time I am impressed how insightful Yi can be. Yi has won countless programming awards and takes coding as a serious hobby. Yi has great enthusiasm in algorithm optimization. His hobby is to log into topcoder and attack one problem after another. He also has the great ability to apply research knowledge to actual programming. He is one of the few guys that will always think of how to turn research results into reality."

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.

Being interviewer: Deletion distance and long common subsequences

Feb. 6, 2018

Introduction

It is 8:00 PM mock interview. I had chance to learn a way to solve deletion distance using long common subsequences.

The idea is to find the longest common subsequences in two strings, for example, "heat" and "hit", the common subsequence is "ht", so the distance is "heat" and "hit" length sum minus 2 times length of common subsequence "ht". It is 7 - 2 * 2 = 3.

Code review

Here is Java code.

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.

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. 

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.

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.

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.

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.

Hard level algorithms - my Canada day

July 1, 2018

Introduction

It is the first time I spent the whole day to go over as much as possible hard level algorithm starting from 11:00 AM to 6:49 PM.

Hard level algorithm

Here are the list. It is not easy to work on hard level algorithms. I did try my best, and focus on getting the ideas first.

Leetcode 97

Leetcode 247 Medium level

Leetcode 248

Leetcode 272

Leetcode 316

Leetcode 327

Actionable Items

It is better to go over hard level algorithm more often, so I can get used to try to solve challenge problem first, sometimes feel good or frustrated. Over the long run, I should feel more confident. It will become part of my daily life. It is like solving Hackerrank contest, I will enjoy the journey.

It is so surprising today I learned another dynamic programming algorithm called interleave string. It is similar to the algorithm called deletion distance.

Leetcode 300: Longest common subsequence

Feb. 14, 2018

Introduction

It is the medium level algorithm and can be solved using dynamic programming. This dynamic programming algorithm is getting easy since I have worked on the dynamic programming algorithm deletion distance over ten times last 11 months, and one of solution is to use longest common subsequence.

Algorithm study

I spent around 20 minutes to go over one blog and wrote down my study note. Here is the link.

Being interviewer: Sentence reverse

May 3, 2018

Introduction

I was mock interviewer and the interviewee worked on the sentence reverse. And then we moved on the discussion of remove leading, trailing middle spaces.

Here is the code I used for me to be interviewer from Leetcode 151: reverse words in a string.

Mock interview

The interviewee wrote python solution and then we had discussion, work on coding to fit into removing extra space.

Here is python code, I lost it again before I saved it gist. I should save it without any name or description first.

Mock interview

It is so interesting I met a young graduate who is preparing Google onsite in a month. I had chance to talk and learn something from the mock interview. The mock interview lasted one hour fourty minutes. I tried to figure out how good a candidate is, but somehow I understood it. The way the peer handles the problem solving, he definitely can write good code using python, also he can work on the improvement right away once I pointed out.

The peer told me that one of the important things about interview is to communicate on the algorithm, and ask questions, clarify the problem, and also talk about things.

Chit chat about my performance

He likes my way to write down analysis using keywords, ask for:, constraints. I told him that I trained myself to spend first 5 minutes to write down the analysis, like system design, talk about keywords, constraints, and what to ask for. And then I can figure out how to design the algorithm. I tried to fully use the first 5 minutes, push myself to write down things, do not memeorize algorithm, do not assume the things, write down constraints.

And also the peer likes me to talk about the algorithm, and gave out the ideas to solve the problems. I told the peer that I have worked on coding skills so many times, definitely I feel comfortable now to write most common algorithm and data structure. For me, I have to make it real, write down the analysis, and then have discussion to find the optimal solution.

The peer gave me his idea to solve the problem. It is much better than me and simple. And then we had discussion, I asked if we can do better compared to his idea. Later, I shared array quadruplet post I did on code review website with the peer.

I have worked on those interview algorithm more than ten times. I already went through the stage to memorize the algorithm, and then made mistakes to mix algorithms. I treat all the algorithms are the same. From scratch, word by word, read the problem statement first.

I got complaint about deletion distance, dynamic programming algorithm, I memorized the solution and got complaint by an Intel senior engineer, Ph.D., he told me that it is no hire if I memorize the algorithm, write something before I fully understand the problem.

Now I try to act like a teacher, a lawyer, write down the keywords, constraints. I do have lessons from hackerrank contest since I missed some important words in the paragraph. It is also good time to demo how good I can read.

Leetcode 97: Interleave string

July 1, 2018it

Introduction

It is a hard level algorithm called interleave string. I have no idea how to learn a hard level algorithm, I just plan to spend 30 minutes time on this algorithm first. Now it is 12:46 PM, I will end the study at 1:16 PM.

Brainstorming ideas

Now it is 1:07 PM. I like to write down what I thought about in last 20 minutes.

Brute force solution - using linear scan from left to right

Check length to see if longest one is the sum of two small ones.
Count how many chars from a - z and see if the sum of each char equals to the sum of interleave string by characters.
Try to think about go from two ends of the interleave string, and find chars from the two strings to match. There is a recurrence formula.


Now it is 1:12 PM. Let me read one of solutions.

One more thinking,
"a"
"a"
"aa"

"ab"
"a"
think about short string first char position in the longer string, there are how many possible position:
length + 1, check prefix and compare to interleave string's prefix to see if there is a match.

Solution 

1:12 PM - 1:22 PM 10 minutes to study.

I just cannot believe that the dynamic programming method is very similar to Deletion distance.

NP complete problem

January 21, 2018

Introduction

It is exciting to learn some new algorithm through mock interview. I like to ask the question what is your favorite algorithm.

It is the first time in a week I heard two time NP complete problem.

Algorithm 

Here is the algorithm I can do some study.

Follow up 

Dynamic programming - Set 25 (subset sum problem)

https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/


Subset sum dynamic programming - similar to deletion distance dynamic programming, regular expression matching problem.


https://gist.github.com/jianminchen/ea004cdf37689d4c2c090dcec638f1c3


Subset sum problem

https://gist.github.com/jianminchen/57704617cd684d8dd61bd5ae93d0b621

Float number and operators algorithm

Dec. 7, 2018

Introduction

It is the fifth mock interview on the platform, and I am the interviewer. I have to be very careful since my last mock interview I got very low rating, the peer said that he wasted time, and I learn something quickly.

I am still trying to use the same two algorithms, but I like to make sure that I have to lead the peer to the optimal solution, this way if I am real interviewer, interviewee will like to work with me. Also I have to show up as the professional, act like a real interviewer.

Julia interviewer 

As an algorithm daily mock interviewer, I am lazy to think about the solution using dynamic programming. Today the peer wrote one dynamic programming solution for the algorithm. I learned quickly, it is so easy, nothing different from deletion distance algorithm I HAVE practiced over 20 times.

I know that sometimes I have this false impression and think that I am super talented.

Here is the python code using dynamic programming, I reviewed the code. The code passes test case [1, 12, -3] with maximum value 33.

The power of the algorithm

I try to practice nice as an interviewer, and then it turns out that the interviewee is super talented. He passed Google onsite interview recently. I just could not believe that I have learned how to behave in mock interview, I just need to follow the interviewee and watch the video how he answered each question.

Bayesian statistics

Do you like to read the performance report using Bayesian statistics. Definitely it is learning experience for me, I really enjoy the ride so far. I met top performers, over 10 years programmer working on search engine, a person can write a compiler (I guess), and a young master graduate who can pass through google onsite.

It is not hard for me to learn one algorithm very well. I just try out for difference interviewees and then learn from the experience.

Have you seen the problem before?

January 22, 2018

Introduction 

It is most common question peer asks me in  mock interview. Have you seen the problem before? Sometimes I just answer quickly, similar problem. I like to practice one more time and see if there is an issue to work on and also get help from the peer. Today I found one in mock interview as well.

Analysis does not match code

Here is Deletion distance dynamic programming analysis and C# code. I asked the peer that the analysis does not match the code. And he confirmed with me after carefully review of my code and the analysis.

Nothing can beat the peer's insights. 

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#.