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.