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.