Leetcode 76: Find smallest substring

Sept. 25, 2017

Introduction

It is the classical algorithm similar to Leetcode 76. I already practiced more than two times, and I stumbled on the algorithm again. The mock interview started from 10:00 PM, and I started first to work on the algorithm, first 12 minutes I spent the time to explain the idea to solve the problem, and then I spent 18 minutes to write the code and thought out loud.

I found a secret. When I am too busy at work, I need somehow to remind myself, what is most important thing to work on.

It is true that most important is to train myself with basics, and learn how to work with the peer in more efficient way.

By going over mock interview, I have chance to educate myself, get more advice, and then I can start to apply to my current job. One mock interview a time, I figure out my weakness every time.

Last mock interview I found the issue of my understanding C# Array, and I spent 4 hours to work on Csharp 2000 things. I wrote a blog and then found "Csharp 2000 things" website, and I really enjoy learning from the short snippet.

Algorithm Practice 

C# code is here. I did not finish code in 30 minutes. I need to work on the left pointer while loop.

After Mock practice

C# code is here, with unique array "xyz" and string "xxxyz", the maximum substring is "xyz".  But failed on several issues.

Line 75, 76, if the visit char is not in the hashmap, the code will have run-time exception.
Line 89, the while loop condition to check if left pointer should move should be changed, one case is that the char is not in the hashmap, or if it is in the hashmap and also its value is negative.

Continue to update C# code, next version is here. The fix is on line 106,
   map[str[left]] ++;  // once the substring is found, and then left pointer should be moved to right, increment the hashmap on the char's count.

Continue to update C# code, the fourth version is here. The run time exception bug is fixed.

Continue to update C# code, the fifth version is here. The feature is added to remove the char not in the array when left pointer is handled.

Last two practices

Review last two practices, the link is here.

Actionable Item

It is so interesting to learn from my experience. It takes me over 3 years to learn the string search algorithm using sliding window. I still remembered that in January 2015, I spent a week every day after the work, wrote a lot of code on papers and tried to figure out the algorithm. At the end of the week, I decide to become a blogger to write blogs every day to track my progress.

I failed in 30 minutes to solve the problem, and failed in a week, and then failed after a few months, I wrote a blog in June 2015, the link is here.

Plan to study the algorithm "Length of the longest substring without repeating characters" on geeksforgeeks.org.

Train my eye to catch common bugs

Those three bugs in my first writing are common ones. The first one is related to hashmap, the dictionary to store unique characters. We need to check if the key is existing in the dictionary first. The second one is to discuss two options for the character, either in the dictionary or not in the dictionary. The third one is to maintain the dictionary value by checking increment and decrement correctly.

Nothing is new in terms of bug type. All I have to do is to review the code while I am doing whiteboard testing, think out loud, and ask myself what possible bugs are in the code.