careless whisper

June 4, 2018

Introduction

I had mock interview this morning with my coach, 8:00 AM. This is our goodbye meeting. I talked to my coach that the dynamic programming solution is hard to come out in the first five minutes. I just named this algorithm as careless whisper. I did hear the word coming out my mouth when I discussed with the peer yesterday, using dynamic programming.

Algorithm is called to find maximum flower. Given a matrix with cells three options: empty, wall, flower, find maximum flowers cell.

Let us say that two dimension grid contains empty cell (S) or flower (F) or wall (W). A person standing in a cell can see north, south, east and west. But all flowers behind wall are invisible. Find the cell with maximum visibility.

S   F   S  F
W S   F  S
F  W  S  F
S  F   F  W
S  F   W S

output: 3

Algorithm practice

Here is my C# algorithm.

I do not have time to put those four functions into one function, avoid code duplication. 

Follow up

June 20, 2018

The friend just shared with me the discussion panel on this algorithm. 

Discussion of maximum visible is here. 

Follow up 

March 5, 2019

I asked the algorithm in mock interview on interviewing.io. I learned from the interviewee that the algorithm can be simplified by checking left/ upper two directions only.



March 6, 2019

I spent time to work on the example again. It cannot be simplified. 

Maximum number of chunks

January 20, 2018

Introduction

It is the best way to learn the algorithm in mock interview together. I asked the peer to solve the extra algorithm, and he worked so hard to solve the algorithm in 20 minutes or so. I watched him and learned how he thought out loud.

Transcript

Here is the transcript. I will review the transcript later on. The peer likes to write down the programming and then think about in the same time. I do not like this kind of style. Actually it is better to work on the idea, and until you have an idea to solve, you write down the algorithm and ask the peer which idea to write.