Monday, August 31, 2015

Leetcode: Recover binary search tree

August 31, 2015

   想写点什么, 因为这道题花了我好几个小时, 在周日, 除了在球场上跑了二个小时, 就泡在这道题上面.

read blogs:

http://www.lifeincode.net/programming/leetcode-recover-binary-search-tree-java/
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

C# implementations:

没有明白算法, 写了一个C#版本, 从读代码, 看有哪些不明白的地方.

https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoverBinarySearchTree.cs

简易递归版本, 但是, 找二个违例点不是很到位. 

https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoverBinarySearchTreeB.cs

总算明白, 开始写几个小函数, 看能不能记住, 容易维护, 测试案例是不是很清楚. 比较满意的代码. 看看注释, 几个月过后, 希望能几分钟内回忆起算法. 

明白了算法, 再把代码写清楚, 让错误无处可藏.
work on extracting small functions, and then, understand the algorithm better. No place for a bug. 

https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoveryBinarySearchTree_C.cs

有空周末在黑板上讲讲这道题, 练习自己的表达能力, 做一个小录像, 放在网上.  


Sunday, August 23, 2015

10 communication tips from bible

August 23, 2015

Try to improve my communication skills. Here are 10 favorite tips from bible teaching.

1. Listen without interrupting

2. Speak without Accusing

3. Give without Sparing

4. Pray without Ceasing

5. Answer without Arguing

6. Share without pretending

7. Enjoy without Complaint

8. Trust without Wavering

9. Forgive without Punishing

10. Promise without Forgetting



String functions review

August 23, 2015


1. stringDemo.cpp

Including
atoi 5 versions of implementation


2. Scramble string:



3. strstr

Boyer-Moore algorithm

Read the string function website and get ideas:

http://algs4.cs.princeton.edu/53substring/

http://zjalgorithm.blogspot.ca/2014/12/leetcode-in-java-implement-strstr.html

Need a test case to help me figure out Boyer-Moore algorithm again on August 23, 2015.
Here is a short one for me to memorize the idea:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/boyerMoore.htm

read the article quickly in 20 minutes on August 23, 2015
http://web.cs.ucdavis.edu/~gusfield/cs224f11/bnotes.pdf

Dec. 12, 2015 video watch:
https://www.youtube.com/watch?v=fHNmRkzxHWs
one of examples the presenter gave in his Cpp conference video.
Know that there is a definitely better algorithm than O(n^2), but also, need to know what the ideas are to beat the naive solution. 

Dec. 11, 2015
Need to work on a small test case, therefore, the algorithm can be easily recalled, and ideas of algorithms can be demoed clearly in the example. Go to find my favorite string, substring. (January 5, 2015, read the wiki page, https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm, read 'The bad character rule' and 'The good suffix rule' )

4. longest palindromic string

5. Look up standard string function implementation, quick review and learn:


January 5, 2016
Read the Java code on the following website:
http://algs4.cs.princeton.edu/53substring/BoyerMoore.java.html

Write a C# version, and check in github, and see if it will help to memorize the algorithm. 

Read the webpage: (well written! now Julia knows two rules: bad character rule, the good suffix rule)
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

http://www.cs.tufts.edu/comp/150GEN/classpages/BoyerMoore.html



Tree algorithms review

August 23, 2015

Here is the list of tree questions worked on:

1. Lowest common ancestor in Binary Tree (January 6, 2016 - Leetcode question: 236 medium)

2. Leetcode 102: Binary tree level order traversal
a few of implementations:

3. C# files:
TreeDemo.cpp

  Pre Order Traversal
  In Order Traversal
  Post Order Traversal

  Breadth First Traversal
  Breadth First Traversal Iterative

 Pre Order Traversal Iterative
 Post Order Traversal Iterative*
 In Order Traversal Iterative (A, B two versions)

 Count One Child Node

 Recover Binary Tree

 Invert Binary Tree
 Invert Binary Tree Iterative

 --

Tree Post Order Iterative
Tree In order Iterative


4. Tree Max Path Sum


5. Linked List To Binary Search Tree


6. Zigzag order traversal of a binary Tree


7. Maximum Binary Tree Path Sum

How to come out the idea using max value cross root? Cannot recall the idea. 
Read the blog again (8/25/2015):
http://blog.unieagle.net/2012/12/09/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Abinary-tree-maximum-path-sum/

https://github.com/jianminchen/Leetcode_C-/blob/master/124BinaryTreeMaximumPathSum.cs

The problem can be extended to  a tree, not just a binary tree. The solution is here:
http://juliachencoding.blogspot.ca/2015/07/itint5-tree-maximum-path-sum.html

8. ININT5: tree maximum path sum


9. Binary Tree Maximum Distance, diameter of binary


10. Morris Inorder Traversal


11. Convert sorted List to binary search tree (I) (Leetcode question: No. 109)


12. Convert sorted list to binary search tree (II) (over 3 hours debugging to find a bug) (Leetcode question: No. 109)



August 23, 2015

It is so good to have chance to review post order traversal iterative solution. So, Julia had chance to read more about the problem, understand another solution using space O(log(n)), use a prev variable to keep track of the previously-traversed node. 

Also, she had chance to work out using two stacks solution for post order traversal iterative solution.
Like this, First stack,       root -> left child -> right child, the order of getting into first stack, 
however, second stack, root-> right child -> left child, the order of getting into second stack. 
since left, right child both get into the first stack, then, pop out two of them in reverse order. 


* Read the following blog to help understand post order traversal iterative

C# implementation of post order traversal iterative solution, using prev variable to help:

https://github.com/jianminchen/leetcode-tree/blob/master/TreePostOrderIterative_PrevVarirable.cs

August 24, 2015

13. Convert sorted list to binary search tree (No. 109)
Read the following blogs:
http://articles.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

C#, bottom up, time O(n), space O(log n) solution:
https://github.com/jianminchen/Leetcode_C-/blob/master/109ConvertSortedListToBinarySearchTreeB.cs

C#, top down, time O(n^2), space O(long n) solution:

worked on code 2 times, first time, the calculation is kind of messy, then, worked on Leetcode question 108, get the idea to make it more simple; tips like len/2 only shows once, afterwards, use m instead. Just need to improve coding, think to make it more abstract, simple.

https://github.com/jianminchen/Leetcode_C-/blob/master/109ConvertSortedListToBinarySearchTreeC.cs

14. Convert sorted array to binary search tree (No. 108)

https://github.com/jianminchen/Leetcode_C-/blob/master/108ConvertSortedArrayToBinarySearchTree.cs

August 27, 2015
Leetcode Tree questions (29 questions):

94
95
96
98
99
100
101
102
103
104
105
106
107
108
109
110
111
114
124
144
145
156
173
199
208
222
226
235
236
250


More practice using C#:
August 28, 2015
104
95
https://github.com/jianminchen/Leetcode_C-/blob/master/95UniqueBinarySearchTreeII.cs

98
Validate Binary Search Tree
Blogs to read: 
http://blog.csdn.net/likecool21/article/details/23271621
https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning

favorite blog about this problem:
http://huntfor.iteye.com/blog/2070278

solutions included in C# practice:
 1. recursive, time O(n), using beta-alpha pruning?
 2. recursive, use long Max value / min Value instead of int's to avoid the bug
 3. use inorder traversal output to help checking BST
 4. same as 3, value TreeNode variable
 5. sames as 3,
 6. same as 3,
 7. same as 3, but use iterative solution
 8. Great analysis, brute force solution, time complexity O(n^2) vs beta-alpha pruning time O(n)

https://github.com/jianminchen/Leetcode_C-/blob/master/98ValidateBinarySearchTree.cs

99 Recover Binary Search Tree - August 30, 2015

read blogs:

http://www.lifeincode.net/programming/leetcode-recover-binary-search-tree-java/
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

C# implementations:

https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoverBinarySearchTree.cs

https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoverBinarySearchTreeB.cs

work on extracting small functions, and then, understand the algorithm better.
https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoveryBinarySearchTree_C.cs

100 same tree

blogs to read:

http://blog.csdn.net/linhuanmars/article/details/22839819

http://www.cnblogs.com/lautsie/p/3247097.html

http://www.cnblogs.com/TenosDoIt/p/3440753.html

julia's implementation in C#
https://github.com/jianminchen/Leetcode_C-/blob/master/100SameTree.cs

Sept. 5, 2015

Morris order post order traversal

blogs to read:
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html


C# implementation:
https://github.com/jianminchen/MorrisOrder/blob/master/MorrisPostOrder.cs


Morris order in order traversal

https://github.com/jianminchen/MorrisInOrderTraverse/blob/master/Program.cs



Sept. 7, 2015

101 Symmetric Tree

this one is good to follow
use queue

LinkedList - as queue - Java

105 Construct binary tree from preorder and inorder traversal

106 Construct binary tree from inorder and postorder traversal


second implementation using C#:
https://github.com/jianminchen/Leetcode_C-/blob/master/106ConstructBTreeFromInOrderPostOrderTraversal_B.cs
Sept. 13, 2015

208 Implement Trie (prefix tree)

blogs:
http://pisxw.com/algorithm/Implement-Trie-(Prefix%20Tree).html
http://www.jyuan92.com/blog/leetcode-implement-trie-prefix-tree/

August 25, 2015
January 5, 2015
Preorder traversal of ternary tree
https://github.com/jianminchen/TreeAlgorithms/blob/master/ternaryTreeTraversal.cs

  More reading about ternary tree:
https://en.wikipedia.org/wiki/Ternary_search_tree