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

	thinking:
	1. sliding window size is fixed? Can we shrink if need?
	2. smallest number can be any position in any position? Can we push it to first one in the sliding window?
	3. Can we maintain the sliding window monotonic increasing/ decrasing? why?
	4. Can we do some comparison when a number to join sliding window? What to compare?
	[4,4,4,4,4]
	[4]
	[4] -> we just keep one
	[5, 4, 3, 2, 1
	[5]
	[5, 4] -> compare to 5, 4 < 5, 5 can not be minimum? move 5 out of sliding window?
	[3, 4, 2, 1] k = 3
	[3]
	[3, 4] -> monotnically increasing -
	[3, 4, 2] -> [3, 2] -> [2] -> sliding window will be [2]
	index -> value numbers[index]
	current interate index = 3, [3, 4,5]

view raw minimum sliding window hints hosted with ❤ by GitHub

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

	[2, 3, 4, 1, 5, 8, 6] => [2, 3, 4]
	[3, 4, 1] -> find minimum in sliding window will take O(k) ->
	sliding windows size is fixed, size = k,
	design of data structure -> find minimum take O(k)
	change sliding window can be short than k, -> make sure the minimum number is always at the first number of sliding window
	->
	leetcode sliding window maximum - hard level
	[5, 4, 1, 3 2, 8, 9, 10]
	k = 3
	[5]
	[5, 4] -> argue that we can do better, 4 < 5, if minimum is the first one in
	dequeue
	5 out of sliding window
	[1,2] -> we can do, arr[2] =1 < 4, 4 is impossible to be minimum
	arr[1]
	[2] <- get first minimum -> minimumArray[1,
	index = 2
	[2, 3] ->
	[2, 3, 4] -> we should not let index = 3 in windows, 3 > 2,

view raw minimum sliding window hints -July 3 2018 hosted with ❤ by GitHub

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

	[5,4, 3, 2, 1]
	[5, 4, 3] k = 3
	min(minele, newele)
	pos - newminpos
	[]
	Given an array -> if i can tell 1st smallest and 2nd smallest in 1 pass
	1 approach -> getmin(0,k) -> 1
	getmin(1,k) -> 2
	[1,2, 3]
	min[2, newele] -> [2,3,4] [2,4]
	[3,4] min - 3
	[3, 5] - > 3
	Time complexity -> [N*k
	My feedback:
	--
	mockinterviewplatform - 330 mock interview last 15 months -
	interviewing.io as interviewer - 53 times
	1. you have to lead interviwee to optimal solution
	2. you suppose to start an easy level algorithm first, extend the algorithm
	3. you should not give hints without permission - 30 - 45 minutes
	solve the problem by themselves
	4. interview is not coaching - code readable
	5. hold it as real interview
	can we change sliding window smaller than k?
	smallest number can be any position in sliding down, can we argue that we can kind of pruning the sliding window
	to make smallest element in the first elemnt of sliding window.
	[1,3,5,4,2] k = 3
	[3]
	[3,5] <- 1
	[1] - 2 index -> 1 - sliding windows -> hard level - maximum sliding window
	[5,3,1]
	pos - 2

view raw minimum sliding window discussion June 28, 2018 hosted with ❤ by GitHub