Data Structures

My favorite algorithms books is Algorithm Design Manual by Steven Skiena.

See also: Interviewing.

Links

• Main Page - Algorithms for Competitive Programming
• Open Data Structures
• Algorithmic Thinking, 2nd Edition | No Starch Press

Array

• Sorting: quicksort, mergesort
• Priority queue
• Binary search

Graph

• Representing graphs
• DFS and BFS
• Spanning trees
• DAG, topological sort, and SCC
• Shortest path algorithms: Dijkstra, Bellman-Ford, Floyd-Warshall

Set

• Disjoint set (Union-Find)

String

• Hash functions
• KMP
• Rabin-Karp (rolling hash)
• Trie (Prefix tree)

Tree

• Traversal modes
• Self-balancing search trees
• Which traversal would yield sorted elements in a BST?

Hash table

• Collision resolution: chaining vs open addressing

Dynamic programming

• Knapsack
• Longest common subsequence

Fancy

• Bloom filter – used to implement Safe Browsing feature in Google Chrome