九章 Data Structure

九章 Data  Structure

Linear Data Structure
1. Queue
2. Stack
3. Hash
Tree Data Structure
1. Heap
2. *Interval Tree

Min-Stack
Implement a stack, enable O(1) push, pop, top, min. Where Min() will return the value of minimum number in the stack

Implement a queue by two stacks
Q.push(x);
 S1-Push(x)
Q.pop():
  if S2.empty -> S1->S2
  S2.pop()
Q.top()
  Similar with Q.pop()

Largest rectangle in histogram

Construct MaxTree
find the first left and right bigger number of an element, and the smaller one of those two will be the parent of this element

Hash
Operations
  Insert - O(1)
  Delete - O(1)
  Find - O(1)
Hash Function
Collision
  Open Hashing (LinkedList)
  Closed Hashing (Array)
Hash Function
Typical: From String to int

int hashfunc(String key) {
  //do something to key
  //return a deterministic integer number
  return md5(key) % hash_table_size;
}

APR hashfunc - Magic Number 33
int hashfunc(String key) {
  int sum = 0;
  for (int i = 0; i < key.length(); i++) {
    sum = sum * 33 + (int)(key.charAt(i));
    sum = sum % HASH_TABLE_SIZE;
  }
  return sum;
}

Rehashing

Jave
What's differences of
HashTable-> thread safe
HashSet
HashMap
Which one is thread safe?

C++里面set是用红黑树实现的

LRU
Queue -> doesn't work
 1. Lookup
 2. delete
 3. insert
DoubleLinkedList + HashMap

Jave
LinkedHashMap = DoublyLinkedList + HashMap

Longest Consecutive Sequence

Heap
Operations
  Add O(log N)
  Remove O(logN)
  Min/Max O(1)
Heap - Implementation
Low Level data structure: Dynamic Array
  Heap {
    elems[], size;
 }
 elems[1] - root, also the minimum ele in elems
 i's left child: i * 2, right child: i * 2 + 1
Internal Method: siftup, siftdown
Add:
  push back to elems: size++; siftup
Remove:
 Replace the elem to be removed with the last elem; size --; sift up and sift down

Get median number

Building Outline -> scab line + heap to get max height

Trie -》 做stream of data的时候比较有用