Reading a Problem: Choosing the Right Tool

The actual gap

You already know what a hash map, a heap, and a BFS are. You've drawn the recursion tree. The thing that keeps sending you back to square one every interview season isn't the structures — it's the translation step: a wall of prose comes in, and you can't see which structure it's quietly describing, or you see it but freeze when turning it into Go.

Both halves are trainable. This module is the translation half. The rest of the course drills the coding half, one pattern at a time, with the same triage applied every time so it becomes muscle memory.

The 7-step triage

Do these in order, every time, even when you think you know the answer. The steps you're tempted to skip are the ones that catch you.

Step 3 in depth: constraints → complexity

Competitive-style problems tell you the input size on purpose. Assume the machine does ~10⁸–10⁹ simple operations per second, then read the size backwards to the intended complexity:

Step 6 in depth: the two heuristics that shortlist a structure

Heuristic A — the shape of the input

Heuristic B — what am I optimising / producing?

Brute force is not a waste of time — it's the map

Writing (or at least fully describing) the brute force does three things: it proves you understood the problem, it gives you a correctness oracle to test the fast version against, and its inefficiency points directly at the optimisation. “This inner loop recomputes a sum” → prefix sums. “This recursion recomputes fib(5) ten times” → memoisation. “This re-scans a sorted region” → two pointers or binary search.

1// Contract (triage step 2): 1 <= k <= len(nums). Pin it before coding;
2// outside it, these two disagree (the first returns MinInt, the second panics).
3
4// Brute force: for each right end, recompute the window sum from scratch.
5func maxSum(nums []int, k int) int {
6    best := math.MinInt
7    for r := k - 1; r < len(nums); r++ {
8        sum := 0
9        for i := r - k + 1; i <= r; i++ { // <-- repeated work
10            sum += nums[i]
11        }
12        best = max(best, sum)
13    }
14    return best
15}
16
17// The waste: nums[i] gets re-added k times.
18// The fix: slide the window — add the entering element, drop the leaving one.
19func maxSumFast(nums []int, k int) int {
20    sum := 0
21    for i := 0; i < k; i++ {
22        sum += nums[i]
23    }
24    best := sum
25    for r := k; r < len(nums); r++ {
26        sum += nums[r] - nums[r-k] // O(1) update
27        best = max(best, sum)
28    }
29    return best
30}

How to practise this

• For the next 20 problems you do, write the triage out in comments before coding. Steps 1–6 in words, then code.
• When you get one wrong, don't just read the solution — figure out which triage step would have caught it. Usually it's step 2 (missed an edge case) or step 5 (didn't spot the waste).
• Keep a personal table: problem → the one phrase that gave away the pattern. After ~30 entries you'll see the cues repeat. Log them in the Cue log; the Pattern Matcher is a starter version of the same table, built from the whole course.