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.

Find the smallest substring that contains some given subset of characters

Oct. 28, 2017

Introduction

It is a long journey for me to come out the solution to pass all test cases. I did at least 4 or 5 time last 6 months to work on the algorithm called "Find the smallest substring that contains some given subset of characters". I posted the question on code review, link is here in Sept. 2017.

Today I had chance to interview a peer using the algorithm, I only can hear the voice no video, but I understood how tough the algorithm can be, specially for the first time player. The peer does not work on the algorithm before, and I worked with him near 50 minutes on the algorithm. First 20 - 30 minutes to work on the algorithm itself, I had chance to follow what he approached the problem. Next 20 minutes I asked him to write code so I can evaluate his coding skills and coding style.

The mock interview is such a nice place to meet people and figure out together how to improve technical skills. The conversation is interesting and also very gentle on the topics. I have to let the peer approaches the problem first, and then give some hint, and see how discussion can continue.

The peer is very diplomatic so I know that he must be an important role in his job. First he chose to use JavaScript to code the program, so I complimented him about he must know node.js framework.
Then I noticed that he wrote down some notes to show his logic thinking, it is very clear; he asked my feedback so I know that he is also very good listener.

Mock interview 

I found out that I always get best peer in the world, so I have to keep up with the peer about technical skills, help them to understand their strength and weakness. It is so interesting to have a mock interview.

The test cases discussed in mock interview are the following:
1. yxxz -> "yxxz"
1. xxyz ->"xxyz"-> "xyz"
2. slide window, two pointer technique
left pointer and right pointer
3. Move right pointer first, and then find a substring; and then move left pointer to make the substring smaller if possible.

For analysis, if the peer can come out the test case like the following: For example, for search string ['a','b','c'], source string "aefbcgaxy", the shortest string is "bcga", the peer has excellent analysis of algorithm, assuming that the peer does not work on the algorithm before. 

Julia's practice 

It is also a great idea to review my practices:
April 2015, blog is here.
April, 2017, it is documented here.
June 29, 2017, mock practice C# code is here.
Sept., 2017, it is documented here.
Code review is here.

Oct. 31, 2017
It took me three years to fully understand the algorithm and how to work out a perfect solution. This experience taught me how to treat others, more patient please. And this is the really great algorithm to evaluate the candidate the algorithm analysis and technical strength.