Find next large value in the array - my third mock interview given by my coach

May 17, 2018

Introduction

I have the third mock interview given by my coach. I was surprised that the coach encouraged me think hard in mock interview. I like to write down our discussion and help myself to learn this algorithm using stack to track next large value.

Mock interview

Here is the transcript. I will write down my analysis, discussion with the coach, how the coach gave me hint. What are things to work on?

I am exciting to learn the algorithm through practicing with strongest hitting partner in the world.

After mock interview ...

How to train myself to come out the optimal solution?

In my mock interview, I did a few things correctly. I started from brute force solution with time complexity O(n²), n is size of the array. And I told the interviewer that I like to do preprocessing.

How to do it? I think that there are two popular ways, one is to use dynamic programming technique, to save the maximum or minimum or other statistics from left to right or right to left iteration.

And the other is to bring stack descending or ascending order to help, this one has some advantage to handle magic things.

Actually the second one is to bring stack descending or ascending order to help, this one has some advantage to handle magic things. My coach taught me the two words summarized as ascending stack or descending stack. I just could not believe that I could not figure out the technique since I do not play with more test cases.

The coach told me that I should say that let me think about a few minutes. So this way I do not need to talk all the time. Quiet time is also very helpful.

My favorite algorithm

I do not know how to push myself to think smart in the mock interview. I have practiced largest rectangle histogram using stack a few times last 6 months. But under the stress of the interview, the data structure just cannot come out quickly since I thought about each element in the array to store data using a data structure, like an array. But I break somewhere in thinking process to connect dots, so I like to write some dots like the following:

I believe that playing with simple test cases I can come out the idea naturally.

But in the mock interview, I was thinking that it takes too much effort for the coach to set up meeting, sacrifice of time to sleep, it is past 12 PM midnight in China. I could not concentrate to push myself think harder.

I just wrote down more here now since it is after the mock interview.

First I talked to my coach to simplify the test case. The coach said that let us get half numbers. I told him that let me choose simple number on line 33: 1, 2, 3, 2, 1

But I like to think about more, to work on a few base cases:

1. test case: [1, 2, 3]

2. test case: [3, 2, 1]

3. test case: [2, 1, 3]

How can I do preprocessing?

First let us go over the answer for each test case.

For test case 1, [1, 2,3], the answer is [2, 3, 3]. The largest one is its right neighbor, the array itself is ascending order.
For test case 2: [3, 2, 1], the answer is [3, 2, 1]. Notice that the array is descending order.
For test case 3: [2, 1, 3], the answer is [3,3,3]. Notice that first 2 elements in the array are descending order, and then 3 is bigger than previous.

And also I am thinking this way. Preprocessing using dynamic programming idea.

First test case:

[1, 2, 3]

The coach gave me hint to iterate from left to right, I like to follow him instead of right to left.

Iterate the first number 1, what I should put into preprocessing array, I could not tell, I need to find largest number met in the future iteration. I do not want to go back again, I need to save it.
[1, ?, ?].

Iterate the second element with value 2, we need to give 2 to its previous element with index = 0, we need to move index = 0 out of data structure, and put result array [2, ?, ?].


Second test case:

Let me work on the second test case:


[3, 2, 1]

First iteration, visit 3, we have to save index = 0 into a data structure, since the coach told me that I should save it to a data structure.
Second iteration, visit 2, 2 is smaller than previous one, save index = 1.

Test case 3:

[2, 1, 3]

Let me talk about magic thing about [2, 1, 3] test case.

First iteration, visit 2, we can not do anything, push 2 to the data structure. Next iteration visit 1, since 1 is smaller than previous value 2, I can not do anything either. Push 2 to the data structure. Now iteration visit is 3, which is bigger value than previous number, we have to put index = 1 with value 3, and pop index = 1 out of data structure; now index = 0 is the last one, 3 should also go to index = 0.

So the order of assigning the value is in reverse order. The index is at the top of data structure, and then it can associate with current iterated visting element.

There is a first in last out process.

Just try to please my stack muscle memory! I am counting on this piece of memory. I should practice more on this thinking process, related to one simple test case.

I was busy thinking that each element holds one data structure when the coach gave me the hint.

I love to learn this algorithm, so I just write down more and see if I can use the approach by playing with test cases.

Ready to show my coach the solution

I wrote a C# solution and then I can show my coach the solution this Saturday May 19, 2018 8:00 AM mock interview. I like to find out if there is extra line of code included, or the code can be improved. It is always excited to have a coach. I need to get back to stay confident and positive.

Usually my coach will say that you clean up the code very well. But in mock interview, you write messy code with a few bugs. It will be written down and take points away.

Research algorithm based on stack

I am planning to work on algorithm based on stack. Here are the list of algorithms related to stack.