Case study: Word ladder - find all paths

Oct. 19, 2019

Introduction

It is my 10:00 PM mock interview. I like to write a blog and conduct a short case study.

Case study

Here is the code written in python. No bug, executable code.

Actionable Items

It is such great experience to work with a person with 700 algorithm solved on Leetcode.com. No bug, and perfect structured interview. Top 10% rating on interviewing.io. I just could not believe that I will work hard and push myself hard to improve next 6 months. 

300 algorithm to work on, each month 50 algorithm. Each week only 10 algorithm. 

Case study: Is graph bipartite

August 4, 2019

I gave out the algorithm for the interviewee to work on, he wrote C# solution. Here is the gist. I also went over the code and add some comment, here is the gist.

Case study: mock interview using sliding window minimum

Feb. 12, 2019

Introduction

It is the notification of Linkedin.com. I got the notification of young graduate joining Uber.com, so I checked the message and learned that I interviewed him on Nov. 2018. I like to case study the mock interview on June 28, 2018.

Case study

Here is the date of mock interview.

Case study: mock interview using sliding window minimum

Feb. 12, 2019

Introduction

It is one of my over 100 mock interviews in 2018. Recently I got notification on Linkedin.com about a young graduate joining Google, so I checked the message history and learned that I interviewed him last year. The mock interview was on July 26, 2018. I like to case study the mock interview again.

Case study

Here is the blog to document the mock interview.

Sliding window minimum

July 26, 2018

Introduction

It is my 10:00 PM mock interview. I had chance to give the peer second algorithm to work on called sliding window minimum. He gave me the optimal solution but I could not fully understood the algorithm. So I decided to prove it the correctness using k = 3.

Mock interview discussion

I modified the transcript to make it more readable. Here is the transcript.



To summarize, the sliding window minimum algorithm can be solved using two scan of array, one from left to right, second one from right to left. And then each scan the minimum value is calculated after the elements of array are divided into windows with size k.

Follow up

Feb. 12, 2019

I just learned that the interviewee joined Google this Feb. 2019. I like to review mock interview, and also I like to write an algorithm based on his idea as well.

Find a path with increasing value given two nodes in the matrix

July 14, 2018

Introduction

I was given an algorithm to work on called find a path with increasing value given two nodes in the matrix.

10 minutes discussion

Here is the transcript for the discussion. The peer asked me to write code. I told him that I chose not to write code, and go for the extended algorithm.

Clone graph

July 14, 2018

Introduction

I spent 10 minutes to discuss clone graph algorithm with the peer. It takes some time for the peer to understand the requirement. We had discussion, the gist is here.

Infix expression to a binary expression tree

July 14, 2018

Introduction

It is the second meeting with a peer after six months. We met together this January 2018. And then I gave him the algorithm to work on which is to construct binary expression tree using infix expression.

Problem solving

The peer is very strong at coding skills, so he chose the optimal solution linear time O(N), and tried very hard to figure out how to design parsing algorithm using stack.

Here is the transcript how he approached the problem. I can tell that he is very smart on time complexity compared to me.

My feedback

The peer did very good to find optimal solution, try to use stack to parse the string once and build a binary expression tree. The time complexity is O(N), N is length of infix expression. And the peer communicated very well, there are multiple solutions and he decided to push the number and operator to the stack and also build a binary tree node in the same time. Somehow he should think about validation of expression string, and also try to simplify the code. 

Here is my feedback gist.

Statistics

Meeting time July 14, 2018 9:00 AM PST - 11:10 AM PST

First the peer worked on the infix expression to binary expression tree, and then I worked on the two algorithms, discussion of "Find a path with minimum maximum value in the matrix".

Follow up 

July 16, 2018


I wrote C# code to implement the algorithm using O(N) time complexity, N is the expression length. 

Sliding window minimum

July 5, 2018

Introduction

I learn how to give out the mock interview with nice approach. I learned from one of peers giving me feedback, starting from an easy level algorithm and then extending to the hard level algorithm. Let the interviewee warm up on easy level algorithm, and also demonstrate how good he/ she thinks and writes code first. And then it is hard level algorithm if there is need.

I continuously give the same algorithm to people last 5 interviews. I keep coming cross Microsoft programmer or intern from big four companies in the city of Seattle. And also the programmers in the Sillicon Valley. It is easy for me to form a small group for more discussion once a while. I only found one more person to join the small group discussion last one week.

Keep learning

I try to observe myself how I can understand the algorithm by having discussion with different peers. I wrote some hints today. I just keep practice, and work on one thing a time.

Sliding window is most popular algorithm asked in the algorithm interview. It is easy to relate to an array, and also easy to hop on and get some good training on thinking process.

Every time I wrote down some hints.

July 4 10:00 PM - 11:00 PM


July 3, 10:00 PM - 10:50 PM

June 28, 10:00 PM - 10:50 PM

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 the least number of perfect square numbers sum equal to given number

May 15, 2018

Introduction

It is the second algorithm in my mock interview today. I like to show my transcript here and plan to write a C# solution when I have a few minutes.

Follow up 

Here is my C# code. I made a mistake and then I fixed the bug.

Leetcode 102: Binary tree level order traversal

May 3, 2018

Introduction

I like to work on three ideas to implement the algorithm called binary tree level order traversal. The peer gave me honest feedback after he mock interviewed me on May 2, 2018. It should take you less than five minutes to write, and then you have chance to move on the second question. But you actually did take 20 minutes.

To train myself to work on this algorithm, I plan to spend time to read a few hours on the discussion panel of the algorithm first.

Using extra node null to separate the level

I like to write a C# practice using extra node null to separate the level. Here is my C# practice.

Being an interviewer: Leetcode 273: Integer to English words

March 24, 2018

Introduction

I have to say that I am a good JavaScript learner. I spent over 6 month full-time at work to learn JavaScript and then rewrote the JavaScript code for my current job back in 2015. One drill I like to do is to follow the peer when I interview on mock interview platform. On March 22, 2018, I had chance to watch how the peer worked on the algorithm using JavaScript.

It is also good learning experience of JavaScript by observing, and asking questions.

Code review

Here is JavaScript code to pass all kinds of test cases.

A few JavaScript features I like to look into:

Keywords:
Eval, const, $, ``,

I like to give the test case for the peer to work on,
let testNum = 1234567890

Leetcode 611: Valid Triangle Number

March 9, 2018

Introduction

It is the first time I chose the algorithm in my mock interview as an interviewer. The peer worked on the algorithm in March 9, 2010 10:00 PM. I think that it is the good start for me to master a medium level algorithm called Valid Triangle Number on Leetcode.com. Usually it takes 10 practices to master one hard level algorithm on Leetcode.com. For the medium level, I also like to practice over 6 times. 

This is the third time I worked on the algorithm last 6 months. I did have one mock interview discussion back in Oct. 2017, and then one mock interview in February 2018. 

Code review

The time complexity analysis is so critical in algorithm problem solving. This algorithm can be solved using two pointer techniques and the time complexity can be lowered from brute force solution O(n³) to O(n²). 

Also as an interviewer, I also learn quickly to identify the solution written actually ending using time complexity O(2ⁿ). 

I like to encourage myself and also the interviewee try the best, and heed the lesson of failures in the mock interviews. 

Here is the code I reviewed. The code works, but the time complexity is worse than brute force solution with O(2ⁿ).

Find first missing number

Feb. 25, 2018

Introduction

It is part of my training idea, practice until you cannot get it wrong. I had a mock interview this morning at 10:00 AM. I did write down the idea to do in place swap to find the first missing number. And then I wrote code with a few bugs, I failed a few test cases, and then I fixed the bugs on line 15 and also line 16.

Practice until you cannot get it wrong

One thing I like to train myself through mock interview is to pay attention to small detail. The peer asked me to work on the optimal solution using in place, and then I came out the idea but I did say something to change the value to negative one if the value is bigger than the array size. And the code I wrote was not correct, I ran into index-out-of-range error and failed a few test cases. I fixed the bugs of course very quickly.

Line 18 swap function should be called only after the index is in the array's range.

Here is C# code.

The mistakes I made in my first writing just reminds me that I have to train myself hard than before.

Deletion distance dynamic programming

Feb. 6, 2018

Introduction

I still have difficult time once a while in terms of solving dynamic programming solution. The underneath recursive design of dynamic programming takes more time to practice.  I had a mock interview last weekend and the peer showed me his way to solve the deletion distance.

It is such nice learning experience from the peer. The code is written in Java and the link is here.

Most of important is that the peer showed me how he proved that recurrence formula is correct. Here is the transcript of the analysis.

Follow up 

I asked the peer in mock interview and then we discussed the formula why distance("heat","hit") = distance("hea", "hit").

Here is the discussion:

 //$dog and $frop,
  //$hit, i =   3 $heat, j = 4
  //f[$hit][$heat] = f[$hi][$hea]
  (f[$hit][$hea] + 1)
  (f[$hi][$heat] + 1)
  (f[$hi][$hea]  <- minimum
    min(f[$h][$hea], $f[$hi][$he]) + 1
  )


Let me write down the explanation given by the peer on March 12, 2018. First let me read his explanation and then figure out his reasoning.

First the peer thinks that it is better to add extra char to stand for empty string "", using '$' char.

There are 3 choices to determine the deletion distance between two string "$hit" and "$heat". There are three choices, in other words, here is the expression:

f[$hit][$heat] = Math.Min(f[$hi][$hea], f[$hit][$hea] + 1, f[$hi][$heat] + 1),

We should be able tell that minimum one is f[$hi][$hea].

Follow up 

July 9, 2018

The peer contacted me to ask practice together. I was so surprised since he won ICPC regional contest in 2012. It is the first time I have a peer to practice together with highly competitive skills in contest.

I just quickly looked up his review back in Feb. 3, 2018 6:00 PM. What I did is to check date connected on linkedin, and then found the mock interview round login, and then looked up algorithm. And then I found the blog, and mock interview feedback.

floats number and operators and how to get maximum number

January 27, 2018

Introduction

I had this mock interview on interviewing.io, and the I noticed that the peer is anonymous but he is machine learning algorithm computer science Ph.D. with a few years experience.

Mock interview performance

Here is the transcript related to the discussion and my code written in the hurry. The code is copied from the record video at 55:01/ 1:00:16.

Highlights of mock interview performance:
Line 44: I tried to define the subproblem, what are the subproblems?
Line 120 - 128: I narrowed the subproblems to max/ min value. 

After mock interview 

Here is the algorithm I tried to write after mock interview, it has some bugs in there.

For example, [1, 12, -3], if we use the recursive function, then it is 1 - (12 * (-3)) = 1 + 36 = 37, but since the precedence is flat, 1 - 12 * (-3) = -11 * (-3) = 33. So we may have to process the array in reverse order instead, I have to investigate on the issue.

Here is the code from the friend I met on pramp.com.

Major hint complaint

I got feedback from the peer, the peer told me that I need major hint and also the solution is a brute force solution.

Here is the feedback I got after January 25 mock interview. 

Follow up 

The solution is attached here. Also I posted the question on codereview.com, and the link is here.

It is a good journey

Dec. 25, 2017

Introduction

It is the good journey for me to take first 6 interviews as the interviewer, and I got first 6 rating with full score 5 as an interviewer. In order to do that, I had to be super patient to the beginner of mock interview, and extend the algorithm to challenge the strong player. To overcome technical difficulty on mock interview platform, I used two times to get audio outside mock interview platform, 2.5 hours using wechat with a Chinese, one hour using Microsoft skype with a professional.

Let us take easy, and look at the performance below. Da Da Da, I made it as I chose to be, an advanced interviewer.

Extended algorithm

Here is the leetcode link for the extended algorithm for mock interview on 10:00 PM Dec. 26, 2017.

What I like to do is to write down my talk as an interviewer to help the peer, give the hint and encouragement to solve the problem.

I like to use this talk to encourage myself to be a lazy programmer, and always delegate the task and do as little as possible in terms of writing code.


Before I write the story let us look at the binary search tree, and talk about a few test cases first.

Test case 1: Given value 25, how to find the successor null?

Test case 2: Given value 14, how to find the successor 20?

Assume that I am very lazy, try to solve as little as possible, find a most simple task first for the algorithm. 

Given the node is the same as the root node. What is the successor? 

It should be the root node's right subtree's minimum node. It does not matter if the root node has right child or not. We can just delegate the task to the right child, using one recursive call. 

In other words, we are saying that the left subtree all nodes in the tree are smaller than given value, it is impossible to find root node's successor in left subtree. The root node itself cannot be the candidate. 

Next step, what if we relax the condition, root node's value is not bigger than given node's value? We apply the same logic. 

Now go to next test case. Given value 14, how to find the successor 20? 

Since the root node's value is bigger than given node's value, the root node can be the successor or after the successor in the list of nodes based on inorder traversal. 

Let us delegate the task to its left child, ask the return of successor. If the successor is not existed in the left subtree, then root node is the successor. 

Follow up 

Dec. 26, 2017 9:59 AM

Actually the extend algorithm is a binary search algorithm. To search binary search tree inorder successor given two nodes, root node and given node, what we need to do is to handle base case. 

If the root node is null, then return null. The most challenge part is when to return root node as a successor. Given the above tree, root node is 20, only when given node is 14, the successor is root node 20. How can we tell that it is 20?

Get connected

Give some feedback about mock platform. Maybe there are too many traffic for video and audio, my peer asked me if it is always like this. I told him that I did a few time, get audio no video from wechat or facebook or skype. 

Leetcode 41: First missing positive

Nov. 1, 2017

Plan to look into Leetcode and find the similar algorithm called get smallest nonnegative number.

Get smallest nonnegative number, do not change the array.

My C# practice code is here on Nov. 1, 2017

Also, I spent almost 50 minutes to interview the peer on Nov. 2, 2017 and had some discussion about the algorithm. I like the peer to go over the base cases to show very good reasoning.

[],   0
[0], 1
[1], 0
[0, 2, 3]  1
[3, 0 , 2] 1
[0, 1, 2, 10000]

Leetcode 41: First missing positive 

It is the hard level algorithm. Time complexity is O(n), space is O(1).

Leetcode 37: Sudoku solver

Sept. 6, 2017

Introduction

It is so enjoyable to write sudoku solver as a depth first solution and also walk through each step called "thinking out loud". The conversation after the mocking this evening starting from 10:00 pm until 11:30 pm is also rewarding experience, I try to contribute my two cents for a young person to prepare for an important trial. Although I have written sudoku solver solution over 5 times last 3 months, I still found that this time I wrote a different style.

Algorithm practice 

Here is my C# practice. No bug in the first writing, only fix two compiler errors, pass all test cases the first time.

I forgot that I need to visit current node instead of using two loops to scan the matrix to find the first empty element. After 1 - 2 minutes, I noticed the issue, and then I corrected my thought process and continue to write from line 25.

I wrote line 38 and thought out loud saying that it is kind of stupid to write '1', '2' to '9', actually I am thinking that it is better to split from string "123456789" instead of declaring a char array.

After the mocking interview 

I spent over 20 minutes to share my past 80 interviews with the peer, what I have learned through the mocking practice, specially how I learn to write sudoku algorithm through more than three practices.

One thing I like to say is that if you take it slow, you have a lot of time to write code in 30 minutes mocking interview; but if you write in a rush, then you end up with issues. I am getting more comfortable to stay on one node at a time.

The fact is that in my solution there is no need to write a double for loop at all. Avoid scan from top to down by row, left to right by column to find the first empty element all the time.

The peer gave me the feedback saying that I did very good to explain the algorithm by going over the example to find options 1, 2, 4, 7 ( see line 117 - line 124).