Working an interview problem

Problem

In an interview you are judged on more than the final code. The interviewer wants to see how you turn a vague statement into a precise one, whether you can find a correct answer before a fast one, how you reason about cost, and whether you catch your own bugs. Candidates who know every pattern still fail by jumping straight to code, solving a slightly different problem, or declaring victory without running a single example. The approach below is a habit, not a script: it front-loads the questions that decide the algorithm and leaves time to test.

The table is the index of the whole site: the phrases in a problem statement that point to a pattern, and where that pattern is taught.

Intuition

Most interview problems are a known pattern wearing a costume, and the costume is removed in two moves. First, find any correct algorithm, usually the brute force that tries everything. It proves you understand the problem, gives you a reference to test against, and its cost tells you what to improve. Second, ask what the brute force does over and over. If it rescans for a value, remember values in a hash map; if it recomputes sums, keep a prefix or a window; if it re-solves the same subproblem, cache it; if it tries every order, look for a structure such as sorting that makes most orders irrelevant. The constraints tell you how far you need to go: with n up to 10⁵, a quadratic brute force cannot pass, so the target is O(n log n) or better.

The amber stages are the two most often skipped. The brute force is the safety net and the test is what catches the bug before the interviewer does.

Mechanics

1. Clarify

Restate the problem in your own words and pin down what the statement leaves open. Can the input be empty? Can values be negative, zero, or repeated? Is the array sorted? How large can n get? Should the answer be indices or values, and what if there is none, or several? Is it fine to modify the input? Write one small example yourself and work it by hand; it is the first test case and it often reveals a misreading.

2. State a brute force, with its cost

Say the simplest correct algorithm out loud and give its time and space, even if you will not code it. "Check every pair, O(n²) time, O(1) space." This shows understanding, earns partial credit if time runs out, and names the target: whatever the brute force repeats is what you will remove. If even the brute force is unclear, that is a sign to clarify further, not to start coding.

3. Read the signals

The constraints are a budget. A typical judge does on the order of 10⁸ simple operations in a second, so the largest n each complexity class can afford is roughly:

Read it backwards: n ≤ 20 invites exponential search, n ≤ 500 allows O(n³), n around 10⁴ allows O(n²), and n around 10⁵ or more demands O(n log n) or O(n). Combine that with the keywords in the table above to shortlist two or three patterns. The complexity page derives these numbers.

4. Optimize the bottleneck

Point at the line of the brute force that dominates the cost and ask which pattern removes it. Common moves: trade space for time (a hash map instead of an inner loop), sort once so that order does the searching, keep a running summary (prefix sums, a window, a heap of size k) instead of recomputing, cache overlapping subproblems, or prove a greedy choice safe. Before coding, state the new complexity and check it against the budget, and walk your example through the new idea in words.

5. Code

Write the template from the pattern's page, adapted to the problem. Use names that carry meaning (need, window_start, best) rather than single letters, pull fiddly logic into a small helper, and keep the main loop readable. Talk while you write, but say what the code is for rather than reading it aloud.

6. Test as an adversary

First trace your own example through the code line by line, with the variable values written down, not the values you expect. Then try the edge cases that break naive versions: empty and single-element input, all equal values, all negative values, the answer at the very start or end, duplicates, and the largest allowed values (overflow in fixed-width languages, recursion depth in Python). If you have the brute force, compare on tiny inputs: the smallest input where two versions disagree is the most useful bug report there is.

Worked example

Two Sum: given an array and a target, return the positions of two values that add up to the target. Take the array 2, 7, 11, 4, 8 and target 12.

Clarify: exactly one answer exists, a value cannot pair with itself, indices are wanted, and n can reach 10⁴ or more. Brute force: check every pair, O(n²). Signals: "have I seen the complement?" is a membership question, which points to a hash map; "the array could be sorted" points to two pointers. Optimize: both beat the brute force, and the hash map does it in one pass. Counting each approach's basic step on this input:

Code and test: tracing the one-pass hash map, with the dictionary as it stands before each lookup:

The answer is indices 3 and 4. Looking up the complement before storing the current value is what stops a value from pairing with itself; a target of twice some value is the edge case that tests it.

Why the brute force loses. On 1 to n in order with the two largest values as the answer, the brute force's worst case:

Doubling n roughly quadruples the pair count but only doubles the lookups. The input is already sorted, which is merge sort's cheapest case, so the middle column is a lower bound on what sorting costs on shuffled data.

Bar heights are to scale. The quadratic bars outgrow everything else; at n = 10⁵ the pair count would be about 5 × 10⁹.

Testing finds the bug the example hides. A common slip in Maximum Subarray is to start the best sum at 0 instead of the first value. It passes the usual mixed-sign example. Searching the shortest arrays of values −2 to 2 first, the smallest input where it disagrees with brute force is [-2]: the buggy version returns 0, the right answer is -2. An all-negative input is on the edge-case checklist for exactly this reason.

Implementation

def two_sum(nums, target):
    seen = {}
    for index, value in enumerate(nums):
        need = target - value
        if need in seen:
            return [seen[need], index]
        seen[value] = index            # stored after the lookup so a value never pairs with itself
    return []

Variations and edge cases

The loop's testing step is worth a habit of its own. A brute-force reference and a tiny exhaustive search catch most bugs before an interviewer does:

from itertools import product


def max_subarray_brute(nums):
    return max(sum(nums[i:j]) for i in range(len(nums)) for j in range(i + 1, len(nums) + 1))


def smallest_disagreement(fast, slow, values=range(-2, 3), max_length=4):
    for length in range(1, max_length + 1):
        for nums in product(values, repeat=length):
            if fast(list(nums)) != slow(list(nums)):
                return list(nums)
    return None

• Talk in complexities. "This is O(n) time and O(n) space; we could get O(1) space by sorting, at O(n log n) time." Interviewers look for the trade-off, not just the number.
• When stuck, solve a smaller or easier version: sorted input, no duplicates, k = 1, one dimension instead of two. The fix for the special case often generalizes.
• When the brute force is exponential, draw its recursion tree. Repeated subtrees mean DP; subtrees that can be cut early mean pruned backtracking.
• Edge-case checklist: empty, one element, two elements, all equal, all negative, sorted and reverse sorted, duplicates, the answer at either end, no answer, the maximum n and the maximum value.
• Python specifics. Recursion depth is about 1000 by default, so deep DFS on a 10⁵-node path needs an explicit stack; integers never overflow, but problems set for 32-bit languages still expect you to respect the range.

Complexity and tradeoffs

• Time spent. A typical 45-minute round leaves about 30 minutes for one problem. A rough split is 5 to clarify and give the brute force, 5 to 10 to find the optimization, 10 to 15 to code and 5 to test. Skipping the first five minutes is the most expensive saving there is.
• Optimal versus finished. A clean, tested O(n log n) solution beats an unfinished O(n) one. Say that the better bound exists and how you would get there if time allows.
• Space versus time. Most optimizations spend memory: a hash map, a DP table, a heap. Mention the memory cost and whether it can be reduced, as with rolling DP rows.
• When the loop is overkill. For a problem you recognise instantly, compress the loop but do not skip the clarify and test steps; recognising the costume is when misreading the details is most likely.

Problems

No list problem has this page as its home: it teaches the vocabulary every other page uses.

Practise the loop itself on problems whose pattern you already know, timing each stage:

• 1. Two Sum: the worked example above; taught on hash maps and sets.
• 53. Maximum Subarray: brute force in O(n²), then Kadane's algorithm, then the all-negative test.
• 11. Container With Most Water: a brute force over pairs and a two-pointer proof of which end to move.
• 3. Longest Substring Without Repeating Characters: a clarify question (which characters?) and a sliding window.
• 322. Coin Change: a greedy idea that a small counterexample breaks, then knapsack DP.

Connections

This page sits at the end of the learning path because it draws on all of it. Complexity analysis supplies the budget, the Python toolkit supplies the idioms that keep code short, and each pattern page's signals table feeds the master table at the top. Recursion is where most brute forces start, and the move from a recursion tree to DP or pruning is the single most common optimization step.

Check yourself

References

• Pólya, G., How to Solve It, Princeton University Press, 1945: understand the problem, devise a plan, carry it out, look back.
• Skiena, S., The Algorithm Design Manual, chapter 1 (correctness and counterexamples) and the "War Stories" throughout, on modelling a problem before solving it.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 3rd edition, chapter 2 (loop invariants and analysing algorithms) and chapter 3 (growth of functions).
• Sedgewick and Wayne, Algorithms, section 1.4, "Analysis of Algorithms", on doubling experiments and order-of-growth estimates.
• Bentley, J., Programming Pearls, 2nd edition, column 8 (the maximum-subarray problem, from cubic to linear) and column 4 (writing correct programs).
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.