DSA Atlas

Interview problem-solving playbook

Choose by the operation, not the story.

Translate the prompt into states, transitions, and required fast operations. The algorithm usually becomes visible after those three decisions.

Start the thinking flow Open basic templates Open advanced atlas
  • 8decision flows
  • 9DP families
  • 14structure combinations
interview-loop.md
# Convert story into mechanics
state = what_changes()
transition = one_legal_move()
bottleneck = repeated_operation()

structure = make_fast(bottleneck)
algorithm = explore(state, transition)

say_invariant_out_loud()
test_small_and_hostile_cases()

01 · The interview loop

From unclear prompt to defensible solution

Do not jump from the problem statement directly to code. Produce one concrete artifact at each step.

  1. 01Clarify

    Define input, output, duplicates, mutation, empty cases, and whether an answer always exists.

    Artifact: one precise sentence.
  2. 02Example

    Trace a tiny normal case and one hostile boundary case by hand.

    Artifact: expected state changes.
  3. 03Brute force

    State the obvious complete solution before optimizing it.

    Artifact: baseline complexity.
  4. 04Find waste

    Identify repeated search, recomputation, ordering, or traversal.

    Artifact: the expensive operation.
  5. 05Choose structure

    Select the structure that makes the expensive operation cheap.

    Artifact: operation → structure mapping.
  6. 06Prove

    Name the invariant and why every transition preserves it.

    Artifact: one correctness claim.
  7. 07Code and audit

    Implement helpers, test boundaries, and recompute time and space complexity.

    Artifact: accepted-quality implementation.

02 · Stack or queue?

Ask which item must leave next

The removal order—not the syntax of the input—selects the structure.

Repeated operationWhich pending item must be processed next?
Newest first

Stack · LIFO

Nesting, undo, expression parsing, next greater/smaller, iterative DFS.

Invariant: the top is the most recent unresolved item.
Oldest first

Queue · FIFO

Arrival order, scheduling, level traversal, unweighted shortest steps, BFS.

Invariant: all earlier-discovered work leaves first.
Best priority first

Heap · priority queue

Repeated minimum/maximum, top-k, Dijkstra, event simulation.

Invariant: the root is the best live candidate.
Both ends matter

Deque

Sliding-window extrema, 0–1 BFS, front/back scheduling.

Invariant: dominated or expired candidates are removed.

03 · Three binary-search families

First decide what the final position means

All three repeatedly discard half of a monotonic search space, but their return value and boundary invariant are different.

QuestionWhat should the search return?
Type 1 · Exact lookup

Find this target

Use when values are sorted and any exact matching index is acceptable.

Return
Index or −1
Range
Inclusive [lo, hi]
Loop
while lo <= hi
Move past mid after a mismatch: lo = mid + 1 or hi = mid − 1. Open template →
Type 2 · Boundary search

Find the first valid position

Use for insertion points, duplicates, first/last occurrence, lower bound, or upper bound.

Return
First true index
Range
Half-open [lo, hi)
Loop
while lo < hi
a[i] >= target gives lower bound; a[i] > target gives upper bound. Last occurrence is upper bound − 1. Open template →
Type 3 · Search on answer

Find the minimum feasible value

Use when answers are numeric and a check changes monotonically from impossible to possible.

Return
Smallest feasible value
Range
Candidate answer values
Check
feasible(mid)
Examples: minimum capacity, maximum minimum distance, earliest completion time, or smallest speed. For a maximum feasible answer, search the last true position. Open template →
01Prove monotonicity

After some boundary, every later candidate must stay true—or every later candidate must stay false.

02Name the invariant

State exactly which part of the range may still contain the answer.

03Match updates to the range

Inclusive ranges discard mid; first-true ranges keep a valid mid with hi = mid.

04Test two elements

Dry-run empty, one-element, two-element, all-equal, absent, and boundary answers.

04 · BFS, DFS, or graph?

A graph is any collection of states connected by moves

Grids, word transformations, puzzle configurations, dependency systems, and trees can all be modeled as graphs.

ModelState = node
legal move = edge
GoalWhat must traversal prove?
Fewest unweighted moves

BFS

Explore by distance layers. Mark when enqueued to prevent duplicate work.

BFS template →
Reachability / components

DFS or BFS

Either works. Prefer DFS for recursive structure; BFS when layers are useful.

Graph DFS template →
Dependencies / finish order

DFS or topological sort

Use colors for cycle detection or indegrees when prerequisites become ready.

Topological template →
All paths / reversible choices

DFS + backtracking

Choose, recurse, undo. Keep only state belonging to the current branch.

Backtracking template →
Weighted shortest path

Inspect weights

Nonnegative: Dijkstra. Negative: Bellman–Ford. Small all-pairs: Floyd–Warshall.

Weighted path flow →
Tree aggregation

Tree DFS

Define exactly what dfs(node) returns, then combine child results.

Tree DFS template →

05 · Dynamic programming chooser

Choose DP by the coordinates of the state

DP is organized exhaustive search: define a state, guess a transition, reuse repeated subproblems, and evaluate dependencies safely.

Gate 1Can the answer be expressed from smaller versions of the same problem?
Gate 2Will multiple choices reach the same state?
ThenMemoize the state or fill it in dependency order.
One position / prefix

1D DP

Climbing stairs, house robber, decoding. State usually ends at index i.

dp[i]
Two sequences / coordinates

2D DP

LCS, edit distance, grid paths. State tracks two changing axes.

dp[i][j]
Choose items under a limit

Knapsack DP

Capacity, sum, count, or budget. Iterate backward for 0/1 and forward for reusable items.

dp[capacity]
Split a contiguous range

Interval DP

Burst balloons, matrix chain, palindrome partitioning. Grow by interval length.

dp[left][right]
Answer depends on children

Tree DP

Robber on tree, diameter, subtree choices. DFS returns the states needed by the parent.

dfs(node, state)
Small set of used choices

Bitmask DP

Assignments, traveling salesperson, pairing. A mask records which items are consumed.

dp[mask][last]
Digits under a huge bound

Digit DP

Count numbers satisfying digit rules without enumerating the entire numeric range.

dp[pos][tight][state]
Transitions form a DAG

DAG DP

Longest paths in DAGs and dependency scoring. Evaluate in topological order.

dp[node]
Contiguous choice with a split

Sequence / partition DP

LIS, word break, segmentation, and optimal partitions. Try the last previous choice.

dp[end]

Define the state before the recurrence

A DP state is the smallest complete description of one reusable subproblem

If two recursive calls have the same state coordinates, their future answer must be identical. Anything that changes future choices belongs in the state; history that no longer matters does not.

  1. MeaningWrite one sentencedp[i] = ways to reach step i
  2. ChoiceList the final movecame from i−1 or i−2
  3. TransitionCombine smaller answersdp[i] = dp[i−1] + dp[i−2]
  4. BaseStop the recurrencedp[0] = 1, dp[1] = 1
  5. OrderRespect dependenciesleft → right
Before memoization

Recursive calls form a state tree

The same state appears in multiple branches and repeats the same work.

Repeated color = identical state, identical future answer.
After memoization

The tree collapses into a state DAG

Each unique state is computed once; later calls reuse its stored value.

Time changes from exponential recursion to one computation per state.
Choose top-down whenThe reachable state space is sparse or the recurrence is easier to express recursively.Memoization computes only visited states, but recursion depth matters.
Choose bottom-up whenThe dependency order is clear and most states will be needed.Tabulation avoids recursion overhead and often enables space compression.
Implementation choiceRecursion or iteration?
Top-down recursion

Use when the state graph is sparse

Natural recurrence, uncertain reachability, easy memoization. Check maximum call depth and language stack limits.

Bottom-up iteration

Use when dependencies have a clear order

Dense state space, predictable loops, no recursion risk, and better opportunity for rolling-array compression.

Recursive backtracking

Use when every choice must be undone

The call stack naturally remembers the decision path. Keep choose → recurse → undo adjacent.

Explicit-stack iteration

Use when depth or execution control matters

Store frames yourself when recursion may overflow or when you need pause, resume, or exact traversal ordering.

06 · Backtracking decision tree

Every level answers one decision

A backtracking state contains the current decision index and the partial solution. Each edge makes one choice; returning across the edge undoes it.

  1. 01Choose

    Add the candidate or modify the board/state.

  2. 02Recurse

    Solve the remaining decisions from the new state.

  3. 03Undo

    Restore exactly what the choice changed before trying its sibling.

  4. 04Prune

    Stop a branch as soon as it cannot lead to a valid or better solution.

BacktrackingDifferent paths may matter even when they reach similar-looking positions.

Enumerate valid solutions, arrangements, or paths. Prune impossible branches.

Dynamic programmingMerge paths when the complete future is determined by the same state.

Cache one answer per state instead of exploring the repeated subtree again.

07 · Combine data structures

One structure rarely optimizes every required operation

Write the required operations and target complexity first. Combine structures when each contributes a different fast operation.

Data structure or database? Problems such as LRU cache combine in-memory data structures. Use a database only when the prompt requires persistence, SQL queries, transactions, or data larger than memory.
  1. 01List operations

    Lookup, remove, reorder, minimum, random access, history, or range query.

  2. 02Assign one strength

    Choose a structure for each operation it performs naturally.

  3. 03Connect identities

    Store an index, iterator, node pointer, timestamp, or shared key between structures.

  4. 04Write synchronization invariant

    Every insert, update, and delete must keep all representations consistent.

Required operationsCombineWhy it worksTypical problems
O(1) lookup + move + oldest evictionHash map + doubly linked listMap jumps to the node; list changes recency and removes both ends.LRU cache
O(1) lookup + frequency + LRU tie-breakHash maps + frequency buckets + linked listsOne map finds nodes; another groups nodes by frequency; each bucket preserves recency.LFU cache
O(1) insert + delete + uniform randomDynamic array + value-to-index mapArray gives random indexing; map locates deletions; swap-with-last avoids shifting.Randomized set
Online insert + immediate medianMax-heap + min-heapHeap roots expose the two middle candidates while balancing partitions the stream.Streaming median
Versioned values + latest value before timeHash map + sorted history arraysMap selects the key history; append preserves order; binary search selects a version.Time map
Stack operations + current minimumValue stack + prefix-minimum stackBoth stacks move together; the auxiliary top stores the minimum at that depth.Min stack
O(1) count updates + min/max keyKey map + doubly linked count bucketsKeys jump to buckets; adjacent buckets handle ±1 count; ends expose min and max.All O(1) structure
Replace index + smallest index for valueIndex map + value-to-ordered-set mapOne map removes stale membership; each ordered set exposes its smallest index.Number containers
Array updates + historical snapshotsPer-index version lists + binary searchStore only changed values with snapshot IDs, then locate the requested version.Snapshot array
Follow graph + newest items from many streamsHash sets + per-user lists + max-heapSets track follows; lists preserve posts; heap performs a k-way merge of recent heads.Design Twitter
Count quickly + repeatedly extract top-kHash map + heapMap aggregates frequencies; heap maintains only the best candidates.Top-k frequent items
Minimum priority + update/delete named itemHeap + hash map / index mapHeap selects the minimum; map locates mutable entries.Schedulers, indexed priority queue
Prefix search + payload lookupTrie + hash mapTrie narrows by characters; map stores metadata or counts.Autocomplete, word dictionary
Connectivity + component metadataDSU + arrays / hash mapsDSU finds roots; attached storage tracks size, sums, or labels per root.Accounts merge, dynamic components
Frequency + recency

LFU cache

key map→node→frequency bucket→LRU list

Invariant: every node belongs to exactly one frequency bucket; minFreq names the first eviction bucket.

Official problem →
Random access + deletion

Randomized set

array⇄value:index map+swap last

Invariant: the map index always points to the value's current array slot.

Template →Problem →
Online order statistic

Streaming median

max-heap lower| median |min-heap upper

Invariant: lower ≤ upper and their sizes differ by at most one.

Template →Problem →
Historical lookup

Time map

key map→sorted (time,value) list→binary search

Invariant: each key's versions remain ordered by timestamp.

Template →Problem →
Counts at both extremes

All O(1)

key:bucket map+min ⇄ count buckets ⇄ max

Invariant: buckets are count-ordered and every key lives in its matching bucket.

Official problem →
Mutable reverse lookup

Number containers

index:number+number:ordered indices

Invariant: both directions agree after every replacement.

Official problem →
Aggregate at every depth

Min stack

value stack⇄ same depth ⇄minimum stack

Invariant: each minimum entry summarizes the matching value-stack prefix.

Template →Problem →
Sparse version history

Snapshot array

index→(snapshot,value) history→binary search

Invariant: each index stores only ordered changes, not a full copy per snapshot.

Official problem →

Case study · LRU cache

Hash map answers “where?”; linked list answers “how recent?”

Neither structure is enough alone. A map cannot identify the oldest key, while a list cannot find an arbitrary key in O(1).

Open the LRU C++ / Python template
Hash mapkey → node addressO(1) average lookup
Most recent
HEAD⇄A⇄C⇄B⇄TAIL
Touch: detach node and move after HEAD · Evict: remove before TAIL
  1. get(key)

    Map miss → −1. Map hit → move node to front and return its value.

  2. put(existing)

    Update value, then move the existing node to the front.

  3. put(new)

    Create node, add at front, and store its address in the map.

  4. over capacity

    Remove the node before the tail and erase the same key from the map.

08 · Research basis

References used to strengthen this playbook

The flows synthesize established teaching material; wording and examples here are original and adapted for quick interview use.

Cracking the Coding InterviewOfficial overview: deriving solutions, hints, strategies, data structures, and core algorithms. MIT OpenCourseWare · Dynamic ProgrammingGuessing, memoization, reusable subproblems, and dependency structure. Princeton Algorithms · GraphsDFS reachability and BFS shortest paths in unweighted graphs. Princeton Algorithms · FundamentalsStacks, queues, linked structures, and foundational ADTs. LeetCode 146 · LRU CacheO(1) average get and put requirements; hash table and doubly linked list topic signals.