Design patterns - Quick Study

May 26, 2016

Choose the blog to read, at least 2 hours to study:

http://blog.csdn.net/kenden23/article/category/2256833

Review blog:
http://juliachencoding.blogspot.ca/2015/12/book-reading-head-first-design-pattern.html

1. MongoDB (20 minutes reading)

https://en.wikipedia.org/wiki/MongoDB
craiglist -> MySQL -> MongoDB
2. Amazon DynamoDB vs MongoDB

3. https://plus.google.com/104439038177484907272

HackerRank: string algorithm - Reverse Shuffle Merge - Stack, backtracking techniques

May 26, 2016

Reverse Shuffle Merge - Problem statement:

https://www.hackerrank.com/challenges/reverse-shuffle-merge

Algorithm analysis:

Use test case: "abcacb" to explain the solution: 

int[] add = new int[26], 

int[] skip = new int[26]

a - 0, b - 1, c -2 

add[0] = 1, add[1] = 1, add[2] = 1, 

skip[0] = 1, skip[1] = 1, skip[1] =1, 

Find smallest lexical string. 

reverse input char one by one:

push b into stack, 

'c' > ''b', then, push c into stack

stack:

c

b

Now, a is scanned, 'a' < stack.peek() = 'c', skip[2] = 1 > 0, 

backtracking, pop c out of stack, skip[2] = 0

Now, 'a' < stack.peek() = 'b', skip[1] = 1 > 0, 

backtracking, pop b out of stack, then adjust skip[1] = 0

add[0] >  0, push a into stack, add[0] = 0, 

next, c is scanned, cannot skip, push into stack, 

next, b is scanned, cannot skip, push into stack, 

next, a is scanned, skip a. 

stack.ToArray(), keep stack iterator order, "bca", 

Array.Reverse(stack.ToArray()) -> "acb"

Lexical smallest string. 

previous blog: 

http://juliachencoding.blogspot.ca/2016/04/april-3-2016-httpsgist.html

warmup practice:

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

Second practice:

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

so many bugs in second practice:

1. confused on skip, add array --, ++; line 71, line 80 did the opposite.

2. string reverse, char[], string, Array.Reverse etc. lookup

3. add one more test case: "abcacb",

    b in stack, c in stack, then, run into a, pop up c, and pop up b, let 'a' in the stack. Two in row pop up in stack. While loop is tested on line 64 - 67.

4. while statement from line 64 - 67, fix compile error.

   both are ok to compile:

(char)stack.Peek() > runner)

(char)stack.Peek() - runner > 0)

Third practice:
The code passes HackerRank online test cases as well.

A few good changes:
1. add comment from line 67 - line 72, test case: "abcacb", 
use test case, stack top -'c' is removed, help to ensure the code is correct.
2. line 73, avoid bug to overwrite the variable runner, create a new variable called backTracked.

https://gist.github.com/jianminchen/8e2c28262dd3d13c4db856feaed5603e

Fourth practice:

1. create a new function getIndex - on line 100 - 103
2. after reading through the code, still missed a bug in writing - on line 55; debug the code and find
the result of first test case "abcacb" should be "acb", but it was "bca".

Julia examined line by line, but still missed the bug on line 55.

https://gist.github.com/jianminchen/7572e92ea48211d3d05c557d97601dbf

Read C# string constructor char[]: spend 10 - 20 minutes to read all constructors of string in C#.
https://msdn.microsoft.com/en-us/library/aa331865(v=vs.71).aspx

Binary Tree Preorder Traversal - Iterative Solution - Warm up Practice

May 25, 2016

Review blogs - Leetcode binary tree preorder traversal

C# practice:

use stack, and also know the order to push child nodes: right child first, and then left child next.

Code is here.

Question and Answer:
1. How is the practice?

Julia first thought about using queue to implement the solution, left child first, and then right child next. But, it does not work, since left child's left child should go to traversal first before right child. So, she had to stop.

Then, she tried to look into iterative solutions in general through Google, and also checked her previous practice.

Next time, go through a test case, do some analysis on the test case. Draw some diagram, help yourself to analyze, at least behaves like a teacher.

2. Things to work on through the practice?
queue -> stack -> opposite order to push into stack

3. Can you describe the process using your own words, a few of drawings to help the thinking process?

First, read the wiki article about stack.

Let us work on a simple test case:

The preorder traversal of tree: 1 2 3 4 5 6 7
When the root node 1 is visited, 2 and 5 should be added to some data structure, 3 and 4 will be added after 5, but output of 3 and 4 should be before 5.
In other words, the data structure should accommodate last in first out feature. So, it is stack!
Once stack is chosen to use, then work out the simple tree first with 3 nodes:

preorder traversal: 1 2 5
so, push 1 into stack, and then, pop out. 5 is pushed in stack first, and then it is turn of 2.

Next, work on the test case: tree - preorder traversal 1 2 3 4 5 6 7
1 is pushed into stack,
1 is on the top of stack, 1 is popped out,

1's right child 5 is pushed into stack,
1's left  child 2 is pushed into stack,

2 is popped out from stack,

2's  right child 4 is pushed into stack,
2's  left  child 3 is pushed into stack,

3 is popped out from stack,
4 is popped out from stack,

5 is popped out from stack,

5's right child 7 is pushed into stack,
5's left  child 6 is pushed into stack.

6 is popped out from stack,
7 is popped out from stack.

3. Most favorite problem solving using stack?

HackerRank: string algorithm - Reverse Shuffle Merge (IV)

warmup practice - C# practice code

Second practice:

C# code

so many bugs in second practice:
1. confused on skip, add array --, ++; line 71, line 80 did the opposite.
2. string reverse, char[], string, Array.Reverse etc. lookup
3. add one more test case: "abcacb",
    b in stack, c in stack, then, run into a, pop up c, and pop up b, let 'a' in the stack. Two in row pop up in stack. While loop is tested on line 64 - 67.
4. while statement from line 64 - 67, fix compile error.
   both are ok to compile:

(char)stack.Peek() > runner)
(char)stack.Peek() - runner > 0)

Third practice:

The code passes HackerRank online test cases as well.

A few good changes:
1. add comment from line 67 - line 72, test case: "abcacb",
use test case, stack top -'c' is removed, help to ensure the code is correct.
2. line 73, avoid bug to overwrite the variable runner, create a new variable called backTracked.

C# practice

August 8, 2016

Work on facebook code lab, preorder iterative solution. Chicken out! Forget to enforce the rule, right child goes to stack first, and then, left child goes to stack afterwards. And then, instead, nervousness kicked in, gave up in 5 minutes, looked up blogs.

Need more practice!

3 smart choices to ask myself: 

stack vs queue ->
left, right who goes first ->
enforce rule, null pointer will not go into stack, save time ->

one node ->
3 node tree - complete binary tree ->
7 node tree - complete binary tree

Leetcode 88: Merge two sorted arrays

May 25, 2016

Leetcode 88: merge 2 sorted arrays

Study the code:

http://fisherlei.blogspot.ca/2012/12/leetcode-merge-sorted-array.html

C# practice:

https://gist.github.com/jianminchen/0acddf70788fce10b9660dc16b2e3b71

Edge case handling:

line 42 - 47.

string algorithms - C# practice

May 25, 2016

study string algorithms:
http://www.cnblogs.com/luxiaoxun/archive/2012/11/12/2766095.html

1. Find most frequent char in a string:
C# practice
https://gist.github.com/jianminchen/d530d47982262de8a5e1cf5b49f7b54a

2. Find a string can be a substring of another string's rotation:
Given s1 = "AABCD"  and s2 = "CDAA", return true; 
AABCD -> rotate to left -> BCDAA -> contains substring "CDAA"

Given s1 = "ABCD" and s2 = "ACBD", return false.

http://kenby.iteye.com/blog/1451910

http://www.cnblogs.com/kaituorensheng/archive/2013/06/01/3105042.html


BBC documentary: Amazon - Lead principles study:
https://www.youtube.com/watch?v=RXLAlziEzAE

Binary Tree Inorder traversal - Iterative solution - warm up practice

May 25, 2016 Review binary tree inorder iterative solution, add some test cases. Julia C# practice code of binary tree C# practice Questions and Answers: 1. How is the practice of inorder traversal iterative solution? Julia compared to the other solution, line 354 - line 372, inOrderIterative_B https://github.com/jianminchen/leetcode-tree/blob/master/TreeDemo.cs and chose this one to practice: C# practice She wrote some comment to argue that the solution is very efficient and no redundant code. She likes to use reasoning and analysis to help her structure the function. Here are her analysis:           1. First, argue that line 88, why to check "if stack is empty, break the while loop" before outputting any node in the stack. Otherwise, if the stack is empty, then, line 91: execution run time error. 2. Second, argue that output of inorder traversal nodes is not in inner loop. If there are more than 1 in a row to output, then the outer while loop (line 79) will take care of it.       3. Third, argue that line 94: runner = runner.right; It does not matter that right child exists or not, line 81 will take care of null.  Complete one iteration - Push nodes into stack, then first node in inorder is on the top of stack, If stack is empty, break; otherwise, ready to pop top one from the stack, and then, move runner to its right child. Follow up after 12 months March 27, 2017 Read the blog and think about the better presentation, more readable.  Write another C# practice, and post a question about binary tree inorder traversal (iterative solution) for code review.

Leetcode 126: word ladder II (Hard)

May 24, 2016

Will work on algorithm very soon.

May 26, 2016
Read the blog:
http://www.jiuzhang.com/solutions/word-ladder-ii/

Great blog:
http://blog.csdn.net/kenden23/article/details/17611675

1. Spent over 1 hour to study Java Code:
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/126.word-ladder-ii.java

and then prepared the solution using C#:
the code runs ok, but need more changes:
https://gist.github.com/jianminchen/dc64ad0cf06220d293278f874ac07ad4

2. Read more blogs:
http://yucoding.blogspot.ca/2014/01/leetcode-question-word-ladder-ii.html

http://siyang2leetcode.blogspot.ca/2015/01/word-ladder-ii.html

Follow up

July 8, 2018
I need to review the code back in 2016.

Leetcode 127: word ladder (Medium)

May 24, 2016

Work on the algorithm. Will come back very soon.

Review previous practice:
https://github.com/jianminchen/Leetcode_C-/blob/master/127wordLadder.cs

blog:
http://juliachencoding.blogspot.ca/2015/06/leetcode-word-ladder.html

1. Study Java code:
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/127.word-ladder.java

and then, spend 30 minutes to write C# version.
https://gist.github.com/jianminchen/8d9aeaaa8ad98fd1bc4a78237118506c

change a string variable name anb to s, Queue q -> queue, qLen->queueLen, int length -> ladderLength
https://gist.github.com/jianminchen/8f1081b25010c572b0a674e43ffba1e5

use Tuple class to replace two queues with one queue only
https://gist.github.com/jianminchen/60211d6ef2ae9c6b3142570b45525e21

Leetcode 252: meeting room

May 24, 2016

Review the algorithm. Will come back very soon.

LeetCode 159: Longest Substring with At Most Two Distinct Characters

May 24, 2016

Work on the algorithm. The string "eoeab", the longest substring with at most two distinct characters is "eoe", and the length is 3.

1. Read the blog about solution:

http://yuanhsh.iteye.com/blog/2188917

Brute force solution:  O(n^3)

Sliding window  - better solution O(n) solution in time complexity

2. Study the code:

https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/159.longest-substring-with-at-most-two-distinct-characters.java

Write C# code:
https://gist.github.com/jianminchen/9061c12fee5e050e56a98cb3ffcc6f57

Algorithm: check if the number is power of 2

May 24, 2016

Fun part:
10 ways to check if the number is power of 2
http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/

10 solutions:
https://gist.github.com/jianminchen/410d19acf623a7e2a4a349ccd8767c1e

add comment and test case for solution 7: count ones:
https://gist.github.com/jianminchen/1035e23fd6117ba7daa38476596e2784

Plan to spend hours to go over the blog:
1. http://graphics.stanford.edu/~seander/bithacks.html
2. http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2

3. http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/


Review following algorithms:

1. LeetCode 29     Divide Two Integer
2. Leetcode 124:   Binary tree max path sum (Hard)

3. Leetcode 126:   word ladder II (Hard)

4. Leetcode 127:   word ladder (Medium)

5. LeetCode 159:   Longest Substring with At Most Two Distinct Characters

6. Leetcode 252:   meeting room
7. Leetcode 253:   meeting room 2

8. find first repeated word in a string

9. Leetcode 88: merge 2 sorted arrays

http://fisherlei.blogspot.ca/2012/12/leetcode-merge-sorted-array.html

C# practice:

https://gist.github.com/jianminchen/0acddf70788fce10b9660dc16b2e3b71

10. Given a dictionary of words and a word, return the word if it exists in dict, else return the top 5 words in the dict that are closest to the given word
11. http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/
12. http://articles.leetcode.com/double-square-problem-analysis/
13. Design a parking Lot.

Leetcode 297: Serialize and deserialize a binary tree - 2 study cases

May 23, 2016

Problem statement:

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Study solutions:

1. Study code:
Java Solution:
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/297.serialize-and-deserialize-binary-tree.java

C# code:
https://gist.github.com/jianminchen/1f88954d31d1ea7c18a2e5f17ed4ab97

Spent 60 minutes (9:30pm - 10:30pm) to set up a test case, modify code to make it readable, debug the code and then understand the design, code works.
https://gist.github.com/jianminchen/da26aa9dbe2a74ea6f641298e57fd289

Test Case:
Tree diagram:

Tree preorder traversal:
            9   5   1   4  2   3  8  7  6
Index:  0   1   2   3  4   5  6  7  8

So, node 9 is serialized:
step 1:
int[3]{9, 1, 6},
9 is the value of node value,
1 is the left child's index position in List<int[]>, value is 5.
6 is the right child's index position in List<int[]>, value is 8.

The tree is serialized as a string:
"9 1 6 5 2 3 1 -1 -1 4 4 5 2 -1 -1 3 -1 -1 8 -1 7 7 8 -1 6 -1 -1 "

2. Study code:
http://www.cnblogs.com/yrbbest/p/5047035.html

C# practice based on the above blog:  (output limit exceeded - Leetcode Online Judge)
https://gist.github.com/jianminchen/f4d6d81f300a0c7c26cc4bcdbe99b3db

Test case:
Tree: Same tree from 1 - 9

Tree serialization string:
9,5,1,#,#,4,2,#,#,3,#,#,8,#,7,6,#,#,#,

Tree preorder traversal:
            9   5   1   4  2   3  8  7  6
So, the binary tree can not be uniquely identified just by preorder traversal of binary tree - a string, only if it is a complete binary search tree or other special tree. The serialization string does not include all the information needed. The design has flaws.


Questions and Answers:

1. How is the practice?

Answer: Try to get more experience on preorder traversal iterative solution, and see how the preorder traversal helps to solve the problem. Debug the code step by step and then understand the design.

C# code:
https://gist.github.com/jianminchen/da26aa9dbe2a74ea6f641298e57fd289

based on study of code:
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/297.serialize-and-deserialize-binary-tree.java

Also, study the design of serialization of binary tree using the following ideas:
1. First, use an array to store a tree node;
           array[0] = value;
           array[1] = li,    // left child index, if null, -1
           array[2] = ri,    // right child index, if null, -1
       
 2. nodes will be added to a list of arrays; then, convert the array list to a string.

Come back later to play more with the solution!

More reading about Leetcode problems and solutions:

1. Read the blog - Amazon SDE II - Leetcode solutions

2. Review Leetcode solutions (2nd practice):
http://www.cnblogs.com/yrbbest/tag/2%E5%88%B7/

3. 3rd practice:
http://www.cnblogs.com/yrbbest/tag/3%E5%88%B7/

Actionable items:

1. Need to warm up the algorithm, code writing; it is hard to write bug-free code under stress.

Fun part:
10 ways to check if the number is power of 2
http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/

Leetcode 236: Binary Tree Lowest Common Ancestor - warm up practice (IV)

May 23, 2016

 First thing in Canadian Victoria long weekend morning, 9:00am, warm up an algorithm. Write the code using inorder preorder traversal, using recursive function, find binary tree lowest common ancestor.

 Latest practice on this problem (Less than 24 hours ago):
http://juliachencoding.blogspot.ca/2016/05/leetcode-236-lowest-common-ancestor_22.html

C# practice on May 23, 2016
https://gist.github.com/jianminchen/c9941b8daf6afe51d049ecb5f5a17e19

Questions and answers:

1. How is your warm up practice?

Answer: Julia likes to train herself, discipline herself to write bug free code, ready to production code if she knows the idea to solve the problem, and also has strong analysis of problem solving already through multiple practice, over 5+ hour practice.

May 22, 2016 practice is based on geeksforgeeks.com blog, and then, May 23, 2016 practice is based on her own analysis and reasoning, the code has more than 2 differences. Good ones.

First one, on line 43, return early if p==null or q==null.
line 43: if (root == null || p == null || q == null)

Second one: line 56
line 56: if (findPath(root.left, search, path) || findPath(root.right, search, path))
                return true;

old version:
line 67: if ( (root.left  != null && findPath(root.left, path, searchNode)) ||
                 (root.right != null && findPath(root.right, path, searchNode)) )
                return true;

old version line 67, the condition checking is a giant expression, root.left != null is not neccessary, let it fall through to allow findPath to do the checking, code is much more clean.

2. You already practiced preorder and post order traversal to solve binary tree least common ancestor problem. How about inorder traversal?

Answer: Inorder traversal does not work out this algorithm. Since we are looking for paths from root to search nodes, in the inorder traversal the root node's position is unknown. It is neither the first one as preorder traversal does, nor the last one as post order traversal does. It is somewhere in the middle.

Leetcode 236: Lowest Common Ancestor - practice (III)

May 22, 2016

  Leetcode 236: Lowest common ancestor 

  Based on the blog:

    http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

Julia practices using C#:

user recursive function, use preorder traversal to do search: 

https://gist.github.com/jianminchen/3a9931ecb7818498cbbb47152ed66d89

Reference:

1. Use post order traversal to find the lowest common ancestor in binary tree:
http://juliachencoding.blogspot.ca/2016/05/leetcode-236-lowest-common-ancestor_21.html

Binary Tree Post Order Traversal Iterative solution

May 22, 2016

 Warm up the post order traversal after 10 hours intensive study of binary tree lowest common ancestor.

 First version, there is a bug in the code: out of memory on line 59

https://gist.github.com/jianminchen/4092880aef47a501ce2c3097531744fa

Need to reset the runner node as stack.Pop().

 Correct version:

https://gist.github.com/jianminchen/9eaa168499642430baa463fef6471c76

Review solutions:

1. User two stacks:
https://github.com/jianminchen/leetcode-tree/blob/master/TreePostOrderIterative.cs

2. Review previous blog:
http://juliachencoding.blogspot.ca/2015/06/leetcode-post-order-binary-tree.html

3. Previous blog: Leetcode 106: binary tree serialization - Leetcode
http://juliachencoding.blogspot.ca/search/label/post%20order%20traversal

4. Review blog:
http://juliachencoding.blogspot.ca/2016/01/divide-and-conquer-preorder-traversal.html

5. The solution can be optmized - redundant code.
https://github.com/jianminchen/leetcode-tree/blob/master/TreePostOrderIterative_PrevVarirable.cs

Questions and answers:
1. How is the practice?

Julia made a bug in first time writing, she did not notice that she needs to maintain runner when nodes in a row are popped out, so only one node with value 3 (test case: a tree with post order traversal 1 - 9) will be popped out, node with value 4 cannot be popped out.

First, wrong answer.
Second, the code runs on the test case - tree 1-9 will stop on node with value 4, and then, keep adding node with value 4 forever.

line 57:  while(stack.Count > 0 && (stack.Peek().right == null || stack.Peek().right == runner))
                {
                    TreeNode node = (TreeNode)stack.Pop(); // bug - out of memory - should be runner = (TreeNode)stack.Pop()
                    postTraversal.Add(node.val);
                }

line 63:    if(stack.Count == 0)
                    break;
                else
                    runner = stack.Peek().right;

Julia was not sure if runner should be reset. She does not have strong clues at that time.

Lessons: Need to stop, and take 3-5 minutes to do some reasoning and analysis. Do not rush to finish coding even if you have ideas to implement.

Actually, while loop - line 57 is maintained by runner variable, previous's node is using runner variable.

2. Tips about practice?
Do not rush to compile/ running the code, ask yourself, if you can make the code no compiler error, no run time error, with correct answer, without compiling and running the code, you start to use reasoning and analysis to poke every place possible going wrong.

one of practice goals: reasoning and analysis.

Radix Sort - a distribution sort

May 22, 2016

Read the blog, have some code using C# in short future:

http://www.geeksforgeeks.org/radix-sort/

C# practice based on the above blog:
comment: Line 47, change array name from int[] count -> int[] position, but still get confused; This variable does more than one task. 

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

Make some changes:
Change the array's name to helper, helper serves three functions (line 47): 

1. First, get count for each digit

2. Second, add sum from 0 to up 

3. Third, decrease one by one to track index of next available position for i. 

comment: Line 47, change array name to helper, and add comment to list tasks for helper. Feel more control, there is a term called "express the intent." 

https://gist.github.com/jianminchen/09f12e539fce1b267e75d808e13c4ff6

Prepare for Leetcode 164: Maximum Gap 

http://juliachencoding.blogspot.ca/2015/06/leetcode-maximum-gap-no-164.html

Statistics:
Time Spent:
4 hours +

Leetcode 331: Verify Preorder serialization of a Binary Tree

May 22, 2016

Review the blog, and write some code using C# related to serialization of tree:

http://juliachencoding.blogspot.ca/2016/02/leetcode-331-verify-preorder.html

Read the blog: (10 - 15 minutes)
https://www.hrwhisper.me/leetcode-verify-preorder-serialization-of-a-binary-tree/

C# code practice:
https://gist.github.com/jianminchen/a24a6f88b7d66721695032ac9cb8373a


Also, check out this one:
https://www.hackerrank.com/challenges/uds-echo-server

Review blogs:
http://blog.hackerrank.com/step-0-before-you-do-anything/

Leetcode 37: Sudoku solver - a warm up practice

May 21, 2016

Introduction

It is time to warm up Leetcode 37: Sudoku solver algorithm. The problem statement is here. I reviewed the blog written in July, 2015 first, the blog link is here.

I also like to review one blog written by fightforyourdream, the link is here.

Analysis about Sudoku solver in Chinese

I like to translate the analysis from Chinese to English. The analysis from the above Chinese blog:

典型 DFS/递归/回溯/深搜题。对于 DFS，说白了

1. 什么时候返回？

在本题中，

    1. 当 x > 8 或 y > 8 表示已经遍历完所有的格子，因此成功完成，返回 true。

    2. 当下一个搜索（子搜索）返回true，说明已经找到，返回 true。  

    3. 如果测试过本轮的所有可能解，但无一是对的，说明无解，返回false。  

    4. 如果当前空格不是空格，则改变x，y坐标后，继续下一个空格的尝试

2）DFS 就是针对本轮的所有可能解进行逐一尝试，找到本轮的一个可能解后，这时要调用递归，基于本轮的解对下一轮（子问题）进行求解。如果下一轮（子问题）求解成功，则说明大功告成，及时返回true，停止之后的尝试。

否则如果下一轮（子问题）求解失败，则说明本轮的解不适合子问题，因此，必须换一个本轮的解，然后基于本轮的新解，继续尝试子问题。如果已经本轮所有的解都尝试过了，也都失败了，说明本问题无解，返回false。

当然在每次尝试子问题前和如果失败返回后，都要恢复原来的环境（撤销动作）。

所以，要想使 DFS 成功返回, 条件就是找到满足本轮的解和这个解也要满足下一轮（子问题）。

Analysis in English 

Plan to write down English translation on Nov. 3, 2017.

Warm up practice

May 21, 2016

Try to finish in 30 minutes, here is Julia's C# practice, based on past practice - C# code. 

Leetcode 236: Lowest Common Ancestor - Warm up practice

May 21, 2016

  Julia took more than 10 hours to play with the tree traversal algorithm. Then, she likes to write down the algorithm bug free within 20 - 30 minutes. It is a warm up practice. Just enjoy the adventure and see how many issues are not resolved.

 Here is the second blog she worked on more than 10 hours on May 22, 2016:
http://juliachencoding.blogspot.ca/2016/05/leetcode-236-lowest-common-ancestor.html

Previous blogs: (April 22, 2016)
http://juliachencoding.blogspot.ca/2016/04/find-lowest-common-ancestor-of-two.html

http://juliachencoding.blogspot.ca/2015/07/leetcode-lowest-common-ancestor-in.html

Review solutions again:
https://github.com/jianminchen/LowestCommonAncestorInBinaryTree/blob/master/LowestCommonAncestorB.cs

Now, start her warm up practice:
 May 21, 2016 9:18pm - 9:48pm - 30 minutes taken

https://gist.github.com/jianminchen/5aa398b8c6e9f13c5a11213ef03cb5bc

Julia found out a few things:

1. First, a  new variable is added: stopTraversal on line 49.
   When both two nodes p and q are found, stop to traversal the binary tree.

   Julia also learned how to break two while loop:
C# does not allow  two "break; ", complaining that the second "break; " unreachable.

   4 lines are added:
   line 49, line 69, line 76, line 77.

   set StopTraversal = true, and then,  break the inside while loop, next to the while loop, check
   if(StopTraversal == true) then, break outside loop.

   The code Julia studied and practiced before just break inside while loop only. So, here is the change.
   line 74 in the following version needs some extra work:
   https://gist.github.com/jianminchen/388114d99020972413464a072e5e9a9b

2. Julia forget to declare the stack at the beginning, and also, declare two lists for p and q.

Question and answer:

1. Why do the warm up practice right away? 

Answer:
Julia knows the importance to learn an algorithm a time. Keep working on the code, until it works perfectly, until she makes all mistakes and learns lessons. Afterwards, she may start to learn to analyze the algorithm, even memorize the algorithm easily.

The code is executable, optimized, every line is executed and she pays some attention on them how to optimize.

Practice makes perfect. Show progress, that is mental toughness, that is value of sharing - document progression to excellence.

2. Write C# version based on the blog:
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

Leetcode 236: Lowest common ancestor

May 18, 2016

  Lowest common ancestor:

  http://juliachencoding.blogspot.ca/2016/04/leetcode-236-lowest-common-ancestor-in.html

  Julia's C# practice on May 21, 2016
1. User Stack class ToArray API, keep stack iterator order
code has a bug - index out of range - line 93
https://gist.github.com/jianminchen/2bec8a70ef520e715240a226c01c7371

https://msdn.microsoft.com/en-us/library/415129w1(v=vs.110).aspx

2. Second warm up, just use List.AddRange(Stack), still keep stack iterator order
code has a bug - index out of range - line 93
https://gist.github.com/jianminchen/754f45023f60992211cb34bef6d6254f

3. Third warm up, use the test case in the diagram 1, 2, 3, 4, 5, 6, 7, 8, 9, and then, find out the bug! Big surprise! Every line of code should be optimized, and then examined.

Fix the bug - index out of range - line 93
https://gist.github.com/jianminchen/99585d73e4196136fd87274174dec3b9

4. Fourth warmp up practice, change code while loop code, make it explicitly - loop variable
https://gist.github.com/jianminchen/388114d99020972413464a072e5e9a9b


Make the code more readable about line 93.


 Review blog about post order traversal,

http://juliachencoding.blogspot.ca/2015/09/morris-order-post-order-traversal.html

And then, we can easily find out that the order of output can be implemented using stack, and then, the stack - the root node is always the last one. We can find two nodes p, q through post order traversal, once any one of those two nodes is visited, the path from root to p or q can be retrieved from the stack. Use stack API, move stack content to a list.

So clever, let us recall those images used in the above blog:

The node may be visited more than once, it is better to check if it is one of two input nodes  when first time to visit. 

Also, the stack is kind of tricky, you can peek, if the node is ready to add into post order traversal output, then pop it. 

Questions and Answers:

1. Please write down what you learn through this practice, warmup? How long do you take? 

It takes over 6 hours to get back in tree traversal algorithm. 

The most important to remember that the tree's post order traversal only has 3 parts:

1. Push root node and its left child to the stack, repeat to the end of leftmost node. 

    

2. And then, peek the node has right child or not. In the above diagram, N1 has no right child. 

    if there is one, denoted as N3, then, treat the node N3 as step 1  - push node and its left's child to the end of leftmost node. 

    else, it is ready to pop the node, and add it to traversal result. 

2.  Save a variable as a previous visited node, check the current node relationship to previous node, 

    in the above diagram, 3 -> 4 ->5, upward traversal through the stack, how do we know? 

    previous node = current node's right child, in other words, right child is just visited, it is root node's turn to pop out. 

2. Please write down steps of post order traversal in the above diagram: 

In the above diagram, 

step 1:  9 -> stack

        2:  5 -> stack

        3.  1->stack

        4. check stack is empty or not, 

        5.  not empty, peek the stack, the node N, see if previous is N's right child or not

            not true

        6. Pop node with value 1

        7. Peek stack's top node, and see if previous visited node is current node's right child or not

            it is not

        8. Check its right child existing or not

        9. It is existing, then, add current node to stack, repeat while loop...

 Julia could not explain it very clearly, she spent over 2 hours to get lost in the code, played with simple test cases: 

Null tree, tree with one node, tree with two nodes, tree with only left child, tree with only right child. 

She just noticed that it is easy to get complicated while loop, much more complicated code, and then, spin inside and waste time. 

It is better to delete everything and then start it from beginning. 

3. Go through the code and explain what you learn through the practice:

Answer: 

To make solution simple as possible, three things need to be taken care of:

1. First, downward, push nodes to stack, like 9->5->1, leftmost nodes to the stack, continuously push them to the stack. 

2. Second, need to know when to pop out to add traversal list

1 to the list, 

then, 5 is the top of stack, smart enough to know that it is turn to visit right child. 

3. Third, need to take care of upward pop up, like 7->8->9

When you design the process, leave "set stack's top node's right child to runner" as last. 

Then, take care of upward pop up process, it is a while loop, not a if checking - one time deal. 

         Like the above diagram, let 7 ->8->9 three continuously pop out. 

         And then, check the stack is empty or not, if it is empty, break the while loop. 

For example, the last one, root node 9 is popped out, then, break the outside while loop, terminate the loop, otherwise, it is a dead loop. 

         Last, stack is not empty, we need to set stack's top node's right node as runner node, let iteration repeats. 

Julia learned that in order to produce working code with no bug, take a lot of practice. 

line 68: while (stack.Count > 0 && (stack.Peek().right == null || stack.Peek().right == runner))

                {

                    runner = stack.Pop();

                }

                if (stack.Count == 0)

                {

                    break;

                }

                else

                {

                    runner = stack.Peek().right;

                }

4. What are most difficult to learn through your practice? 

Answer:

When the node is added to post order traversal list, in the above diagram, 

Node with value 1 (denoted as short hand N1) is added to post order traversal output list, then, stop output, add more nodes (N4, N2) into stack;

N2 is added to post order traversal, and then, stop output, add N3 in the stack; 

N3 is added to post order traversal output list, then N4, then N5, 3 in a row to add output traversal list. 

N1, N2, N3 can generalized to upward output process, N1, N2 are special case, only 1 in row, N3 starts a 3 in a row. 

Every node is added to stack, N9, N5, N1, 3 in a row to add into the stack; then, N4, N3, two in a row, so adding nodes to the stack is always in a process - downward, left most nodes in a row process. 

So, the design of function now becomes the following 4 steps:

1. Set up a while loop, work on runner node, use extra variable called previous visited node, prev

2. Take care downward push into stack in a row process. 

3. Take care upward pop out from stack in a row process. 

4. If the stack is empty, terminate the while loop. 

5. If the stack is not empty, set runner as stack's top node's right child, let while loop takes care next iteration. 

One more note, the upward pop out from stack in a row process, 3 conditions to check, first, the stack is not empty, and then, stack top node's right child is null (For node N1), or stack top node's right child is previous node. 

Based on the above analysis - 3 conditions, let us write down in one line of code:

while(stack.Count > 0 && (stack.Peek().right == null || stack.Peek().right == prev)  <- first try, it is wrong! 

second writing: 

while(stack.Count > 0 && (stack.Peek().right == null || stack.Peek().right == runner) 

The study code Julia chose is so good, even previous node variable is not needed to be declared! 

https://github.com/douglasleer/LeetCode-Java-Solutions/blob/master/236.lowest-common-ancestor-of-a-binary-tree.java

Julia spent 2 days to work on this algorithm, felt very down struggling with complicated while loop code, gave up after 3+ hours. Come back again with more warm ups, with a bug - out-of-index, and then, continuously test the code, write down ideas. 

5. What are fun part? 
Julia learns to teach herself algorithm very struggling on this algorithm, take more than 8 hours, she likes to focus on code; always work on code, play with code, get hands dirty, frustrated, add more test cases. She finds out playing part is fun like sports playing.