Free Algorithms & data structures lessons
Choose for operations, constraints, and evidence
An array buys constant-time indexing and locality but makes middle insertion expensive. A hash table buys expected constant-time key lookup but gives up natural ordering and needs a collision policy. A balanced tree keeps ordered operations logarithmic. A heap exposes only the next priority cheaply. The workload—not the name—decides.
A hash function maps keys to buckets; collisions must be resolved; the table must keep load controlled through resizing or another policy. Expected constant time assumes hashes distribute the actual keys well and adversaries cannot force pathological clustering. Equality still confirms the key.
Invariants, growth rates, and honest analysis
A loop invariant supports correctness; a decreasing measure supports termination. Time and space analysis count how work grows with input size. Worst case gives a bound, amortized analysis spreads rare expensive operations across a sequence, and expected analysis depends on a probability model.
The candidate interval contains every location where the target could still be. One comparison removes roughly half of it while preserving that invariant. After k steps at most n/2^k candidates remain, so k grows like log₂n. A boundary convention such as [low, high) keeps empty ranges and updates precise.
Search, sort, and graph traversal patterns
Sorting creates order that accelerates later operations. Breadth-first search explores an unweighted graph by distance layers and finds shortest hop counts. Depth-first search follows a path before backtracking, exposing reachability, cycles, and dependency structure. Both require a visited discipline on graphs with cycles.
If records are sorted by team and later stably sorted by score, equal-score records retain their previous team order. Stability therefore composes ordering decisions. Whether it matters depends on the product contract, not merely algorithm trivia.
Greedy choices, dynamic programming, and proof
Greedy algorithms commit to a locally best choice and need an exchange or cut argument proving no optimal solution is lost. Dynamic programming stores solutions to overlapping subproblems; its central act is defining a state that contains exactly the information the future needs. Both are proof-driven design patterns.
For edit distance, state (i,j) means the optimal cost to transform the first i source symbols into the first j target symbols. Delete, insert, and match/replace transitions point to smaller states. Once that recurrence and base cases are correct, memoization or tabulation chooses the evaluation order.