Julia's coding blog - Practice makes perfect

From January 2015, she started to practice leetcode questions; she trains herself to stay focus, develops "muscle" memory when she practices those questions one by one. 2015年初, Julia开始参与做Leetcode, 开通自己第一个博客. 刷Leet code的题目, 她看了很多的代码, 每个人那学一点, 也开通Github, 发表自己的代码, 尝试写自己的一些体会. She learns from her favorite sports – tennis, 10,000 serves practice builds up good memory for a great serve. Just keep going. Hard work beats talent when talent fails to work hard.

Sunday, May 29, 2016

Leetcode 126: Word Ladder II - warm up practice (II)

May 29, 2016

Share one tweet from profession tennis play Angelique Kerber (2016 Australian Grand Slam champion):
https://twitter.com/AngeliqueKerber/status/734019444868059136

"Everyone asks me what's next. I'm here to stay, taking it one game at a time."

One algorithm at a time. Still work on Leetcode 126: word ladder II,

Here is the practice version on May 28, 2016, less than 15 hours ago.
http://juliachencoding.blogspot.ca/2016/05/leetcode-126-word-ladder-ii-warm-up.html

And then, she spent over 2 hour to make changes on the code, here is the new version:

https://gist.github.com/jianminchen/90075ee13a6ad0d9d59c8843d17e3a18

Here are the list of things she made the change:
1. line 21, class member variable is commented out. ladders.
It is replaced by an argument in the function:
line 189 getLadders_DFS_Backtracking, 8th argument - ladderHelper

2. line 27, comment out member variable ladderHelper, pass an argument in
function getLadders_DFS_Backtracking line 189, last argument: List<string> ladderHelper

3. line 60, change function name to getLadders_DFS_Backtracking, remind myself two things:
1. it is a DFS algorithm
2. Do not forget to do backtracking

4. line 102, change function name to getLadderLengthAndDictionary_BFS. BFS stands for
breadth first search.

5. line 203, line 204, add two more explanation variable, make code more readable.
isEndWord,
isBeforeEndWord

6. line 220, add explanation variable, backtracking_char, helps user to understand
the backtracking process.

7. line 221, add explanation variable replace, the char will be replaced by any one of from 'a' to 'z'.

8. line 225, 226
if(j == replace)
continue;

Make the code more flat, no nested two if statements, only one if statement.

9. line 229, ij_word, ij prefix helps to track index i and index j.
10. line 245, line 249, line 251 3 backtracking statements.

Saturday, May 28, 2016

Leetcode 126: word ladder II - warm up practice

May 28, 2016

Share professional tennis player Kristina Mladenovic tweet:
https://twitter.com/kikimladenovic/status/732966170375114752

I know what it takes to win. Forget everyone else and put the work in.

Spend one hour to work on the word ladder II, Leetcode 126.
Previous blog:
http://juliachencoding.blogspot.ca/2016/05/leetcode-127-word-ladder-medium_24.html work on one test case:
hit-> cog
Dictionary<string, int> has entries:
Let us talk about a test case to help understand the work:

hit -> cog

Two transformation paths:

dot -> dog

hit -> hot -> -> cog

lot -> log

dist value is 5

Dictionary<string, int>

key value new value

hot 1 3

dot 2 2

lot 2 2

dog 3 1

log 3 1

cog 4 0

Extract a function called resetDistanceFromEnd

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

Thursday, May 26, 2016

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:

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

Wednesday, May 25, 2016

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.

Tuesday, May 24, 2016

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.

Monday, May 23, 2016

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.

Sunday, May 22, 2016

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/

Saturday, May 21, 2016

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/