Overview

  • Java basics
  • Complexity
  • Elementary sorts
  • Shuffle
  • Merge sort
  • Quick sort
  • Priority queue
  • Heap sort
  • Symbol tables
  • Binary tree
  • Binary search tree
  • Balanced search tree
  • Hash Table

Sort:

# inplace? stable? worst avr best extra space remarks
selection Y N n^2/2 n^2/2 n^2/2 1
insertion Y Y n^2/2 n^2/4 N 1 depends on order of items
shell Y N ? ? N 1
merge N Y NlogN NlogN NlogN N
quick Y N n^2/2 1.39NlogN NlogN lgN probabilistic guarantee
3-way quick Y N n^2/2 1.39NlogN N lgN probabilistic guarantee also depends on order of items
heap Y N 2NlogN 2NlogN NlogN 1

Search:

underlying data structure implementation pros cons guarantee search guarantee insert avr search hit avr insert
linked list(sequential search) SequentialSearchST best for tiny STs slow for large STs N N N/2 N
ordered array(binary search) BinarySearchST optimal search and space, order-based ops slow insert lgN N lgN N/2
binary search tree BST easy to implement, order-based ops no guarantee space for links N N 1.39lgN 1.39lgN
balanced BST RedBlackBST optimal search and insert, order-based ops space for links 2lgN 2lgN lgN lgN
hash table SeparateChainingHashST, linearProbingHashST fast search/insert for common types of data need hash for each type, no order-based ops, space for links/empty
SeparateChainingHashST array of lists <lgN <lgN N/(2M) N/M
linearProbingHashST parallel arrays clgN clgN <1.5 <2.5
Continue reading

Lessons Learned in Scaling Twitter

一周结构及缺陷

Monarail + MySQL

Defects:

- MySQL难扩展:表格关系复杂;分布式更增加join复杂型
- 小变化也要全部部署,deploy时间长
- 性能差
- 架构混乱
Continue reading

Victoria Hong

Master student at CMU
Foodie & Programmer & Fashionista
Looking for full-time position @Bay area


Software Engineer


Mountain View, CA