Algorithms from zero
Arrays and strings: build a log query engine
Knowing a pattern is not the same as reaching for it under pressure. Build a small query engine over a numeric log, implement each unit pattern by hand, and let the benchmarks prove that the pattern you chose actually beats the brute-force version — with the complexity you predicted.
Turn the unit’s patterns into one working module: contiguity-aware operations, two pointers, sliding window, prefix sums, and in-place rearrangement — each implemented from scratch, tested against a brute-force baseline, and benchmarked to confirm its Big-O behaviour empirically.
Build a small query engine over a fixed-length numeric log (e.g. per-minute request counts) that answers four kinds of question, each using the right Unit 02 pattern, and prove with tests and timing that each beats its brute-force baseline at the predicted complexity.
- A before/after timing table: brute-force vs. pattern for each of the four query types, measured on the same n (and at least two values of n) — wall-clock numbers, not estimates.
- Doubling n roughly doubles the pattern's time (O(n) ops) and roughly quadruples the brute-force time (O(n²) ops), confirming the predicted complexity empirically.
- Every pattern's result is asserted equal to its brute-force baseline across the random seeds and all listed edge cases — tests pass.
- A one-paragraph write-up per operation: which pattern, its time and space complexity, and the precondition it depends on (sorted input for two-sum; static array for prefix sums; positive integers for the shrinking window; destructive write for in-place).
- Add a string view: treat a log line as a string, validate a palindromic id with opposite-ends two pointers, and build a large export with array-push + join — then benchmark it against naive += to reproduce the O(n²) concatenation trap.
- Add longest substring without repeating characters (variable-size window over a char set) and confirm O(n) with a hash-set membership check.
- Add a 2D prefix sum over a fixed grid of samples and answer rectangle-sum queries in O(1), extending the 1D idea.
- Add an update path: when one sample changes, measure the O(n) prefix rebuild cost and discuss when a Fenwick/segment tree would be the right next structure instead of a plain prefix array.
This is the loop you run whenever a query is slow: identify the cost model (contiguity), pick the pattern whose precondition the data satisfies, implement it against a brute-force baseline, and confirm the complexity with timing — not by assertion. Prefix sums for repeated static range queries, sliding window for contiguous-subarray properties, two pointers for sorted-pair search, in-place for memory-bound rearrangement. Building each once on a toy log makes choosing the right one in production automatic.