Two hours system design study together

June 11, 2018

Introduction

It is June 3 8:00 AM two hours coaching session. My coach told me that he would like to help me understand grokking system design lecture notes together with me. We spent two hours to go over the foundation notes first together, and then we went over one system design together.

He helped me understand a few concepts. He joked about me what I do in my daily work. How come I missed some basic knowledge. I just relaxed and enjoyed his coaching for Hadoop, distributed file system. He gave very good explanation on file system. He is the first person to tell me some programming paradigm using key value pair instead of traditional if and while loop paradigm.

Paradigm

In theory, normal programming use if, while logic can be replaced by using key value pair only.

I really like his teaching. I need to follow up with more study.

Here is the transcript.

Leetcode 399: Evaluate Division - from my coach

June 4, 2018

Introduction

It is the last session of my training. I sent the algorithm I am interested to my coach, and he told me the graph algorithm is Leetcode 399: Evaluate division.

Last lesson 

The coach gave me his analysis about the graph using this algorithm. I did not fully follow his idea.

Here is the transcript.

Say goodbye to my coach

June 4, 2018

Introduction

It is hard for me to work on algorithm back to alone, and try to find another best algorithm player along the mock interview practice. I did find very good friend to practice with through blogging. I could not believe that power of marketing of each blog, I can easily get all the important information at my finger, and find a strong algorithm player to bounce ideas and work together to reach a new target.

Say goodbye!

I did write an email to say goodbye to my coach.

hi, 

  I wrote a blog to put all coaching session together, and like to share with you. 

  Here is the blog link.

  I also spent a lot of time to think about the coach I like and guess what you look like, my favorite tennis player Dimitrov's coach. I wrote blogs to share with you, but I was too busy to send too many emails. 

  Here is the coach's advice. 

 "Trust your instinct. You already practice all patterns. Figure out ways to solve the problem, make mistake and let it go." The coach talked about how to mentor the player mentally. I think that you are kind of the style, on dynamic programming solution coaching. 

  Here is blog I wrote to send to you. 

  One more coach I like and I thought about is Rob Kentlay. 

  The coach is my favorite.   

  Daniel is my favorite coach, and you must look like him. 

union find algorithm - 7th mock interview from the coach

May 28, 2018

Introduction

It is my most favorite algorithm called union find algorithm. My coach asked me to solve the algorithm to find maximum group. We had discussion around 100 minutes. Through the discussion, the coach showed me how to do time complexity, and then we had good time to discuss a few topics. At last, I asked the coach to write two function, one is to quick find, one is to union.

Transcript

Here is the transcript of mock interview on May 27, 8:00 AM.

Follow up

I spent a few hours to review my past practice on this union find algorithm, and then I wrote C# code for review. Also I was asked to write a depth first search algorithm, and I will write one.

Breadth first search distributed algorithm - 6th mock interview from the coach

Introduction

It is my most favorite algorithm May 2018. I was surprised to spend more than one hour to write the C# code and also fixed my original design issue. My design was kind of weak until I tried to test the third test case with 4 x 4 matrix. I found out the answer is not correct. For some reason, the current layer of node will get into next round when I apply breadth first search. Later, I added a hashset to exclude the current layer node to get into next round.

The algorithm is so ineresting and I remmebered that I worked on the similar algorithm called shortest distance to all building.

Algorithm 

I wrote a breadth first search algorithm based on my coach's hint. Find all elements in the matrix with zero value first, put all of them in the queue, and then process breadth first search on those elements in the same time.

It is kind of distributed algorithm. I like the challenge. I feel excited after I complete the algorithm.

Here is my mock interview transcript.

Here is my C# code after mock interview.

Being an interviewee: Suggest a char with maximum occurrence at the position with the given prefix

May 23, 2018

Introduction

It is my most favorite algorithm to practice with my coach. The algorithm is called to suggest a char with maximum occurrence at the position with the given prefix.

The coached asked me if I have Trie experience two days before my mock interview, so I spent some time to review Leetcode 212 and also my question on stackexchange.com.

The conversation of writing a Trie data structure was very interesting.


Coach: can you explain how you define the Trie?
Julia: It should be recursive structure, Children should have Node type as well.
Coach: Do you need to have a list of numbers for children?
Julia: No. It should be minimum. Every node just takes care of its own number.

In-between the mock interview, the coach asked me why you define the Trie this way, save "ABC" as a member of class definition. I just told the coach that I memorized the solution I reviewed recently. But actually we do not need to do that here. I felt much more relax after we work together more than 10 hours.

Trie algorithm

I learn how to work with the coach and write a solution in the mock interview. And also the coach asked me to test the code using the test case documented from line 93 to line 96, I found the bug on line 107, and delay increment of index variable until line 123.

Here is the transcript of the mock interview.

Follow up 

I wrote the C# code and tested it using a simple test case. Now it is 12:21 AM, I need to rush to go to bed since at tomorrow 8:00 AM I will have a mock interview.

10:00 PM mock interview as interviewer

I also ask the interviewee to work on the algorithm at 10:00 PM mock interview. The intervewee has more than eight years experience working in Silicon Valley to target for biggest software companies, and I helped him to write a Trie solution. What I did is to try to copy my coach, how he did to me. I asked the interviewee to work on the test case, show me the trie, and also give hint to use array for fixed size instead of using Dictionary.

Here is the C# code the interviewee wrote before I write my own C# solution.

Code review from my coach

I sent an email to ask the coach to review my code before I will have next mock interview. The coach offered me to send the code before mocking interview after our second mock interview, so he can prepare better for next mock interview. We can squeeze in more activities in the mock interview together. My coach is super talent programmer and I like his working attitude.

"I think that it is definitely no problem at all. Let us meet Friday morning.

I just like to send you the code I wrote for suggest char based on prefix.

Here is the link."

May 25, 2018
8:00 AM

My coach told me that one thing is not correct. The iterate variable may be null pointer. I need to add null pointer checking on line 152.

Find string s2 containg s1 permutation - 5th interview from my coach

May 23, 2018

Introduction

It is the algorithm called find string s2 containing s1 permutation. I wrote the algorithm using sliding window, and also implement the algorithm using time complexity O(N) where N is the length of string s2.

Algorithm

Here is the transcript for my mock interview. We used Google Docs.

I wrote the code but there are some issues in my code. The coach spent over 5 minutes to test my code using a test case, and then he shared with me his implementation using time complexity O(26*N) solution.

Here is my C# algorithm I wrote after the mock interview.

My fourth mock interview given by coach - suggest a char

May 21, 2018

Introduction

It is the fourth mock interview I got from my coach. He demonstrated his superior coding skills, he reviewed the code I wrote after mock interview, I made a terrible bug in iterative solution of find the height of tree algorithm documented in the blog, and then I should continue to simplify recursive solution for height of tree as well. It took around 40 minutes for him to review those two algorithm, and one more from the peer I interviewed as an interviewer.

Algorithm to suggest a char

Here is the transcript I worked on the algorithm and my coach spent time to coach me using less space, instead of going over each word, he advised me to go over each char at the same position in all the words.

I also showed him my word count practice, and asked his code review.

We worked together very hard, I am in the city of Vancouver, and the coach is in Beijing, China. I wad told that the talk is cheap, show me the code. I never doubt my coding ability, I think if I explain the idea, he should trust I can write. But that is not the case yet.

The time of interview is from May 19 8:00 AM - 9:46 AM PST.

The code is here to lookup.

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.

Find height of tree - My third mock interview given by my coach

May 17, 2018

Introduction

It is my third mock interview this 8:00 AM. I had very good learning experience in mock interview. I started to learn how to communicate better to work with my coach. He also started to think about helping me to work hard to find bugs in my code.

Mock interview

Here is my transcript. I will write C# code with some test cases, and also try to use recursive function to get node's level of tree for each node starting from 0 as root node.

Coach's advice

Through the mock interview, I was told that there are several issues on my iterative solution. I made a few mistakes. And then I was told to think recursively. If the current node depends on parent's node in terms of height calculation, then it is better to write a recursive solution.

Here is recursive solution I wrote after the mock interview.

I still could not believe that I made a few mistakes, and even I used Visual Studio debugger to help me to troubleshoot the issue. I missed the line 115 to assign value to heightIds[index].

Iterative solution is hard to think

I spent over 30 minutes to write and debug the code, I had to fix my thinking process ending up nothing is calculated. I missed the base case when the node has parent with value -1, then the node's height is one.

Here is iterative solution in C#.

From the performance of this algorithm in the mock interview, I learned the lesson to write an iterative solution correctly is not easy at all. So many bugs and even I write using Visual studio I keep finding issues.

A few places to be corrected after the mock interview:

1. base case: line 126 - line 128
2. line 139, I like to break the list iteration as soon as possible. Make sure that only uncalculated nodes are visited.

I think that the solution may also be broken the time complexity O(N). It is hard to write iterate a solution.

Lesson learned

Think recursively, think memorization. Try to cut time to O(N) linear time.

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.

Special drill for next three weeks

May 12, 2018

Introduction

It is my decision to contact my mock interview peers and then I decide to get some private lessons from those peers I like the most. Since they are working hard, best performer I have met over the practice. One of them is Tsinghua university gradudate student. I could not find time to finish over 500 Leetcode algorithms in last three years. I asked two of them to be my coach for next three weeks.

How to choose a good peer to be a coach? 

It is not easy at all to do so many things very well. It takes time to practice so many Leetcode algorithms. So it is better to have a coach and find out how to work on the practice more efficiently.

First of all, I like to figure out that what job needs a super talent software programmer.

If I have a good coach to practice at 8:00 AM to be interviewed for two algorithms 10 sessions next three weeks, then I can have Saturday and Sunday, play grouse on the top of grouse mountain this past Saturday and enjoy Sunday service with friends from Florida.

The picture and videos can be viewed from instagram here (?) very soon.

Actionable item:

Plan to study solutions as many as possible next three weeks. I need to read as many as possible solutions.

Here is my next three week's bible.