DSA field guide

This note is the index for interview prep in the garden — the diagnosis toolkit, not a list to memorize. Turn an unfamiliar prompt into the smallest correct model: name the state, name the property you can exploit, choose a technique, and name the alternative you rejected.

Every technique sits one click away on the map below. The written notes — Two pointers, Sliding window, Binary search, and Monotonic queue — go deep with a fill-in-the-blank skeleton, an animated walkthrough, and a problem ladder. Start here to diagnose; open a note to drill.

Choose your route

• General coding interview: master Layers 0–2, then the common parts of Layer 3. You should be able to derive, code, test, and explain each core pattern.
• Senior / Staff interview: add the structural transformations in Layer 4 where they follow naturally from a baseline DP or search problem. Depth beats a long collection of obscure names.
• Principal interview: keep core coding fluency, choose specialist algorithms for the role’s domain, and spend equal or greater preparation time on system design, operational trade-offs, technical strategy, and examples of cross-team influence. Advanced contest algorithms are domain depth—not a replacement for those skills.

The decision model

Start by asking what the state looks like, not which algorithm name you remember.

The map

The whole taxonomy as one interactive mindmap — zoom, pan, and click a node to expand its branch. Every leaf carries two or three canonical problems (or, in Layer 4, what the transformation unlocks).

open full map ↗

Depth markers: unmarked = master · refresh = re-derive quickly · recognize = know it exists, reduce to it.

Selecting a technique

When the prompt is unfamiliar, walk it top-down: name the data type, look for the keyword that fixes the pattern, and only then let the size of N slice off the runtime you can afford.

flowchart TD
  A(["Read the prompt"]) --> B{"What is the input?"}
  B -->|"array or string"| C{"Keyword in the prompt?"}
  B -->|"linked list"| LL["fast-slow / dummy head"]
  B -->|"tree or graph"| TG["DFS / BFS"]
  B -->|"no structure to exploit"| N{"How big is N?"}
  C -->|"contiguous span + length rule"| SW["sliding window"]
  C -->|"sorted + target or pair"| TP["two pointers / binary search"]
  C -->|"O(1) range aggregates"| PS["prefix sum"]
  C -->|"next-greater / span"| MS["monotonic stack"]
  N -->|"N ≤ 15"| E1["O(2ᴺ) backtracking / bitmask"]
  N -->|"N ≤ 1,000"| E2["O(N²) or 2D DP"]
  N -->|"N ≤ 10⁵"| E3["O(N log N): sort / heap / window"]
  N -->|"N ≥ 10⁹"| E4["binary search on answer / math"]

The playbook

The same decision as fast If → Then reflexes. Read the left, reach for the right.

• array / string → sliding window, two pointers, prefix sum, or monotonic stack
• linked list → fast-slow pointers, dummy head
• tree / graph → DFS, BFS
• “top K / Kth / from a stream” → heap
• contiguous span with a length condition → sliding window
• O(1) range aggregates → prefix sum
• “all combinations / permutations / paths” → backtracking
• sorted input + a target → two pointers, binary search
• N ≤ 15 → O(2ᴺ) backtracking / bitmask
• N ≤ 1,000 → O(N²) or 2D DP
• N ≤ 10⁵ → O(N log N): sort, heap, window, monotonic stack
• N ≥ 10⁹ → binary search on the answer, or math

The production mapping

The same invariants run production systems — this is the principal-level answer to “why learn this.”

When you’re stuck

A working-but-failing solution usually fails in one of four ways. Read the symptom, ask the diagnostic question, and pivot.

flowchart TD
  S{"Where is it failing?"}
  S -->|"TLE from exponential recursion"| A["overlapping subproblems? memoize into DP"]
  S -->|"TLE from a too-slow DP"| B["provable exchange? drop to greedy"]
  S -->|"MLE from a huge BFS frontier"| C["search from both ends: bidirectional BFS"]
  S -->|"wrong answer from a greedy"| D["found a counterexample? lift to DP"]

Learn in six layers

The tiers are a learning order, not a seniority label. A Layer 5 technique is only better than a Layer 1 tool when its preconditions are actually true.

Each layer answers exactly one cognitive question; that keeps the axes orthogonal — no layer mixes data structures with algorithms with transformations with domains.

Layer 0 · Model the problem

What is the problem? Derive the complexity budget from the constraints, make the state and invariant explicit, and decide how you will test. The common substrate under every technique. Master it.

Layer 1 · Linear state

What does the state look like — can I solve it without a graph? The highest-return core: Two pointers, Sliding window, hashing, ordering/intervals/sweep line, Binary search, prefix and difference arrays, monotonic stacks and the deque, cyclic sort, and bit tricks. The array-and-string entry reflexes — two pointers, fast/slow, hashing, cyclic sort — form the Traversal & partition family, whose note collects them behind one chooser. Learn the trigger that splits close alternatives — window maximum (deque) versus ordinary window, range updates (difference array) versus static range queries (prefix sum).

Layer 2 · Explore state spaces

The state isn’t linear — how do I explore it? Represent relationships directly: DFS/BFS, weighted traversal (heap, Dijkstra, 0–1 BFS, Bellman–Ford), graph structure (topological order, SCC), union-find, and tree navigation. The key question is: what does one transition cost, and which part of the state must stay queryable? That picks a queue, deque, heap, or maintained tree rather than habit.

Layer 3 · Reduce the search space

Exploring everything is expensive — how do I avoid it? Greedy when a local exchange is provable; backtracking when choices must be enumerated; divide and conquer when halves combine cleanly; DP when states overlap; and offline processing or coordinate compression when query order or sparse values hide a better representation. Learn DP by its dependency shape — linear, grid, interval, tree, DAG, bitmask, digit — not as a bag of puzzles.

Layer 4 · Transform the problem

The problem is hard — can I change it? The bridge from knowing a recurrence to optimizing it: binary-search the answer, reshape the state (coordinate compression, Euler tour, re-rooting, node splitting), or speed a transition (monotone-queue DP, convex hull trick). Knuth optimization and the Aliens trick are recognition topics first — use them only after you can state and verify their preconditions.

Layer 5 · Specialized domains

Is there domain-specific machinery? Strings (KMP, Z, rolling hash, Aho–Corasick, suffix structures, Manacher), range structures (Fenwick, segment tree, trie), network flows and matching, tree decomposition, geometry, and number theory. Valuable electives for the right role — search, content processing, compilers, routing, infrastructure planning — not a universal prerequisite.

What “principal depth” actually looks like

A principal engineer should use the same mental moves in production contexts: identify the state, quantify a bottleneck, compare alternatives, choose a reversible path, and measure the outcome. The production mapping above is the short version: a monotonic deque powers streaming latency percentiles; multi-source BFS models failure propagation; topological sorting orders a build system; difference arrays apply bulk quota changes; and Aho–Corasick scans for many keywords at once.

The interview signal is not merely naming those algorithms. It is being able to explain their assumptions, operational costs, failure modes, and why a simpler option was not enough. Pair this guide with written system-design cases from your own work: trade-off analysis, security and reliability, rollout/migration, observability, cost, and how you aligned people around the decision.

Study loop

1. Select one family from your current layer and read its pattern note.
2. Solve two or three canonical problems from memory; narrate the invariant before writing the loop.
3. Compare the nearest alternative and explain why it loses on this input shape.
4. Record the solved problem as a /tips entry, tagged with the pattern, difficulty, and source problem.
5. Return after a week without notes. Promote the note only when you can derive it, not when you recognize the title.

Sources

• OpenAI interview guide — one current example of engineering evaluation that includes solution design, code quality, performance, testing, communication, and collaboration.
• Yassir-aykhlf/DSA-Taxonomies — a useful catalogue of patterns and examples, adapted here into a learning order.
• AlgoMonster flowchart — inspiration for choosing by input shape and constraint rather than by title recall.