Coding Interview Templates: Memorize the Frame, Not the Script

Joshua Bloch wrote Java's standard library binary search. He's also the author of Effective Java, one of the most cited books in the field. In 2006, he published a blog post confessing that his own implementation had a bug that went undetected for nearly a decade. The offending line was int mid = (low + high) / 2. Completely standard. Textbook, even. And wrong for any array longer than 2^30 elements, because the sum overflows into a negative number and the index goes haywire.

The fix is mid = low + (high - low) / 2. Algebraically identical. Overflow-safe. You derive it in ten seconds if you understand that you want the midpoint of two numbers without letting the intermediate sum exceed Integer.MAX_VALUE. You never derive it if you just memorized the formula.

So even Joshua Bloch had a bug in his binary search. If that doesn't make you feel better about your coding interviews, nothing will.

That's also the whole argument in three paragraphs. Templates are useful. Blind memorization isn't.

What a Template Actually Is

A coding template is compressed understanding. Not a shortcut around it.

Chess grandmasters hold roughly 50,000 to 100,000 "chunks" in long-term memory. These are clusters of piece positions they recognize instantly as units, rather than as individual pieces. Chase and Simon showed in 1973 that when you scramble the board randomly, experts perform barely better than novices. The expertise is structured pattern recognition built on years of understanding why positions arise. Not raw memory.

A DFS template is the same thing. An experienced engineer sees a connected-component problem and loads a mental chunk: "graph traversal, need visited set, mark before exploring." That chunk encodes weeks of having debugged infinite loops from marking after exploring. The template is the residue of understanding, not a substitute for it.

Template memorization tries to shortcut to the end product without building the underlying structure. You get the words without the meaning. So when the problem shifts slightly, you have nothing to adapt from. You've got furniture but no floor plan.

The Four Coding Interview Templates That Actually Matter

Six patterns cover most of what shows up in interviews. Four are worth having as internalized frames.

Binary Search

left, right = 0, len(nums) - 1

while left <= right:
    mid = left + (right - left) // 2  # not (left + right) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

return -1

Every line has a reason. left <= right because the search space is [left, right] inclusive, so when left == right there is still one element to check. mid + 1 and mid - 1 because mid has already been evaluated and must be excluded from the next interval, or you get an infinite loop when left == mid. The left + (right - left) // 2 formula is there because left + right can overflow for large arrays, as Bloch learned at some cost to his reputation.

The variants for left-boundary and right-boundary search change these details in precise ways. Which variant to use depends on your invariant, not on which template "feels right." More on the invariant approach in Binary Search: One Invariant to Rule the Search Space.

Sliding Window

left = 0
window = {}
result = 0

for right in range(len(s)):
    # expand: add s[right] to window
    window[s[right]] = window.get(s[right], 0) + 1

    # shrink: while window is invalid
    while len(window) > k:
        window[s[left]] -= 1
        if window[s[left]] == 0:
            del window[s[left]]
        left += 1

    # update result (window is valid here)
    result = max(result, right - left + 1)

return result

The expand-then-shrink structure is the invariant. You expand unconditionally in the for loop, shrink in a while until the window is valid again, then update the result. The result update happens after the shrink because at that point the window is the largest valid window ending at right. Flip those two lines and you get wrong answers on problems where the window needs to be valid before you measure it.

The fixed-window variant (where k is given as the window size) is simpler: no shrink loop, just slide by evicting the element that fell off the left. Knowing which variant applies is a ten-second decision before you write any code: is the window size fixed, or does it grow until it becomes invalid?

Backtracking

def backtrack(start, path):
    if len(path) == k:
        result.append(path[:])  # copy, not reference
        return

    for i in range(start, len(nums)):
        path.append(nums[i])
        backtrack(i + 1, path)  # i+1 for combinations; 0 for permutations
        path.pop()

The start parameter is the whole difference between combinations and permutations. In combinations, [1, 2] and [2, 1] are the same answer, so you impose a canonical ordering: only consider elements at index i and beyond. That's the i + 1. In permutations, order matters, so you loop from 0 and track which elements are in the current path with a visited set.

This distinction trips up template memorizers on problems like Letter Combinations of a Phone Number (LeetCode 17), which looks like combinations but uses separate digit positions, so there is no start index at all. The template is similar but the structural reason is different. Just pattern-matching to "backtracking = use start" means you adapt the wrong thing.

The path[:] copy at the leaf is the other landmine. Skip it and you get a list of empty lists after all the pops unwind. The copy is not decoration.

DFS on Graphs

def dfs(node, visited, graph):
    visited.add(node)  # mark BEFORE exploring neighbors
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited, graph)

Mark visited before recursing, not after. Marking after means that during the recursive calls you may visit the same node again before the mark is applied, causing an infinite loop on any cycle. Trees don't need this because there are no back-edges. The moment you move from tree DFS to graph DFS, this line is the correctness pin. Get it wrong and your code loops forever on any graph with a cycle, which is most real graphs.

The Part the Template Can't Do

No template tells you which one to reach for.

This is where most candidates break down. The template is correct. The pattern match is wrong.

A classic example: you see "subarray," you reach for sliding window. Makes sense, right? Sliding window is the subarray tool. Except sliding window only works when validity is monotone. Adding an element can only make the window more invalid, never less. The counter-example is "subarray sum equals k" (LeetCode 560), where the window can flip from invalid to valid as you expand. Sliding window produces wrong answers. The right tool is a prefix-sum hash map.

By the time you figure this out, you've written forty lines of code.

Mike Wazowski stunned face: interviewer asks a LeetCode question for a web-frontend developer position

When you memorized the sliding window template but the problem needs a prefix-sum hash map

Knowing when the template applies is the actual skill the interview tests. The template-fluent candidate writes clean code fast. The pattern-recognition-fluent candidate writes clean code fast on the right problem. Only one of those gets hired.

If you understand that sliding window works because of monotone validity, you can check that property in thirty seconds before committing to the approach. If you just recognize "subarray, use sliding window," you realize it's wrong only after you've committed to forty lines.

How to Internalize Without Just Memorizing

The process is active reconstruction, not passive copying.

Read the template once. Close the tab. Implement it from scratch. Then compare your version to the original and find every line where you made a different choice. Those differences are exactly the things you do not understand yet.

For binary search: did you write <= or <? Did you write mid + 1 or mid? Did you use low + (high - low) // 2 or (low + high) // 2? Each difference is a question. Each question has an answer you can work out from the invariant.

Drake meme: rejecting copy-paste the tutorial code; approving type out the code by hand to make it feel like you're actually coding

The Drake meme is accidentally correct here. Typing from memory isn't procrastination theater. It's how patterns actually stick.

Do this three times per template over a week, then solve five problems with it. Not five problems where you copy the template in. Five problems where you write the template from memory and adapt it to the problem's specific details. Variation forces you to understand which parts of the template are fixed (the invariant) and which are parameters (the condition function, the result-update position, the shrink predicate).

SpaceComplexity voice-based mock interviews surface exactly this: you can write the code, but can you explain why each line is there? Interviewers ask. "That's just how the template goes" is not a satisfying answer. If you want reps explaining your reasoning out loud, try a session.

The Template Is a Starting Frame

Think of a template as the foundation of a house. It determines where the load-bearing walls are. You still have to build the rest of the structure to fit the actual lot.

Binary search on a sorted array is the vanilla template. Binary search on a rotated array needs an extra condition to determine which half is sorted. Binary search on a condition function (the "find the minimum value such that..." style) replaces the nums[mid] == target branch with a call to your condition. The frame stays the same. The interior changes.

The engineers who interview well have internalized frames with enough understanding to know which walls are load-bearing and which are drywall you can move.

The engineers who fail have memorized blueprints they can't modify. They prepared in a way that felt thorough but was closer to false confidence. Like studying for the right exam in the wrong year.

Recap

Templates are compressed understanding, not shortcuts around it. The Bloch bug is the proof: you write the safe low + (high - low) / 2 only if you understand overflow.
Pattern recognition beats template recall. Sliding window fails on non-monotone validity. Backtracking's start index fails on problems with positions, not pool selections.
Internalize by reconstruction: write from memory, compare to source, investigate every difference.