Monday, August 31, 2015

Leetcode: Recover binary search tree

August 31, 2015

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

read blogs:

C# implementations:

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

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

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

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

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

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

atoi 5 versions of implementation

2. Scramble string:

3. strstr

Boyer-Moore algorithm

Read the string function website and get ideas:

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:

read the article quickly in 20 minutes on August 23, 2015

Dec. 12, 2015 video watch:
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,, 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:

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)

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:

  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):

The problem can be extended to  a tree, not just a binary tree. The solution is here:

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:

August 24, 2015

13. Convert sorted list to binary search tree (No. 109)
Read the following blogs:

C#, bottom up, time O(n), space O(log n) solution:

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.

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

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


More practice using C#:
August 28, 2015

Validate Binary Search Tree
Blogs to read:

favorite blog about this problem:

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)

99 Recover Binary Search Tree - August 30, 2015

read blogs:

C# implementations:

work on extracting small functions, and then, understand the algorithm better.

100 same tree

blogs to read:

julia's implementation in C#

Sept. 5, 2015

Morris order post order traversal

blogs to read:

C# implementation:

Morris order in order traversal

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#:
Sept. 13, 2015

208 Implement Trie (prefix tree)


August 25, 2015
January 5, 2015
Preorder traversal of ternary tree

  More reading about ternary tree: