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.