Coding interview notes: map patterns, not solutions

Replace a list of solved problems with a decision

Coding interview notes are hard to reuse when every page is named after a problem and contains only the final code. Start a mind map around decisions: “Need membership lookup?”, “Need a fewest-edge path?”, or “Can I reuse overlapping subproblem results?” Keep the answer conditional.

A problem cue is a suggestion, not proof. The word “sorted” does not automatically justify every two-pointer solution, and the word “shortest” does not automatically mean breadth-first search. Under each pattern, write the assumptions that make the approach valid.

This guide develops one pattern in detail so you can repeat the structure. It is not a complete interview syllabus or a promise that a particular employer will ask these questions. Continue practising implementation and explanation in the environment you expect to use.

Give a BFS branch an invariant

For an unweighted graph represented by adjacency lists, breadth-first search explores vertices in layers from a source. A first discovery gives a fewest-edge distance. MIT's BFS lecture notes explain the layer structure and O(V + E) traversal bound.

Write the practical invariant in your note: the queue processes discovered vertices in nondecreasing distance, and a vertex receives its distance only once. Mark a vertex when you enqueue it, not after repeatedly placing it in the queue.

Then trace this example: A connects to B and C; B and C each connect to D; E is isolated. Starting at A gives A:0, B:1, C:1, D:2. E remains unreachable. The shared neighbor D makes this a more revealing example than a simple chain.

Keep a small implementation with its assumptions

This original JavaScript example uses a Map of adjacency arrays and an array-backed queue with a moving head. A missing adjacency entry is treated as a vertex with no outgoing edges. It returns distances for reachable vertices, not a reconstructed path.

function bfsDistances(graph, start) {
  const distance = new Map([[start, 0]]);
  const queue = [start];
  for (let head = 0; head < queue.length; head += 1) {
    const vertex = queue[head];
    for (const next of graph.get(vertex) ?? []) {
      if (distance.has(next)) continue;
      distance.set(next, distance.get(vertex) + 1);
      queue.push(next);
    }
  }
  return distance;
}

With adjacency lists and expected constant-time Map operations, the traversal takes O(V + E) time over the reachable portion and O(V) extra space. The queue keeps processed entries, so the extra storage is still linear. If you need the actual route, store a predecessor when discovering each vertex and reconstruct it afterward.

Attach tests and a reason the pattern can fail

Check the implementation with a cycle, a self-loop, two routes to the same vertex, an isolated source, and a disconnected component. For the A-B-C-D example, explain why D is inserted once even though two vertices lead to it.

Now change the problem: edges have different costs, and the goal is lowest total cost. Ordinary BFS no longer solves that objective in general. Add “edge cost changed” as a boundary note and return to your course's weighted shortest-path algorithms rather than silently reusing the code.

Keep the failing assumption near the pattern name. During revision, ask what would make you reject the pattern. That question is often more revealing than recognizing the successful example.

Connect the map to practice, not just storage

After a problem, record one useful mistake: chose the wrong state, missed a boundary case, or could not explain the invariant. At the next session, attempt a different problem that tests that weakness without reading your saved solution first.

Mappy can store pattern branches, code blocks, source links, and checklists in expanded notes. It is a local mind-map and notes app for Mac with no subscription. Code blocks are for reading and explanation; they do not execute. Run tests in your editor or terminal and keep substantial implementations in version control.

Use the downloadable record below for one pattern at a time. A small collection of explanations you can defend is more useful than a giant map of algorithm names you cannot apply.

Coding interview pattern record

Use this outline in any notes editor, or recreate its branches in Mappy. It is a plain-text worksheet, not an automatically importable .mindmap file. No signup is needed for the template.

Download the text template (.txt)

Pattern:
Problem cue (not proof that this pattern applies):
Required assumptions:
State maintained:
Invariant:
Why each step preserves it:
Termination / result:

Small input and hand trace:
Failure case if an assumption changes:
Time and space, with representation assumptions:
Tests: empty / minimal / duplicate / disconnected / boundary
Problem link and what I got wrong:
Next unfamiliar problem to attempt: