Choosing the right approach

Write the obvious, exhaustive version first. It is quick to write and almost certainly correct, and that makes it your reference: when you write the fast version, you can run both on random inputs and check they agree. Optimised code is where bugs hide, and a known-correct baseline is the cheapest testing you will ever do.

It also tells you whether optimising is needed at all. If the input is never more than fifty items, the brute-force version may simply be the right answer, and time spent making it clever is time wasted.

Merge sort is the canonical example: split in half, sort each half, merge. Quicksort is another. The shape recurs constantly once you look for it.

The Master Theorem is a formula for working out the Big-O of a divide-and-conquer algorithm from three facts: how many pieces you split into, how much smaller each piece is, and how much work the combining takes. It is worth being able to apply, and not worth memorising the proof of.

The same shape scales far beyond single programs. MapReduce, and distributed data processing generally, is divide and conquer across many machines rather than many function calls.

Giving change is the intuitive example: to make 87p, take the largest coin that fits and repeat. With normal currency this always gives the fewest coins. With a made-up currency it does not, and that is exactly the danger.

A greedy approach is correct only when the problem has two properties. The greedy choice property: taking the locally best option never rules out the overall best answer. And optimal substructure: the best answer contains the best answers to its sub-parts. If you cannot argue that both hold, do not trust a greedy solution — test it against brute force on small random inputs.

When it does work it is beautiful. Huffman coding builds the compression tables inside ZIP, JPEG and MP3 by greedily merging the two least frequent symbols. Interval scheduling — fitting the most meetings into a room — is greedy on earliest finishing time.

It is exhaustive search with pruning. You still explore possibilities, but you cut off entire branches as soon as they are provably hopeless, which can remove astronomically many combinations without ever checking them.

Solving Sudoku is the standard example: place a digit, check whether the grid is still valid, and if not, undo it immediately rather than filling the remaining eighty squares first.

The structure is always the same: choose, explore, un-choose. That last step — undoing your change before trying the next option — is where the bugs live.

Go back to the recursive Fibonacci you wrote in week 14. To compute Fibonacci of 40 it computes Fibonacci of 38 twice, Fibonacci of 37 three times, and so on — hundreds of millions of calls for an answer involving forty numbers. Add a dictionary that remembers each answer the first time and it returns instantly. That is the entire idea.

There are two ways to write it. Memoisation is top-down: keep the natural recursion and cache the results. In Python, adding @functools.cache above a function does this for you in one line, which makes it a very cheap experiment. Tabulation is bottom-up: work out the smallest cases first and build up in a table, avoiding recursion entirely.

A problem is suitable when it has overlapping subproblems — the same smaller question comes up repeatedly — and optimal substructure, meaning the best overall answer is built from best answers to the smaller questions. Spotting those two properties is the actual skill.

Work the canonical ladder in order, because each rung adds exactly one idea: Fibonacci, climbing stairs, coin change, the 0/1 knapsack, longest common subsequence, longest increasing subsequence, edit distance, matrix chain multiplication. Skipping ahead does not work here.

Allocate more time to this than to anything else in the stage. It is the hardest topic in the roadmap for most people, and the one that pays off most in real work.

Two pointers keeps track of two positions at once. On sorted data, to find a pair adding to a target, start one pointer at each end: if the sum is too big move the right one in, if too small move the left one out. One pass instead of checking every pair.

A sliding window looks at a stretch of the list and moves it along, adding the item entering and removing the item leaving, rather than re-examining the whole stretch each time. Any question about the best run of k consecutive items is this.

Prefix sums prepare a table of running totals once, after which any range total is a single subtraction. Preparing costs one pass; every query afterwards is instant.

All three are the same underlying insight: do not throw away the work you did on the previous step. That is worth internalising as a general habit, not as three separate tricks.

A useful first one: exclusive-or has the property that a number combined with itself cancels to zero. So combining every item in a list where everything appears twice except one leaves exactly that one, using no extra memory at all.

Bitmasks let a single number carry many yes/no flags at once — one bit per permission, per feature toggle, per option. Compact and fast to check.

The trick n & (n-1) clears the lowest set bit, which gives a neat way to count how many 1s a number contains. Python has int.bit_count() built in, but knowing why the trick works is the point.

This is the least broadly useful topic in the stage. Learn the common patterns and move on; do not sink days into it.