Discussion Panel of Leetcode 72 - Edit Distance

Dec. 30, 2017

Plan to study the discussion panel of Leetcode 72 - Edit Distance.

Here is the image of top ranked discussion readings:

Edit Distance lecture notes

Dec. 30, 2017

Plan to study lecture notes again. Here is the link.

Leetcode 72: Edit Distance

Dec. 30, 2017

Plan to study the blog Edit Distance. Here is the link.

Lecture note study: Edit Distance

Dec. 30, 2017

Plan to study the lecture note about edit distance from Jeff Erickson. Here is the link.

Leetcode 72: Edit Distance

Dec. 30, 2017

Plan to study the blog related to Leetcode 72: Edit Distance.

Here is the blog link.

Wikibooks: Algorithm Implementation/ Strings/ Levenshtein distance

Dec. 30, 2017

Plan to read the wiki page about Levenshtein distance. The web link is here.

Leetcode 72: Edit the distance

Dec. 30, 2017

Introduction

Plan to watch the video about edit distance, it is titled "How to Calculate Edit Distance Between Two Strings". The video is about one hour long. Here is the link.

Leetcode 72: Edit Distance

Dec. 30, 2017

Introduction

It is the Saturday morning, I like to go out to play tennis, and it is the first day of week we have a sunny day. Also I like to review the algorithm Leetcode 72: Edit distance.

Here is the blog I like to review today, I found it through my 2015 blog.

I also created a gist for the code written by the author. Here is the link.

Leetcode 334 - Increasing Triplet Subsequences

Dec.29, 2017

Plan to study the code using this blog. 

Algorithm blog quick scan

Dec. 29, 2017

Introduction

I plan to go over all many algorithm blogs as possible for this holiday break found on the website, a graduate of Imperial College London, Rafal, R. Szymanski.

Leetcode algorithm

There are 31 algorithm in the blog, I will quickly scan the algorithm and learn something. And I will tell which one is my favorite algorithm. 3 things I like in terms of algorithm code quality, give some code review as well.

Codility

There are 15 algorithms. I will study those algorithms as well.

Project Euler

There are 5 algorithms.

Algorithm topic

There are 23 blogs for various topics.

Leetcode 10: regular expression matching

Dec. 29, 2017

Introduction

It is so interesting for me to learn Leetcode these days. I work on mock interview continuously on those 30 algorithms. And today I reviewed Leetcode 18: 4 sum last 5 practice, and then I tried to get organized and reviewed the past practice, and then found this young graduate software engineer working in facebook, I start to code review his post on each Leetcode algorithm.

Code review

Leetcode 10 algorithm blog is here.

Here is the gist I created for the study. I will play this code and write a C# and figure out how it is.

Algorithm notes

Dec. 29, 2017

Plan to read and use the algorithm notes written by a facebook engineer. Here is the link.

K Sum Problem (II)

Dec. 29, 2017

Introduction

I wrote a K sum problem in Chinese this morning, and then I found that I have to write an English one in order to get better understanding the problem. It is Friday, my free time, one week off. And I already spent over 60 minutes to improve writing in Chinese to make it more accurate, and readable. So I start to google and then find some article to read in English, I miss the very good writing with mathematical analysis.

Here is what I found. The article is called K numbers in array that sum to C. And then I checked the contact, the author is working for facebook. So I am better to spend some time to read the article, high chance the article is good one. Also the author has practice on Euler.net, 75 algorithm solved. I have not solved any problem on Euler.net yet.

K sum problem

Every good algorithm problem attracts top talented programmers. I like to read and figure out if I can have good time to learn something today. Now it is 2:43 PM, I have booked mock interview 8:00 PM, 10:00 PM. Plan to go to Ice Rink to skate and swimming, and then enjoy the rest of day with two mock interviews.

K sum problem

Dec. 29, 2017

Introduction

I spend time to get organized last 5 practice of Leetcode 18 4 sum algorithm. And then I came cross a blog written 18 months ago, and then started to read the blog.

The blog is title called "K sum problem". It is written in Chinese and the link is here.

K sum problem 

The mock interview practice is to relate to how to quickly figure out the solution and also write code in less than 30 minutes, sometimes it should take less than 20 minutes, or less than 10 minutes. The training is to focus on good understanding of the algorithm, not too much theory involved.

But I do have strong interest in the topic about time complexity. So I decide to copy and paste the Chinese writing here, and modify the content in terms of style, make it more readable. But the time I spent on is over 30 minutes now. I decide to find a good written article in English instead.

Later on do some study related to it.

k sum problem （k 个数的求和问题）

问题陈述：

在一个数组，从中找出 k 个数（每个数不能重复取。数组中同一个值有多个，可以取多个），使得和为零。
找出所有这样的组合，要求没有重复项（只要值不同即可，不要求在原数组中的 index 不同）

解法：

2 sum 用 hash table 做，可以时间 O(n)，空间 O(n).
2 sum 如果用 sort 以后，在前后扫描，可以时间O(nlogn + n) = O(nlogn)，空间O(1)
2 sum 用 hash table 做的好处是快，但是等于是利用了不用排序的特点。排序的办法，在高维度（也就是k sum问题，k>2) 的时候，nlogn 就不是主要的时间消耗成分，也就更适合 2 sum 的 sort 后双指针扫描查找的办法。

那么，对于 k sum， k > 2 的，如果用sort的话，可以 对 n - 2 的数做嵌套循环，因为已经sort过了，最后剩下的两维用2 sum的第二个办法， 时间是O(nlogn + n^(k-2) * n) = O(n^(n-1))，空间O(1)。 但是这样跟纯嵌套循环没有什么区别，只是最后一层少了一个因子n。有什么办法能优化？
就是说，对于 k sum (k > 2) 问题 （一个size为 n 的array, 查找 k 个数的一个tuple，满足总和 sum 为0）， 有没有时间复杂度在O(n^(k-2))的办法？

之前常规的一层一层剥离，n 的次数是递增的。只有在最后一层，还有两个维度的时候，时间开销上减少一个 n 的因子，但是这样时间开销还是太多

我们可以通过对问题分解来解决
举个例子 [..., -5，-4，-3，-2，-1, 0，1, 2, 3, 4, 5, ...] 要找 4 sum = 0. 那么先分解 4 分成 2 sum + 2 sum 来解决，但是这里的子问题 2 sum 没有sum = 0 的要求，是保留任何中间值。只有当子问题的 2 sum 解决以后，回归原问题的时候，我们才又回归原始的 2 sum 问题，这时候 sum = 0
子问题，空间和时间消耗，都是 O(n²). 回归大问题，时间消耗，是O(n²).

假设 k sum 中  k = 2^m, 那么一共有 m 层，会有 m 次分解
分解到最底层，时间空间消耗 从 原始 O(n) 变为新的 O(n²).
分解到次底层，时间空间消耗 从 O(n²) 变为新的 O((n²)²)
...
到达最顶层，时间空间消耗就都变成了O(n^(2*m)) = O(n^(2logk))

和之前的方法 O(n^(k-1)) 相比，O(n^(2logk)) 的时间是少了很多，但是空间消耗却很大。
因为子问题无法确定把哪一个中间结果留下，那么就需要把子问题的结果全部返回，到最后，空间消耗就很大了。整体效果算是空间换时间吧。

通过 问题的分解 + hashtable 的运用，能明显减少时间消耗, 但是空间消耗变大是个问题。比如说，如果有10⁶的 int 类型数组，我如果用这个hashtable的办法，就要有10¹²的pair，这就有 10T 以上的空间消耗。

问题的分解是个很好的思路，但是中间值得保留迫使空间消耗增大，这和用不用hashtable倒没有很大关系，只是说，如果不用hashtable，时间消耗会更大。

另外，还有一些题目的变形，比如如果要求所有组合，满足
sum < k,
sum = k,
sum > k,
或者是 closest to k
遇到这些变形的时候，hashtable 的做法就显得乏力了，但是嵌套循环的方式却仍是可行的。尤其是对closest to k 这种非确定性的要求。

Summary of five practice of Leetcode 18: 4 Sum

Dec. 29, 2017

Introduction

It takes over 6 months to learn one algorithm similar to Leetcode 18: 4 sum, and also each of five practice is helpful and also documented. I just need to go over them again and figure out what to learn from those practices.

4 sum algorithm

5th practice, Dec. 27 2017, here is the blog. After the practice, I updated the code review code with this version to replace 4th version written in Nov. 2017, and also added some commented in the question.

4th practice, Nov. 4, 2017, here is the blog. After the practice, I posted the question on code review.

3rd practice, August 31, 2017, here is the blog.

2nd practice, April, 2017, here is the blog.

May 2017, Leetcode 18: 4 sum practice is here.

Here is the link to search 5 practice using label: 4 sum practice, Leetcode 18: 4 Sum.

Full stack academy

Dec. 28, 2017

Introduction

I had a mock interview 12:00 PM, and my peer just finished his full stack academy program. And I spent extra hour to talk more about the algorithm and data structure. I was so amazed at his performance.

Here is JavaScript for me to review.
Here is JavaScript for binary search inorder successor.

Full stack academy

Plan to do some study about full stack academy program.

It is 9:38 PM, I am watching 20 minutes video. Here is the link.

It is 3:43 PM, I am working on Leetcode code review. I just start second time to watch the video of full stack academy as well, the link is here. 30 minutes, a panel discussion at our "Back to the Stack conference", where a few alumni came back to our campus to talk about their lives after Fullstack.

Time to learn object-oriented programming

Dec. 28, 2017

Introduction

It is time for me to watch some object-oriented programming course on pluralsight.com. I plan to watch some videos of object-oriented programming, I just need to spend around 12 hours to watch those videos, and then take some notes.

Courses

Here is the list of courses I can watch before January 2, 2018.

Leetcode Number of Island II

Dec. 28, 2017

Plan to study the algorithm Leetcode Number of Island II.

Follow up

1/21/2018 3:19 PM
I like to follow up on this algorithm. I spent over 10 minutes to read the discussion about one solution. I like to put Java code into github and create a gist first, and then I will write a C# solution as well.

Also plan to study the algorithm blog written in Chinese, the blog link is here.

Leetcode 200: Number of Islands

Dec. 28, 2017

Introduction

Plan to study the algorithm Leetcode 200: Number of Islands. I got the advice to work on the algorithm from my mock interview peer on Dec. 27, 2017.

Every algorithm there is a story about hard working programmer

Dec. 28, 2017

Introduction

It is another normal mock interview practice Dec. 27, 2017 10:00 PM. My task is to write another binary search algorithm called root of a number. I have worked on binary search algorithm over 30 times last 9 months, I have wrote so many blogs about the algorithm as well. But this time I still made a mistake in the edge case, while (start < end) should be while( start <= end), and the peer was very smart to tell me that if x = 1 then my code will return -1 instead of 1. The peer was surprised that I found the bug missing = sign in less than 2 minutes before. I did not tell him that I recently had same issue and wrote a blog about the case as well.

Here is my C# code on this practice.

Binary search algorithm

The peer asked me in the mock interview a question, "how come you are so good at binary search algorithm?" I told him that I have worked on binary search algorithm last 6 months over 30 times. I have mock interviewed the peer using binary search algorithm over a few times. I made a few mistakes before, and one time the peer advised me to focus on middle, do not work on start or end edge case.

I still remembered that my last practice on this number I did wrong on the binary search range, but the mock interview platform does not catch the error.

Newton method

The peer shared me his Newton solution to solve the root of number. Here is the code.

Recursive algorithm

I spent extra 30 minutes to use ShareCode to discuss with the peer, I like to use my favorite algorithm Binary Search Tree Inorder Successor to test how good he is in terms of confidence to solve the recursive algorithm.

Leetcode 18: 4 sum

Dec. 27, 2017

Introduction

It is the cold day in the city of Vancouver, I spent the whole day inside the home for another vacation day. I have a whole week off. I only went out with my friends to take a walk in Burnaby central park, and I booked 3 mock interview 12:00 PM, 8:00 PM, 10:00 PM.

First peer is working on next January Google onsite interview, second peer is working on next January Facebook onsite interview. Third peer is from Shanghai, China, he had Google onsite 4 years ago, and then he prepares to get another one.

I was busy to observe how other programmers work on problem solving. My thinking is that young people are smart, and very good at communication, but lack of challenge in daily work or practice compared to working on Hackerrank contest advanced level algorithm. I want to see those determination and dedication in their problem solving process in the future.

 I went through the Hackerrank contest to work on advanced level algorithm, I understood that it is so hard to make things work, score zero from over 5 hours for a depth first search, but the algorithm cannot meet the time complexity requirement.

Those young peers are trying their luck, they will experience how tough the fight is after their onsite interviews. There are some candidates with a lot of practice and being able to solve the problem in less than 10 minutes.

Here is my records of practice:

Leetcode 4 sum

I had mock interview 8 PM. The peer has experience to work for Microsoft, and then I got advice how to improve my code.

My last practice is on Nov. 14, 2017. I wrote the blog the document the practice. And after that I posted a question on code review website but no one gave me review.

Dec. 27 is my fifth time I worked on the algorithm, I wrote exactly same code of 4th practice. But the peer gave me a few of advice to simplify the code.

The above code can be simplified. First look at the redundant code to manipulate the dictionary.

The first is to reduce four variable to two variables, save i, j instead of arr[i],arr[j], i, j. Secondly line 17 and line 23 are the same, extract them outside the if/else branches.

Here is the code after simplification.

Actionable Items

Look into those four companies, Nitanix, Uber, Qualtrix, Splunk.

Code review: Binary search tree inorder successor

Dec. 26, 2017

Introduction

I spent over one hour to write a question to post on code review website. As a mock interviewer, I like to get some help from the code review website.

Here is the code review link.

Count the connected components in a matrix

Dec. 26, 2017

Introduction

It is the good idea to write a recursive function to complete the algorithm in less than 10 minutes. I could not do it. My last practice took me near 20 minutes or so.

Here is my last practice at 10:00 PM on Dec. 24, 2017.

Today I had a mock interview at 6 PM, and then the peer wrote a C# version as well. I will write one using similar idea, to check recursive for left/ top/ right/ bottom four neighbors if the range is ok and also the value is 1.

H-Tree recursive solution

Dec. 26, 2017

Introduction

I had a mock interview at 6 PM this evening and then I met a programmer who prepared a test case for my algorithm. I felt that the peer is the very good programmer and then I gave a lot of feedback on his coding review as well.

Here is my C# code to write a recursive function to implement H-tree.

Code review: Leetcode 10: regular expression matching

Dec. 26, 2017

Introduction

It is another mock interview 12:00 PM. I had chance to help the peer solve Leetcode 10: regular expression matching. I did not expect that the peer can solve the problem almost perfectly. I was so surprised to learn from the peer how he wrote an elegant recursive function using while loop.

Code to study

Here is the peer's C# code. I like the implementation.

The above code failed last test case, "abaa" and pattern string "a.*a*". It should return true.

Here is the code to fix the above bug. The code passes all test cases on mock interview platform. But it failed on Leetcode 10 online judge.

Index out of range error, Line 28: System.IndexOutOfRangeException: Index was outside the bounds of the array. Last executed input: "ab" and ".*c"

Line 28: If(text[tIndex] != pattern[pIndex])

Actionable Item

After spending over 30 minutes to debug the issues using Leetcode 10 online judge, I learned that the recursive solution has a lot of issues. Later I will revisit the solution and give more objective comment on this solution.

sliding window in the array

Dec. 26, 2017

Introduction

It is the mock interview of 12:00 PM. I have to practice a solution for k-messed array sort. Since C# does not provide minimum heap class, the peer told me that I can apply sorting similar to insertion sort.

After we discussion to use linear scan k + 1 window to find the index with the minimum value, and then swap the start position with minimum index, I wrote the following code.

C# code is here.

My argument is to write the code and also the code can pass all mock interview platform test cases. Although the time complexity is O(kn), k is the size of slide window, n is the array's length. The optimal one using minimum heap is better with time complexity O(nlogk).

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. 

Code review written in C++

Dec. 25, 2017

Plan to review C++ code written by the peer in the mock interview on Dec. 25, 2017 6:00 PM.

Here is the C++ code.

Swap technique applied to search minimum missing number

Dec. 25, 2017

Introduction

It is almost 2 hours mock interview. I had chance to practice the algorithm to use swap technique again. And then the peer asked me to write the optimal solution as well.

I wrote the solution, and did the white board testing. Run the code and there is a dead loop, timeout.

Code review

The C# code is here with constraint "The array cannot be changed".

The C# code is here with the permission to change the input array.

Follow up 

The C# code can be optimized for the case to change the input array. The code is optimized and the link is here.

How to work with graduate student?

It is learning experience for me to work with the peer today. I learn that if I treat the peer with patience and great attitude, then the peer will treat me with patience as well. Just be patient and learn some C++ through mock interview today. 

Listen to your elder sister (III)

Dec. 25, 2017

Introduction

It is good experience to have a elder sister who is a physician and working full time last 30 years. I never need to worry about anything about my mom until Nov. 11, 2017 as a daughter. I know that the doctor sister has an idea how to solve the problem, my mom enjoyed her life and lived 87 years old. My mom enjoyed most of her time in her last 17 years.

I still remembered that my elder sister wrote letters to urge me to help my mom to purchase her own home first time when she almost turned to 70 years old in 1999. Life was so different when you have some one to share her story in different country. I should have more understanding about big difference earning income as a full time employee in two countries 17 years ago when I was younger, work as a full time software engineer in my first year in United State.

Now as a Christian, I understood that the important thing is to be humble and give the help to the need to follow the bible teaching.

Listen to your younger sister (II)

Dec. 25, 2017

Introduction

It is the biggest treasure to have a younger sister, specially after my mom passed away since Nov. 11, 2017. My younger sister is a lecturer all her career to teach biochemistry in the university of Yichun, Jiangxi province. We all are busy and grow apart, and then follow different directions in the life.

I like to write something to say how good it is to have a young sister in your life.

Research and law

2000 - 2001

My young sister started to teach in the university when she was 23 years old. She helped my mom to apply visa to USA back in 2000 when she took one year break to study in the university of Beijing as a teacher exchange program. Therefore my mom had chance to visit Florida twice in 2000 and 2001, first time my mom stayed in Florida with me four months, and then second visit was five month long. I had work visa H1-B at that time and worked for a online entertainment software company.

2016 - 2017

My nephew grew up so quickly, he spent 6 years to live with my young sister and my mom from 2005 to 2011. And my younger teacher sister helped him to learn and study very hard. And then he spent two years with my elder teacher sister, another one in Shenzhen city from 2010 to 2001. At that time, his English teacher tutored him to work on English since my teacher sister did research and analysis on his potential and weakness to prepare his university admission examinations. English is easy to get improved in short training or tutoring.

Now back to July 2016 my teacher sister told me to work on sponsor application, go to check the law. I listened and then started my journey.

It is my turn to be a grown-up and help young generation. It is hard and take it slow, invest time to learn and figure out things by myself. I did complete the sponsor application at the end of 2017.

Listen to your elder sister (I)

Dec. 25, 2017

Introduction

I have an elder sister who retires in China and she always laughs at me. She boasts all the time how social community country treat her really nice as a teacher. She worked all her career as a high school geography teacher and enjoy everything. She has visited more than 20 countries.

It is the biggest help if I can make some dollars in the city of Vancouver by investing a property five years ago. If I have more financial freedom, then I can enjoy myself to practice more algorithm, write more coding blog, less concern to work on something else to make ends meet.

But my point is to respect your elder sister, honor the woman who brought up a son, a mom of a staff engineer in California. If I can be close and dearest sister, I may add over $100, 000 dollars with less pain and sweating. The most important is to listen to your elder sister.

I have four sisters and one brother, one sister is such a smart one and she told me that I should buy a home five years ago. Now she thinks that it is too late to purchase a property in the city of Vancouver.

I was stubborn, and I set up my priority different way.

Bible teaching is to settle down a new place, be part of the community at the very beginning. Instead I choose to live an easy life, do not put myself under pressure of mortgage, and focus on my career.

Learning technology and work on career is hard to achieve with less guidance. Compared to listening to my elder sister,  I should have followed her guidance as she relocated to Guang dong province in 2000. I should choose to live a nice and comfortable home first, and enjoy the urban work and life as a Chinese, purchase a home and work with biggest bank first, and then figure out how to survive later.

I have been a Canadian last eight years now. I have to catch up and learn something about personal finance.

Leetcode 10: regular expression matching

Dec. 25, 2017

Introduction

It is time to write hard working stories that will touch my heart again, I always like to read my own blogs and then get encouraged to work on more on algorithms.

I started my six round of mock interview after I finished around 30 algorithm a few days ago, so I started to use ID: 2017 to start a new round. Also I chose the setting called: Advanced level of interview, one level below the top one. The top one is to eat and sleep on algorithm. I just could not believe that I had to chance to learn so many things about the industry and how good people are to study or work for a software engineering career.

It is Christmas holiday break, and I decided not to hang out with friends. I choose to work and meet new people. I set up a few mock interviews on Dec. 24, 2017 from 4:00 PM, 8:00 PM, 10:00 PM. You know what, since machine learning algorithm picks up my setting of advanced level, this round is different. All first three interview questions for me to interview peer are hard level algorithm, same algorithm same day for three peers, Leetcode 10: regular expression matching.

Hard working graduate student

First peer is a university master graduate student with top 50 ranking university in California, I had chance to learn how to write a dynamic programming solution from him. I spent extra one hour 20 minutes to discussion other algorithm with him as well.

Dynamic programming solution is not easy for me to figure out. I had some questions about the implementation, and then I asked the peer. But I could not be convinced for three cases, a*, for zero time, one time or more than one time.

Here is the blog for the review of the peer's code.

The peer complained to me that he could not find enough interview opportunity for intern. I gave the advice for him, increase online presence. Write on quora.com or coding blog, document the practice. The peer is really good at dynamic programming algorithm.

Linear scan the array

Dec. 25, 2017

Introduction

I had a mock interview at 12:00 PM. I wrote a linear scan algorithm and finished the algorithm in 22 minutes. The peer asked me if I solved the problem before, and then I explained to the peer that I solved similar algorithm, there are two famous algorithms related to linear scan algorithm, test how good you can write a for/ while loop. One is called Leetcode can plant flower, one is called hackerrank Bear and gene.

Code review

The C# code is here.

Leetcode 10: regular expression matching

Dec. 24, 2017

Introduction

It is the hard level algorithm in Leetcode. Leetcode 10 is also called regular expression matching. I have practiced over ten times, and I always choose to use recursive solution.

I had a mock interview and the peer solved Leetcode 10 using dynamic programming.

Code review 

Plan to study the dynamic programming solution. Here is the Java code.

Leetcode 315: Count of Smaller Numbers After Self

Dec. 24, 2017

Introduction

It is the hard level algorithm, and binary search tree can be selected to store the array of elements from left to right. The only trick is to increment the count whenever the new node is bigger than root node's value.

My practice

I like the hard level algorithm. So what I do is to go over the brainstorm first, and think about sorting the array, save the index; and then figure out the time complexity could not beat the brute force O(n<sup>2<sup>), and then think about store the array into binary search tree, and also keep some calculation in the same time.

I underestimated the problem, and I spent 30 minutes to write code but I could not pass the sample test case.

Here is C# code which could not pass the sample test case.

Follow up 

I asked the peer after mock interview on Dec. 24, 2017, a university of southern California university master graduate student, he analyzed using dynamic programming approach. We reached the agreement after 10 minutes, the solution may end up O(n²) at last.

Follow up 

I asked the peer after mock interview on Dec. 27, 2017 10 PM, a software engineer over 10 years experience in the city of Shanghai,he explained to me the divide and conquer algorithm similar to merge sort. I was not able to follow his explanation.

Array linear scan algorithm

Dec. 24, 2017

Introduction

It is the Christmas day and I like to take some time to practice mock interview. And I had 10:00 am mock interview.

The algorithm is the array linear scan and reverse the array.

Here is the C# algorithm.

Code review

Plan to find all past practice first and review every practice here.

Interval overlap?

Dec. 24, 2017

Introduction

I had a mock interview 10:00 PM to work on the algorithm related to interval. And then I had chance to practice the algorithm in 30 minutes. I explained the algorithm by some drawing first and then write the algorithm.

Dec. 23, 2017 practice is 30 minutes long. Here is C# practice. The code could not pass edge case to return empty case, need to figure out later.

Interval overlap

There are more than one way to define the interval overlap. To choose minimum value of two start values and then maximum value of two end values, and also check the max value is bigger than the minimum value.

Interval algorithm 

It is time for me to review my practice on interval related algorithms last few years.

Code review: At least 2 paths down the binary tree have the same sum

Dec. 23, 2017

Introduction

It is my most favorite algorithm in the world in June 2016. I had to go through the transition to accept myself as a software programmer, and learn how to improve myself through this simple algorithm. I did the practice and then stopped without writing an optimal solution in June 2016. Now after more than 12 months, I know that at the time I do not have high standards on practice at all.

Here is the algorithm I practice in June 2016.

I reviewed the code on Dec. 23, 2017 and asked the question on code review website. Here is the code review web link.

June 2016

It is tough to deal with frustration, what I did is to write a blog to study the failure on June 5, 2016. I was so excited to go over one day meeting with the most highest standard software company. And then I experienced so many issues through meetings. One thing is that I did not perform very well on the similar algorithm using C# LINQ.

Add one more paragraph

One thing I like to do is to add one more paragraph on the code review. Since I do not get any upvote after 24 hours, so I like to step out and do something to help myself.

Here is the paragraph:

Code improvements

I decided to make a few improvements based on my last practice over 18 months ago. Internal class is used instead of external class. I choose to use camel case for public method, and rename the function DuplicateCheckingPathSum to make the function name self-documenting. Specially I took 10 - 20 minutes to go over those stackoverflow links to learn LINQ and also ASP.NET C# class and I found that those links are really helpful for me to warm up LINQ. It is tough for me to see that after 18 months I still do not make big progress on LINQ and the functional programming syntax still looks like foreigners to me.

Most of important change is that I learn better recursive function design after 18 months. I was surprised that I ended my last practice with so many issues. The base case should be selected to avoid duplicated count of each path. I like to see the depth first search algorithm specially a recursive function is written in very structured way, base case is very clear and also the recurrence formula afterwards.

Follow up 

Dec. 25, 2017
Early in the morning I got code review, and I was so excited to read the review. Here is the link of code review.

Code review: Leetcode 10: regular expression matching

Dec. 23, 2017

Introduction

It is the smart idea to ask the classical algorithm on the code review website. I did one on Dec. 22, 2017. I got one down vote, and 3 upvotes in first 24 hours. Compared to the classical algorithm Leetcode 10, I asked another algorithm question based on my practice, here is the link. I am still waiting for the first upvote for the algorithm.

Here is the link.

Recursive function practice

Dec. 22, 2017

Introduction

It was another 10:00 PM mock interview. I had one algorithm to work on, write a recursive function.

Here is my C# practice.


Blog written in November, 2017, here is the link.

Blog written in June, 2017, here is the link.

Structure of depth first search

After I practice depth first search with so many peers, until this November, 2017, I start to learn that it is very important to write the algorithm in a very structured way.

First, I should check edge case to prevent the run-time exception,and then I like to write a base case. What is most simple task I can complete to do the work. For the above algorithm, it is the node without any children. Every one can write one line of code to figure out the minimum path. There is only one choice, and one value, just return the value.

So next step is to ask all your children nodes to do the same task for you, and then you only have to find the minimum one, and add current node's value to it.

To peer with so many talent programmers in the world, I have chance to learn the recursive algorithm in most fashion ways. Because if I do perform very well, the peer will give me extra time to share some tips, and also I have time to learn a new person, and get connected with another hard working person.

Analysis of the algorithm

I like to write some review about my practice in November. The peer found the bug in my code. Usually it also tells me that I should work on the analysis of the algorithm. Do not let the problem come to the bug, I should catch it in the analysis of the algorithm.

Statistics

Past practice on the algorithm last 5 rounds:
.1107 12/21, .sh 9/14, .mp 7/30, .ca 6/14, .fl 5/7

Buy or rent?

Dec. 21, 2017

Introduction

It is the most hard question for me to answer at the end of 2017. I start to look for a place to purchase, I have not purchased any property last 18 years.

I like to do some research 10 to 20 minutes a time, and write down what I should learn.

Let me make my research less serious. It is coding blog, we like to document how hard we work. But a laugh always cheers me up.

My friend laughed at me recently, 5 years ago the property is $300,000, now it is $500,000 in the city of Vancouver. Now it is the peak time, but I start to plan to work on the purchase.

Research topic

How to define the most important thing in the life? Recently I talked to my friend in Florida and he told me that he has to pay $1000 medical insurance by himself, and then I compare to Canada MSP medical insurance. The insurance in Canada is much less compared to Florida. So I decide to purchase a home in Canada.

How to decide which city to purchase? Surrey or Langley or Abbotsford?

Book reading: Mathematics for computer science

Dec. 21, 2017

Introduction

It is time to enjoy the book reading: mathematics for computer science.

Leetcode 10: regular expression matching

Dec. 21, 2017

Introduction

I met a peer who likes to share his regular expression matching dynamic programming solution last Sunday, so I know that he is very talented programmer. I like to review his analysis and his code written in C++.

The analysis is here. C++ code implementing dynamic programming is here. 

How to find time to work on coding challenges?

Dec. 21, 2017

Introduction

I had a mock interview on Dec. 20, 2017 10:00 PM. And I was asked how to find the time to improve the coding skills and become a competitive programmer.

There are risks to spend time working on the data structure and algorithm. Since we only have limit hours to work on coding every day, sometimes if we do spend time on training, drills for practicing data structure and algorithm, then we will find that we are short of time to deal with daily tasks.

Just trust that the practice and drills will make you a strong player. Find ways. Write best code in the world, most elegant code with style called readable, clean as possible.

Train insane or remain the same

It is my favorite quote to encourage myself to train myself. 

Professional tennis players train themselves, in order to play 2 or 3 hours matches, they practice hundreds of hours. Hitting partners, mental trainers, coaches, and all kinds of get-together practice with peers, there are a lot of people get involved with training. Sports is fun to watch, but all those hard work and training is tough to go through. Same as I train myself to develop crafting skills, it is hard and it is not easy at all.

Coding skill is like the weight control project. In order to stay fit, we have to change life style, related to my own case, I have to be a sports player, and also need to study everything about tennis. Also I have to control my diet, and choose to eat unprocessed food as possible. Coding skills is the same. 

We have to learn how to take care of ourselves as a individual contributor, as a software programmer. Work on crafting skills, share and document the practice, journal the practice and keep improving. I also learn to encourage other peers do the same thing, it is not easy to work on training.

Code study 

Best and quick way to evaluate myself coding skill is to find some code I write. It is hard to learn the fact that I was not a good programmer at all back in year of 2013.

I shared my coding sample back in 2013. After full time work 4 years, I could not write a short and clean code in less than 15 lines. Instead of the clean, readable code, I wrote over 80 lines of code to make me try to hide the sample code 3 years afterwards.

What I did in last 3 years is a lot of challenge work. I have to work on so many issues. 

Pull all gists from github

Dec. 21, 2017

Introduction

As an owner of coding blog, I like to download all 1000 gists on github to the local computer. What I do is to google and find ideas to solve the problem. Once I have 5 - 10 minutes, I will search google and find some ideas to work on this small project. I found some python code to download the gists from github before, but today I like to give it a try.

Some progress

Dec. 21, 2017

As a github user, I also like to learn how to use github day by day. I do not want to do labor work, download one by one, do it 1000 times. Today I came cross the blog related to "pull all gists from github", here is the article link.

I read the python code, and then ask myself how to run bash script on windows. I search google and then I found that I need to install cygwin. And then I installed cygwin first, and then chose to install curl and then python3. I ran the code and I got some downloads.

Unfortunately, the download stopped after only 30 gists are downloaded.

Github API

Plan to study github api, and then I can solve more problems in the future.

Write down the date if I study API more than 30 minutes.

Code review: Leetcode 10: regular expression matching

Dec. 20, 2017

Plan to code review a dynamic programming solution to solve Leetcode 10: regular expression matching.

Here is the source code with the analysis.

I reviewed the above code, and rewrite the for loop using while loop since I do not like the loop variable in the for loop is changed inside for loop. I choose to use while instead.

I have some issues to rewrite the logic in the giant expression from line 57 to line 58 but had some issues to fail some test cases. So I keep the style even though I do not like it. I will figure out the issue later.

Here is the C# code.

Design review

Dec. 20, 2017

Introduction

I had a mock interview at 10:00 PM with a peer. After the mock interview, I asked the object-oriented design question, and the peer wrote down his idea.

Here is his writing, the idea is very clear to use interface, class, and the API design.


Also, the peer shared with me two design interview links.

https://github.com/donnemartin/system-design-primer

https://github.com/checkcheckzz/system-design-interview

Find the running median on Hackerrank

Dec. 20, 2017

Introduction

It is another 10:00 PM mock interview, I had chance to talk to the peer after the mock interview. I asked a few algorithm for him to solve, and then he advised me to watch Hackerrank Cracking the Coding Interview Challenges on the algorithm Find the running median.

Find the Running Medain

Plan to study some C# implementation and see if there are very good code to study.

Every good coding blog needs a revisit

Dec. 19, 2017

Introduction

It is interesting to learn how those peers develop their career by revisiting their blogs. I revisited one of blogs I blogged 2 years ago, and then I found out that the peer is an excellent coding blogger.

It is my time to review Leetcode 20 algorithm, and then I came cross this blog with the implementation of Leetcode 20.

Here is the blog written in Chinese. It is so interesting to study how good Chinese programmers are.

Blog study: OO design PH.D.

Dec. 19, 2017

Plan to study blogs written by a PH.D. graduate focusing on object-oriented design. Here is the blog.

My favorite reading today are the following:

1. Design model talk, here is the link written in Chinese.

2. Talk about mathematics as a software programmer, the article link is here.

3. Java design - the book link is here.

Follow up 

Dec. 15, 2017

Here are the articles I like to read carefully. 

design pattern java - the link is here. 

Leetcode 20: Valid Parentheses (II)

Dec. 19, 2017

Introduction

It is very hard challenge to plan what to study and what to review in this holiday season. Specially I will have a holiday break in the last week of December.

On Dec. 18, 2017, I practiced the mock interview, and then the peer worked on the valid bracket algorithm. The peer is a young undergraduate student who just started his computer science degree in university of Washington, top ranking computer science. The peer just started this year.

What advice can I give to the peer? I was asked by the peer.

I knew that it takes some time to develop the mock interview skill. But it is good to take the hint, and also follow the peer's idea. I was stubborn before on one mock interview when I met a computer science undergraduate from UCLA, and I learned the lesson on this algorithm called the largest smaller key in BST. I explained the idea to follow the hint to the peer.

Addition to mock interview 

It is a good idea to extend the algorithm for the mock interview algorithm. For bracket match algorithm, there are a few algorithms from Leetcode. I reviewed one of them called Leetcode 20: Valid Parentheses, and then I like to write down my review one by one.

Here is the blog I chose to study in January 2016, I also created a gist for the blog. The blog author wrote 170 blogs in Chinese, and he wrote very well. And also I found out that the blog Ethan Li 的技术专栏was written in 2015, now the peer works for snapchat, a facebook company.

I did great job for myself today, find 170 blogs to read related to algorithm, analysis and very nice readable code. It is hard for me to keep learning new algorithm while taking mock interview every week day 10:00 PM. It is better for me to read a lot of coding blogs, and reduce time on wechat related to social stuff.

I will choose five algorithm written by the engineer, and then write a blog for each algorithm.

Blog study: OO design PH.D.

Dec. 19, 2017

Plan to study blogs written by a PH.D. graduate focusing on object-oriented design. Here is the blog.

My favorite reading today are the following:

1. Design model talk, here is the link written in Chinese.

2. Talk about mathematics as a software programmer, the article link is here.

3. Java design - the book link is here.

Follow up 

Dec. 25, 2017
It is now 5:39 PM. I have mock interview in less than half an hour. I like to update my blog about reading progress.

I could not believe that I was too busy to read the article from the professor. Today I found a good article to read in 10 minutes. Here is the link to talk about template method.

Leetcode 32: Longest Valid Parentheses (I)

Dec. 18, 2017 

Introduction

Longest valid parentheses is the hard level algorithm and is one of Leetcode algorithms. 

Back to January 2016, I did not know that Leetcode discussion panel has so many solutions. I always tried to google and found the solutions. Here are my favorites back in 2016. 

Code study 

A Chinese blog with more than 8,000 views. The link is here. 

To learn the algorithm, in case the study blog may be retired some day,  I start to put analysis in my gist as well, the link is here. The Java code is here. 

Actionable Items

Review more blogs:

http://bangbingsyb.blogspot.ca/2014/11/leetcode-longest-valid-parentheses.html

http://shanjiaxin.blogspot.ca/2014/04/longest-valid-parentheses-leetcode.html

Julia C# practiced the algorithm in January 2016, here is the code.  

Leetcode 20: Valid Parentheses (I)

Dec. 18, 2017

Plan to review the algorithm called Valid Parentheses. It is the easy level algorithm. 

Last practice in 2016 is here. Another version is here. 

Here are the blogs I chose to study in January 2016, documented in a blog here:

http://blog.csdn.net/fightforyourdream/article/details/13011825

http://bangbingsyb.blogspot.ca/2014/11/leetcode-valid-parentheses.html

http://blog.csdn.net/foreverling/article/details/49685177?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io

http://segmentfault.com/a/1190000003481208

http://www.jiuzhang.com/solutions/valid-parentheses/here

Actionable Item

One thing I like to do is to break the blog written in January 2016 into multiple blogs, I may study a lot of hours on those algorithms. It is better for one blog for each algorithm. And also one blog for each good idea for Leetcode 20. 

Make life easy, specially learning algorithm should be more organized. 

Leetcode 22: Generate Parentheses

Dec. 18, 2017

Plan to work on Leetcode 22: Generate Parentheses.

It is medium level algorithm. My last practice is here, back to 2016.

Code review is fun

Dec. 17, 2017

Introduction

I spent 10 minutes to review the algorithm written in C++ after I spent over one hour to write a  C# version of Leetcode 4: Median of two sorted array. The code in C++ is based on the work I presented and the peer made some simplification in C++.

I like to give a quick and short code review.

Code review for fun 

Here is the C# code I wrote.

Here is the C++ code I like to review.

A variable written in r on line 9 can be understood using multiple meanings, it can last index of the array, or it can be the length of the array, and interview is kind of competitive programming, under pressure you will confuse yourself as well, time is limited to 30 minutes. So if you write something which is verbose, it is good and it is self-explanation. 

Of course, coding style can be picked up in less than a few hours, as long as the algorithm is correct you should be ok. Most important is the strength of algorithm analysis itself. But you certainly should ask the interviewer his/ her style. 

FindIthElement -> FindKthSmallestElement, if it is private function, then in C# starting from lowercase. The function name should be called findKthSmallestElementThroughTwoSortedArray, the name covers every detail of function arguments. And also one more thing is missing in the title, it should be called findKthSmallestElementThroughTwoSortedArrayWithGivenStartIndexes. 

Do not laugh at me. I am just acting like a teacher, or an interviewer. 

Michael Mmoh - ATP tennis player study

Dec. 17, 2017

Watch the video of 10 minutes, the link is here.

Kyle Edmun - ATP player study

Dec. 17, 2017

Introduction

It is the best time in the day to study a player Kyle Edmun. I need the fresh idea how to develop myself as a recreational tennis player. And also I like to learn new things and know a new player.

Now it is 11:03 PM, I just finished 10 minutes of video called Kyle Edmund - Rising British Tennis start, Trans World Sport.