Which Pattern?

Every advanced module so far has taught one technique, and its exercises used that technique. A real problem does not come with a module title. An interviewer says "find the longest run of days under budget", not "use a sliding window". This lesson is about the step before the code: reading a problem for the details that pick the technique.

Read the problem, not the code you last wrote

The most common mistake is to reach for the technique you used most recently. The fix is to read the problem slowly and underline the details that rule plans in or out. A handful of details do most of the work:

A table is a starting point, not a rule. The rest of this lesson shows how to use it on three problems you have not seen.

First, write the slow answer

Before choosing anything clever, write the plan that tries everything. It is usually short, it is almost always right, and it gives you two things: an answer to check the fast version against, and a cost to beat.

Here is the problem: does any value in a list appear twice?

def has_repeat_slow(values):
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] == values[j]:
                return True
    return False

assert has_repeat_slow([3, 1, 4, 1]) is True
assert has_repeat_slow([2, 7, 1, 8]) is False

It compares every pair: about n²/2 comparisons, which is 50 million for 10,000 values. The detail "have I seen this before?" in the table points to a set:

def has_repeat(values):
    seen = set()
    for value in values:
        if value in seen:
            return True
        seen.add(value)
    return False

assert has_repeat([3, 1, 4, 1]) is True
assert has_repeat([2, 7, 1, 8]) is False

One pass, one lookup per value: O(n) time, paid for with O(n) memory.

Check the fast answer against the slow one

The slow answer earns its keep a second time. Run both on many small random inputs and compare. A disagreement shows you an input where the fast plan is wrong, which is far easier to debug than a wrong answer on a big input.

import random

rng = random.Random(1)
for _ in range(200):
    sample = [rng.randint(0, 9) for _ in range(rng.randint(0, 8))]
    assert has_repeat(sample) == has_repeat_slow(sample), sample

Sorted input: two pointers or halving

The problem: in a sorted list, is there a pair of values whose difference is exactly d?

The details are "sorted" and "pair". Sorted order tells you which way to move: if the difference between two values is too small, the larger one must move further right; if it is too big, the smaller one must catch up. Both pointers move in the same direction, and neither ever moves back.

def has_gap(values, d):
    left, right = 0, 1
    while right < len(values):
        gap = values[right] - values[left]
        if gap == d and left != right:
            return True
        if gap < d or left == right:
            right += 1
        else:
            left += 1
    return False

assert has_gap([1, 3, 8, 12, 15], 4) is True     # 8 and 12
assert has_gap([1, 3, 8, 12, 15], 6) is False
assert has_gap([5, 5], 0) is True

Each step moves one pointer forward, so it takes at most about 2n steps. The promise that keeps it right: every pair with its smaller value before left has already been ruled out.

The other sorted-input signal is a question whose answer switches once. "What is the largest whole number whose square is at most n?" Squares grow, so "is k² at most n?" is yes, yes, yes, then no forever. That is a halving problem even though no list is in sight:

def whole_square_root(n):
    lo, hi = 0, n + 1          # the answer is in lo…hi - 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if mid * mid <= n:
            lo = mid
        else:
            hi = mid
    return lo

assert [whole_square_root(n) for n in (0, 1, 8, 9, 10, 1_000_000)] == [0, 1, 2, 3, 3, 1000]

A million needs about 20 halvings instead of a thousand tries.

When two patterns seem to fit

The hard cases are the ones where a familiar plan almost works. Three to watch for:

• A window over values that can be negative. A window grows on the right and shrinks on the left because adding a value never lowers the total. Allow negative values and that promise breaks: shrinking can raise the total, and the window loses track of which end to move. Running totals do not need the promise.
• Depth-first search for "the fewest steps". Following one path as deep as it goes finds a way to the goal, not the shortest. Exploring in rings, everything 1 step away before anything 2 steps away, finds the shortest first.
• Greedy for "the best total". Taking the biggest thing available looks right and is often wrong. When a choice now rules out choices later, look for a small counterexample before trusting greed; if you find one, the problem needs dynamic programming.

In each case the slow answer and a random checker, as above, find the counterexample in seconds.

A routine for a problem you have not seen

1. Say the problem back in one sentence, with the input and the output.
2. Underline the details: sorted? consecutive? negative values? endless? fewest? best?
3. Write the slow answer and say what it costs.
4. Pick a pattern from the details, and say the promise it keeps as it runs.
5. Write it, then check it against the slow answer on random inputs.

Step 4 is the one interviewers listen for. "The window's total never exceeds the budget once I have shrunk it" is a sentence that shows you know why the code works, not just that it does.

What it costs