Sliding window minimum

August 4, 2018

Introduction

It is the mock interview algorithm I gave to the interviewee. The interviewee went through several steps and then I like to document the discussion, one of his ideas is related to Binary search tree, and we had discussion about time complexity of delete a node in BST.

Sliding window minimum

I like to talk about things I learned from his analysis of sliding window minimum algorithm.

The problem statement I wrote is here.

Here is the transcript to show the algorithm to get range sum using dynamic programming.

Extended algorithm is to get the minimum value of the sliding window.

The interviewee had two Google intern experience, and he is just a new graduate. I like to share his transcript. 

Sliding window minimum

July 26, 2018

Introduction

It is my 10:00 PM mock interview. I had chance to give the peer second algorithm to work on called sliding window minimum. He gave me the optimal solution but I could not fully understood the algorithm. So I decided to prove it the correctness using k = 3.

Mock interview discussion

I modified the transcript to make it more readable. Here is the transcript.



To summarize, the sliding window minimum algorithm can be solved using two scan of array, one from left to right, second one from right to left. And then each scan the minimum value is calculated after the elements of array are divided into windows with size k.

Follow up

Feb. 12, 2019

I just learned that the interviewee joined Google this Feb. 2019. I like to review mock interview, and also I like to write an algorithm based on his idea as well.

Sliding window minimum

July 5, 2018

Introduction

I learn how to give out the mock interview with nice approach. I learned from one of peers giving me feedback, starting from an easy level algorithm and then extending to the hard level algorithm. Let the interviewee warm up on easy level algorithm, and also demonstrate how good he/ she thinks and writes code first. And then it is hard level algorithm if there is need.

I continuously give the same algorithm to people last 5 interviews. I keep coming cross Microsoft programmer or intern from big four companies in the city of Seattle. And also the programmers in the Sillicon Valley. It is easy for me to form a small group for more discussion once a while. I only found one more person to join the small group discussion last one week.

Keep learning

I try to observe myself how I can understand the algorithm by having discussion with different peers. I wrote some hints today. I just keep practice, and work on one thing a time.

Sliding window is most popular algorithm asked in the algorithm interview. It is easy to relate to an array, and also easy to hop on and get some good training on thinking process.

Every time I wrote down some hints.

July 4 10:00 PM - 11:00 PM


July 3, 10:00 PM - 10:50 PM

June 28, 10:00 PM - 10:50 PM

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.

Window minimum

April 21, 2016

Try to get some algorithm reading and then find a similar algorithm in HackerRank, and get some workout on coding.

It is called Window minimum.

Problem statement from the geeksforgeeks website

Given an array of size N, a window of size W slides over it by increment of slide S. If the window reaches to the end, we should stop there. Find a formula in form of N, S, W so that we can find the number of valid windows. Write a program to find minimum in every window and print it. Optimize it.

e.g. {1,2,3,4,5}, W=2, S=1
first window: {1,2} min=1
second window(increment by S=1): {2,3}, min=2

…

last window: {4,5}, min=4

The array might not be sorted. I have taken sorted array for simplicity.

or in Chinese, 

滑动窗口求最小:

 给了一个ArrayList：4, 2, 12, 11, -5，窗口size为2，返回的ArrayList为：2, 2, 11, -5。这里窗口size是一个参数。

Leetcode 239: Sliding window maximum

Read one of solutions using Java:
Java solution