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 smallest substring containing unique keys

Feb. 27, 2018

Introduction

I had two mock interviews as an interviewer and the algorithm is find smallest substring containing all keys. I had chance to observe how top university graduate learned the algorithm from the scratch. I know that it is hard level algorithm, even though one of peers is top graduate and very well educated, but understanding the idea and putting them into the code are two different talent. I just learned that the peer wrote a portion of the algorithm to use a hashset to check sliding window containing all keys or not.

The code was so buggy and even I could not handle the code very well. I missed the bug even after I reviewed the code. It took us more than 10 minutes to work on the code together.

Through the process, I definitely could tell that the peer was working very hard. The peer communicated very well.But coding takes some practice. It cannot be shortened without failure, mistakes, and all kinds of issues in-between.

Code review

Since I reviewed the code, I should claim part of the ownership of the code. I should copy the code and remind myself later on, be more careful when I review the code.

The mistake is
unorder_set<char> map
...
map.insert(arr[left])
map.insert(arr[right])

The char should be str[left], str[right] instead. I made the same mistake before to mix two variable names, from that on, I always go ahead in the beginning to change the variable names in the meaningful way.

Find smallest substring containing unique characters practice

January 14, 2018

Introduction

It is the Saturday morning and I had 10:00 AM mock interview. I had a very good peer to help me to practice one more time the algorithm called "Find smallest substring containing unique characters practice". The peer also uses C# to write code, but after the peer wrote the algorithm called "Find Binary search tree successor", I compared his performance to my first performance in 2016 and a first practice in 2017, I knew that he has strong engineering skills. So I managed to get his very good code review for my practice this time.

Algorithm analysis

Here is my analysis of the algorithm. I like to present here. Since I wrote the code based on the idea presented in the analysis, the peer advised me to change the design, do not define the substring variable (line 31) and get the substring all the time; and the concern of heap usage to store C# reference variables. Only last line of code to return substring using slide window left pointer value and substring length (line 40).

I spent extra a few minutes to explain the time complexity of the algorithm, since we are doing iteration of the string once, and then each sliding window we are not recounting all the chars to see if the substring is found or not, a variable is maintained to keep check. So the time complexity is optimal. It should be around O(n), since left pointer of slide window at most visit each char in the search string once, same as right pointer of slide window.

Code review  

Here is my code to pass all test cases, I spent around 40 minutes to explain the algorithm and write the code for the idea. Since the peer had not worked on the problem before, I spent extra time to go over the idea and explain my analysis and design of the algorithm.

I spent extra 5 minutes to find the bug and then make sure that dictionary variable is filled with all keys.

My code with a bug I did not catch through my whiteboard testing, run tests button catches it:
    var dictionary = new Dictionary<char, int>();
    keys.ToDictionary(key => key, val => 1);

Should be:
Line 14:  var dictionary = keys.ToDictionary(key => key, val => 1);

Since the peer has more experience on LINQ than I do, he is very helpful to give some explanation how to construct the key and value using LINQ. Need to look up Lamda expression keyword later on.

The above code a few places are reviewed by the peer for improvements.

line 50 - the peer advised me first to move the code to if block to avoid extra work, string usually takes some heap space. Later the peer advised me to remove the variable.

line 52 - the bool variable is not necessary

line 60 - add ++ after var leftChar = search[left++]; so line 71 can be removed.
line 64 and line 65 merges to one line.

Here is the code after the peer gave me the code review. I will document each review the peer gave to me, and some explanation.

No need to store substring

I like to present a diagram about the code review I got.

Code with modification

Here is the code after the modification by the peer for the above section.

Being interviewee: Find smallest substring containing all keys

April 28, 2018

Introduction

It is my algorithm called find smallest substring containing all keys. I was so happy to write a perfect solution in 30 minutes, but I noticed that I had to slow down, work with the interviewee since he was not so strong in terms of coding. I may have to focus on the explanation of the algorithm, and also work on a small example to walk through the algorithm.

Mock interview

The peer actually asked a few questions on the test case I chose. After that, he asked me to give him some advice how to prepare algorithm and data structure interview.

I gave 5 minutes talk at least, and also wrote down some notes.

Here is the transcript.

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. 

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 smallest substring containing all keys

Feb. 4, 2018

Introduction

It is the algorithm I have to write for my 10:30 PM mock interview. The peer was very helpful and I had 30 minutes to complete the analysis and code, I did fix the grammar error in last minute and pass all test cases.

I can tell the difference. Since I understand the process of sliding window containing substring, how the left pointer can slide through if the substring contains all keys. I had one practice in January and then I got a few advice to optimize the algorithm. This time I could write the algorithm much quickly.

The peer advised me to speed up coding if I can.

Code review

The C# code is here. The peer advised to add extra variable to store the start position of substring, I added variable on line 21 called startIndex.

Being interviewee: Find smallest subarray length containing all numbers in target array

April 23, 2018

Introduction

It is the classical algorithm called find smallest substring containing all keys. I have practice the algorithm over ten times last 12 months. I learn so many things through the practice, and it is my most favorite algorithm.

I wrote an algorithm using exactly same idea to apply to integer array.

Mock interview

Here is my C# code.

Follow up after mock interview

It took me a while to write and simplify the code from line 60 to line 66 during mock interview. What I did is to go over in detail if the left char of sliding windows is not in the dictionary, or in the dictionary. And then discuss one step a time.

Other way to think to expedite the process is asking myself four critical question:
1. When to break the while loop 51?
2. When to decrease the variable numbersFound
3. when to decrease the dictionary for the key if the left char is in the dictionary
4. Please move the left point one step forward to start a new sliding window

Find smallest substring containing all keys

March 6, 2018

Introduction

It was so exciting to know that the peer got the algorithm when I booked the interview early this afternoon. I know that the algorithm is hard level, and definitely it is very interesting to learn how the peer will solve the algorithm, specially if the peer does not work on the algorithm before.

Code practice

I know that the hard level algorithm is biased for the people never working on before. So it turned out that the peer came out the linear time solution with optimal time complexity, but the design has flaw which could not find smallest substring.

This is the first time I evaluated the idea as the interviewer, and then I came out the counter example to explain the defect in the design on line 35.

What I saw is that the peer was very calm and approached the problem, and then wrote code ready to run the test cases.

Here is the code I reviewed. I also learn some technology and know more about react framework. I did spend 30 minutes on react course before the mock interview today.

LeetCode article: Finding the Minimum Window in S which Contains All Elements from T

April 26, 2015

Problem statement:

Finding the Minimum Window in S which Contains All Elements from T

Introduction

I tried to solve one algorithm in 5 days in a row from January 28 to February 3 in 2015, every two hours after 6 PM in a week. But I could not do it successfully. 

The algorithm is called find smallest substring containing unique keys. At that time, I did not have the peer to talk to, and I came home after the full time work, I wrote the code on the paper, 2 hours each time from Monday to Friday. 

I wrote on papers, page by page. I tried so many times but there is always new issues coming out. It is the first time I learned that there is brute force solution, and time complexity can be analyzed using kind of mathematics. 

The idea to solve the solution is to use slide window and also keep the minimum time complexity by tracking the unique keys inside the slide window by maintaining a variable.

从2015年1月28到2月3日, 每天二小时, 总共14个小时, 我练习写这个算法。

最优解是用O(N)的时间, N是字符串的长度。

从一个简单的例子, 开始分析。 

比如, abc 是要寻找的字符, 另外一个字符是 abbca; 如何从abbc, 找到 bca?

最笨的方法, 就是起点有多少选项, 终点有多少选项， 时间复杂度就是O(N²)。

最笨的方法就是O(N x N), 想要最优, 只能走一遍, 二个指针, 起点, 终点, 如何移动, 保证起点移动是在O(N)的算法中, 终点的也在. 设计中小心不要移太多.

Follow up after 10 days

on June 5, 2015

Algorithm blog in Chinese, with good example and illustration of the algorithm. Blog link is here.

Follow up after 24 months 

April 9, 2017

Follow up Feb 5 2018

One thing I like to do is to read the above blog in Chinese, and then make notes more readable, and then go over the source code as well. Save notes and code as two gists, and later I will write a C# solution based on the source code.

Write down the notes in the above blog and pay attention to the thinking process. Here is the gist. 

Smallest substring containing all unique keys

Feb. 12, 2018

Introduction

It is so much fun to play mock interview. I met the same peer fifth time.

After the mock interview, I gave the algorithm to the peer to solve, and I am busy working on my hackerrank contest algorithm.

Last minute, after ten minutes to give out the algorithm, I found out that I made a mistake on the constraint. The array should include non-negative elements only. And the peer came out the solution I could not understand.

The problem is to find a continuous subarray with the given sum, and then the solution is to apply dynamic programming using O(n) time to get the prefix sum from left to right, and then use two pointer techniques on an ascending array.

Code review

I chose to skip my algorithm, and asked to study the peer's solution. Here is C# solution I like to review and then rewrite later.