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.

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

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

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

Leetcode 72: Edit Distance

Sept. 11, 2017

Introduction

It is one of classical algorithms related to recursive function and also memoization. I have practiced a few times and I am still learning the algorithm. My last practice is documented here, and all past practices are available through the search by Leetcode 72.

It was such great experience to be interviewed using the algorithm again. This is my third algorithm practice, my last practice was more than one month ago. I still remembered the mistake I had and the advice I got from the peer.

Algorithm practice 

Here is my C# code written in 30 minutes. I had a mocking experience starting from 10:00 pm.

I knew that I have to work hard to be an interviewer in order to get unlimited credit. I just started my new round of mocking practice. I could not memorize the algorithms, there are a lot of new issues coming out on this algorithm. I failed to do analysis of brute force solution, it should be 2^{(max(str1.Length, str2.Length))}, because every time there is at most 2 choices. I was given the hint and then I took the hint to go from n * m to power of 2 analysis. In other words, the time complexity is lowered from polynomial time to quadratic time.

Assume that the worst case happens. In other words, the comparison of two chars are not equal, so one of them has to be deleted. There are two choices to do deletion, the minimum value of two choices will be recorded. For example, two strings are "abc" and "edfg". The total choices are at most 2⁷. In mathematical term, the upper bound is 2⁷ = 512. The dynamic programming using memoization will lower time complexity using jagged array memo[3][4], time complexity 3 * 4 = 12.

I also was told to make correction on the first line of the function, line 8. The checking is for the case of both strings are null or empty. Not at least one of them. I wrote || by the mistake.

Related to a simple life choice

9/12/2016

It is always good idea to write down the practice experience, what did I actually learn from the mocking? This time, 30 minutes coding passes all test cases, with one of corrections from the peer. But I was surprised to know that I need to grasp the basic algorithm analysis, as I shared my knowledge of Monte Carlo algorithm to a young graduate from a linguistic major, I have to explain the algorithm to myself. The most important is to know how to analyze instead of guessing.


If I have two choices to calculate distance, how should I make a decision? I have to go for the minimum one from the two choices. If I have a series of choices to make, then the combinations of choices will be 2ⁿ. To summarize, Leetcode 72 is the algorithm for me to teach myself how to understand the brute force solution with polynomial time complexity, know how to solve the problem first, and then apply dynamic programming, lower the time complexity to m * n using memoization, dynamic programming using bottom up solution.

It is interesting to know the memoization design, the best choice I know is to use jagged array, memo[][], the size of jagged array is str1.Length * str2.Length, that is how many intermediate result we have to hold. Assume that each of them is calculated to use a few simple steps which are O(1) time complexity. 

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. 

A cheerful heart is good medicine

May 27, 2017

Introduction 

Proverbs 17:22, Julia's favorite verse. "A cheerful heart is good medicine, but a crushed spirit dries up the bones". Every time Julia is too busy to work on something, she starts to check whether she has the feeling of a cheerful heart, specially she likes to stay late past midnight to work on a contest algorithm. She likes to share a story of a cheerful heart, and ends her weekend with some good story.

The mock experience is related to people skills and Julia started to learn how to make most from it. She has limited resource and limited budget to try new things. She chose free mock experience, she never tried any paid mock experience, but she did feel that she has to make mock experience very good learning activities.

Always have a cheerful heart on your own or peer's mistakes, they are the best friends of algorithm problem solvers. Coding is a crafting skills, talk about mistakes, journal the transcript, and then get back to compete again.

4 Sum

People with top talent to attend mock usually are very young and just start his/ her career, and one time Julia felt that the hints were too strong in the first 5 minutes, she had to take the hint given by peer. The algorithm is 4 sum, Leetcode 18. Second time she was mocked again using similar algorithm like 4 sum, she decided to work on practice Leetcode 4 sum. Here is her practice C# code. Her second mock code is here.

Edit Distance

Julia learned so many lessons from her own mistakes. She could not figure out dynamic programming Edit Distance in her first round mock in 2017. Overall, she almost failed at least 20% - 30% in her first round.

Julia wrote a bug on spiral matrix first as an interviewee, and then she interviewed some one the spiral matrix. She observed carefully the peer's performance, she had more confident to make the code perfect later on.

Every peer get stumbles in mock experience, she reminds herself not long ago she had same experience. Julia felt so connected through mock experience.

She suddenly found out that she never met and talked to so many engineers in the world, but she did in one weekend. As a programmer, she felt a little proud of learning to review peer's code and also recommend a book "The Art of Readable Code".

Last long weekend, she managed to finish 11 mock experience. So she almost finished her second round. The fact is that second round is learning round. Test your own code, not using compiler, use your own whiteboard techniques.

Reverse string 

The fact is that she met strong peers who shared her importance to learn and write good clean code, specially recursive, DFS, and also the peer still practices. The meeting is short but she feels that the study group formed through the discussion is also very rewarding experience, she would be a nice algorithm teacher one day if she continues.

It is fun to play with a peer. One day, Julia  met a peer again and she was too busy to follow the peer's idea to solve the problem, but she knew that the peer was working hard and the idea needs to be tuned. Julia likes to gain some skills to be a professional interviewer one day, so she learned quickly to say sorry, not followed closely with the ideas in the code. Good heart leads to a new world, the peer told her that there is something new and different, she was well received with a tip.

"Every player knows how to play tennis". That is the famous tennis professional player's quote. Only those survive with strong mind set, and determination, and the hard work training, practice.

Related to tennis sports, Julia learns to treat peers equally and be supportive in mock experiences.

Julia missed how a professional mock experience will look like. She booked one mock and surprisingly she got one in less than one week.

Study and talk 

Julia wrote a blog about the study "Does mock make difference", and then she moved herself to next stage in her practice, know a professional interviewer with thousand experience, and also learn to mark herself with a mark, May 27, 2017, she got a mark which is called passing the bar - 2.5. 

Good heart leads to a new world. Julia likes to show people that she has determination to gain skills in algorithm and data structure, and is working hard on the improvement. Still exploring...

Julia understood that those contest practice with medium levels are very helpful, she prepared herself, she felt that the depth first search, recursive function call is so important to learn.

She forgets to write a base case in DFS algorithm, still she needs to the hint to go over the test case and then find out that she lets the loop forever because of that.