Code Review - Find biggest basin

Dec. 31, 2016

Find biggest basin

Julia's favorite review: 

http://codereview.stackexchange.com/a/49477/123986

Julia, write a C# practice as well.

BFS/ DFS algorithms' Review

Julia, please review BFS/ DFS algorithms practiced this year.

Search blog using keyword: BFS

1. Connected Cell in a Grid - Warm up with Five Practices

Use Queue/ Stack/ Recursive function, get familiar with all five algorithms.

2. Leetcode 317: Shortest distance from all buildings

HackerRank - Connected Cell In A Grid (II) - C# solution (II) using Queue

April 17, 2:50 - 3:25

Problem statement


First practice using C#,  solution written by Julia:

C# practice by Julia


Study the code: 1. Use Queue, instead of using recursive calls, using 2 dimension array, excellent code to study:

Study code 

So, Julia did one more practice, and just wrote second implementation using idea in the above blog. 

Write C# code again using idea - 2 dimension array, queue, and also, mark the visited node using '2'. 
C# solution 1

Second Practice

It takes 30 minutes to write and fix bug, log interesting things happening in the practice:

1. First, fix the issue to read a row to a string, and then go over one char a time to get each node for the row.

   use Console.ReadKey()  first <- fatal error

2. use wrong local variable about key

3. Count should be 5 but 11 for one test case, count same thing more than once! - > add extra checking before counting. Or, set node is visited just before adding to the queue. 

Compare to the solution #1, two dimension array uses integer 1 or 0, my copy is using char '1', '0';
And also, the solution #1, every node sets visited true before adding to queue.
And my design, do not set, which causes problem. Same node is added to the queue more than once.

It is better to add unvisited node to the queue once.

Julia, you have to make sure that no bug in the code, it does not matter what idea you use. 

Third practice:

Write in 20 minutes, no bug:

3rd practice using C#


Again, 3 practices:

No. 1 - C# code

No. 2 - C# code

No. 3 - C# code

Algorithm: Count the number of palindromes in a string

Count the number of palindromes in  a string

January 28, 2016

    Write down ideas:
    1. First of all, do not count duplicate.
    2. Brute force solution:
 any substring of O(N^2) substrings to see if it is a palindrome;
 Add the substring of palindrome to a hashset if it is not in the hashset.
  And return the length of hashset
    3. Use recursive solution - using subproblem to solve. Cannot filter out duplicate - not good
    4. Better solution - use center point of string - 2n + 1, and then, go over each one, add all palindromes substring.

  Requirement: write a C# code in 10 minutes for the solution, using brute force one.

  https://github.com/jianminchen/AlgorithmsPractice/blob/master/NumberOfDistinctPalindromes.cs

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)

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

Lowest common ancestor in Binary Search Tree (January 6, 2016 - Leetcode question: 235 easy)
https://github.com/mengli/leetcode/blob/master/LowestCommonAncestorOfaBinarySearchTree.java

https://github.com/jianminchen/Leetcode_C-/blob/master/235LowestCommonAncestorBSearchTree.cs

https://github.com/jianminchen/Leetcode_C-/blob/master/235LowestCommonAncestorBinarySearchTree.cs

2. Leetcode 102: Binary tree level order traversal

a few of implementations:

https://github.com/jianminchen/BTreeLevelOrderTraversal

January 7, 2016 review
https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal4.cs

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

https://github.com/jianminchen/leetcode-tree

4. Tree Max Path Sum

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

5. Linked List To Binary Search Tree

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

6. Zigzag order traversal of a binary Tree

http://juliachencoding.blogspot.ca/2015/06/leetcode-zigzag-order-traversal-of.html

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

http://juliachencoding.blogspot.ca/2015/07/itint5-tree-maximum-path-sum.html

9. Binary Tree Maximum Distance, diameter of binary

http://juliachencoding.blogspot.ca/2015/06/binary-tree-maximum-distance-diameter.html

10. Morris Inorder Traversal

http://juliachencoding.blogspot.ca/2015/06/morris-inorder-traversal-binary-tree.html

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

http://juliachencoding.blogspot.ca/2015/06/leetcode-convert-sorted-list-to.html

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

http://juliachencoding.blogspot.ca/2015/06/leetcode-sorted-list-to-binary-search.html

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

http://articles.leetcode.com/2010/10/binary-tree-post-order-traversal.html

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 Binary Tree Inorder Traversal 95 Unique Binary Search Trees II 96 Unique Binary Search Trees 98 Validate Binary Search Tree 99 Recover Binary Search Tree 100 Same Tree 101 Symmetric Tree 102 Binary Tree Level Order Traversal 103 Binary Tree Zigzag Level Order Traversal 104 Maximum Depth of Binary Tree https://github.com/jianminchen/Leetcode_C-/blob/master/104MaximumDepthOfBinaryTree.cs 105 Construct Binary Tree from Preorder and Inorder Traversal 106 Construct Binary Tree from Inorder and Postorder Traversal 107 Binary Tree Level Order Traversal II 108 Convert Sorted Array to Binary Search Tree 109 Convert Sorted List to Binary Search Tree 110 Balanced Binary Tree 111 Minimum Depth of Binary Tree 114 Flatten Binary Tree to Linked List 124 Binary Tree Maximum Path Sum 144 Binary Tree Preorder Traversal 145 Binary Tree Postorder Traversal 156 Binary Tree Upside Down  173 Binary Search Tree Iterator 199 Binary Tree Right Side View 208 Implement Trie (Prefix Tree) 222 Count Complete Tree Nodes 226 Invert Binary Tree 235 Lowest Common Ancestor of a Binary Search Tree 236 Lowest Common Ancestor of a Binary Tree 250 Count Univalue Subtrees
More practice using C#: August 28, 2015
104 Maximum Depth of Binary Tree https://github.com/jianminchen/Leetcode_C-/blob/master/104MaximumDepthOfBinaryTree.c
95 Unique Binary Search Trees II
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 http://www.cnblogs.com/TenosDoIt/p/3440729.html LinkedList - as queue - Java http://www.cnblogs.com/springfor/p/3879595.html julia's practice: (Sept. 8, 2015) https://github.com/jianminchen/Leetcode_C-/blob/master/101SymmetricTreeA.cs 105 Construct binary tree from preorder and inorder traversal 106 Construct binary tree from inorder and postorder traversal http://siddontang.gitbooks.io/leetcode-solution/content/tree/construct_binary_tree.html C# practice: https://github.com/jianminchen/Leetcode_C-/blob/master/106ConstructuBTreeFromInorderPostOrderTraversal.cs
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