Patterns, Interviews and the Capstone

1Fifteen patterns

Most problems you will meet are one of these wearing a costume. Recognition is the skill; the code is the easy part.

2A procedure for an unseen problem

Seven steps, in order. The order matters more than any individual step.

1. Clarify. What are the input ranges? Can values be negative, empty, duplicated? What should happen on invalid input? Two minutes here saves twenty later, and in an interview it is half of what is being assessed.
2. Work a small example by hand. Not to test a solution — to find one. The steps you take manually are usually the algorithm, and the moment you feel yourself doing something repetitive is the moment you have spotted the subproblem.
3. State the brute force. Out loud, with its complexity. It proves you understand the problem and it gives you something correct to compare against. Never skip it because it is “obvious”.
4. Name the bottleneck. Where exactly is the brute force wasting effort? Repeated work (→ memoise), repeated scans (→ hash map or precomputation), repeated sorting (→ heap), rediscovering an order (→ sort once).
5. Match a pattern. The table in §1. The bottleneck usually names it for you.
6. Code it. Only now. Say what you are about to write before you write it.
7. Test deliberately. Empty input, one element, all-equal elements, the maximum size, negatives, and the specific edge your algorithm is fragile at — you know where it is.

If n ≤ 20, stop looking for a clever polynomial algorithm — the problem is telling you it wants an exponential one. If n = 10⁶ and you are contemplating a nested loop, you already know it is wrong.

3Picking the structure

The whole course, compressed into one table: what you need to do, and what does it fastest.

4The capstone

One system that needs a graph, a heap, a hash map, an LRU cache, a trie, a set, a queue and a sort. Nothing here is new; assembling it is the exercise.

Build a route planner. A small city map, a query interface, and enough load that naive choices show up. The specification:

class RoutePlanner:
    """The shape of the capstone. Each method is a chapter of this course."""

    def __init__(self):
        self.graph = {}          # adjacency list          -> Ch. 19
        self.trie = Trie()       # place-name autocomplete  -> Ch. 18
        self.cache = LRUCache(128)   # recent route queries -> Ch. 29
        self.version = 0         # bumped on every edit, so the cache can be keyed on it

    def add_road(self, a, b, minutes):
        """Adding a road must invalidate cached routes."""

    def cheapest(self, a, b):
        """Dijkstra, with the LRU cache in front of it."""

    def fewest_turns(self, a, b):
        """BFS — a different question, a different algorithm, the same graph."""

    def suggest(self, prefix, k):
        """The k best-known places starting with prefix."""

    def gritting_plan(self):
        """A minimum spanning tree over the whole network."""

    def busiest(self, k):
        """The k junctions appearing in the most cached routes."""

The exercises below build the pieces — autocomplete, top-K, a running median, a rate limiter — and then assemble a working planner. Take them in order; the last one uses the earlier ones.

5Where to go next

What you have, what you do not, and a sensible order to fill the gaps.

You now have the structures and algorithms that account for the overwhelming majority of practical work: arrays and their costs, linked structures, hashing, trees and balance, heaps, tries, graphs and their four main traversals, sorting and searching, and the three design paradigms with the judgement to choose between them.

What is missing, roughly in the order it becomes worth learning:

• Amortised analysis properly — the potential method, which explains why splay trees and Fibonacci heaps work at all.
• Randomised algorithms — skip lists, treaps, randomised quickselect, Karger's min cut. Often simpler than the deterministic version and just as good in practice.
• Network flow — max flow, min cut, bipartite matching. A surprisingly large family of problems reduces to it, and recognising that is a genuine superpower.
• Computational geometry — convex hulls, sweep lines, closest pair.
• String structures — suffix arrays, suffix automata, Aho–Corasick.
• NP-completeness — recognising that a problem is probably intractable, so you stop looking for an exact fast algorithm and start looking for a good enough one.
• Approximation and heuristics — what to do once you know it is NP-hard.
• Concurrent and external-memory structures — lock-free queues, B-trees, LSM trees. This is where database engineering lives.

>_Playground

A pattern-matcher you can feed a problem statement to, a complexity budget calculator, and a working route planner assembled from the whole course.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.