[Java] Common Knowledge Pocket Reference

https://docs.google.com/document/d/1bJrzcsm7YjN_uD-qx9MOaHf6BHw8wnCZptxcwkF4pjU/edit

[LeetCode] Programming Bug Note

1. Delete Element In Unordered ArrayList, Vectors

    a. Say delete 3 from 1 3 5 7 9, we replace 3 with 9 and erase 9, resulting in 1 9 5 7 9

    b. But when deleting element 9, when we replace 9 with 9, then delete 9, (Seems works ok)

        But in the Leetcode problem Insert 380 381 Delete GetRandom O(1), when the index of the removed element, 1 in example 1, and 4 in example 2 is going to be used again in the future. Index 4 is actually out of bound in the second example.

        In this case, operation sequence matters, it is infact two different types of operation sequence, while the result coincidents in some cases.

[Test] Test Cases

关于TC的问题:

1. 分类 (classification)
   unit test -> functional test -> integration test -> scenario test
越往右边TC的数目应该越少一些

2. 设计TC，还是要分类
   1) positive TC - happy path
   2) negative TC - 0, NULL, exception, overflow/underflow,
   3) corner TC

3. 其他TC(基本就是靠嘴巴说)
   1) Performance
   2) Scalability
   3) Load
   4) Stress
   5) Code coverage
   6) Localization
   7) Internationalization
   8) Security

[LeetCode] 145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

My Code is too long...

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    /* Magically, I implemented the morris traversal post order traversal version
    
    private void swap(List res, int i, int j){
        if(i == j)
            return;
        res.set( i, res.get(i) ^ res.get(j) );
        res.set( j, res.get(i) ^ res.get(j) );
        res.set( i, res.get(i) ^ res.get(j) );
    }
    
    private void reverseArrayList(List res, int i, int j){
        
        while(i < j){
            swap(res, i++, j--);
        }
        
    }
    
    
    public List postorderTraversal(TreeNode root) {
        
        TreeNode d = new TreeNode(-1);
        
        // Error: forgot to put root to d.left.....
        d.left = root;
        
        List res = new ArrayList();
        
        TreeNode c = d;
        
        while(null != c){
            
            if(null == c.left){
                c = c.right;
                continue;
            }else{
                TreeNode n = c.left;
                // Error: null != n && c != n
                // We shouldn't traverse n to c, should be before c.
                while(null != n.right && c != n.right){
                    n = n.right;
                }
                if(null == n.right){
                    n.right = c;
                    c = c.left;
                }else{
                    // c == n.right
                    // add the last element of left.right subtree
                    //res.add(n.val);
                    // add the last element of left subtree
                    // Error: There are two cases of n, n could be a left child node and right child node. 
                    //if(c.left != n)
                    //    res.add(c.left.val);
                    
                    // Error: the above ones are wrong
                    // When tree were returned from the rightmost child, it will print a series of root node. following the return of the subtrees.
                    
                    n = c.left;
                    int count = 0;
                    //Error: while( c != n.right), this time it is 
                    // In this case, last element in this list is not added in.
                    while(c != n.right){
                        //printPathReverse(root.left, pre);
                        //we need a way to print the path reversely to do that. 
                        //One way is to reverse this path like we reverse linklist. 
                        res.add(n.val);
                        n = n.right;
                        count++;
                    }
                    res.add(n.val);
                    count++;
                    if(count > 1)
                       reverseArrayList(res, res.size() - count, res.size()-1);
                    n.right = null;
                    c = c.right;
                }
                
            }
            
            // we can not put d != c in while condition, because it is initial condition
            // Error: we don't need to add this here,
            // we need this loop when c = d to add c.left child into result.
            // Since d has no right child, and d is not a children of anybody, it will never be printed out
            
            //if(c == d)
            //    return res;
            
        }
        
        return res;
        
    }
    
    */
    
    /* The second implementation is based on one stack, which stores all elements on the path from root to current node,
       all we need to judge is the current node c is the left or right child of the top element of the stack.
       if it is left child, we go right. (note, if it has no right child, we keep pop stack, i.e. the same behavior as it is right child)
       if it is right child, we keep pop stack
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList();
        
        if(null == root)
            return res;
        
        Stack st = new Stack();
        TreeNode c = root;
        
        while(true){
            
            // null == c is not going to work anymore, we don't know if null is left or right.
            if(null == c.left && null == c.right){
                
                st.push(c);
                
                while(!st.empty()){
                    c = st.pop();
                    res.add(c.val);
                    // Error: st.empty() should resides here.
                    if(st.empty())
                        return res;
                    TreeNode r = st.peek();
                    // Note: The same operation always hold for
                    // 1. c is the left child of r, and r.right is null
                    // 2. c is the right chiild of r.
                    // In both case, we track back to the path towards root.
                    // Therefore, when c is left child of r, and r.right is not null
                    // we loop into r.right
                    if(c == r.left && null != r.right){
                        c = r.right;
                        break;
                    }
                }
            }else if(null == c.left){
                st.push(c);
                c = c.right;
            }else{
                st.push(c);
                c = c.left;
            }
            
        }
        
    }
    */
    
    // The third implementation is based on a previous node recorder to keep track of the direction of traversal flow.
    // We need loop enviroment to maintain a clean program
    // Without loop enviroment, there might be many conditional statements.
    // This is the version we seperate the top of stack and c, i.e. top of stack is always one layer above c.
    public List postorderTraversal(TreeNode root) {
        
        List res = new ArrayList();
        
        if(null == root)
            return res;
        
        TreeNode c = root;
        TreeNode pre = null;
        Stack st = new Stack();
        
        while(true){
            
            //System.out.println("c.val = " + c.val);
            //System.out.println("pre.val = " + (null == pre? -1 : pre.val) );
            //System.out.println("size = " + st.size());
            
            if(null == pre || pre.left == c || pre.right == c){
                // Moving downward, in this case, we try to keep dig down
                if(null != c.left){
                    st.push(c);
                    pre = c; 
                    c = c.left;
                }else if(null != c.right){
                    st.push(c);
                    pre = c;
                    c = c.right;
                }else{
                    pre = c;
                    if(st.empty()){
                        System.out.println("empty");
                        res.add(c.val);
                        return res;
                    }else{
                        c = st.pop();
                    }
                }
                
            }else{
                // Moving upward
                res.add(pre.val);
                
                if(pre == c.right || (pre == c.left && null == c.right) ){
                    //System.out.println("Up");
                    pre = c;
                    if(st.empty()){
                        System.out.println("empty2");
                        res.add(c.val);
                        return res;
                    }else{
                        c = st.pop();
                    }
                }else{
                    // pre == c.left
                    pre = c;
                    st.push(c);
                    c = c.right;
                    
                }
                
            }
            
        }
        
    }
}

[Language] Playing with protocol buffer

1. Install Protocal Buffer
1. Please read the readmes.  Running "make install" in the root directory installs the C++ libraries only.  You need to install the Java and Python versions separately by following the instructions in the corresponding directories. 
2. https://groups.google.com/forum/#!topic/protobuf/60-OFrBXlAE
2. How to start from protocol buffer


1. Check example code from source code package. 
2. https://github.com/google/protobuf/tree/master/examples
3. Including source for java, c++, and python
3. Examples
1. CPP
• protoc_middleman: addressbook.proto
• protoc --cpp_out=. --java_out=. --python_out=. addressbook.proto
• @touch protoc_middleman
• 
  
• protoc_middleman_go: addressbook.proto
• mkdir tutorial # make directory for go package
• protoc --go_out=tutorial addressbook.proto
• @touch protoc_middleman_go
• 
  
• add_person_cpp: add_person.cc protoc_middleman
• pkg-config --cflags protobuf  # fails if protobuf is not installed
• c++ add_person.cc addressbook.pb.cc -o add_person_cpp `pkg-config --cflags --libs protobuf`
• 
  
1. pkg-config --cflags --libs protobuf 
• pkg-config - Return metainformation about installed libraries
• The  pkg-config program is used to retrieve information about installed libraries in
•        the system.  It is typically used to compile and link against one or more libraries.
•        Here is a typical usage scenario in a Makefile:
• 
  
•        program: program.c
•             cc program.c 'pkg-config --cflags --libs gnomeui'
2. `pkg-config --cflags --libs protobuf ` returns
1.  -lprotobuf -lz -lpthread on centos
2.  -pthread  -pthread -lprotobuf -lpthread on ubuntu 14.04
3. "Package protobuf was not found in the pkg-config search path." if it is not installed
3. Generated: 
1. add_person_cpp
1. Run this file, saved it to an address book following prompt
2. File looks like something like this
2. list_people_cpp
1. Run this file, returned with:
• Person ID: 1
•   Name: Charles
•   E-mail address: charles@gmail.com
•   Home phone #: 541 346 1380
4. Python
1. Error： ImportError: No module named google.protobuf
1. sudo pip install protobuf
5. Java
1. make Error:  package com.google.protobuf does not exist
2. need protobuf-java-*.jar

[Algorithm] Union Find Applications

1. Kruskal Algorithm Minimal Spanning Tree
1. Greedy Algorithm, sort all edges.
2. Initialize each node as a set.
3. Start from the smallest edge, union if they are not in the same set.
2. Check Loop of Undirected Graph
3. Check connection in undirected graph
4. Tarjan's off-line lowest common ancestors algorithm
1. Offline algorithm. All queries know in advance
2. For tree with n node and m queries. We have O(n + m) running time.
3. Request (u, v) is answered when u is visited, v is the current visiting node. or vice versa.
4. https://gist.github.com/caot/696fb3d762af0d2340c1
5. Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class TarjanOfflineLCA {

  void LCA(Node u) {
    MakeSet(u);
    Find(u).ancestor = u;
    for (Node v : u.children()) {
      LCA(v);
      Union(u, v);
      Find(u).ancestor = u;
    }
    u.colour = Node.black;
    Node v;
    for (Pair uv : P.pair()) {
      u = uv.u();
      v = uv.v();
      if (v.colour == Node.black
          && u != null && v != null
          && Find(u) == Find(v)     // required, but algorithm [3th Ed. p584] doesn't have it.
          ) {
        System.out.println("Tarjan's Lowest Common Ancestor of {" + u.data
            + ", " + v.data + "}: " + Find(v).ancestor.data);
      }
    }
  }

  

1. The basic idea is in infact DFS
2. Recursive DFS travels from all the way from bottom to up, left to right.
3. A node is marked as black if all its children are visited (marked as black)
4. Black means, in query Ancester(u, v), if u is marked as black, the ancester pointer is pointed to the right place ( right place = exacted the common ancestor of v)
5. The property of 3 is guaranteed by the nature of DFS. 
5. HDU-1213 How many tables
1. Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers. One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table. For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
6. 
   

[Java] Parsing Char String Integer Double

char / Character

        char c = '5';

                To Integer

1. Character.getNumericValue(c)
2. int i = c - '0';                

                To Double

1. double d = (double) (c - '0');

        Character c = '5';

1. Convert to char using c.charValue(); 

Double  / double

        double d = 1.0;
        Double D = 1.0;

        To Integer

1.  Integer i = D.intValue();
2.  int i = (int)d;

int / Integer

        To Char

                Integer.toString(i).charAt(0)

        Generate char according to it's index

                (char)('A' + i)
                (char)('a' + i)
                 'A' + i and 'a' + i in java are ascii integers, need (char) to convert back to char.

        To String

                Integer.toString(i);

String

        String s1 = '500';

        String s2 = "5.0".

                To Integer

1. Integer.parseInt(s1);  

                To Double

1. Double.praseDouble(s2);