Being an interviewer: Find minimum substring containing all characters

May 4, 2018

Introduction

It is very good learning experience to be an interviewer for this hard level algorithm from Leetcode. The algorithm is hard for the first time player to come out the optimal solution using slide window, and also apply time complexity O(n) where n is the string's length.

I just learned one more time to communicate with the peer, worked on brute force solution first, and then moved on optimal solution discussion after 30 minutes.

Mock interview

Here is Java code I reviewed. I also started to ask questions about Java, and ask the peer how long they work on Java, why to choose Java for interview.

I was so glad to introduce the slide window technique to the peer, and also used the example: "AAAAABC", explained that extra four A characters can be removed for minimum substring.

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

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 string using slide window - a small talk

April 9, 2017

Introduction

It is exciting to write the sliding window search algorithm with time complexity O(N),  N is the string's length. The similar algorithm is here on geeksongeeks.com, and also it is very close to the Leetcode 76: Minimum Window Substring.

There is a short story about the sliding window algorithm. Julia still remembered that 2 years ago in 2015 January, Julia asked to get her first onsite interview after a tech talk social event, she could not pass phone screen from top four software companies, Facebook. But she likes to find out what if she has one onsite interview and what she should learn.

She was asked to solve the algorithm to search a minimum substring as the second algorithm, but she failed to solve the problem on onsite interview and she could not write any code with a lot of hints. This is the first onsite coding interview she managed to get in the city of Vancouver after working full time over 5 years.

After a week analysis of the algorithm, Julia decided to start to write a coding blog, practice coding every day.

A coding blog starting January 2015

The only way Julia can think about improving the algorithm and data structure problem solving is related to learn from her tennis sports practice in the city of Vancouver. What she did is to work on tennis sport practice over one hundred hours, two hundreds hours, and then she started to play double matches and met over hundred people on the tennis court.

She understood that onsite interview is such a great help for her to understand that she needs to make life style change. She needs to find those people working hard on algorithm and data structure practice, work on something together, practice together.

She likes to give back to others, shows her generous to share, most likely she will share her failure, struggle at the beginning.

She started to write day by day, now her coding blog is like a tree planted by the water that sends out its roots by the stream (Jerimiah 17:8).

Here is the blog about the algorithm to find minimum substring using sliding window technique written 2 years ago, January 2015. This is the time Julia understood that it is important for her to start to write a coding blog to help herself. She felt so frustrated on the onsite interview but she quickly learned something related to her tennis sports practice.

This time Julia came out the idea in less than 1 minute, but she still needs to work on a few implementation details.

Code review and study 

Julia wrote 30 minutes about an algorithm to search a string using slide window in the mock interview. The code has some issues and she could not finish the algorithm. First she likes to code review her algorithm.

C# code is here at the practice, it took 30 minutes to write.

Will work on code more after the practice, here is C# version - revision 1.
Will add some test case to make sure the code is perfect.

4/9/2017
Added a test case, debugged the code and found a bug, C# version - revision 2.
line 72 - line 103 - code smells, duplicate logic in if/ else both cases.

4/10/2017 10:28pm
Continue to make code more clean, readable. The code smells in revision 2. Move left pointer loop standalone. C# version - revision 3.

6/30/2017
Fix the bug in the code, add a few lines of code 98 - 101. The C# code is here.

Code Review 

C# code is here at the practice.

Highlights of good things and bad things in the code written in mock interview 30 minutes:

1. line 2 - 19 writing of algorithm analysis is very good.
2. line 2 - 19 missing the slide window left point move forward design - skip more than one char
3. line 63 - 65 - this is a bug, for example, unique string "xyz", slide window "xyyz", if next char is x, then "yzx" will be shortest. It is a bug to reset start and end pointer.
4. line 74 - 76 - if statement should be a while loop
    need to add checking whether minimum string is found or not.

Final version after mock interview experience is here. C# version - revision 3.

Fully understand the test case first

In order to write good and working code, Julia had to force herself to work on a test case first next time. Here is the test case she worked on April 11, 2017, a few days after mock interview experience.

Work on the simple test case again and again, write down the analysis here (4/11/2017):

Find string using sliding window

xyz     xyyzx

Iterate the string one char a time

x

xy

xyy

xyyz

xyyzx

When to move left pointer? skip two chars in a row - "xy"

xyyzx -> yyzx, remove left pointer, skip x 

yyzx -> yzx,     remove left pointer, skip y

Do one thing a time. Every iteration, add the visited char to the slide window, add char to the slide window if it is new, otherwise increase the count.  Check left pointer to see if it can move forward, make sure do a loop, sometimes it can skip multiple chars. Check if slide window contains a string including all unique characters.  

Actionable Items

1. Study the discussion of Leetcode 78.

2. Review the article - how to get unstuck in technical interview?

On the other hand, seeing you find your way out of a difficult situation tells a lot about your character, how you perform under pressure, your ability to think on your feet and your problem solving skills.

1. Not thinking about an algorithm

Make things simpler for yourself. Write down an example on the board and think about just solving that particular instance of the problem by hand.

Small test case -> generalize it back into an algorithm form. 

Julia, please validate the argument. Sounds like true to Julia in 2017.
People tend to bomb their first few sets of interviews. This is mostly because they don’t have sufficient practice with how to handle that pressure of solving an unknown question.

15 mock interview - systematic way 

Actionable Items

Related blog in Chinese - sliding window algorithm, link is here. 

Follow up 

June 29, 2017

Mock practice again, C# code is here.

Need to write some test case and make sure that the code is working.