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.