Interview craft cheat sheet

Spotting the pattern from the question

Read the question for cues, then match them: unsorted lookups suggest a hash map; sorted input suggests two pointers or binary search; 'best contiguous stretch' suggests a sliding window; 'k largest' or 'merge sorted' suggests a heap; grids and networks suggest BFS or DFS; 'count the ways' or 'fewest' with repeated sub-questions suggests DP; 'list every' suggests backtracking. Say the cue and the pattern together, then confirm with a small example.

The first five minutes of a coding interview

Restate the task in your own words, ask about input size, value ranges, duplicates, empty input and the expected output for ties, and work one small example by hand. Then state a brute-force approach and its cost, and say which pattern you will use to improve it. This catches misunderstandings early and gives the interviewer a chance to steer you.

Brute force first, then improve

A brute-force answer proves you understand the question and gives a baseline cost. To improve it, look for repeated work: a lookup done in a loop (use a hash map), a range recomputed each time (use a window or prefix sums), a sorted structure you ignore (use two pointers or binary search), or the same sub-question solved many times (use DP). Each improvement should come with its new cost.

Count position pairs whose values differ by exactly k

The brute force checks all pairs in O(n²). Instead, walk the list once with a counter of values seen so far: each value v pairs with every earlier v - k and v + k. Add both counts, then record v. O(n) time and O(n) memory: the counter replaces the inner loop.

from collections import Counter


def pairs_k_apart(vals: list[int], k: int) -> int:
    earlier: Counter[int] = Counter()  # values seen before this one
    total = 0
    for v in vals:
        total += earlier[v - k] + earlier[v + k]
        earlier[v] += 1
    return total

Talking while you code

Narrate decisions, not keystrokes: say what the next block does and why ('this loop grows the window until the total passes the budget'). Pause to state invariants and edge cases as you handle them. If you go quiet to think, say so. Interviewers score communication separately, and they can only give hints if they know where you are.

Dry run: the first day an account is overdrawn

One pass with a running balance: add each change and return the day it first goes negative. O(n) time, O(1) memory. The point of this page is the dry run: walking the code by hand on a small input catches off-by-one errors and wrong return values before the interviewer does.

def first_overdrawn_day(changes: list[int], start: int) -> int:
    balance = start
    for day, change in enumerate(changes):
        balance += change
        if balance < 0:
            return day
    return -1

Testing your own code in an interview

Run the example you agreed at the start, then the edge cases: empty input, one item, all items equal, already sorted or reversed, negative numbers, the largest allowed values and a case with no answer. For each, say the expected output first, then trace or run the code. Finish by restating time and memory complexity.

What to do when you are stuck

Say you are stuck and what you have tried. Go back to a small example and solve it by hand, noting what you did. Try each likely pattern against the cues. Write the brute force so there is something correct, then look for repeated work. Ask a focused question ('would sorting the input be allowed?'). A clear, honest process scores far better than silence.