Hash Table

### Collision resolution:

#### 1. Chaining wtih LinkedList

- $O(N)$ worst case
- most common approach

#### 2. Chaining with BST

- $O(logN)$ worst case
- take more space than linked list
- hence, rarely used unless we had extremely nonuniform distribution

#### 3. Open Addressing with Linear Probing

- idea: move to next cloest closed open spot
- no bucket chaining, total entries limited by array size
- issue of clustering because of linear probing
- worst case query time
`get()`

is $O(N)$

#### 4. Quadratic Probing and Double Hashing

- instead of probing linear as in approach 3, we prob quadratically
- or use second hash function to random determine prob distance (reduce chance of clustering)

### Code

1 | package ood; |

ref: https://discuss.leetcode.com/topic/102606/design-a-hashmap

Trie

### Why Trie?

- hashing search, insert, delete takes $O(L)$ (for
`hash()`

opeartion) in average, but need to handle collision - Trie: insert and serach string in $O(L)$, where $L$ is the length of string, no need to handle collision
- prefix search & autocomplete

https://www.geeksforgeeks.org/advantages-trie-data-structure/

### Implementation1: Array

- fixed sized array, limited to lower case letters
- use
`c - 'a'`

to index array for character`c`

- waste of unused space

1 | class TrieNode { // nested class |

example:

1 | private class Trie { |

ref: https://leetcode.com/problems/most-common-word/

### Implementation2: HashMap

- slower query/search than array (time for hash(), etc)
- saves spaces, only store the children nodes we need
- more flexible in functionality (suppoert upper-cases letter, or TrieNode could store words in hiericy, Quantcast OA JSON storage & query)

1 | class TrieNode { // nested class |

### Trie w/ implementation2

1 | class Trie { |

ref: https://leetcode.com/explore/learn/card/trie/

Binary Search Tree (BST)

ref: http://pages.cs.wisc.edu/~paton/readings/Binary-Search-Trees/

1 | package ood; |

1 | package ood; |

Test program:

1 | package ood; |

ref:

数据结构：二叉搜索树（BST）的基本操作

http://blog.csdn.net/lemon_tree12138/article/details/50366993

用java源代码学数据结构<七>: BST

http://blog.csdn.net/wanghao109/article/details/13508357

二叉查找树 (C#)

http://www.cnblogs.com/gaochundong/p/binary_search_tree.html

你曾实现过二叉树吗 (C#)

http://www.cnblogs.com/gaochundong/archive/2013/04/24/csharp_binary_tree.html

Stack

### Using Array

- works, however, array has fixed size, space used
**NOT**proportional to number of items in list. - require expansion $O(n)$ extra time complexity for each expandsion, but $O(1)$ amortized/average time
- OR better always $O(1)$ for
`push()`

w/ a shadow array.

### Using LinkedList (Preferred)

- insert to
**head**, remove from**head**(difference to Queue) - dynamically size, space used
**proportional**to number of items in list, no expansion required. - extra space to store
`next`

pointer for each of the value (Array no such extra pointer)

### LinkedList implementation

ref: http://pages.cs.wisc.edu/~paton/readings/Stacks-and-Queues/

1 | // ListNode class |

1 | // Stack class |

Test Program:

1 | public class StackOODTest { |

Queue

- trade of between Array and LinkedList is similar to Stack
- i used LinkedList for implementation
- insert to
**tail**, remove from**head**(difference to Stack)

1 | package ood; |

Test Program:

1 | package ood; |

Heap

### Heap Property

- Heap is a tree-based datastructure with
**two**special properties:- ORDER property
- SHAPE property

- A common implementation of a heap is the binary heap, in which the tree is a binary tree (
**complete**binary tree) - Hence we could use array as representation of a heap
- All examples given in this section are
**max-heap**, min-heap is similiar

**The ORDER property:**

For every node n, the value in n is **greater than or equal to** the values in its children (and thus is also greater than or equal to all of the values in its subtrees).

**The SHAPE property:**

- All leaves are either at depth d or d-1 (for some value d).
- All of the leaves at depth d-1 are to the right of the leaves at depth d.
- There is at most 1 node with just 1 child, that child is the left child of its parent, and it is the rightmost leaf at depth.

**The SHAPE property Examples:**

Image from uwmadion cs367 webpage

**The ORDER property Examples:**

Image from uwmadion cs367 webpage

### Implementing priority queues using heaps

- Array or ArrayList
- Starts at
**position 1**(instead of 0) - The root of the heap is always in
`array[1]`

. - In general, if a node is in
`array[k]`

, then its**left child**is in`array[k*2]`

, and its**right child**is in`array[k*2 + 1]`

. - If a node is in
`array[k]`

, then its parent is in`array[k/2]`

(using integer division, so that if k is odd, then the result is truncated; e.g.,`3/2 = 1`

).

Image from uwmadion cs367 webpage

### Insert() operation

- insert to the end of the array (the right most leave to tree)
- swap with its parent if it is larger than its parent value
- recursively perform step two until hit root OR step 2 fails

### removeMax() operation

- swap root with last element in array, and pop the last element
- swap new root with its larger childern
- recursively perform step two util its fails

source: http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

Graph

**Graph** consisits of:

- finite set of vertices called
**nodes** - finite set of vertice pair $(u, v)$ called
**edges** - two types of graph:
**directed graph**and**undirected graph** - two types of graph representation:
**adjacency matrix**and**adjacency list** - undirected graph has
**symmetric**adjacency matrix

[TODO] X-code PPT

https://goo.gl/pd5XDK

https://goo.gl/hciJzA

updated: 05/30/2018

## 133. Clone Graph

`clones`

map serves as both a visited list, as well as a dict for clones- https://leetcode.com/problems/clone-graph/description/

### BFS

1 | public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { |

### DFS (bottom up)

1 | public UndirectedGraphNode cloneGraph2(UndirectedGraphNode node) { |

Logs

- 03/15/2018 - add Trie
- 03/15/2018 - add Hash table
- 03/16/2018 - add BST
- 03/16/2018 - add Stack & Queue
- 05/07/2018 - add heap
- 05/30/2018 - add Graph
- 05/04/2019 - add example for trie array[26] implementation
- 05/11/2019 - refactor StackOOD code
- 05/11/2019 - add DFS and BFS for clone graph