Find minimum cost from top left corner to bottom right corner

May 13, 2018

Introduction

It is the algorithm to find the minimum cost from a matrix top left corner to bottom right corner.

Transcript

Here is my work in the mock interview. The interviewer told me that I should write the code after the mock interview, give him to review the code for next mock interview.

My next mock interview will be in Tuesday.

Mock interview 

Learning algorithm is such great experience. It is so much fun to work with a young graduate student around twenty five years old. He was very kind and also very encouraging. I spent first 5 to 10 minutes to think and communicate with the interviewer depth first search, compared to breadth first search. And then he kept asking me how you can improve the algorithm compared to depth first search. He did more than two times.

I finally came out the idea to use dynamic programming algorithm. Even though I have practice Deletion distance algorithm over 20 minutes last 12 months. But I still miss some dots to come to dynamic programming algorithm.

Arguments

I like to write down a few words about my analysis using depth first search is not optimal.

First, the algorithm is to find the minimum cost. There is no need to find actual path. Using depth first search of course takes extra effort to find path from source to destination.

The question is to ask minimum cost. I should quickly related to deletion distance.

I will do some research and figure out how I can come out dynamic programming algorithm without hints by the interviewer.

I have weakness to come out dynamic programming solution at the first place today.

Assignment

The interviewer told me to show him the code I write and he will give me some review next mock interview.

Follow up 

May 14, 2018
It is the algorithm called Leetcode 64: Minimum Path Sum.

I was asked if I worked on the problem before. I said that I did not. But actually I thought about the hackerrank contest I worked on similar algorithm. So I search all contests I played from oldest to latest one, I found the algorithm and blog called Manhantan 2.

I am so glad to learn that my last practice in the contest. I was so glad to see my hard work, and here is my C# algorithm written based on dynamic programming. The solution still has bugs with score 33.

Print binary tree extreme corner in alternate order

May 13, 2018

Introduction

It is my first algorithm to work on. I spent 28 minutes to work on the algorithm.

Transcript

Here is my transcript.

First mock interview from my coach

May 13, 2018

Introduction

I may come cross a most hard working top engineer in the world. My coach is a busy graduate student and working for top four companies in China as an intern. He has to squeeze time just before going to sleep and then giving me a mock interview for 45 minutes.

My first mock interview started from 8:00 AM PST. In less than one minute, the coach sent me a wechat message. We started our first mock interview after we first met on mock interviewing platform this January 2018.

Summary

The interview lasted 71 minutes. I finished the first algorithm in 28 minutes, and then second algorithm we discussed the solution and then I got hint to use dynamic programming instead of using depth first search, I wrote down base case and recurrence formula. And then we ended discussion of second algorithm in 55 minutes, moved on the other topics related to the future practice etc.

Feedback

I was asked to answer the question about array and list difference. And then I did not answer very well. I was told to look up Google after mock interview.

I was reminded to use negative operation to make the code more efficient. And also I was asked if I work on the algorithm recently. I told him honestly that  I worked on binary tree level order traversal and zigzag order level traversal recently.

He told me that I was nervous. He gave me the hint to use queue, since I talked about zigzag level order traversal using stack. I followed his hint to use queue instead.

I explained to him after mock interview that I have met a lot of peers through mock interview, write a complicated function in the interview and end up to get stuck. I like to write a simple function to traversal the tree by level using queue first, and then I like to piggyback the work to add the list of extreme nodes.