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.