Frequently used Java class
- TreeMap
- Red-black tree based
- Ordered for key
- LinkedHashMap
- Hashtable and linked list based
- Insertion order preserved
- HashMap
- Hashtable based map
- Allow null value and null key
- Unsynchronized
- No order of key or value
- ConcurrentHashMap
- More modern than hashtable
- Use more buckets therefore less likely to be blocked
- Hashtable
- Synchronized
- Blocking queue
Multil-threading
- Read write lock
- Fairness policy
Distributed system design
- ACP in 12 years
- Memcached
- Distributed in-memory key-value store for small chunks of arbitrary data
- Membase, later changed to CouchDB
- Caveat:
- Volatile due to eviction, full, service crashing
- Too many items may cause thrashing
- Non-transactional
- UDP vs TCP
- UDP is connection-less protocol and faster than TCP, especially when occasional loss is not a big issue such as video stream, VoIP. UDP is very good for pub-sub used in Tibco. Good for heartbeat too. Packages may arrive out of order. Package based
- TCP has very huge overhead for handshaking and is bytestream based, therefore merging them back is a big overhead. Point-to-point connection has to be maintained
- http://stackoverflow.com/questions/1099672/when-is-it-appropriate-to-use-udp-instead-of-tcp
- Scatter-gather IO
- readv, writev
- facebook uses it cut down CPU by 50%
- Tinyurl
Reference
-
http://n00tc0d3r.blogspot.com
- UIUC professor notes
- Professional code style
- http://google-styleguide.googlecode.com/svn/trunk/cppguide.html
- http://google-styleguide.googlecode.com/svn/trunk/javaguide.html
- http://google-styleguide.googlecode.com/svn/trunk/pyguide.html
DP
- Longest increasing sequence (LIS)
- There is always a DAG of computation underlying every dynamic program but it is not always clear
- http://bix.ucsd.edu/bioalgorithms/book/excerpt-ch6.pdf
- http://wordaligned.org/articles/patience-sort.html (not sure correctness)
- Given n houses and m colors. The cost of painting different house with different color might be different. Find out the min cost of painting all houses such that no adjacent houses have same color.
