Being interviewee: Regular expression match

July 1, 2018

Introduction

It was my 10:00 PM mock interview on June 30, 2018. It is my favorite algorithm called regular expression matching, and it is hard level. I have not written any new algorithm in the whole week. The peer did such great job to help me go over the tough thinking process to write code in 40 minutes, and a few debugging to pass 4 out of 6 test cases. After the mock interview, the peer shared with me her Google onsite interview experience and Linkedin onsite experience, so generous sharing. I also learned the lesson to keep practicing.

Dynamic programming one more practice

Here is the code I wrote in mock interview 40 minutes.

I mixed the text string and pattern string. On line 41,

Line 41: else if(currentP == '*' && row >= 2 && text[row - 2] != '*')

The above statement row variable checking should be col >= 2 && pattern[col -2] != '*'

Here are a list of things to slow me down in mock interview:

1. Line 25, write down base case for dynamic programming table first row, when the text string is empty, "b*", ".*", "a*b*" should match empty string.

   The expression can be simplified as well.

2. Line 44 missing pattern[col - 2] == '.' for one or more than one case.

Here is the C# code I fixed the bug after the mock interview.

Being an interviewee: Leetcode 10: regular expression matching

April 21, 2018

Introduction

It is hard level algorithm called Leetcode 10: regular expression matching. I had a mock interview 8:00 PM and the peer told me that I should hurry and complete everything in 30 minutes. I did finish coding and ran my own test case. But my code failed last test case "abaa" with pattern string "a.*a*".

Mock interview

I had difficult time to play with dynamic programming table. I have to match the index of text and pattern string to the dynamic program table, and then I need to build the recurrence formula.

Being a programmer, I learn to be patient again since I could not memorize the thing. I have to make mistake first and run a few simple test cases and fix the bug.

Here is my C# code.

The first twenty minutes was so exciting and nerve breaking. I just write down what I like to do. For example, I wrote something like // base case "" match "a*" or "a*b*", and then I can write code by looking up the comment.

I confused myself about -1, so I wrote down on line 20 as a comment, // pattern[col - 1].  Because I cannot declare an explanation variable because it may be out-of-range of the array. On line 21, I wrote down dp[0, col - 3] which should be dp[0, col - 2] because I confused dp table index with pattern string index.

It is kind of training I like under stress, work on whiteboard, and also work on communication with the peer, manage the peer to make sure the whole process is up to standard.

I wrote a comment like the following:
// base case "a" does not match "" - do not need to do anything - default false

Good thing I did in the mock interview is to run a few simple test case first. When I ran the test case "b" match "b*", I ran into index-out-of-range error, so I fixed the bug on line 21.

My code passes all four test cases I wrote, but failed mock interview platform test case: "abaa", "a.*a*".

Bug fix 

Here is the code I fixed the bug. All my practice on Leetcode 10: regular expression matching can be looked up here.

Please compare my last practice March 29, 2018, here is the blog.

How to deal with tough interviewer?

I had a peer who has more than five year work experience at Microsoft. He is very strict on time limit 30 minutes, so I was in the rush to complete the code and run test cases. At the end of 30 minutes, the interviewer told me that he was very happy for my performance, and he thought that I should be able to fix the bug quickly.

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.

Leetcode 10: regular expression matching

March 13, 2018

Introduction

It is my most favorite algorithm in 2018. I was told to write the algorithm using recursive function in mock interview, and I did spend more than 30 minutes to write, I should analyze the algorithm and write it in less than 25 minutes.

Code review

Here is the code I wrote in mock interview today 7:15 PM today. I need to work on the improvement of speed, I took almost 40 minutes to write the algorithm.

One idea I have is to go over Leetcode 10 discussion, and study some discussion using recursive solution. I will plan to study a few hours and get some good ideas and code to work on.

Swift means sweet

Feb. 11, 2018

Introduction

Swift language is chosen by young generation programmers and they like to work on ios app etc. I was explained by the peer through the mock interview. I rated that the peer is one of top performer in my last 160 peers last eleven months.

It is my decision to start a new round of mock interview using ID: beet after I finished the round using ID: apple. I also chose to interview using Swift language, since I practiced one time with a peer using Go, I like to learn new things and stay out of my comfortable zone this round.

This is the first time over 160 mock interview that I met a peer who used Swift in the mock interview. As a matter of fact, he was the first person who asked me to give him time to look at his algorithm before I started to code my algorithm Leetcode 10: regular expression matching.

And also the peer shared his Swift code of Leetcode 10 after I performed my algorithm. And then the peer told me that he solved the problem differently, and I asked him to explain it to me. And then I had chance to learn Swift language from him, and also I had chance to ask question on the implementation. I learned to ask questions and identify the recursion zero time, one time or more than one time in the code. I was so surprised that I just learned a new way to solve the problem. It is an iterative way, and it is to go over pattern string and perfect solution. I really enjoyed the learning.

Swift code

It is kind of sweet for me to learn a new language. I learn starting from my most favorite algorithm. I just could not believe that the teaching and learning can happen so quickly.

Here is the swift code. I added comments to highlight the b* pattern repetition zero time, one time or more than one time.

Leetcode 10: regular expression matching algorithm

Feb. 11, 2018

Introduction

It is 10:00 AM mock interview. I had to work on the algorithm of hard level, Leetcode 10: regular expression matching algorithm. I told that it is not easy to write in 30 minutes, I did exactly 30 minutes, wrote analysis and also wrote the code, fixed the index-out-of-range error, and then passed all test cases.

Mock interview 

I wish that the mock interview platform has some recordings like interviewing.io so I can replay how I did less than five minutes to go over the test case and explained my approach.

I just quickly pasted the analysis I did in mock interview here. And then I will write a few sentences to match my presentation in the mocking interview.

Add caption

What I did is to go over the example with text string "acd" and pattern string "ab*c", and then drew a matrix with text string and pattern string. I did not make the choice, and by accident, I chose the pattern string in the right top corner, and then it is to go over each pattern char from left to right in the row. And also I explained to the peer that I will go over the base case first, which are first row and first column. After that I will go over each row and then I did go over the row on line 72, using text "a" and compare to each pattern string and fill the value with True or False.

Specially I explained the case with text "a" and pattern string "ab*", and b* will apply zero time. So the result should be true. T(0) is the symbol whereas 0 stands for pattern repetition number of times.

Analysis and C# code 

Here is my analysis and C# code. I explained to the peer later on how many practice I went over this algorithm, so many people in the world help me to go over the algorithm. I also watched the peers to perform the algorithm more than five times.

I still remembered that the Christmas day in 2017 a young Chinese graduate student performed the algorithm almost perfectly, I could not believe that he could do it perfectly in front of my eyes, I did go through several times with experienced programmers in the world, how they struggled to write recursive function multiple times. I did ask a lot of questions.

Just two days ago, the peer shared me the news he joined LinkedIn as an intern through the wechat. It is a side story. But I just wrote down to remind myself that teaching and learning is so efficient and once I know that a young graduate student can perform, I believe that one day I also can perform as well.

Leetcode 10: regular expression matching

February 1, 2018

Introduction

I understand that there is no hard algorithm, only lazy student. I have spent over 10 times to practice Leetcode 10: regular expression matching last eight months. Usually the peer writes a perfect solution and it takes 30 minutes, I experience a lot of good learning experience from those peers.

Last two months I start to write dynamic programming solution as well to solve the problem.

One hour practice

On January 31, 2018 I had a mock interview, and then I spent one hour to be interviewer. The peer  wrote a perfect dynamic programming solution. And the peer shared his argument that one time for b* pattern is not necessary in implementation.

Argument to think about

b* can repeat zero time, more than one time. But one time can be covered by zero time and more than one time this two cases.

Here is the transcript I reviewed.

Leetcode 10: regular expression matching

January 26, 2018

Introduction

It is another 8:00 PM mock interview. The peer is top ranking computer science master student, and she helped me to work on the dynamic programming solution of Leetcode 10: regular expression matching. First time after I practiced over 5 times on mock interview, I wrote a dynamic programming solution and passed all test cases.

Code review

Here is the C# code.

Highlights of changes in mock interview discussion advised by the peer. I told the peer that she paid so expensive tuition as an international student, and spent half hour to help me and tutor me to work on dynamic programming solution, I am so appreciated her help. She also thanked me to give her advice as well.

1. Line 15, change dp data type from int to bool;
2. Line 32, add i - 2 >= 0 in case index-out-of-range error;
3. line 39, use row, col variable instead textIndex, patternIndex;
4. line 50, remove dp[row, col] = 0 since the peer told me the default value is 0;
5. line 58, need to change dp data type from integer to bool, otherwise the expression is too hard to read.

Follow up 

May 9, 2019

Here is the code I wrote and fixed the issue and passed online judge.

Leetcode 10: regular expression matching

January 14, 2018

Introduction

It is so surprising that I met such a great master student from California and he also encouraged me to write a dynamic programming solution for Leetcode 10: regular expression matching. The peer is also very good to help me to understand b* pattern how to apply zero time, one time or more than one time. The peer looked at my analysis of logic and asked me to optimize to skip last char * if applying once. It is the first time I understood the idea after I struggled so long, the peer told me in person.

Learning is so much fun, specially when the peer is top ranking master graduate student with a lot of good intern experience, and also good research ability. I can tell the big difference from other graduate students with less practice on Leetcode algorithm.

Code review

My C# code was written in less than 30 minutes. The code has a bug to pass the test case "" with pattern string "b*". I need to work on base case when the text string is empty, it still can match pattern "b*" or "b*a*" etc.

Please study this version of dynamic programming code and then fix the bug in my C# code. Please work hard as the young graduate Chinese student does, here is the blog.

Follow up

The code is fixed and now it works for all test case. C# code is here.

Leetcode 10: regular expression matching

Dec. 29, 2017

Introduction

It is so interesting for me to learn Leetcode these days. I work on mock interview continuously on those 30 algorithms. And today I reviewed Leetcode 18: 4 sum last 5 practice, and then I tried to get organized and reviewed the past practice, and then found this young graduate software engineer working in facebook, I start to code review his post on each Leetcode algorithm.

Code review

Leetcode 10 algorithm blog is here.

Here is the gist I created for the study. I will play this code and write a C# and figure out how it is.

Code review: Leetcode 10: regular expression matching

Dec. 26, 2017

Introduction

It is another mock interview 12:00 PM. I had chance to help the peer solve Leetcode 10: regular expression matching. I did not expect that the peer can solve the problem almost perfectly. I was so surprised to learn from the peer how he wrote an elegant recursive function using while loop.

Code to study

Here is the peer's C# code. I like the implementation.

The above code failed last test case, "abaa" and pattern string "a.*a*". It should return true.

Here is the code to fix the above bug. The code passes all test cases on mock interview platform. But it failed on Leetcode 10 online judge.

Index out of range error, Line 28: System.IndexOutOfRangeException: Index was outside the bounds of the array. Last executed input: "ab" and ".*c"

Line 28: If(text[tIndex] != pattern[pIndex])

Actionable Item

After spending over 30 minutes to debug the issues using Leetcode 10 online judge, I learned that the recursive solution has a lot of issues. Later I will revisit the solution and give more objective comment on this solution.

Leetcode 10: regular expression matching

Dec. 25, 2017

Introduction

It is time to write hard working stories that will touch my heart again, I always like to read my own blogs and then get encouraged to work on more on algorithms.

I started my six round of mock interview after I finished around 30 algorithm a few days ago, so I started to use ID: 2017 to start a new round. Also I chose the setting called: Advanced level of interview, one level below the top one. The top one is to eat and sleep on algorithm. I just could not believe that I had to chance to learn so many things about the industry and how good people are to study or work for a software engineering career.

It is Christmas holiday break, and I decided not to hang out with friends. I choose to work and meet new people. I set up a few mock interviews on Dec. 24, 2017 from 4:00 PM, 8:00 PM, 10:00 PM. You know what, since machine learning algorithm picks up my setting of advanced level, this round is different. All first three interview questions for me to interview peer are hard level algorithm, same algorithm same day for three peers, Leetcode 10: regular expression matching.

Hard working graduate student

First peer is a university master graduate student with top 50 ranking university in California, I had chance to learn how to write a dynamic programming solution from him. I spent extra one hour 20 minutes to discussion other algorithm with him as well.

Dynamic programming solution is not easy for me to figure out. I had some questions about the implementation, and then I asked the peer. But I could not be convinced for three cases, a*, for zero time, one time or more than one time.

Here is the blog for the review of the peer's code.

The peer complained to me that he could not find enough interview opportunity for intern. I gave the advice for him, increase online presence. Write on quora.com or coding blog, document the practice. The peer is really good at dynamic programming algorithm.

Leetcode 10: regular expression matching

Dec. 24, 2017

Introduction

It is the hard level algorithm in Leetcode. Leetcode 10 is also called regular expression matching. I have practiced over ten times, and I always choose to use recursive solution.

I had a mock interview and the peer solved Leetcode 10 using dynamic programming.

Code review 

Plan to study the dynamic programming solution. Here is the Java code.

Code review: Leetcode 10: regular expression matching

Dec. 23, 2017

Introduction

It is the smart idea to ask the classical algorithm on the code review website. I did one on Dec. 22, 2017. I got one down vote, and 3 upvotes in first 24 hours. Compared to the classical algorithm Leetcode 10, I asked another algorithm question based on my practice, here is the link. I am still waiting for the first upvote for the algorithm.

Here is the link.

Code review: Leetcode 10: regular expression matching

Dec. 20, 2017

Plan to code review a dynamic programming solution to solve Leetcode 10: regular expression matching.

Here is the source code with the analysis.

I reviewed the above code, and rewrite the for loop using while loop since I do not like the loop variable in the for loop is changed inside for loop. I choose to use while instead.

I have some issues to rewrite the logic in the giant expression from line 57 to line 58 but had some issues to fail some test cases. So I keep the style even though I do not like it. I will figure out the issue later.

Here is the C# code.

Leetcode 10: regular expression matching

Dec. 17, 2017

Introduction

It is the best mock interview so far I have. I met a very senior developer working in Seattle area, and then I have to work on the algorithm called regular expression matching.

It is the challenging algorithm and very classical. I was told to work on dynamic programming and the peer likes to help me to work on the analysis and coding. But my argument is if I write a recursive with memo correctly then it should be easily applied to dynamic programming.

Code review

Here is the code I wrote in mock interview. The peer gave me instant feedback right away, and also wrote comment right away while I write first few lines of code.

Line 44 - 53, the code failed 6 test cases, only passed two test cases. I was told by the peer that I missed the test case like "" match pattern string "a*b*.*".

Also line 51, if the pattern string has only one char, it should return checking (char == '.'). The peer explained to me by adding the comment, using test case to help me understand the bug.

I fixed the variable issue on line 61, patternIndex variable should be used instead of using textIndex.

Leetcode 10: regular expression - Fun to play

Nov. 8, 2017

Introduction

It is really fun to play with code related to recursion tree after the mock interview. I ran into various error with a simple test case each time using Leetcode online judge, I learn from each failure and try to play with them. It is fun to play over hours and actually I like to learn something here. Let me document the issues first, and then figure out the solution later.

Test cases to help 

I like to list the test cases to help design the algorithm.

"", "a*"
"", "a*b*"
"bbbba",".*a*a"

Here is the C# code with a bug timeout - need to run at least 1 time first for a* pattern, and then run 0 time for a * pattern.


The test case for time out is here:
"aaaaaaaaaaaaab"
"a*a*a*a*a*a*a*a*a*a*c"

And the code causes the problem is shown in the following picture:

Here is the C# code with fix of timeout:

Leetcode 10: regular expression

Nov. 7, 2017

Introduction

It is such an adventure to work on Leetcode 10: regular expression. I chose the algorithm as my most favorite mock interview algorithm on quora.com last month, the link is here. But of course I was so nervous since I could not believe what I will write down.

My practice 

The peer was very nice and also helpful. I went over each test case and explained the matching, and I told the peer that I will use one of test cases to do whiteboard testing, recursive tree I will use at least 2 branch. For any char followed with *, I will match 0 time or 1 time or more than 1 time.

Here is my C# practice code. I ran the test cases, the code failed the test case with "" and pattern "a*". So I tried to fix it, added one base case, but still failed the test case. The code is here.

I told the peer that I will fix it after mock interview. I already took 43 minutes. Such a great workout.

Discussion between two peers 

Here is the discussion between two peers in mock interview:

how do you match "abb" with pattern "b*b"? Peer asked, and he put down the test case next to line 68.

I think that there are 3 branches in recursion tree:

b* match 0 time, so "abb" will check to match "b", return false;
b* match 1 time, so  'a' != 'b', return false;
more than 1 time will also return fail.

Let us check "bbb" with pattern "b*b", Julia suggested to work on.

We like to check 0 time, 1 time or more than 1 time.

For 0 time case, "bbb" will try to match "b" since "b*" 0 time means empty string. Return false;
For 1 time case, b matches b*, so "bb" will try to match "b", return false;
For more than 1 time case, "bb" will match "b*b", go back to 3 cases, return true.

Show some image to help understand the discussion:

Feedback from the peer

I just could not believe that the peer was a competitive programmer in high school, and then he just finished his computer science graduate school two months ago. He showed to me how strong his analysis was to handle the algorithm and coding was fast and quick later on, he finished in 12 minutes and it seemed to me that he got very good training on the algorithm. Will continue on my next blog Catalan number on the performance. The peer played contest on csacademy.com.

Follow up 

Nov. 8, 2017
The code is updated with code from line 37 to line 41 to fix the base case, empty string "" matchs "a*" pattern string.

C# code is here.

Two peers comparison

It is interesting to know that two peers can evaluate each other with top rating, but how about to compare the profile of two peers and see what we can tell from those numbers.

Leetcode 10 - regular expression matching

August 31, 2017

Introduction

It is my most favorite algorithm in 2017 called regular expression matching. I spent over 20 hours and over 3 months to work on the solution, and today I met a peer through mocking. And the peer showed me to solve the algorithm using dynamic programming, pass all test cases. Amazing talent!

Algorithm practice 

Here is Java code for me to study using dynamic programming. I watched the performance in 30 minutes meanwhile I went over my previous practice using dynamic programming code as well.

I did ask a few questions about the design.

Recursive function small talk

July 22, 2017

Introduction

It is most favorite thing to do in the world, write a quick and short solution using depth first search, and also in recursive function call. Julia wrote a blog about her recursive function practice a few days ago, called Maze.

Today Julia spent near 30 minutes to conduct a mocking practice, and then she chose to practice one more time.

One more practice 

Given a binary search tree, write a function to return the largest smaller value in a binary search tree. Here is the C# code.

It is the first time Julia wrote this recursive algorithm. She made a few correction through whiteboard testing. And then she argued that the algorithm should work, one thing is to prove that any number returned should be less than given value.

Time to share

It is so interesting that Julia did impress the peer after 60 minutes mocking interview, and the peer asked Julia how she practices. So it took extra 40 minutes for Julia to share her experience. Julia likes to get organized and give good advice to the peer.

Last 3 months Julia practiced the algorithm a few times, and she also used the algorithm as an interviewer. But she did not come out a correct solution first time.

Three things Julia shared her practice:

1. Leetcode 10 - the most important about recursion tree, return A || B || C, A is that b* stands for empty string, B is that b* stands for one b, C is that b* stands for more than once, like "bb". The recursion is in 3 branches.

It is the hard algorithm and Julia interviewed over a few people, only one person is very close to the perfect solution. The code was very clean and almost perfect. Julia learned through the experience, she was interviewed to write the algorithm twice, both of them were not correct, not very close to optimal solution at all. Julia shared honestly her experience on the algorithm.

This algorithm became Julia's most favorite one after she invested so many hours on it. She wrote a few blogs on this algorithm, the one she likes to share is here.

2. Code review on stackexchange website, her experience on code review. Link is here.
3. Refdash mocking interview.

It is the first time Julia was told to adjust the camera so that the peer can see her face impression, in first a few minutes. This is the second time Julia got complaint, first time the peer complained the echo sound, so she decided to use headset.