Bit Manipulation

Bit Manipulation

常用operators:
~        unary bitwise complement operator, inverts a bit pattern
<<       signed left shift operator
>>       signed right shift operator
>>>     unsigned right shift operator, a zero into the leftmost position
&        bitwise AND
^         bitwise exclusive OR   (必须有且只有一个为真才行）
|          bitwise inclusive OR

特性：
（n&(n-1) == 0) true if n is power of 2. (or if n=1)
  n^n = 0
可以用来判断两个词有没有重复字符

常见问题：
Leetcode 136 - Single Number
Leetcode 268 - Missing Number
Leetcode 318 - Maximum Product of Word Lengths

Class and Project - Design and Refactoring

Goal: Design a class to support path finding through a maze
Questions:
1. What do I want to do with the graph?
2. What is the ration of edges to nodes? (adj list or matrix?)
3. How do I need to access to nodes/edges?
4. What properties do nodes and edges need to store?

Objects that make sense, whose data and methods go together.
Interfaces are clean; private data (or data structures) are not exposed.
Easy and fast to do the operations you want to do.
Methods are short and easy to read and understand.

DFS is not short!
Solution: refactor! - restruture code without changing functionality
Each method should have one task!

还可以创建一个MazeEdge class
以及一个Coordinate class来存coordinate。

Leetcode 217 - Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

需要能够快速查询，然后有一个数和对应出现次数的对应，所以想到用Hashtable
Solution1:

import java.util.*;
public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Hashtable nummap = new Hashtable();
        for (int n : nums) {
            if (nummap.get(n) != null) return true;
            else nummap.put(n,1);
        }
        return false;
    }
}

其实只关心每个num出现没出现，0或者1，所以用不到map，只需要知道有没有就可以，所以hashset就可以。
Solution2:

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet numset = new HashSet();
        for (int n : nums) {
            if (!numset.add(n)) return true;
        }
        return false;
    }
}

黑白棋 - Java

黑白棋规则：
棋盘共有8行8列共64格。开局时，棋盘正中央的4格先置放黑白相隔的4枚棋子（亦有求变化相邻放置）。通常黑子先行。双方轮流落子。只要落子和棋盘上任一枚己方的棋子在一条线上（横、直、斜线皆可）夹着对方棋子，就能将对方的这些棋子转变为我己方（翻面即可）。如果在任一位置落子都不能夹住对手的任一颗棋子，就要让对手下子。当双方皆不能下子时，游戏就结束，子多的一方胜。

参考：
http://blog.csdn.net/da_keng/article/details/47779141

Leetcode 242 - Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

做法1：

把两个string都sort好，然后比较之。
Time: O(nlogn)
Space: O(1)

这样的话答案78.41%

public class Solution {
    public boolean isAnagram(String s, String t) {
        char[] ss = s.toCharArray();
        Arrays.sort(ss);
        String sss = new String(ss);
        char[] tt = t.toCharArray();
        Arrays.sort(tt);
        String ttt = new String(tt);
        return sss.equals(ttt);
    }
}

做法2： 用一个数组存起来
似乎比sort还要慢一些, 46.32%, 8ms。

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        else if (s.length() == 0) return true;
        int[] numbychar = new int[256];
        int num_unique = 0;
        int num_complete = 0;
        char[] s_char = s.toCharArray();
        for (char c : s_char) {
            if (numbychar[c] == 0) num_unique++;
            ++numbychar[c];
        }
        for (int i = 0; i < t.length(); i++) {
            int c = (int) t.charAt(i);
            if (numbychar[c] == 0) return false;
            --numbychar[c];
            if (numbychar[c] == 0) {
                ++num_complete;
                if (num_complete == num_unique) {
                    return i==t.length()-1;
                }
            }
        }
        return false;
    }
}

Improve the 2nd solution: use a hashtable

import java.util.*;
public class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()) return false;
        
        Hashtable 
            theTableS = new Hashtable(),
            theTableT = new Hashtable();
        for (char i:s.toCharArray()) {
            if (theTableS.containsKey(i))
                theTableS.put(i,theTableS.get(i)+1);
            else theTableS.put(i,1);
        }
        for (char i:t.toCharArray()) {
            if (theTableT.containsKey(i)) 
                theTableT.put(i,theTableT.get(i)+1);
            else theTableT.put(i,1);
        }
        return theTableT.equals(theTableS);
    }
}

Leetcode 238 - Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
O(n), 所以只能扫一遍就得到该有的信息，自然想到的是左边扫一遍右边扫一遍。
省空间的话简单，右边扫的时候直接把答案存起来。

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        //keep track of product of left elements in the array
        // then scan from right to left to multiply the right elements
        int n = nums.length;
        int[] results = new int[n];
        results[0] = 1;
        for (int i = 1; i < n; i++) {
            results[i] = results[i-1] * nums[i-1];
        }
        int right = 1;
        for (int i = n-1; i >= 0; i--) {
            results[i] *= right;
            right *= nums[i];
        }
        return results;
    }
}

Graphs

Unstructured structures: sets
Hierarchy structures: Trees
Basic objects and relationship between them: Graphs

Basic objects: nodes, vertices   ...  websites
Relationship: edges, arcs, links  ...  hypelinks

Definition:
Basic objects: vertices.. V
Relationship: edges... E
Size: |V| + |E|
Directed or undirected
Weighted or unweighted
Path: a sequence of vertices and edges that depicts hopping along graph
In degree: number of edges coming to v
Out degree: number of outgoing edges from v

Adjacent matrix: (better for dense graph)
  Pro: quick add/delete edges etc.
  Con: Adding vertices (need to expand the matrix), and storing N^2 piece information.
Adjacency list: (better for sparse matrix)
  A map: vertices -> neighbors
  private Map<Integer, ArrayList<Integer>> adjListsMap
  Pro: easy (not quick) add/delete edges; easy (not quick) to add vertices; use less memory

Searching a graph:
1. DFS
  Need to keep track of visited node. - HashSet. Constant time add, remove, and find.
  Keep track of the next node to visit. - Use a stack. add and remove node.
  Keep track of the path from start to goal. - HashMap. Link each node to the node from which it was  discovered.
DFS algorithms (recursive)
DFS(S, G, visited, parents):
    if S==G return;
    for each of S's neighbors, n, not in visited set:
        add n to visited;
        add S as n's parent in the parent map;
        DFS(n, G, visited, parents);

DFS algorithms (stack)
DFS(S, G):
    Initialize: stack, visited HashSet and parent HashMap
    Push S to the stack and add to visited
    while stack is not empty:
        pop node curr from top of stack;
        if curr == G return parent map
        for each neighbor of curr, n, not in visited:
            add n to visited
            add curr as n's parent to parent map
            push n to the stack
    // if get here then there is no path

2. BFS
  Just change the to-visit stack to a queue.
BFS(S, G):
    Initialize: queue, visited HashSet and parent HashMap
    Enqueue S onto the queue and add to visited
    while queue is not empty:
        dequeue node curr from front of queue
        if curr == G return parent map
        for each of curr's neighbor, n, not in visited yet:
            add n to visited set
            add curr as n's parent in parent map
            enqueue n onto the queue
    // if get here there is no path
BFS find the shorter path than DFS.

Leetcode 73 - Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Naive Approach:
For word1, use insert/delete/replace to generate all strings as its children, then for each children, generate all strings etc...
But the tree will expand too fast.
Solutions:
1. DP
2. Pruning (delete the nodes that are not actual English words).

HashTable

Use HC as index to quickly query some key in the hash table.

Pro:
Quick lookup, insert and remove O(1) (on average)
Challenge:
1. Collisions: values with same hashcode
    1) Solution 1: linear probing: insert. Just put it in the next open spot.
        Has to search for subsequent space for values. May be a problem when the hash table gets full.
        Random probing is an alternative.
    2) Solution 2: separate chaining. Just keep a list at each spot.
        This solution is usually preferred. But drawbacks.
2. Resizing: resize if gets too full (70%)
    requires create a new table, new hash function, and reinsert everything.
3. Ordering data.
    Hash Table don't have order within structure.

Hash Set vs. Hash Map
1. Hash Set: java.util
    class hashset<E>
    boolean add(E e)
    boolean contains(Object o)
    Just tells you if an item is in the set. Perfect for a dictionary.

2. Hash Map: java.util
    class hashmap<K,V>
    V get(Object key)
    V put(K key, V value)
    Stores both a key and some data associated with the key.

Trie

reTRIEval

TRIE storing dictionary, will use word structure
- Not every node contains words
- Nodes can have > 2 children
- Have internal nodes that does not represent any word.

Performance vs. BST:
1. find a key:
BST: O(logn)
Trie: slightly better (since most words are not long)

Use a hashmap to store the link to the next node in trie because:
1. Use ArrayList waste a lot of space
2. Use linkedList will lose the index of some particular character.
https://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html
HashMap<Character, TrieNode> Children;
put(key, value);
get(key);

Application:
A. Autocomplete: ex. autocomplete "ea"
    1. Find the stem
    2. Do a level traversal from there (if want to generate words from shortest to longest)

Trees

Tree:
Single root;
Each node (except the root) can have only one parent;
No cycle;

Tree一般指Binary Tree.

class TreeNode{
 int value;
 TreeNode left;
 TreeNode right;
}

Binary Search Tree: for all nodes left children <= current node <= right children
Balanced: the depth of the left and right subtrees of every node differ by 1 or less

In Java, built-in Balanced BST: TreeSet.

Applications:
Expression tree such as 48 * (3 + 8)
Decision tree.
File system
If root is most important: heap tree
Organized by character frequency: huffman tree
Organized by node ordering: Search tree

Basic Operations:
A. Depth-first search (go to the path until the end 一条道走到黑)
    比如走迷宫，最好用此策略。
    1. Binary Tree Preorder Traversal
    Visit your self, then visit all your left subtree, then all your right subtree.
    2. Binary Tree Inorder Traversal
    Visit all your left subtree, visit your self, then all your subtree.
    3. Binary Tree Postorder Traversal
    Visit all your left subtree, then all your right subtree, visit yourself.
B. Breath-first search
    比如social network, find your closet path to friend D.
    4. Binary Tree Level Order Traversal
    Use a queue (linkedlist) to keep the visited node, while the queue is not empty, every time a node is visited, remove it, and add its children to the list.

C. Binary Search Tree
    1. search / find Best O(1), Worst O(n), Average O(logn), so need balancing.
    Recursion / iteration

public boolean contains(E toFind) {
  TreeNode curr = root;
  int comp;
  while (curr != null) {
   comp = toFind.compareTo(curr.getData());
   if (comp < 0)
    curr = curr.getLeft();
   else if (comp > 0)
    curr = curr.getRight();
   else
    return true;
  }
  return false;
 }

    2. insert
    Recursion / iteration

public boolean insert(E toInsert) {
  TreeNode curr = root;
  int comp = toInsert.compareTo(curr.getData());
  while (comp < 0 && curr.getLeft() != null ||
    comp > 0 && curr.getRight() != null) {
   if (comp < 0) curr = curr.getLeft();
   else curr = curr.getRight();
   comp = toInsert.compareTo(curr.getData());
  }
  if (comp < 0)
   curr.addLeftChild(toInsert);
  else if (comp > 0)
   curr.addRightChild(toInsert);
  else return false;
  return true;
 }

    3. remove
    Remove leaf or a node with only one child is easy. If remove a node with two children, then find the smallest from the right subtree and replace the value with the value.

 Preorder transersal:
1. Recursive

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List preorderTraversal(TreeNode root) {
        List nodes = new ArrayList();
        if (root == null) {
            return nodes;
        }
        nodes.add(root.val);
        nodes.addAll(preorderTraversal(root.left));
        nodes.addAll(preorderTraversal(root.right));
        return nodes;
    }
}

2. Iteration (using a stack)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List preorderTraversal(TreeNode root) {
        List nodes = new ArrayList();
        if (root == null) return nodes;
        Stack nodetovisit = new Stack();
        nodetovisit.push(root);
        while(!nodetovisit.empty()) {
            TreeNode node = nodetovisit.pop();
            nodes.add(node.val);
            if (node.right != null) nodetovisit.push(node.right);
            if (node.left != null) nodetovisit.push(node.left);
        }
        return nodes;
    }
}

Inorder traversal:
1. Recursive

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List inorderTraversal(TreeNode root) {
        List list = new ArrayList();
        if (root == null) return list;
        list.addAll(inorderTraversal(root.left));
        list.add(root.val);
        list.addAll(inorderTraversal(root.right));
        return list;
    }
}

2. Iteration

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List inorderTraversal(TreeNode root) {
        List list = new ArrayList();
        Stack stack = new Stack();
        if (root == null) return list;
        TreeNode p = root;
        while (!stack.empty() || p != null) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode t = stack.pop();
                list.add(t.val);
                p = t.right;
            }
        }
        return list;
    }
}

Postorder traversal:
1. Recursive

public class Solution {
    public List postorderTraversal(TreeNode root) {
        // trivial recursion
        List list = new ArrayList();
        if (root == null) return list;
        list.addAll(postorderTraversal(root.left));
        list.addAll(postorderTraversal(root.right));
        list.add(root.val);
        return list;
    }
}

2. Iteration

Level Order Traversal:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List> levelOrder(TreeNode root) {
        // use two queue, current and next level
        List> lists = new ArrayList>();
        List list = new ArrayList();
        if (root == null) return lists;
        Queue current = new LinkedList();
        Queue next = new LinkedList();
        current.offer(root);
        while (!current.isEmpty()) {
            TreeNode node = current.poll();
            list.add(node.val);
            if (node.left != null) next.offer(node.left);
            if (node.right != null) next.offer(node.right);
            if (current.isEmpty()) {
                lists.add(list);
                Queue temp = current;
                current = next;
                next = temp;
                list = new ArrayList();
            }
        }
        return lists;
    }
}

Problems:
Leetcode 144 - Binary Tree Preorder Transversal
Leetcode 94 - Binary Tree Inorder Traversal

Testing - Java, JUnit

To increase confidence:
- Be critical to algorithms/code
- Consider/test corner cases
- Attempt to formally reason about correctness
- Create automated test cases

Test-driven development: Write test -> Write code -> Test

Unit test: testing method
Then integration test: e.g. test your method with database connection etc.

JUnit: lightweight unit test platform
Components:
1. Code to setup tests
2. Code to perform tests
3. Code to cleanup tests

@Before
setup: is run before each test to initialize variables and objects

@BeforeClass
setupClass: is run only once before the class to initialized objects

@Test
test<feature>
Denotes a method to test <feature>
Two useful methods:
fail

try {
   emptyList.get(0);
   fail("Check out of bounds");
  }
  catch (IndexOutOfBoundsException e) {
   
  }

emptyList.get(0) should throw an exception, if it doesn't, we call the fail method.

assertEquals

assertEquals("Check first", "A", shortList.get(0));

assertEquals enforces that shortList.get(0) is "A". Otherwise, throws an error.

@After
tearDown: can be useful if your test constructed something which needs to be properly torn down (e.g. a database).

@AfterClass
tearDownClass: if your setupClass constructed something which needs to be properly torn down.

Generics and Exceptions - Java

Generics:

class ListNode {
    ListNode next;
    ListNode prev;
    E data;}

E: parameterized type

Exceptions:
throws exceptions to indicate fatal problems.

Checked exception must be declared.

public class RememberLast {
public T add(T element) throws NullPointerException { //Not required since NPE is unchecked, but OK
if (element == null) {
throw new NullPointerException("T cannot store null pointers");
}
...
}
}