Training as a programmer

August 12, 2018

Introduction

There are so many ways to advance yourself to top programmer in the world. But it is not easy at the beginning, in the middle of process, maybe last 10% should be easy.

It is hard work, and a lot of coding. No recipe can replace hard working, training, coding every day, every week.

My training 

I have tried so many things last four years. I did see some progress but I still need to work on more.

Here are the list of things I worked on last few years.

1. Over 25 Hackerrank contests played; 100 algorithm problems solved or partially solved. Here is my hackerrank profile.
2. 40 algorithm questions asked on code review stackexchange.com. Here is my code review stackexchange.com web link.
3. 140 Leetcode algorithm solved up to August 12, 2018. Here is my Leetcode profile.
4. 350 mock interviews. Here is the link on my github for mock interviews.
5. 60 mock interviews as an interviewer. Here is the link on my github as an interviewer.
6. 2000 blogs about algorithm and related topics.
7. Real experience for code challenges, meetings like phone screen, onsite, mock interviews. One of blogs is here. Another one is here.


Based on my ex-coach advise in July 2018, I need to work on Leetcode easy level algorithm, work on easy level algorithms first, and then move on medium level algorithm, and then move on to hard level algorithm. I like to submit 200 algorithms on Leetcode.com first. I submitted 100 algorithm up to July 1, 2018. Let us see how long it takes me to complete second 100 algorithms, most of them are easy level Leetcode algorithms.

August 12, 2018, Leetcode solved problems:

July 21, 2018, Leetcode solved problems:

July 21 - August 12, 2018, 32 easy algorithms, 5 medium algorithms, 3 hard level algorithms.

Leetcode Tree algorithm

Here is the link to find all Leetcode tree algorithm. 91 algorithms include 27 easy, 55 medium, 9 hard algorithms.

23 solved, total 27
14 solved, total 55
2 solved, total 9.

Recursive function design talk

July 16, 2017

Train insane or remain the same - Get recursive function training one more time!

Maze algorithm

Given an array, there is only one item is value of 9, all others are 0 or 1. 0 stands for the exit is not availabe, 1 is ok to continue. Make a judgement if starting from (0,0), 4 directions: upper, down, left and right, and see if there is path to find 9.

Plan to study the code written in Java first. The code is here.

Practices

Using queue, the C# code is here.

Using queue, but four directions are written more clearly, C# code is here.

After 90 mocking interviews, Julia knows that it is important to write a short version solution in less than 5 minutes, without any bug. So she decided to write a recursive solution using depth first search, she ran into stack overflow issue. It took her over 10 minutes to figure out the issue, mark the node visited on line 46.

Here is the C# version code using recursive function. The goal is to write in less than five minutes, and pass the test case in less than 10 minutes.

In order to shorten the time to write code, Julia spent hundreds of hours to learn recursive function. One of her most lesson learned through mocking interview is the bug she found, documented in the blog called Leetcode 10: regular expression match.

Ask a vote?

Which version of code you will choose to write? Julia learned the lessons through years, she learned from 90 mocking interviews, she still could not nail down the most important solution using recursive solution in less than 5 minutes, today, July 18, 2017.


Just like a song, Julia you have to memorize the lyrics, you only have 4 sentences to remember. First one is to return false, second one is to return true, third one is to set to 0 as marking visited, and then fourth one is to call recursive function for 4 possible neighbors. In other words, here is the transcript to remember:
Line 8           return false
Line 13         return true
Line 18         maze[row][col] = 0
Line 21 - 24 four recursive function calls concatenated by || operator

Leetcode 142: Linked List Cycle II - first practice

July 14, 2016

Continue after first blog on this problem:
http://juliachencoding.blogspot.ca/2016/07/leetcode-142-linked-list-cycle-ii.html

Java solution written in facebook code lab:

https://gist.github.com/jianminchen/cc0f97525e3eb68db23f4a07ec0b7e90

The code failed to pass some test cases.

Highlight problems on the first writing:

1. line 20,
normalRunner - one step a time, the variable name is too long; slow will be better.

2. line 21,
doubleRunner - the variable name is not so accurate; fast will be better.


problem 1:  base case checking:
line 17:   if(a == null)
                   return null
  if the list is null or only has 1 node, then no cycle.

problem 2: doubleRunner and normalRunner is in the same list, and doubleRunner is ahead of normalRunner if there is no cycle; and if there is a cycle, two runners will run forever. In both cases, only need to check doubleRunner != null, if it is true, then normalRunner != null will be true as well.

In short, doubleRunner != null  =>   normalRunner != null

The while checking has duplicate checking! 

problem 3:
   line 24:  doubleRunner is not null <= it is duplicated with base case checking (line 17)! 
    While loop line 24, doubleRunner != null is duplicate with base case checking.

  While loop design:
Let us check fast node can move 2 steps, next two nodes are not null;
if slow and fast node meets, then break the loop. <- make the logic checking positive, not negative (line 25)

problem 4: 
   while loop is not designed very well - easy to make bugs, hidden bugs.
   line 25: negative checking - make the code more confusing

problem 5:
   line 34: bug001 - if clause checking problem
   line 35: doubleRunner != null => normalRunner != null
   so if statement is not optimal
problem 6:
   line 35: there is a hidden bug here - still cannot figure out.

problem 7:
   line 38: extra variable - not necessary, reuse the old one, still in the scope.
   line 40: not necessary
   line 41: not necessary

Actionable item:

1. Document the mistakes made in the practice, learn from the experience.

2. Review code and figure out issues without any help.

Could not figure out bugs in the first practice
-> Failed facebook code lab test cases
-> Studied optimal solution
-> Ran optimal solution in facebook code lab
-> passed all test cases
-> then, started to find problems in the first practice
-> wrote down problems one by one






Train insane or remain the same - focus on training!

Train insane or remain the same 💪#progress #nopainnogain #mondaymotivation
Séance de 1/2squat aujourd'hui😉 et vous? pic.twitter.com/K8tGiOXixC

— Kristina Mladenovic (@KikiMladenovic) June 20, 2016

Leetcode 139: word break I - 3+ practices

June 22, 2016

Work on leetcode 139 - word break I

Problem statement:

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Programming skills is like muscle, if you do not maintain it, it will go back to fat. When Julia tries to stretch DP muscle, she found out that she has nothing to stretch. She has to work on it, build up by hours, build up again. Leetcode 139: word break I (medium).
Julia read the code/ solution, but she could not figure out in detail, specially for those two loops - for DP algorithm. 

http://bangbingsyb.blogspot.ca/2014/11/leetcode-word-break-i-ii.html

1 hour, play with 2 test cases. 

3 practices using C#; Set up a test case, run the code, and then, understand the algorithm.

Same code, different test cases
1st practice:
https://gist.github.com/jianminchen/f763ce5033ea4b152c7a56aaf98b7075

2nd practice:
https://gist.github.com/jianminchen/a1bafb4271b8bbdb18b92d0b3dad913e

3rd practice:
https://gist.github.com/jianminchen/bd9301c3ad38d801001d1d66a08256fe

Let us walk through a test case:
string test = "abcd",
and dictionary string array: {"a","bc","d"}

We know that, "a" can be constructed by word "a" in the dictionary.
"ab" cannot be constructed by the dictionary.

Now, what we can do to work on substring "abc", assuming that "a", "ab" are processed already.

How to approach the problem?
Use dynamic programming, reduce the work to minimum.

abc, so 'c' is the new comer, assuming that "a" and "ab" have been processed. By debugging the code, Julia put together the following comment:

so, step 1, "ab" cannot be constructed by the words in dictionary, so it does not matter if 'c'  is in dictionary. 

   Use array bool[] dp to store the cached value; 

  

   Cannot conclude that "abc" can be constructed by words in dictionary, need to go through all possible new words: {"c", "bc", "abc"}

    step 2, backward one more char, new word: "bc", 

 "a" is in cache - dp[1] = true, 

 "bc" is in the dictionary. 

 so,  "abc" can be constructed by words in dictionary. 

 Stop here, break the loop.     

    At most there are 3 words ending at 'c':
    "c",
    "bc",
    "abc",
    All other substrings are the substring of  "ab", assuming that DP is used, so no need to worry about.

4th C# practice:
https://gist.github.com/jianminchen/36de4c46292e79290af95098dfee3cb0

Question and Answer:
1. What is most time consuming part in coding?
Julia spent over 20 minutes to figure out what should be looped on - line 80, it is hard to figure out
meaningful ways to loop. She tried a few of ideas, then, she chose to loop on the position of right string.

   "abc",
   i = 2, then, 3 things are tried:
  1.  "ab", "c"
  2.  "a", "bc"
  3.  "",   "abc"

  two strings are in each case, right string's starting position in the original string "abc"
 line 80    for( int pos = i;  pos >= 0; pos--)
  i = 2, "c"
  i = 1, "bc"
  i = 0,  "abc"

4th C# practice:
 https://gist.github.com/jianminchen/36de4c46292e79290af95098dfee3cb0

Spend 10 minutes to write the program again.
5th C# practice:
https://gist.github.com/jianminchen/9766aea70c9015fabbea98fb71b56d6d

hightlight of changes:
1. line 41 - variable name is changed from "left" to "existingWord", existingWord is already processed, which can be looked up through cache array - true/ false.
2. line 42, newWord, each time the new char is processed, there are ith words ending at position i.
Need to check if it is in word dictionary.
Comparison between 4th practice and 5th practice:
comment:

code:
4th practice:
1. Do not know only work on substring 0-i, length i+1 substring, bottom up approach as DP - dynamic programming.
2. Confuse with string left, right, why left string needs to check cache, and then right string checks word dictionary.

Read blog to review dynamic programming:
https://en.wikipedia.org/wiki/Dynamic_programming

Review a few concepts:
Principle of Optimality
optimal substructure
larger problem - sub-problems
Bellman equation - optimization literature names relationship
optimal substructure and overlapping sub-problems
Divide and Conquer   vs dynamic programming
Top-down approach vs Bottom-up approach

Word break I uses bottom up solution -

6th practice:
https://gist.github.com/jianminchen/29758bad5d56d54e87c2a6f52d057835
comparison line by line:
    6th practice                                             5th practice

7th practice:
second loop on DP algorithm, new word loop starts from start position from 0 to i, in ascending order, line 43. 
https://gist.github.com/jianminchen/2e56665d934f9b9cbc2f94adc8e567bb

Statistics:
Time spent:
2 hour +


Train insane or remain the same - focus on training!

Train insane or remain the same 💪#progress #nopainnogain #mondaymotivation
Séance de 1/2squat aujourd'hui😉 et vous? pic.twitter.com/K8tGiOXixC

— Kristina Mladenovic (@KikiMladenovic) June 20, 2016