Find smallest substring containing all unique keys

March 10, 2018

Introduction

It is my most favorite algorithm called "Find smallest substring containing all unique keys". I had a 10:00 PM mock interview, and then the peer solved the problem using less than 20 minutes. I could not believe that he wrote such great solution.

After mock interview, we discussed a few algorithm. He advised me to work on the algorithm called Leetcode 688: Knight probability in chessboard. I had a short discussion about the random process, and he quickly told me to study the algorithm.

I am so glad to share my favorite Leetcode blog, former ICPC coach's link to the peer. The peer already solve over 500 algorithm on Leetcode. We had discussion over 80 minutes, I learned a few things about the problem solving.

Code review

I did review Java code, here is the link. Later I like to write a C# version of the algorithm.

Find minimum substring containing all unique keys

Feb. 25, 2018

Introduction

It took me 25 minutes to analyze the algorithm and also write C# code. I used exactly 30 minutes to complete the task.

Code review

Here is the C# code passing all test cases.

Comparison to the practice 5 month ago

The code I wrote is much more simple compared to the one I wrote more than 5 month ago, I can look up the code through the question I asked on stackexchange.com.

The while loop to handle left pointer is much simple using one variable to count unique keys in sliding window. The loop invariant is clear and short compared to the one asked in the code review. The loop invariant in the while loop in the code review is giant expression and should be shortened.

Find smallest substring containing unique keys

Feb. 18, 2018

Introduction

It is my most favorite algorithm in 2018 called find smallest substring containing unique keys. That is the algorithm I have practice over 10 times from March 2017 to February 2018. And also it is the most popular interview question and I had one in 2015 January. I had a very good experience 45 minutes since I could not pass the phone screen, but I learned to be open and welcome the challenges as a programmer, show the world that I do care about learning the algorithm, and keep working hard as a software programmer.

This algorithm is the reason I start to write a coding blog starting from May 2015. I knew that I was not so good at learning, but I just started to document my learning and my emotions like feeling of struggling and then enjoy the journey to be a good thinker in algorithm and data structure.

My experience of interviewing

It is the Sunday morning 10:00 am mock interview. The peer had to work on the algorithm, and I worked with the peer 70 minutes until she finished the code, and also passed all test cases.

The first 30 minutes I went over my own blog to review the past practice, and once a while I stopped and gave some advice to the peer.

I do enjoy the interview. I do not have coworker as a programmer in my work place, I am a solo programmer. I really know that it is my own task to find the chance to work with people.

I learn from my experience on this algorithm, so I also like to share the tips to the peer through the mock interview.

Here is the C++ code I reviewed, and the code passes all test cases.

Here is the comment I wrote to share the advice after the mock interview.

My feedback after the mock interview

The peer worked very hard and also very open to advice, took the hint. The peer wrote the algorithm around 70 minutes including discussion, fixing all the bugs etc. 

I like to share that I could not finish the smallest substring algorithm in my first five practice on the mock interview platform, in 30 minutes. I had different issues, but last 3 or 4 times I kept got very good peer to help me, one is really good. Please take a look here, the peer helped me.  And the other one is also good, the peer helped me to pass all test cases in 30 minutes, here is my practice blog. 

Just practice the same algorithm again and again, work on one thing a time. 

Smallest substring containing keys

January 7, 2018

Introduction

It is the great learning opportunity in Sunday morning. I spent 40 minutes to work with the peer on her first time to solve smallest substring containing all characters. I learn from the peer to work on the solution, the peer solved the problem to pass all test cases with my help. Even though the time complexity can be improved.

Code review

Here is the C++ code the peer wrote and I like to review the code later on.

Here is the gist I wrote for the analysis of time complexity and I explained the issue using an example.

Highlights of my review on mock interview:

1. line 20 - 22, I made the suggestion to group all three int variables declaration together.
2. line 26, I found the bug to add head <= runner instead of head < runner
3. line 27, I advise the peer to extract a variable currentChar to avoid duplication code
4. I added extra line on line 35 and a few other places
5. I argued with the peer the idea of runner = head -1 on line 42 and then I understood her idea, because she likes to offset +1 on line 47
6. I added line 47 for the peer
7. I told the peer that I like to review the code before she likes to run the code, so I can make the changes from item 1 to item 6.

Find smallest substring containing keys

January 6, 2017

Introduction

It is another 8:00 PM interview and I had to work on the algorithm called "Find smallest substring containing keys". I have worked on the algorithm over five times last nine month, on my last mock interview the peer helped me and advised me to change my idea to slide left pointer of sliding window.

Here are blogs related to search results using keyword: smallest substring in my coding blog.

Here are last few practices:

Oct 28, 2017 practice is here.

Dec. 2, 2017 practice is here.

Code review 

The peer helped me through the whole process, I spent over 38 minutes to write code, pass all test cases except one. Here is the code.

Follow up

Now it is 10:50 PM, I used Visual Studio to debug the code and found the bug. On line 52, left < i should left <= i since one char should not excluded as a substring. The start and end position are the same index value.

I do not need to use HashSet to check if the char is one of keys, seen line 17, I can just use dictionary.ContainsKey(visit) to find out, seen line 30. I looked up my last practice and it is the advice from my peer back in Dec. 2017.

Feedback from the peer

It is very hard algorithm for me to work on in mock interview, but with the peer's help, I managed to find bugs early and continued to write and completed the code.

Here is the feedback.

Editorial notes

Programming is such a fun activity for me now. At least today January 6, 2018 I had so much fun to work with best talent programmers in the world.

Every mock interview is so surprising. The first one I was surprised to work with a peer, he taught me how to write a spiral matrix print, and then we exchanged the experience about algorithm problem solving related to same tree and median of stream. The second one was more surprising, because this one told me that he will work on Google onsite interview next month. The third one was even more surprising, I was busy learning python to follow the peer's problem solving, and then peer told me that she is M.I.T. computer science graduate.

How difficult is it to work on algorithm and data structure problem solving? I have worked on the hard level algorithm to find smallest substring so many times, and then I finally understood that how long it takes me to master an algorithm. It takes me 3 years to fully master the algorithm.

Today every step the peer worked me through the code and asked me questions, meanwhile I explained to the peer what I tried to work on, I even copied the analysis and then said that I do not know what to do, just make sure the test case will work for first three chars, and then go over each char through whiteboard testing.

How patient I will be when I write code in daily work, can I write production ready code every day starting from January 8, 2018? Do I need to write hard level code like this one "Find smallest substring containing keys" every day?

The mock interview experience just brought the whole world to me. I sit in the home office whole day and continuously work on the algorithm, exchange the tips to solve the problem.

I know that programmer life should be easy once I master the skill to work with smart people, open and share the ideas.

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.