Leetcode 152: Maximum Product subarray

May 17, 2018

Introduction 

I just could not believe that I have chance to interview top university graduate student with excellent performance. I chose two algorithms I had this week mock interview given by my coach, the interviewee solved two of them quickly and very efficiently.

I just asked her third algorithm after 50 minutes to see if I can fail her on the dynamic programming algorithm. We had good discussion on this algorithm called Leetcode 152: Maximum product subarray.

Mock interview 

I will write down some discussion here. I like to learn the algorithm at least 10 times with various talents in the world first,  and then I will definitely feel more comfortable to solve the dynamic programming solution.

Being an interviewer: Leetcode 152 Maximum product subarray

May 2, 2018

Introduction

It is so interesting to work as an interviewer. I did interview a ICPC contest silver medal winner, facebook intern using the algorithm a few days ago. And today I had chance to interview a 15-years professional software engineer.

What I like to do is to tell the difference? How to approach the goal to be a super talent programmer? Experience, education, what is most important part to play the role? We can not tell, but we can do tell through problem solving on the algorithm related to dynamic programming problem.

Mock interview

Here is the transcript I reviewed.

Two stories to give out major hint of dynamic programming idea 

The subproblem is to define the subarray ending at index i, what is maximum subarray product? Why is this subproblem defined? Since it can be constructed in the series of index i, and easy to do it. Our solution is to get global maximum value for each index i.

But it is not easy for me to teach or tutor the candidate in mock interview on this idea. Basically it is not good idea to tutor peers on mock interview. But sometimes I have to learn how to give major hint, how to define the hints to make it easy for the peer to understand.

I tried on my last two mock interview but I did not do very well. Here is more detail story.

Learning to be a good interviewer is so much fun. I did talk to the peer on mock interview, while the peer worked on the test case and tried to understand my hint, I was surfing Leetcode 152 discussion, and see if there is any tip for me to share with the peer. I could not believe that the peer could not understand my hint, and let him try a few more times to get the solution by himself. Actually he could not do it.

The same thing happened a few days ago with the peer who has much strong analysis skill set. He did say that he understood my hint. But then he moved on to explain his original idea and made a few modification. I could not understand his idea fully, but he showed no interest on my hint.

Learning the algorithm together is so much fun. It is not easy, specially for people over 10 years experience but lack of constant challenge on algorithm and data structure.

I have to learn how to encourage the peer, make him less stress and get out comfortable zone to try something new.

Being interviewer: Leetcode 152 Maximum product subarray

April 29, 2018

Introduction

It was my 10:00 pm mock interview. We both finished our algorithms in first 30 minutes. Then we spent extra one hour 20 minutes to work on algorithms together. I asked two algorithms for the peer to solve.

Here is the first algorithm called Leetcode 152: Maximum product subarray

Mock interview

The peer worked on the solution, and then we had discussion and then our discussion lasted more than 30 minutes.

Here is the transcript.

The peer wrote a brute force solution in less than 2 minutes, code is from line 54 to line 64. Two days ago, I helped a young undergraduate student to work on the brute force solution more than 10 minutes. What is big difference. I was so amazed and could not stop expressing my biggest surprise.

And then we had discussion about optimal solution using time complexity O(n). I tried to explain to the peer that his algorithm is not so good since it could not apply to the double array. And then he said that if it is a double array then it is another problem.

One more argument we had is about the algorithm he proposed from line 88 to line 112. The problem is that I could not understand his algorithm, I was too lazy to think and I need to run a simple example first.

I decided to give out the hint, I wrote the hint from line 32 to line 45. I like to introduce the dynamic programming algorithm, and help the peer to follow the idea.

And then the peer continued to work on his idea, he wrote down the notes from line 66 to line 86. The peer is very good at writing pseudo code and explain thing.

He did told me that he worked on ICPC contest in high school, and he found out that mock interview algorithms are easy etc. We talked about codeforce contest etc.

Being interviewer: Leetcode 152: Maximum Product Subarray

April 26, 2018

Introduction

It was very nice experience to be an interviewer. I helped the interviewer learn a brute force solution first and then we had very good discussion on the optimal solution using dynamic programming. The peer is preparing Google phone screen, I may come cross a Google future employee this time.  I met a senior undergraduate student who also works full time for a startup company in silicon valley area.

Mock interview

Of course I could not tell from the person how good she will be, specially when a peer is undergraduate student. But it is very easy to communicate with the peer.

Here is JavaScript code we worked on together, around 60 minutes. I also had chance to learn JavaScript from the interviewee.

I also learned from the peer. I challenged her code using comment line 63, I told her that line 68, temp_max *= arr[i] * arr[j], and then she added a few lines of comments from line 64 to 67, and then I understood her idea to use dynamic programming. She fixed the bug, and line 68: temp_max *= arr[j], arr[i] is removed from the product.

Leetcode 152: Maximum product subarray

March 27, 2018

Introduction

I like to work on this algorithm Leetcode 152: Maximum product subarray, and I find that it is similar to the algorithm I practice so many times called float numbers and operators.

Algorithm practice as an interviewer

I chose the algorithm to interview the peer in mock interview. The peer is very talent programmer, he had a facebook onsite last December, and he prepares for Google onsite. what I found out is that he needs some hint to come out dynamic programming solution, but his coding ability is very strong, and also the analysis ability.

Here is the transcript.