Leetcode 10 - Regular Expression Matching

July 2, 2017

Introduction

It takes a lot of practice to learn one of the hard algorithm on Leetcode. Leetcode 10 regular expression matching's problem statement is here.

Algorithm Practice

Julia practiced the algorithm more than five times in last three months, she wrote more than two times in her practice as an interviewee, and then she mocked interview more than three people to work on the algorithm.

One of best codes is here written in Ruby, Julia met a very experienced programmer and then learned a few things. The code is here. Julia will write it using C#, and then try to run against Leetcode 10 online judge and see how many things are missing.

July 2, 2017 2:48 pm
Julia spent 40 minutes to work on C#, and the code is working except timeout issue. C# code is here.

Memoization Solution

One of the solutions is to use memoization to solve the problem. 

3:02 pm, Julia added memo as a Dictionary<string, bool>, to simplify the problem, assuming that " " is not used in regular expression matching, the code passes all test cases.

C# code is here.

No Memo Solution 

Julia could not figure out the solution by herself, so she googled and then came cross this solution through Leetcode discussion. C# code is here.  Leetcode discuss link is here. She wrote a blog about the solution, link is here.

July 6, 2017

One more recursive solution without using memo is here.

Problem solving

July 2, 2017 2:48 pm
Julia spent 40 minutes to work on C#, and the code is working except timeout issue. C# code is here.

July 6, 2017

To solve timeout issue, it is to early return the recursive tree, do not go over every node of tree.

Here is the C# code.

It is a brutal truth, Julia is not ready to be a professional interviewer or expert on algorithm. She could not spot the timeout bug in the code. She took more than 4 days and then figure out the bug. Right side is the C# code written in July 2 with a timeout bug, left side is the bug-free code.

The return statement with the format of "return A || B" will not run B if A is true. In other words, "return A || B" is not the same as
bool result = A; 
result |=  B;
The above solution to separate in two statements will cause timeout, since every branch of recursive tree will be executed. It is a fatal bug.

Inspired by the short and clean code, Julia continued to make the C# code short and clean. C# code is here.

One more step to simplify the code, code is here.

Summary 

It is so exciting to learn a hard algorithm through so many practice and code review. Julia worked with over 5 peers to solve the algorithm, she also wrote more than 5 times. Through the journal of the practice, she is able to track her progress and learn to solve the problem.

It is so much fun once the timeout bug is found through online judge on July 2. Julia kept reading more solutions until she found out the real issue - subtle bug in the writing.

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.

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

Leetcode 10 - Regular Expression Match II

July 2, 2017

Introduction

Where is the best place to find better idea for an algorithm? Julia checked the hackerrank leaderboard, but for her practice of Leetcode 10 - Regular Expression Match, she googled using keyword, "Leetcode 10 C# solution", she found one today. Here is the C# solution in the dicussion panel.

Here is the C# solution she need to study today, and the algorithm implemented is better than Julia's one. She likes to study the algorithm.

Algorithm Study

C# solution using recursive, but no timeout issue. Solution is here.


July 5, 2017

Julia worked as the mocking interviewer 35 minutes on this algorithm, she had some issue to give out clear advise on the iterative solution.

In other words, there are 3 options with string "a" and pattern "a*":

a* counts as empty, why?  because it may be "a" and "a*a"
a* counts as single a, so, next will be string "" and pattern ""
a* count  as multiple a, so next will be string "" and pattern "a*"

July 6, 2017
Continue to study a DP solution, discussion link is here.
Dynamic programming solution - practice code is here.

Read an Amazon intern story in Chinese - link is here.

Another recursive solution - Julia's most favorite one
C# practice code is here.

Leetcode discuss: Leetcode 10: regular expression

Here is the link. 

C# My showcase of practice starting from 2017

July 2, 2020

It take some time for me to review all my past practice on this hard level algorithm. What I like to do is to write a few discussion posts first, and then I will figure out how to review those practice.

I went through very good learning experience to work with over 10 programmers as an interviewer or interviewee. I documented my p-r-a-m-p mock interview website over 10 times practice here.

Leetcode 10: regular expression
July 2, 2017
Case study - mock interview as an interviewer on July 2, 2017

C# code review memoization practice on July 2 2017

January 26, 2018
Case study: dynamic programming solution on January 26, 2018

April 21, 2018
Case study: mock interview as an interviewee on April 21, 2018

Practice with a bug
March 29, 2018
Case study: dynamic programming solution with a bug on March 29, 2018

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

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.

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

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

10+ rounds of mock interviews

April 24, 2018

Introduction

It took me more than one hour to figure out how many rounds of mock interview I had starting from March 2016. I learn that it is important for me to get organized, and try to get some insights from those mock interviews.

Mock interview 

Here is the summary to show my ten rounds of mock interview.

Learning is so much fun

I used to attend church and had good time in Willingdom small group from 2010 to 2015. I used to go out with over twenty people to hiking and enjoyed trails near the city of Vancouver. But I never imaged that learning algorithm and data structure can be the similar experience. You can learn from one peer a time, and then learn from hundreds of players. Only thing is that I have to force myself to work on those 30 algorithms again and again. But it surprises me that I learn better from those 30 algorithms.

What I believe is that once you learn how to master a hard algorithm like Leetcode 10: regular expression matching and Edit distance, you just apply to other algorithms.

Bible teaching always uses seven to remind us to forgive a person. But learning algorithm Leetcode 10: regular expression matching takes me more than 7 times, more than 14, 21 times. With so many peers to work together on the algorithm, I start to think and understand how I learn the algorithm thoroughly. That is a lot of hard work and a lot of patience to allow myself master the algorithm.

C# source code

It takes time for me to put together all C# source code I wrote for each round of mock interview. Here is the folder to check on github. I will add one by one for each algorithm or all algorithms for each round.

Reference:

All the algorithm and problem statements can be looked up here.

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.

July 18, 2017 algorithm review

Sept. 14, 2017

Introduction

It is two months ago, I did spend 3 to 4 hours to review my own practice before 8:00 pm. I went over around 30 algorithms, print one by one on the paper, and then read one by one. I really learned from the preparation, and I like to open a folder on my own github, and list all those algorithms I chose to study on July 18, 2017.

It is so interested to know that once I am busy with the study, the nervousness is kind of going away. I did very good one on preparation, and I had great performance later on the evening to complete code in limited time.

Algorithms

Algorithm 1. In order successor
Algorithm 2. Flatten the dictionary
Algorithm 3: HTree
Algorithm 4: Reverse words
Algorithm 5. Find distance binary tree
Algorithm 6. Leetcode 23 Merge K Sorted List
Algorithm 7: Leetcode 37 Sudoku
Algorithm 8: Leetcode 49 Group anagrams
Algorithm 9: Leetcode54 SpiralMatrix
Algorithm 10: Leetcode 72 Edit distance
Algorithm 11: Leetcode 114 Flatten Binary Tee to Linked List
Algorithm 12: Leetcode 212 Word Search II
Algorithm 13: Leetcode 295 Find median for path stream
Algorithm 14: Leetcode 295 median of stream
Algorithm 15. Leetcode 300 Longest Increasing Subsequence
Algorithm 16. Leetcode 416 Partition equal subset sum
Algorithm 17: Leetcode 516 Longest palindrome subsequence
Algorithm 18: Leetcode 605 Can place flowers
Algorithm 19: Binary tree two path same value
Algorithm 20: Leetcode 239 Sliding window maximum
Algorithm 21: Leetcode 57   Insert interval
Algorithm 22: Leetcode 10   Regular expression matching
Algorithm 23: Leetcode 547 Find Circle
Algorithm 24: Leetcode 130 Surrouned region
Algorithm 25: Maze Project
Algorithm 26: Short Job First using Icomparer
Algorithm 27: Leetcode 554 Brick wall

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

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.

Tell a friend to tell a friend

August 4, 2018

Introduction

It is a good idea to join interviewing.io for mock interview practice. I choose to be an interviewer on the platform since this January, 2018, I have more than 60 mock interviews as an interviewer. It is so nice to get on the platform and meet and talk about algorithms. Tell a friend to tell a friend is the title of my blog.

It is most rewarding job to be a mock interviewer. I like to showcase one of my mock interview as an interviewer here.

One showcase

Yesterday I had chance to interview a new graduate from Waterloo,  and I learned from his performance how good he can perform. He enjoyed the multiple solutions and then took hint to go for the optimal solution based on minimum sliding window.

After we finished 30 minutes interview, I talked about my favorite algorithm last 3 days. He gave me his analysis, such great sharing.

Sharing feels so good 

I like to take some time to write notes for this mock interview 60 minutes. I had recording, transcript, code. I like to document how good it should be. I will work hard to get myself there. It is on interviewing.io, we do not choose to share the video as showcase this time.

The peer does not advocate too much to practice a lot of Leetcode algorithms. Just work on basics subsets of problems. I can tell from his talking and analysis and he has good talent. Of course, he can improve a lot in terms of coding and other things if he invest a lot of time to complete a lot of Leetcode algorithms.

Sliding window minimum

I like to talk about things I learned from his analysis of sliding window minimum algorithm.

The problem statement I wrote is here.

Here is the transcript to show the algorithm to get range sum using dynamic programming.

Extended algorithm is to get the minimum value of the sliding window.

Here is the blog with more detail, I will work on and make it complete.

Second algorithm - Iterator for list of iterators 

We did talk about the iterator, and what is size of minimum heap? If all iterator's lists are not sorted, then the minimum heap will load all elements into heap or binary search tree.

Here is the discussion of transcript. The main idea is that all lists are sorted then it is easy to use a minimum heap with size of count of iterators. If all lists are not sorted, all elements in all lists can be put into the list first.

Here is the blog I wrote for the discussion.

The advice from the interviewee

It is better to study leetcode by the tag called design. Here is the link.

Two more links:

//https://www.youtube.com/channel/UCPumyEKs86w-GtWDd2XQYtg
//https://www.youtube.com/channel/UCDHkPnEcrEf3B9-isB4jXIw

Learn dynamic programming

I chose to learn dynamic programming using Leetcode 10: regular expression matching over 10 round of mock interviews.

The interviewee suggested me to work on 10 dynamic programming on elements of programming interview, and then work  on easy level dynamic programming on leetcode.com

Summary

I had chance to meet a strong undergraduate student on mock interview. I learned from his performance. We had discussion over one easy, two hard level algorithms. And also we had exchanges of ideas how to work on interview, and how to prepare.

One of statement May be an argument or fact:

Waterloo undergraduate computer science students, all they do are working on algorithm problems and prepare for interview.

References

Feedback from the interviewee

Interviewer feedback

Leetcode discuss: Leetcode 10: regular expression

Here is the link.

Case study: dynamic programming solution on January 26, 2018

July 2, 2020
My practice was on January 26, 2018. Here is my blog to document my experience.

Case study
It is a good idea to work on a simple test case, and then build a table to calculate the value of regular expression matching.

I like to share the table I prepared on my blog in 2018. Here is the blog.

Test case: acd with "abc" pattern string

public class Solution {
    public bool IsMatch(string text, string pattern)
        {
            if (text == null || pattern == null) // false 
            {
                return false;
            }

            var tLength = text.Length; // 0 
            var pLength = pattern.Length; // 4

            var dp = new bool[tLength + 1, pLength + 1]; // 1, 5

            dp[0, 0] = true; // 

            for (int i = 1; i < tLength + 1; i++)
            {
                dp[i, 0] = false;
            }

            // "" matches "a*b*" etc. 
            for (int i = 1; i < pLength + 1; i++)
            {                
                dp[0, i] = i >= 2 && pattern[i - 1] == '*' && dp[0, i - 2]; 
            }

            for (int row = 1; row < tLength + 1; row++)
            {
                for (int col = 1; col < pLength + 1; col++)
                {
                    var visitChar = text[row - 1];
                    var patternChar = pattern[col - 1];

                    var isStar = patternChar == '*';
                    if (!isStar)
                    {                        
                        dp[row, col] = (patternChar == '.' || visitChar == patternChar) && dp[row - 1, col - 1];                        
                    }
                    else
                    {                                  
                        dp[row, col] = col >= 2 &&
                             // zero time
                            (( dp[row, col - 2]) ||
                             //                                                                  one time         || more than one time
                             ((pattern[col - 2] == '.' || visitChar == pattern[col - 2]) && (dp[row - 1, col - 2] || dp[row - 1, col])));
                    }

                    /*
                     * code review on May 9, 2019
                     * "mississippi"
                       "mis*is*p*."
                    else
                    {                            //   zero time          one time           more then one time        
                        dp[row, col] = col >= 2 && (dp[row, col - 2] || dp[row, col - 1] || dp[row - 1, col]);
                    } 
                     */
                }
            }

            return dp[tLength, pLength];
        }
}