Data Structures and Algorithms
What each structure guarantees, and what it costs.
Most of the algorithms on a typical interview list come down to a few dozen ideas. A sorted array allows halving. A heap keeps the smallest item one step away. A hash table trades memory for constant-time lookup. A dynamic programming table remembers answers so that a problem never has to be solved twice. Once the invariant behind each idea is clear, the individual problems stop looking like a list to memorize.
This track goes through those ideas in order, starting with how to measure cost, then searching and sorting, then the linear structures, hashing and heaps, then trees, graphs, and the design paradigms: dynamic programming, backtracking and greedy algorithms. It ends with bit manipulation and number theory, and a map of which technique fits which kind of problem.
Every implementation is in Python and was run and checked against a brute-force answer. Timings were measured with Python 3.14 on one Mac, so the exact numbers will differ elsewhere, while the growth patterns hold. The site’s Big-O article covers the basics of complexity that chapter 1 builds on.
Chapters
- 1Complexity analysisPrecise asymptotic notation, best, worst, average and expected cases, space and recursion depth, amortized analysis on a real dynamic array, recurrences and the Master Theorem, and the places where Big-O stops describing real hardware.
- 2SearchingLinear and binary search with exact invariants, lower and upper bounds, binary search on the answer, the modified binary search patterns, ternary search, and exponential, jump, interpolation and Fibonacci search, measured on uniform and skewed data.
- 3SortingThe quadratic sorts, merge sort, quicksort with Lomuto and Hoare partitions and introsort, heap sort, the linear-time sorts, Shell and cycle sort, the cyclic sort pattern, Timsort and Powersort, selection with quickselect and median of medians, the n log n lower bound, and measured comparisons against Python's sorted().
- 4Arrays and sliding windowsHow arrays sit in memory and why contiguity matters, then the core array techniques: two pointers, sliding windows, prefix sums, difference arrays, Kadane, Dutch flag, majority vote, rotation, matrix traversal and intervals.
- 5Strings and pattern matchingHow Python stores strings, frequency maps and window techniques on text, then the pattern-matching algorithms in depth: KMP, Rabin-Karp, Boyer-Moore, Z, Manacher, suffix arrays, suffix automata and Aho-Corasick, measured against str.find.
- 6Linked listsSingly, doubly and circular linked lists, what they really cost against arrays, and the standard techniques: sentinel nodes, reversal, fast and slow pointers with Floyd's and Brent's cycle detection, merging, k-group reversal, random-pointer cloning and the LRU cache.
- 7Stacks and queuesStack, queue and deque abstractions, their array and linked implementations, Python's list and collections.deque, circular buffers, expression parsing, iterative DFS, monotonic stacks and deques, BFS and multi-source BFS, and where these structures appear in real systems.
- 8Hash maps and hash setsHow hash tables work: hash functions and hash flooding, load factor, separate chaining, linear and quadratic probing, double hashing and Robin Hood hashing with measured probe counts, tombstones and resizing, CPython's compact dict, the standard hash map problem patterns, consistent hashing and Bloom filters.
- 9Heaps and priority queuesThe binary heap as an implicit array tree, sift-up and sift-down, linear-time heapify, Python's heapq including the 3.14 max-heap functions, top-k and selection, two heaps for a running median, k-way merging, scheduling problems, Huffman coding, d-ary and indexed heaps, and the more exotic heaps.
- 10TreesBinary tree vocabulary and representations, every standard traversal including Morris, the classic tree patterns from diameter to binary lifting and tree hashing, binary search trees, and the balanced trees that keep them fast: AVL, red-black, B-trees and B+ trees.
- 11Tries and range structuresTries and their compressed relatives, segment trees with lazy propagation and persistence, Fenwick trees, square root decomposition and Mo's algorithm, interval, quad and k-d trees, and heavy-light decomposition, each implemented, checked and measured.
- 12Graph traversalGraph vocabulary and representations, DFS and BFS with their invariants, grid and implicit-graph search, multi-source BFS, cycle detection, topological sort, union-find and bipartite checks, with tested Python and measured costs.
- 13Shortest paths, spanning trees and beyondDijkstra, Bellman-Ford, Floyd-Warshall, 0-1 BFS and A*, minimum spanning trees, strongly connected components, bridges, Euler and Hamiltonian paths, the Traveling Salesman Problem and graph coloring, with tested Python and measured behavior.
- 14Dynamic programmingWhat makes a problem a dynamic programming problem, the recipe for designing a state, memoization against tabulation with measured costs, and the classic families: knapsack, subsequences, strings, grids, intervals, trees, bitmasks and digits.
- 15BacktrackingThe choose, explore, unchoose template and the state-space tree; subsets, permutations and combinations; N-Queens, Sudoku, Knight's Tour and other constraint searches; branch and bound, meet in the middle, and estimating a search tree's size before writing code, with tested Python and measured node counts.
- 16Greedy algorithmsWhen making the locally best choice is globally optimal: the greedy-choice property, exchange and staying-ahead proofs, interval scheduling, meeting rooms, knapsack, Jump Game, Gas Station, job sequencing, Huffman coding, coin systems, Container With Most Water, interval covering and matching, and a brute-force harness that finds counterexamples to greedy ideas.
- 17Bits and mathematicsTwo's complement and Python's unbounded integers, bitwise operators and the classic bit tricks, primes and sieves, GCD and modular arithmetic, fast exponentiation, combinatorics mod a prime, reservoir sampling and shuffling, and the cross-product geometry behind segment intersection and convex hulls.
- 18Patterns and how to chooseA reference map of the recurring algorithm patterns and paradigms: the signals in a problem statement that point to each, input-size limits calibrated against measured Python 3.14 speed, a table from problem signals to techniques, and the common failure modes, with tested skeletons and links to the chapters that cover each in depth.