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");
}
...
}
}