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.

How to read the algorithm?

March 10, 2018

Introduction

I reviewed the mock interview this January 25, 2018 as an interviewee, I was asked to solve the algorithm to find shortest continuous subarray that contains all of the values from the set. After a few minutes to go over keywords, I told the interviewer that the algorithm is exactly the same one I practiced over 20 times last few months called "Find minimum substring containing all unique keys".

How to read the algorithm?

Here is what I did, I wrote down keywords:

Keywords:

 given a set with integer -> >0, distinct

 given an random integers

Ask for: 

Shortest -> greedy

continuous -> stop -> 

subarray -> 

return subarray itself ->

minLength =

Algorithm review

I just copied my analysis with pseudo code from the mock interview. The interviewer told me to go over the algorithm with him using pseudo code, so I did explain the algorithm in detail.

Here is the mock interview practice.

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.

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 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.

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.

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.

code review: Find the smallest substring that contains some given subset of characters

Dec. 2, 2017

Introduction

The sliding window algorithm is very challenge one even after I posted Find the smallest substring that contains some given subset of characters  two months ago. Today 12 PM I had a mock interview and then I have to work on the similar algorithm with a peer from the United Kingdom. With the peer's help, I spent 50 minutes to go over the analysis and coding but still could not finish the algorithm writing, we had a chat about how to work on algorithm after we worked on both interviews 80 minutes. The peer asked a break, we took 20 minutes break to chat about algorithms. In last 5 minutes, I was asked by peer to finish the algorithm. I almost finished but timeout, time limit is 110 minutes. The fact is that I lost my writing on the platform.

I need to recall what I did about the coding, and then post the algorithm here. The peer had good advice for me to write the algorithm this time, the code will be different from the one I wrote before.

Coding

Now it is Dec. 3, 12:09 AM. This version of code passes 2 test cases, fail 5 test cases. The C# code is here.

There are two issues in the code, first the input ["A"], search string "B", the result should be empty, not "B". Second issue is "Index was outside the bound of the array".

Continue to work on the bug fixing.

Now it is 12:35 AM. I fixed all the bugs. The function's arguments are not meaningful, so I mixed them together, one is arr, one is str. There are more than four places I mixed them in C# code here, line 26, arr[index] should be str[index], same as line 45, line 47. I changed them to meaningful name using char[] source, string search.

Lesson learned

Lesson learned: Always use meaningful name. Express the intent. I should change the variable's name to avoid the errors at the very beginning.

The C# code is here to look up.
Line 58
var isNeeded = dictionary[visit] > 0;

Actually I wrote first like this:
var isNeeded = Array.IndexOf(arr, visit);

And the peer asked me the time complexity of Array.IndexOf, it is O(m) and m is the length of the arr length. I should make it O(1) time instead. The peer worked very hard to help me, he followed my analysis of algorithm, time complexity O(n) where n is the length of search string instead of O(mn).

And the bugs are fixed to make the changes on the following lines.

Line 65 - add dictionary.ContainsKey(current) to avoid run time exception. The peer told me to move line 77 - 85 inside the while loop starting from 58 to 88, to make the code more simple to write.

ToDictionary using LINQ

Julia wrote the code in mock interview, she is still learning how to write LINQ statement. She memorized the tip she got from the code review.

var dictionary = arr.ToDictionary<char, int>();

And the peer was confused, and asked what I was writing. So, I wrote a for statement instead right away. I did not know that I have to write two mapping for key and value using LINQ statement in mock interview.

The LINQ learning is challenging, I should write
var dictionary = arr.ToDictionary(c => c, c => 1);

Discussion between two peers

It is the first time Julia learned that how good a peer can perform on the recursive algorithm, specially how to compose the test case quickly with the art of simplicity, and followed with the code.

Julia also learned that a programmer from other side of earth, North Ireland. Julia thought that the peer must work for Nokia before, but it ended up that Finland is far away from North Ireland. The peer corrected Julia on this.

The peer praised that Julia did very well on analysis of the algorithm, best one in last 5 or 6 peers worked on the algorithm. Julia gave honest response. It is all about hard work. Here is the code review about the algorithm on stackexchange.com, Julia worked on the algorithm over 2 weeks in 2015, and then she practiced mock interview on the algorithm over and over again. Here is the blog about over 5 or 6 mock interviews on the algorithm wrote in April 9, 2017.

Julia later looked up the university of North Ireland, Queen's University Belfast and talked to her roommate about Great Britain, compared to University of Victoria.

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.

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.