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.