Being an interviewer: Leetcode 84: Largest rectangle in histogram

April 10, 2018

Introduction

It is my favorite algorithm and it is hard level algorithm in Leetcode.com. I chose this algorithm to interview a friend met on mock interview. He is preparing next week Google onsite, and I gave him another hour mock interview.

I practiced the algorithm recently, but I found out that I still missed something important. The optimal time complexity is O(n), and it has to use stack to save the index of rectangle left boundary when ascending. The stack is always keeps non-descending heights. Here is the link for my past practices.

Learning is fun

The peer is very organized and also very good at explaining the algorithm. I specially like the way he structured the content.

Here is the script for the mock interview.

Leetcode 84: Largest rectangle in histogram

April 5, 2018

Introduction

It is time for me to learn this hard level algorithm again. I know that it takes at least 10 practice for me to learn a hard level algorithm. Today I chose to study the video prepared by basketwangcoding in Chinese. My last practice was on January 18, 2018. Here is the blog.

30 minutes video lesson

I like to write down some notes from the lecture.

Brute force solution


In order to learn the algorithm very well this time, I like to work on the test case, [2, 4, 6, 5, 3], explain to myself how to solve the algorithm using O(n^2) brute force solution first.

How many rectangles to be calculated? What is the maximum rectangle area's value?


Iterate the end position from i = 0 to 4.

i = 0, the rectangle is 2.
i = 1, the rectangle is 4.
i = 2, the rectangle is 6.
i = 3, the rectangle is 5 + 5 = 10
i = 4, the rectangle is 3 + 3 + 3 + 3 = 12.

So the maximum rectangle is 12.

For each end index, we can go backward to search until the array's value is less than end index's value.

Or I also can think about the alternative idea. It is to iterate the start position from i = 0 to 4,

i = 0, the rectanlge is 2 + 2 + 2 + 2 + 2 = 10.
i = 1, the rectangle is 4 + 4 + 4 = 12.
i = 2, the rectangle is 6.
i = 3, the rectangle is 5
i = 4, the rectangle is 3

Leetcode 84: Largest rectangle in histogram

January 18, 2018

Introduction

It is the hard level algorithm and it can be solved used stack to achieve the optimal time complexity O(N) where N is the array's length. The algorithm is called largest rectangle in histogram.

On January 17, 2018, I had a mock interview and I was asked to work on the algorithm. I went through the brute force solution first, but I did not come out the optimal solution to lower the time complexity to O(N).

One more practice 

What I like to do is to study one blog I like in June 2015, and then rewrite the notes and also write the C# code as well. It is very easy to look up past practice, here is my blog to document the practice in June 2015. At that time, I was shy and did not write down my thinking process to learn to solve the problem.

Right now, I think that it is very important to write down thinking process and also the idea to break through the hurdles in the problem solving. I think that it is more important to build up some new habit to learn to solve a problem. Write down the constraints, write down the problem, difficult issues, concerns, and then ideas to solve the problem, or ideas to solve partial solution. 

First, I rewrote the note to make it more readable, and then saved a gist. Here is the gist. 

Analysis of the algorithm

Most of important is to write down the analysis, and that is something lasting longer than coding itself. Specially if I draw something to highlight the main design ideas and it will be extremely helpful to bring back the memory.

This time I drew one to help myself learn the design using stack, check upward and downward.

The main idea is very simple to explain in Chinese, let us take a look at notes in Chinese first, and then I quickly explain them in English.

Going upward

When the graph is going upward, in detail, current index is i, next step is i + 1, and height[i] < height[i + 1], there is no need to calculate the area. Since it is getting bigger value when i moves to next value.

Going downward

When the graph is going downward, in detail, current index is i, next step is i + 1, and height[i] > height[i + 1]. it is time to calculate the current rectangle's area.

Get help from a stack 

At the current index i, only right end's index is known, how to get the left end's index? So in order to iterate the array, a stack is need to maintain the backtracking history.

How to design a stack?

In this stack the right end's index is saved to the stack, but when is time to push into stack? Every time there is element in the array which is bigger than the top of the stack, push the index to the stack. Otherwise it is time to calculate the current rectangle's area and compare to the largest area.

Every algorithm will become one of your valuable weapons 

until you teach some one and show him/ her how it work.

Leetcode 84: Largest rectangle in histogram analysis

January 17, 2018

Introduction

It is 10:00 pm mock interview. The peer gave me the algorithm Leetcode 84: largest rectangle in histogram analysis to solve.

Algorithm analysis

The peer gave me his analysis using stack, and how to store the stack with (value, index). The discussion link is here.

Mock interview

Leetcode 84 is the hard level algorithm. I did not come out the optimal solution using time complexity O(N), and then the peer reminded me to go over upward test case like [1, 2,3, 4, 5] and then go over downward test case like [5, 4, 3, 2, 1]. And then the peer gave me the hint and then I came out using stack to push previous nodes into the stack, but I did not have idea how to manage the stack, when to push into the stack and when to pop the stack.

The peer went over quickly using the example to explain the idea.

I know that it takes me 10 mock interview practice to learn a hard level algorithm Leetcode 10: regular expression matching.

Actionable Item

Review what I did in the past on this algorithm. I did practice the algorithm in June 2015, here is the blog.