Patterns for coding problems

Prefix sums: totals over any range

The trail club has a counter at the trailhead that records hikers each day. "How many came between day 30 and day 90?" Adding up the range every time costs O(n) per question. Instead, build the running totals once: prefix[i] is the total of the first i days. Then any range total is one subtraction, prefix[b] - prefix[a].

The same idea answers a harder question in one pass: how many stretches of consecutive days add up to exactly k? A stretch from a to b sums to k exactly when prefix[b] - prefix[a] == k, so as you walk, count how often each running total has appeared, and look up total - k:

from collections import Counter
from itertools import accumulate

daily = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = [0] + list(accumulate(daily))
print("days 2 to 5:", prefix[6] - prefix[2], "=", sum(daily[2:6]))

def stretches_summing_to(values, k):
    seen = Counter({0: 1})   # the empty start
    total = found = 0
    for v in values:
        total += v
        found += seen[total - k]
        seen[total] += 1
    return found

print("stretches adding to 10:", stretches_summing_to(daily, 10))

from collections import Counter

def stretches_summing_to(values, k):
    seen, total, found = Counter({0: 1}), 0, 0
    for v in values:
        total += v
        found += seen[total - k]
        seen[total] += 1
    return found

print(stretches_summing_to([1, 2, 3], 3), stretches_summing_to([2, 2, 2], 4))

Sliding windows and running bests

A sliding window is a range that moves along the data. For a fixed size, like "the busiest 7 days", don't re-add all 7 days at each step: add the day that enters and subtract the day that leaves. For a variable size, grow the window on the right and shrink it from the left whenever it breaks a rule. The longest stretch of trail markers without a repeated color, for example, keeps a set of what's inside the window.

A running best is the simplest one-pass pattern: keep the best answer so far, plus whatever you need to update it. The largest rise between an earlier and a later reading needs only the lowest reading so far:

def busiest_week(daily, k=7):
    window = sum(daily[:k])
    best = window
    for i in range(k, len(daily)):
        window += daily[i] - daily[i - k]   # one day in, one day out
        best = max(best, window)
    return best

def longest_without_repeat(colors):
    inside, start, best = set(), 0, 0
    for end, c in enumerate(colors):
        while c in inside:              # shrink until the repeat is gone
            inside.remove(colors[start])
            start += 1
        inside.add(c)
        best = max(best, end - start + 1)
    return best

def largest_rise(readings):
    low, best = readings[0], 0
    for r in readings[1:]:
        best = max(best, r - low)
        low = min(low, r)
    return best

daily = [12, 30, 8, 41, 22, 19, 35, 50, 7, 14]
print(busiest_week(daily), longest_without_repeat("RGBRYGBB"), largest_rise([40, 31, 35, 28, 52, 47]))

The last one is a classic interview question, usually told about prices. Here it's the counter's readings: the largest rise between an earlier reading and a later one is 52 - 28 = 24. Keeping only the lowest value so far makes the obvious "compare every pair" answer unnecessary.

Talking through a problem

In an interview, how you get to the answer counts as much as the answer. A steady routine also stops you freezing:

1. Restate the problem in your own words, and ask about the input: can it be empty, sorted, negative, huge?
2. Work a small example by hand, out loud. It often shows the pattern before any code does.
3. Say the brute force and its cost. "Check every pair: O(n²)." It proves you understand the problem, and it's a working answer if time runs out.
4. Name what's slow and the pattern that removes it. "The inner loop searches for a partner; a set finds it in one step." Then write the code.
5. Test it on your example and the edges: an empty list, one item, duplicates, all the same value.

None of this is only for interviews. Restating, trying a small case and saying the cost out loud are how good engineers explain a design to their team too.

import random
import time
from collections import Counter

def brute_force(values, k):
    count = 0
    for a in range(len(values)):
        total = 0
        for b in range(a, len(values)):
            total += values[b]
            if total == k:
                count += 1
    return count

def one_pass(values, k):
    seen, total, found = Counter({0: 1}), 0, 0
    for v in values:
        total += v
        found += seen[total - k]
        seen[total] += 1
    return found

values = random.Random(4).choices(range(-5, 10), k=1500)
for f in (brute_force, one_pass):
    start = time.perf_counter()
    answer = f(values, 12)
    print(f"{f.__name__:>11}: {answer} stretches in {time.perf_counter() - start:.3f}s")