Binary tree at least 2 path sum same

Feb. 6, 2018

Introduction

I spent 20 minutes to review the post on code review, and then I wrote the solution based on the review. Here is the code review link, I asked the question over one month ago.

Code practice

Here is the C# code integrated with all the reviews. I use the algorithm to warm up recursive function and think about using it in anonymous interview in short future.

Float numbers and operators

Feb. 6, 2018

Introduction

It is the algorithm I like to use in anonymous interview. I used it four times, and I started to think about more on the algorithm.

Brute force solution

Here is the brute force solution. This algorithm is really challenging and the peer complained to me on Feb. 5, 2018 that I should lead the interviewee to the optimal solution, otherwise it is waste of the time. The algorithm is for interview of principle lead or programmer, not even for senior.

There are a few issues to handle besides using recursive function, flat preference, max and min used to reduce the numbers from four to two, and also using memoization or dynamic programming will lead to optimal solution.

I will continue to use the algorithm and see if there is a super talent interviewee, and I can learn from the experience how to write the optimal solution.

Being interviewer: Deletion distance and long common subsequences

Feb. 6, 2018

Introduction

It is 8:00 PM mock interview. I had chance to learn a way to solve deletion distance using long common subsequences.

The idea is to find the longest common subsequences in two strings, for example, "heat" and "hit", the common subsequence is "ht", so the distance is "heat" and "hit" length sum minus 2 times length of common subsequence "ht". It is 7 - 2 * 2 = 3.

Code review

Here is Java code.

Leetcode 214: Shortest palindrome (I)

Feb. 6, 2018

Introduction

It is hard level algorithm and I like to learn the algorithm. It is called Shortest palindrome.

30 minutes thinking

Since the algorithm is hard level, I plan to practice at least 10 times. Today I spent 30 minutes to thin k about the solution, and address possible issues in the brute force solution.

Follow up

Feb.15, 2018

I did spend over 30 minutes to read the discussion, and then wrote C# solution based on Java code. I did not fully understand KMP algorithm yet.

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.

Ready for a new week

Feb. 6, 2018

Introduction

It is so exciting to change my goal for my algorithm and data structure practice. I start to learn from the mock interviews, and try to find things to help me to be a better person as well.

I had 12 mock interview from last Friday to last Sunday.

Practice highlights

I tried to teach a dynamic programming solution in mock interview and got some good feedback from the peer. Learning is so much fun and I also had chance to learn how a young graduate learns to handle a difficult dynamic programming solution.

I struggled on word count practice and actually I wrote i++ instead of i-- on line 33, and it took me more than 5 minutes but I could not spot the error. The peer is a computer science PH.D. student and he told me that if the index-out-of-range, you not need to check the pointer null. So reasoning is something I have to work on to narrow down the possibilities.

Through the practice I learn that it may be a good idea to build a habit to write a loop in ascending order and then change the inside statement of for loop instead. After mock interview, I tried to compare with my last successful practice and then identify the issue. Programmer time is no longer valuable if I have to spend time to find those trivial error since I need more strong analysis skills and also willing to apply to the bug fix.

I also observed an experienced programmer and learned how he troubleshooted his code and fixed bugs in less than 5 minutes on this binary search algorithm.

I also wrote a sorting algorithm and then noticed that the API should not be called swap two index's value, instead it should be called moveFromOneToAnother. The practice is here.

I also had chance to learn from the peer who has more than three years pythons experience. She showed me how good she can solve the binary search algorithm in this practice.

The valuable lesson to be a good interviewer

Feb. 6, 2018

Introduction

I never expect that I have to learn how to be a good interviewer until I finished 10:00 PM mock interview today. I got the feedback from an experienced programmer.

Code review

I have to review the code the peer wrote and also need to think about the feedback I got.

First algorithm is about Spiral Matrix. I did review the code and the code is very good.

Second algorithm is about float number and operators, I had to review the brute force solution. I did learn something from the code as well.

My feedback

It is hard to learn to be a good interviewer. I have to learn to focus on the basics and remove my bias.

The interviewee wrote very readable code and also very easy to work with. He did show his solution on the first algorithm Spiral matrix, the code he wrote demoed his very good analysis skills and high coding standard in his daily practice. The second algorithm is float numbers and operators, and then the peer wrote a solution but failed to pass test case [1, 12, -3], and then the peer asked for the hint, and then he came out the idea by himself to write a brute force solution using O(N^4) time complexity and also space O(N^4). The interviewee also taught me something as an interviewer, what I should learn. For example, I have to leave impression to the person, first the difficult level of the algorithm, is the algorithm for senior developer or junior developer. There are several areas the interviewee can improve, like coding style, communication skills, like algorithm analysis of the second algorithm. How to come out the optimal solution, reduce the time complexity from 4^N to 2^N? Based on the conversation after the mock interview, I think that interviewee taught me a good lesson to be an interviewer. I decide to let him go to next round.

Feedback from the interviewee

I have to make mistakes in order to learn to be a good interviewer.

Here is the feedback. Please close your eyes.

Would you want to work with this person? No
How good were the questions? Waste of time
How helpful was your interviewer in guiding you to the solutions? Not helpful at all
Help your interviewer get better!
Please put more thought into the questions you're asking others. Usually there are multiple ways to solve any problem - you as interviewer should be fine with any of the ways interviewee solves posed problem.

Play with the code

It is unbelievable that the interviewee wrote production ready code, so I changed the code to C# programming and ran the test case, it works for [1, 12, -3] with maximum value 33, the C# code is here.

I am not sure how the interviewee came out the design and wrote almost perfect code for a brute force solution. I continuously played the code and added some comment to look into those variables. Here is the C# code with some comments.

Algorithm study

Feb. 5, 2018

Introduction

It is so much fun to learn from a person by reading his website. I decided to read the book Element of programming interview, and then I found myself really enjoy to read the website of the author Tsung-Hsien Lee.

Algorithm teaching

Feb. 5, 2018

Introduction

I made the choice based on the peer's recommendation in my last weekend mock interviews. I decide to read the book called Elements of programming interview in Java. And then I started to read preface of the book on Amazon.com. I started to read about two authors. The first one is top ranking university computer science professor, I really like the website, specially with the notes the professor shared when he studied in the college. Those handwriting notes just brought me back to the college age, and the hardworking classmates of Shanghai Jiaotong university and their notes.

I do have very good notes as well. I took a math graduate course back from 2010 to 2014, I like to go back to Florida one day and see if I can find my Introduction to cryptography course home work, I like to share them on my blog as well.

Plan to read the website http://users.ece.utexas.edu/~adnan/

A great professor must be a good student when he is in the college. 

Find smallest substring containing all keys

Feb. 4, 2018

Introduction

It is the algorithm I have to write for my 10:30 PM mock interview. The peer was very helpful and I had 30 minutes to complete the analysis and code, I did fix the grammar error in last minute and pass all test cases.

I can tell the difference. Since I understand the process of sliding window containing substring, how the left pointer can slide through if the substring contains all keys. I had one practice in January and then I got a few advice to optimize the algorithm. This time I could write the algorithm much quickly.

The peer advised me to speed up coding if I can.

Code review

The C# code is here. The peer advised to add extra variable to store the start position of substring, I added variable on line 21 called startIndex.

10 minutes to be interviewed

Feb. 4, 2018

Introduction

It is the game I play after the mock interview. Today after the mock interview, I gave two questions and asked peer to solve. One is spiral matrix and another one is maximum number of chunks. The peer is very experienced programmer, went to onsite facebook last year, second round Google phone screen, and since last 12 months he finished 300 algorithm on leetcode.com. I just saw the big difference compared to me, since he worked so hard on 300 algorithm recently, it is so easy for him to follow the hint to work on spiral matrix to write a simple while loop solution, it only took him less than 10 minutes to come out a total different solution.

After 20 minutes, I asked him to give me one algorithm to be interviewed.

10 minutes to be interviewed

Here is the transcript for my performance. I just could not believe with 4.9 out of 5.0 reputation, I continuously in the row this afternoon partnered with three programmers, with good intern experience or education background, with 4.0 GPA master graduate student. I think that it is so easy to learn thing quickly through the discussion.

I definitely learned something today.

Elements of programming interviews in Java: The insider's guide

Feb. 4, 2018

Introduction

It is hard decision to choose what to work on. It is a busy year, I just started to subscribe frontendmasters.com, but I find that it is hard for me to sit down watch a few hour of videos. It takes time to learn new things, I need to practice after I watch something.

Today the peer of my mock interview shared with me a book, he read the book and bought a paper copy; so he can read the book all the time.

The book is called "Elements of programming interviews in Java: The insiders' guide". This is the second time in less than one month two peers recommend me to read the book. One got Google onsite interview, one had facebook onsite interview less than one year.

Elements of programming interviews in Java

This will be my book. I like to find my most favorite three algorithms in next 30 days.

Binary search algorithm

Feb. 3, 2018

Introduction

It is so interesting to know that mock interview is shorter than ever before. I met a peer who had intern experience with top software companies, and then he only spent less than 10 minutes to write the code and pass all test cases.

Both of us finished mock interview algorithms in less than 30 minutes.

Binary search algorithm

Here is Java code related to binary search.

Binary search tree algorithm

Feb. 3, 2018

Introduction

It is another mock interview at 4:00 pm, I spent around 15 minutes to analyze the algorithm and write the code. I worked on the binary search tree algorithm called Find inorder successor, and the peer shared with me his advice, it is also easy to check first left parent instead of comparing the value with parent node's value.

Code review

C# code is here.

New algorithms please!

Feb. 3, 2018

Introduction

It is time for me to set up a goal to work on more algorithms from Leetcode.com. There are over 600 algorithm on leetcode.com, new questions almost come out every day.

It is time for me to learn from the peer to prepare for onsite interview, I met a few people to prepare for onsite interviews. I met a peer one week ago, and he shared with me his Google document last month practice. From Dec. 1 to January 18, he practiced more than 30 algorithms on Leetcode.com. He is preparing Google onsite interview.

I finally spent 30 minutes to go over those algorithms, and then select some problems and decide to go over those algorithm. One of my favorite algorithm is called Leetcode 351: Unlocked Android App.

Mock interview

Mock interview is easy to continue right now for me. I have worked on those algorithm over ten times.

In order to push myself outside comfortable zone, I have to start to work on new algorithms. There are over 600 Leetcode algorithms, I have only worked on more than 100 algorithms.

Array of array products

Feb. 3, 2018

Introduction

It is the time to write the algorithm in less than 10 minutes. The algorithm is called Array of array products. Once the dynamic programming idea is used, all I have to remember is to do one multiplication from left to right iteration, but from right to left iteration, two multiplications are needed, one is to multiply the left product with right product, and then apply dynamic programming to right product using one multiplication.

Code review

Here is C# code.

Recursive function design talk

Feb. 3, 2018

Introduction

It is the third time I met the peer on mock interview platform. The peer worked on the algorithm root to leaf path sum minimum value, and then the peer explained to me his design in five minutes.

Tail recursion, local state, global state

The peer explained to me his idea of solving the problem. Local state is prefixSum variable, global state is minSum variable.

Here is the C# code.

60 minutes to reach out the community

Feb. 3, 2018

Introduction

It is the best time in the morning for me to reach out the community, I had 10:00 AM mock interview and I met a young graduate student in United States, and then I had to work with her to find a solution using binary search. Based on my past practice, it is very easy for me to give out some practical advise. I also enjoyed the learning process of Java programming language.

Code review

The idea used in the code is to find the pivot index in the array, the element's value is smaller than previous one, or it is the first one in the array.

After the pivot index is found, the normal binary search can be applied.

The Java code is here, I reviewed the code to remove index-out-range bug in binary search algorithm.

Java Array.binarySearch API end index is exclusive, so the peer fixed the bug to add one in the input arguments.

After the mock interview, the peer told me that she really likes the mock interview experience. She learned a few things from me. Also I shared the website called frontendmasters.com to her.

It is amazing that the new master graduate student is aiming to web development, and learn react framework and try to use mean stack to do development.

Largest smaller binary search tree key

February 3, 2018

Introduction

It is 10:00 AM mock interview and I had to work on the algorithm called largest smaller binary search tree key.

Analysis of the algorithm

To search the key in the binary search tree, we do not have to traversal the whole tree, all we have to do is to start from root node and then go right or left, until meeting the dead end. For example, the node does not have left node but we have to check smaller value, or the node does not have right node but we have to check larger value. 

I made so many mistakes in past practices, and I remembered the time I was so nervous and then think about largest smaller, how to keep the largest one in the set of numbers. Since the value of smaller one is found, those numbers are in ascending order, only one variable is needed to keep current one. 

Code review 

Here is the C# code.

Leetcode 301: Remove invalid parentheses (I)

Feb. 3, 2017

Introduction

I like to work on a hard level algorithm on leetcode.com. Also I do not like to rush and find the answer as I do sometimes. Through the learning experience of Leetcode 10: regular expression matching, I know that it may take me 10 practice before I can fully understand the hard level algorithm.

First 30 minutes

On Feb. 6, 2018 I had chance to work on the algorithm called Leetcode 301: removed invalid parentheses. I like to write down the notes and see if I can find the answer through the first 30 minutes work.

Leetcode 679: 24 Game

Leetcode 503: Next Greater Element II

Leetcode 490: The maze

Leetcode 351: Android Unlock Patterns

Feb. 3, 2018

Plan to work on the algorithm. Read the blog here first.

Leetcode 425: Word Squares

Leetcode 272: Closest Binary Search Tree Value II

Leetcode 42: Trapping Rain Water

Feb. 2, 2018

Plan to work on hard level algorithm Leetcode 42.

May 23, 2018

I could not believe that I could not come out the idea to calculate the rain water when I was asked by the interviewer on May 22, 2018 8:30 PM. I asked one of Chinese graduate student to help me, give me some mock interviews and this was the first algorithm he asked me.

I talked about descending stack, and the interviewer asked me why it is the descending stack. And also the interviewer asked me to give out the correct brute force solution. I noticed that my brute force solution is also not correct. I need to find left boundary for the current bar which should be maximum height of prefix elements.

Here is my C# solution written after the mock interview.

There are three issues to fix in order to pass online judge. First one is to check base condition, check array length is 0 on line 26; second one is to apply Array.Reverse API, it has been called three times. And the last one is to add if condition statement on line 49.

Leetcode 685: Redundant Connection II

Feb. 2, 2018

Plan to work on hard level algorithm.

Float number and operators algorithm

Feb. 2, 2018

Introduction

I asked the peer to solve the float number and operator algorithm on Feb. 1, 2018 10:00 PM mock interview. It is such a learning experience for me to learn how the peer came out the recursive solution.

Code review

The code has some issue. Subproblem should include maximum and minimum value.

The Java code is here.

Actionable Item

I will write the code based on the idea of recursive function.

Leetcode 54: Spiral matrix

Feb. 2 2018

Introduction

It is the second time I asked leetcode 54: spiral matrix in the anonymous interview as an interviewer. I met a peer who was willing to be interviewed, and followed my hint and try to write a solution using one loop instead of four for loops for each direction.

Code review

Here is Java code to review. The peer spent around 20 minutes to work on coding, I was able to see how good the peer can write readable code.

I told the peer that he did better than me. When I was asked this algorithm and the idea to write one loop only, it took me more time to come out the ideas, and I needed two hints, one for direction array, one for visited array.

Compared to the peer, I knew that I have to learn to stay open and think hard in the mock interview.

Minimum path from root node to leaf node in a tree

Feb. 2, 2018

Introduction

It is 8:00 PM mock interview. My algorithm is to calculate the minimum path sum from root node to leaf node.

Code review

Here is C# code.

Leetcode 10: regular expression matching

February 1, 2018

Introduction

I understand that there is no hard algorithm, only lazy student. I have spent over 10 times to practice Leetcode 10: regular expression matching last eight months. Usually the peer writes a perfect solution and it takes 30 minutes, I experience a lot of good learning experience from those peers.

Last two months I start to write dynamic programming solution as well to solve the problem.

One hour practice

On January 31, 2018 I had a mock interview, and then I spent one hour to be interviewer. The peer  wrote a perfect dynamic programming solution. And the peer shared his argument that one time for b* pattern is not necessary in implementation.

Argument to think about

b* can repeat zero time, more than one time. But one time can be covered by zero time and more than one time this two cases.

Here is the transcript I reviewed.

Leetcode 394: Decode string

Feb. 1, 2018

Plan to work on the algorithm.

Leetcode 726: Number of atoms (V)

February 1, 2018

Introduction

It is hard level algorithm and I like to learn one thing a time through the practice. This practice is based on the coding blog written in Chinese, and I like to develop a blog based on the idea.

Here is the Chinese blog link.

Analysis of the algorithm

The idea is to find the first close bracket ')' and then look ahead for the number and look backward to find open bracket to match the close bracket.

Here is C++ code to study. I will write a C# solution based on C++ code.

Leetcode 726: Number of Atoms (IV)

Feb. 1, 2018

Introduction

It is very interesting to read one of discussion and the code is implemented in python. What I like to do is to spend 30 minutes to go over the analysis, and then get the idea how python code works.

What I like to do is to go over the analysis again, and write down the analysis in my own words. Spend more time on the analysis, and then understand the algorithm one thing a time.

Python code

Here is the discussion link.

Study of the blogger

Here is the link I like to study about system design.

Analysis of the algorithm

Regular expression

The first is to understand how to read regular expression, the atom can be expressed in the following expression: ([A-Z]{1}[a-z]?|\\(|\\)|\\d+). I just learned how to write regular expression in 5 minutes.  I documented my practice on algorithm on word count engine algorithm on January 25, 2018 and learn how to write regular expression for delimiters.

The number of atoms

The regular expression can be used to split the input string, and the only four tokens are discussed.  (1) An atom (2) A number (3) Open bracket (4) Closing bracket.

Let us go over a few test case and then how to read them in char array.

An input of Mg(OH)2 will be tokenized into: ['Mg', '(', 'O', 'H', ')', '2'].
An input of K4(ON(SO3)2)2 will be tokenized into: ['K', '4', '(', 'O', 'N', '(', 'S', 'O', '3', ')', '2', ')', '2'].

How to solve the problem?

As we iterate through the tokens, there are three cases that we need to handle:

1. Open bracket - We push a new dictionary onto a stack to keep track of the atoms and its count in this current group.
2. Close bracket - The next token might be a number/count. Check whether if it is a count. If it is, multiply all the atoms at the top of the stack by the count and combine it with a dictionary below it in the stack.
3. Normal atom - The next token might be a number/count. Check whether if it is a count. If it is, add that atom and its count to the top of the stack.

Cases 2 and 3 are very similar, so we can combine them.

At the end, sort the atoms alphabetically and format them nicely to be returned.

Leetcode 726: Number of Atoms (III)

Feb. 12, 2018

Introduction

It takes at least 10 times to learn a hard algorithm on Leetcode 726. One thing I did is to study one of C# solution on discussion panel, and review the C# code and try to make it better.

Iterative solution

Here is the C# code I spent over 30 minutes to rewrite. I will continue to review the C# code. The practice is very helpful for me to understand the algorithm.

Scalability Harvard Web Developemnent

January 31, 2018

Plan to watch the video again. Here is the link, the length is 1 hour 45 minutes.

Leetcode 726: Number of Atoms (II)

January 31, 2018

Introduction

It is so nice to watch a video of Leetcode 726: Number of Atoms. I like to spend 20 minutes to watch the video first, and then write down some notes here.

Video lesson

Here is the video to watch.

Coding blog

Here is the coding blog. I plan to study the code as well. And then I will write a C# solution based on the idea.

Here is Java solution. I will work on C# solution based on Java code.

C# code practice

I spent 90 minutes to write the C# code. Here is the code. I felt that it is like flatten dictionary, only difference is to handle close bracket to return dictionary. Every close bracket will be handled right away, which likes a leaf node in the tree.

Leetcode 726: Number of Atoms

January 31, 2018

Introduction

It is the last day of January 2018, I like to celebrate the first month of 2018 using one hard level algorithm. I found one today by reading a Chinese algorithm blog, the link is here. The algorithm is hard level one on leetcode called Number of Atoms. I know that it will take some time for me to understand the algorithm with hard level.

Algorithm study

Plan to study the Chinese blog and write down some notes. One thing I like to do is to read the chinese blog, and go over each word, try to put together and make it more readable first. And then write down a few things to look into, highlight them, and plan to go over it again later.

三种方法，第一种采用递归，而后两种采用栈式结构。

 方法一：递归

首先编写一个解析器Parse，这个解析器应当能统计出从当前字符串位置开始，直到遇到一个右括号“）”或读到字符串末尾，然后连带上右括号“）”后面可能跟上的数字，这可做为一段整体。

用一个counter来记录这一段各个元素的个数。最后返回counter。

1. 首先初始化counter
2. 在解析器循环中：
1. 当遇到左括号“（”时，就递归调用Parse；并把Parse子程序中元素统计结果加入当前的counter当中。
2. 如果不遇到左括号，那么会发现一定是大写字母，也就是一个原子名称的开头，那么就统计这个元素的个数。
3. 循环结束后，检查右括号后面是否跟有数字，如果有的话要对当前的counter进行相应倍乘。
4. 最后返回counter。
5. Parse可以写成一个递归函数，然后用主函数做驱动函数。

方法二：采用栈式结构

和第一种方法类似，不采用递归函数，采用栈来进行操作。（其实函数的递归和栈本就具有极大的相似性）
先初始化counter栈，然后仍旧需要一层循环，直到读完所有字符。

循环中：
1. 当遇到左括号“（” 时一层新的counter入栈。
2. 遇到右括号“）”时栈顶counter弹出，并检查后面是否跟有数字，如果有的话对当前counter进行相应倍乘，并把结果累计到新露出的栈顶。
3. 遇到大写字母，就统计这个元素的个数，计入counter，类似方法一。

方法三：同方法二，但是不手动解析字符串，而是采用正则表达式

规则表达式Regular Expression，通常被用来检索、替换那些符合某个模式的文本.

把字符串分成一个一个独立的块，这里采用的表达式为："([A-Z][a-z])(\d)|(()|())(\d)"。这里面的块分别表示：可能带有数字的元素如“Fe3”、“H”等；左括号“（”；可能带有数字的右括号“）”、“）3”等。
然后在循环中对正则表达式中的每块进行各自对应的处理。

复杂度分析

无论哪种方法，理论的复杂度相同。但是这里推荐使用第三种方法，因为栈式结构比递归的写法更加简洁, 还有第二个原因, 正则表达式极大地简化匹配操作。

时间复杂度

O(N^2)

这里N为字符串的长度，遍历一遍字符串需要O(N)的时间，但是当遇到左括号时，会对子式的元素向外累加，这就有可能达到O(N)的时间，而总字符串长度为O(N)，所以左括号的个数为O(N)（注意大O记号的含义是“不超过”，这里的意思是不超过线性界，而不是等于线性界）。故所花时间为O(N^2)，

这里给出一种时间比较逼近N^2的表达式：A(B(C(D(E(F3)4)5)6)7)。

注意：正则表达式的时间界不容易判断，这里正则表达式没有回溯，所以总的时间复杂度不会超过O(N^2)，这与正则表达式的实现方法有关。

空间复杂度

O(N)，这里无论是栈还是Map，空间复杂度不会超过O(N)。

Being an interviewer: System design - design instagram

January 31, 2018

Introduction

I do not have chance to sit in the classroom to learn the system design, and then I do not plan to learn system design today. But today the peer had super performance, first 40 minutes he passed through all four algorithms, including array, recursive, graph and then dynamic programming. So I asked him to have a system design question, design instagram with scalability.

System design best one

It is so enjoyable to learn through the best system design in the world.

Here is the transcript. And the best thing is that I can watch the video again and again, learn every step he developed the design. The interviewer has more than 10 years experience to work on search engine in the city of Seattle, USA.

Every time I feel stressed to learn system design, I just go back to watch the recording, and then learn from the best.

I remembered one time I met the senior developer working for Microsoft fifth time in mock interview. I told him that I work as an interviewer in another platform. And he asked me how much I get paid. I laughed about it.

Transcript starts here:
end here.

Follow up 

Nov. 15, 2019
I like to review the notes again. I like to spend 10 minutes and learn from my own experience. What should I do in terms of system design? I did not have chance to write so many content in my Facebook onsite in August 2019. I was interrupted before I like to talk about diagram, distributed file system or storage.

maximum number of chunks

January 31, 2018

Introduction

I cannot believe that I have strongest peer in the world and then I just need to find some good algorithms, and then I can get tutored through the mock interview. I could not believe that I got matched with super talent programmer, good lord, machine learning algorithm does great job for me tonight.

Algorithm code review

Here is the transcript to understand the algorithm.

Float number and operators algorithm

January 31, 2018

Introduction

I was thinking whole day how to come out the recursion in the correct order on this algorithm called Float number and operators algorithm. Tonight I met a super talented programmer with over 10 years experience to work on a large scale system, and he taught me how he approached the problem in less than 10 minutes.

Code review

Since I already checked the peer's code skills, I just asked the peer write down a few lines of code and try to get his idea.

Here is the pseudo code. Perfect order to fit for flat precedence. Only one hint using [1, 12, -3] on line 30.

Leetcode 54: Spiral matrix

January 30, 2018

Introduction

It is such a big surprise that my first mock interview as an interviewer turns out big success. The peer solved all four algorithms I asked in first 40 minutes. He is the best peer I have met in my peers, over 150 peers.

Best thing is that I got education how to design a perfect system design: Instagram scalability in 30 minutes. I could not believe that I may interview a top company senior developer in the future.

Code review

Here is the C# code I like to learn. The idea is very clear and it is the production ready code.

Leetcode 123: Buy and sell stocks

January 30, 2018

Introduction

I have to learn the algorithm again, I believe that the algorithm of dynamic programming is such an interesting learning experience. It is like seek and hide game, every time I come back to work on the algorithm, it is like a new algorithm. What is happening?

Recursive

Please solve the problem once and then build the recurrence formula. This time I also like to watch the video and see if there are some new tips.

Follow up

Feb. 16, 2018

Here is the gist I saved from the blog to talk about dynamic programming related Leetcode algorithm.

Other two gists are written in Chinese about dynamic programming. Here are the link 1 and link 2.

AlgoExpert - 55 algorithms

January 30, 2018

Introduction

I got advice to look into those algorithms on the website algoexpert.io. I like to spend some time to learn those algorithms marked as free videos first.

So nice a Monday

January 30, 2018

Introduction

It is such a nice Monday, I am back to daily work and try to learn something from frontendmasters.com. Also I had a 10:00 PM mock interview, I learned an idea to work on reverse the sentence, with a minor bug in the implementation.

Code review

Java code is here.

Say goodbye to the weekend

January 29, 2018

Introduction

It is time to say goodbye to a busy weekend, now it is morning time 7:40 AM before I prepare to leave home for a new work weekday. Last weekend I had thirteen mock interviews first time. The interview started from the Friday evening and ended in the last hour of Sunday evening.

Let us take a look the schedule, I only went out for quickly grocery shopping in Saturday, I did not have time to go out to play sports, swimming.

It is so enjoyable to spend time to talk about algorithm using C# language, JavaScript, Python, Java this weekend, I met so many talent programmers and it is the first time I practice so many algorithms in less than 3 days.

Good experience

I applied some skills I learned from church small group meeting to the mock interview. I am getting better on those algorithms, learn a few things to make me better to write dynamic programming, recursive function.

What I have learned

Do not memorize the algorithm. Try to show some reasoning.

I still remembered that the peer told me that he read my post on quora.com about mock interview when I shared my coding blog, and then I had chance to get the trust from the peer, he shared me a lot of tips and also got invited to join Google foobar.

Deletion distance algorithm

January 28, 2018

Introduction

It is very hard for me to learn a dynamic programming solution to solve deletion distance. One thing I have learned is to understand the difference between recursive and dynamic programming. The peer is a latest computer engineering PH.D. from top university, he asked me tough questions. I had hard time to go over the analysis and answer his questions, but I managed to learn and answer correctly.

It is not good to memorize the solution, that is the reason I seek for the advice for each mock interview. This time I had chance to learn from top graduate and understand how important it is to be able to explain the algorithm.

I have to understand the algorithm and be able to defend my analysis. Mathematics is my undergraduate study major, I love to prove something based on theorem.

Analysis and code review 

Here is the transcript I wrote in less than 30 minutes. 

Leetcode 54: Spiral Matrix

January 28, 2018

Introduction

It is the algorithm I have to write on my 10:00 PM mock interview. I worked on the spiral matrix, and it took me in total 20 minutes to explain the solution and write the solution to pass all test cases.

Code review

The peer told me that I can save the space using four pointers instead of visited array. I explained to him that the mock interview is for me to write the correct solution using minimum time.

Here is the C# code I wrote.

Advice from the peer

January 28, 2018

Introduction


It is something I learn from the work. I have to let people talk and then learn something from the conversation. Recently the office coworker shared the tip to use Vancouver library card to access Lynda.com 6000 courses.

Today I had 8:00 PM mock interview. The peer shared with me the tips what to learn through so many resources. I write down and will look into later. One thing he told me is to use New York library card to access Lynda.com courses.

Here is the link.

Udemy

January 28, 2018

Introduction

I had a mock interview 6:00 pm, the peer advised me to check udemy.com. You can get a good quality course on react over there.

Learning JavaScript

January 28, 2018

Introduction

I had 6:00 PM mock interview. I had 30  minutes to learn how to write JavaScript from the peer, who went through full stack academy.

JavaScript code

Here is the code I reviewed to apply binary search in the array and find smallest index which equals to the element value on the index.

Four Sum problem

January 28, 2018

Introduction

It is busy weekend. Today I had a mock interview at 4:00 pm,  I felt that I were a student to be interviewed for an algorithm, the teacher is questioning me everything, and make sure that I understand everything I write.

Code review 

Here is the code.

Highlights of interview:

1. First the data type of function on line 44, getTwoSum, its return type dictionary's key is integer, not string;
2. Second, the array should be sorted in ascending order. I forgot to write the first round.
3. Discussion of dictionary search algorithm time efficiency.

Power function do it yourself

January 28, 2018

Introduction

It is the algorithm the peer shared with me on 10:00 PM mock interview January 27, 2018. Learning algorithm is kind of fun. I have to read python code, and also I learn how the peer wrote down his solution using memoization, and later he told me that the friend told him to remove memoization, just use one recursive call to reduce the number to half.

Code review

Plan to study the algorithm and review it later. The code is here.

Find first missing number

January 28, 2018

Introduction

It is the algorithm for me to work on this 12:00 PM mock interview. I like to review the analysis and code.

Code review 

Here is the code with the analysis.

Leetcode 6: Zigzag conversion

January 28, 2018

Introduction

The peer asked me to work on Leetcode 6: Zigzag conversion today after the mock interview. I wrote down my idea, here is the link.

Guess 4 digit number algorithm

January 28, 2018

Introduction

It is very good practice to ask the peer to give me an algorithm to work on, through the discussion, I can learn something from the peer quickly.

This is the algorithm I like to continue to work on. It is called "Guess 4 digit number algorithm".

I got Google foobar invitation

January 28, 2018

Introduction

I read the story on code review website about Google foobar. And I got the invitation to join Google foodbar. I was so excited to have chance to work on some algorithms over there.

Convert a binary search tree into a double linked list

January 28, 2018

Introduction

It is good idea to ask the peer what is his/ her favorite algorithm. I had a mock interview 12:00 PM today, after mock interview, we discussed several algorithms. One algorithm is to convert a binary search tree to a doubly linked list.

Here is the link on Leetcode discussion.

Learning python

January 28, 2018

Introduction

I met a peer second time in one month and she used python. What I like to do is to learn python through mock interview, and write down notes when she coded. Python is easy to follow and quickly to write. The peer told me that she works day time using C++ but she chose to write python for mock interview.

The peer started to write python since she was in the university, actually she graduated from MIT. The python code should be pretty good.

Python code about matched brackets

Here is the code.

Design a data structure

January 27, 2018

Introduction

I had a conversation with the peer after mock interview. One thing we discussed is about the data structure design. He asked me to design and data structure to do insert for a range numbers from array, I quickly thought about binary index tree. And he also said something about interval algorithm.

Algorithm related to binary index tree

It is time for me to look up Leetcode and find the algorithm. I asked the kindergarten adventures on code review stackexchange.com a while ago. It is time for me to learn the algorithm through a simple example.

H-Tree algorithm

January 27, 2018

Introduction

I practiced one more time on H-tree algorithm at 4:00 PM mock interview. I was really appreciated to have chance to look into time I need to spend. I tried to cut time short, so I meet the expectation from the interviewer on interviewing.io. Time is money, time is asset. If I can make it 10 minutes, why I like to spend 20 minutes. Extra 10 minutes I can work on another algorithm, usually it only takes 10 times to work on one algorithm, the interviewer does not need to see you code every algorithm.

Today I spent 20 minutes to write the algorithm with some analysis. But I tried to cut the analysis to minimum.

Algorithm code review

Here is the code.

Use bit manipulation to solve problem of power of n

January 27, 2018

Introduction

I really like Roger Federal as a professional tennis player, but I never have any chance to talk to him. But do not worry, today I had a chance to talk to a programmer from Switzerland, he speaks exactly same as Roger Federal does, a Switzerland accent. And he also tried to teach me the algorithm called power of n using bit manipulation.

I did some research after mock interview. Here is one article about the detail.

I just could not believe that I got best help from top programmer through mock interview this weekend.

Here is the algorithm the peer wrote. The great thing is to watch him how he did the testing using 5² and then after the testing, he cleaned up the white board testing code. He just quickly demoed how he wrote a new code and also tested and put it in the production, nicely presented after removing those test cases.

Catalan number

January 27, 2018

Introduction

It is another mock interview and I had to work on the algorithm related to Catalan number. This time the peer dropped a hint, do not need to use previous row, only use current row and then save the space. I wrote the code based on his advice.

Algorithm 

Here is the code based on the advice from the peer.

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.