Optimize & Solve Sep 19, 2017

BUD:
   Bottleneck,   Unnecessary work,   Duplicated work.

DIY: Do It Yourself

Simplify and Generalize

Base Case and Build

Data Structure Brainstorm

Read more ...

Best Conceivable Runtime Sep 20, 2017

BCR: Best Conceivable Runtime

BCR is the fastest an algo can be. For example, compare 2 sorted arrays, you at least scan once, BCR-> O(n) BCR can be a goal that you optimize your algo. If your algo reach the BCR, then think about optimize space complexity. If both BCR and space O(1), then the algo cannot be optimized anymore. Also you can analyze your algo with BCR, if your algo has O(n^2) while BCR O(n), then try to reduce a O(n) to O(1) in your algo.

BCR is a instructor to let you know how good your algo is.

Arrays and Strings Sep 23, 2017

Hashtable:
SO useful especially unsorted situation. Can be implemented as Array or Array+LinkedList.

ArrayList in Java
• Default size is 10
• Grow: newSize=oldSize+(oldSize>>1);
• Not synchronized.

StringBuffer:
Faster than String.

Linked Lists Sep 23, 2017

Delete node: n.next=n.next.next;

Runner Technique:
2 pointers, "fast" pointer and "slow" pointer. "fast" pointer might be ahead by a fixed amount.

Recursive Problem:
A numer of linked list problems rely on recursion. If you are having trouble solving a linked list problem,you should explore if a recursive approach will work.

LinkedList in Java
• Double-linked list
• Not Synchronized.
  List list=Collections.synchronizedList(new LinkedList());

Stacks and Queues Sep 23, 2017

Stacks are often useful in certain recursive problems or Palindrome problems.

Queues are often used in breadth-first search(BFS) or in implementing a cache.

Binary Heaps Sep 24, 2017

Feature: Each node is smaller than its children. The root is the minimum element in the tree.

Two key operations
• Insert:
Insert the element at the right bottom, then compare with its parent and move the node upper.
• Extract Minimum Element:
Remove the element in the root, move the last element to the root, bubble down this element if it is bigger than its children. If both of its children are smaller than it, swap with the smaller one.

Binary Tree Sep 24, 2017

    //In-Order traversal
    void inOrderTraversal(TreeNode node)
    {
        if(node != null)
        {
            inOrderTraversal(node.left);
            visit(node);
            inOrderTraversal(node.right);
        }
    }
    //Pre-Order traversal
    void preOrderTraversal(TreeNode node)
    {
        if(node !=null )
        {
            visit(node);
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
        }
    }
    //Post-Order traversal
    void postOrderTraversal(TreeNode node)
    {
        if(node !=null )
        {
            postOrderTraversal(node.left);
            postOrderTraversal(node.right);
            visit(node);
        }
    }

Graphs Sep 25, 2017

    //DFS
    void search(Node root)
    {
        if(root == null) return;
        visit(root);
        root.visited = true;

        for each (Node n in root.adjacent)
        {
            if(n.visited == false)
                search(n);
        }
    }
    //BFS: queue
    void search(Node root)
    {
        Queue queue = new Queue();
        root.marked = true;
        queue.enqueue(root); // Add to the end of the queue

        while(!queue.isEmpty())
        {
            Node r = queue.dequeue(); //Remove from the front of the queue
            visit(r);
            foreach(Node n in r.adjacent)
            {
                if(n.marked == false)
                {
                    n.marked = true;
                    queue.enqueue(n);
                }
            }
        }
    }
    //Bidirectional Search: Find shortest path
    //Running two simultaneous BFS, when their searches collide
    //we have found a path.

Bit Manipulation Sep 28, 2017

Negative Numbers: 1, Operate ~ then + 1 2,Inver the bits until meets 1.

Shift
• x>>1 , add 0 to the left --Arithmetic shift
• x>>>1, add sign bit to the left --Logical shift

//Common Bit Tasks: Getting and Setting
    //1,Get Bit &: shift 1 over by i bits(00010000),then AND
    boolean getBit(int num, int i)
        return ((num & (1 << i)) != 0);

    //2,Set Bit |: shift 1 over by i bits, then OR
    int setBit(int num, int i)
        return num | (1 << i);

    //3,Clear Bit &
    int clearBit(int num, int i)
    {
        int mask = ~(1 << i);
        return num & mask;
    }

    //4,Update Bit
    int updateBit(int num, int i, boolean bitIsOne)
    {
        int value = bitIsOne ? 1:0;
        int mask = ~(1 << i);
        return (num & mask) | (value << i); //Clear. then set
    }