Being interviewee: Leetcode 10: regular expression matching

March 29, 2018

Introduction

It is my sick day. I have to stay at home. Yesterday I noticed that my nose was running and made sneeze, one of coworkers asked me if I was sick. I told her that I had allergic. But I had to honestly admit that I had a cold, I could not go to work and stay at home.

I had 10:00 AM mock interview, I had to work on Leetcode 10: regular expression matching algorithm. I spent 34 minutes to write analysis and code, I fixed a few bugs to pass all test cases.

Code review

Here is my analysis and C# code.

I like to write down my misunderstanding in my first writing, and then how I fixed the bug through the white box testing and web compiler.

For example, to build a dynamic programming table, I have to work on "b", "b*".

                    ""  "b"   "*"
                    ""  "b"   "b*"  - pattern
              --------------------
""    ""         T     F      T
"b" "b"        F     T      T

In order to calculate dp[row, col], I need to find the text char and pattern char first, and then work on current char only.

Highlights of bug fix after first writing in mock interview:

1. I did white box testing, need to fix the bug using test case "" matches pattern string "a*b*". I added line 21 to line 33.
2. web compiler runs the test cases. I failed most of test cases.
I noticed that I could not memorize the solution. I need to work on the solution itself.
I fixed line 25 checking pChar == '*' instead of checking pChar and its next char.
3. line 40, check pChar is '*' instead of checking next char is '*'.
4. line 46, col - 1 instead of col - 2 which causes index out of range error.

Dynamic programming quote

Today's quote on dynamic programming. I think that I learn something from today's practice.

Work on dynamic programming, do not worry about next char. Work on current char only. 

Best medicine to cure my cold

Here is the feedback I got from the peer. It helps me to recover from my cold. Actually the peer is very competitive programmer on codeforece.com, expert with contest rating: 17xxx ( max: expert, 1886), competitive, also on hackerrank.com with 5 gold medal.

One more practice

I knew that I was sick with a cold, and then I felt some nervous in mock interview. It is hard to write a dynamic programming solution in less than 30 minutes.

I knew that something will go wrong. To learn a hard level algorithm, I have to be so patient and let myself make mistake first; and then find the ways to fix it in mock interview, and also in less than 30 minutes.

First of all, I mixed the dynamic programming solution with recursive solution. Since my last practice I spent over 40 minutes to write a recursive solution in mock interview to play with a friend less than one month ago. I look ahead for star pattern, current char is a - z, I check if next char is star. But it is wrong to do that in dynamic programming, mix current problem with next problem.

Dynamic programming is to work on the current problem and use subproblems cache results.