Cheatsheet
Coding Interview Patterns
Fourteen coding interview patterns on one page: the property that points to each, what it costs, when it fails, and its loop in Python.
ravnary.com/cheatsheets/coding-interview-patterns · Checked against Python 3.14, Java 25 and TypeScript 5.9 on Node 24.
- 14 entries
- 4 groups
Checked against
Python 3.14, Java 25 and TypeScript 5.9 on Node 24.Scope
Every pattern in the subject; a problem none fits goes to the six steps of Solving an Unseen Problem, and graph algorithms to their own sheet.The rule
A pattern is chosen by a property the problem has, never by a word it uses: the input's structure first, then the question, then the values.
Choosing
14 choicesWhen A linked list, and the question asks about a loop, the middle, or a position counted from the end
, chooseWhen A linked list must be reversed or reordered, whole, in a stretch or in groups, without a copy
, chooseWhen A tree, and the answer at a node comes from the path above it, the subtree below it, or its level
, chooseWhen A map of cells, and movement goes between cells that touch
, chooseWhen Things linked in pairs with no graph given, and a question about fewest steps, an order or groups
, chooseWhen Each item has a start and an end, and the question asks about overlaps, gaps, or how many are open at once
, chooseWhen The k best items from anywhere in the input, the next across sorted sources, or a running middle
, chooseWhen The answer is where a yes-or-no test turns from false to true, over positions or possible answers
, chooseWhen For each item, the nearest item on one side that is larger or smaller
, chooseWhen The best contiguous run of a fixed length, or of any length when growing it moves the rule one way
, chooseWhen Sums of contiguous runs when values can be negative, or many range sums over data that never changes
, chooseWhen Sorted input and a question about pairs or a split, or three or more items that meet a target
, chooseWhen Each item is a few yes-or-no flags, or every value appears twice but one, in constant memory
, chooseWhen Single items in unsorted input, such as one seen before, a pair's partner, or counts, with memory to spare
, choose
Arrays and numbers
6 entriesEach answers a question over a sequence of values in about one pass, and they differ in what the values must allow.
A map of the items seen so far answers each item's question in one lookup: O(n) on average.
Avoid when
Memory must stay constant, or the input is sorted and two pointers find the pair without a map.
Move one of two pointers on a sorted array, each move ruling out a row of pairs: O(n), worst case.
Avoid when
The input is unsorted and cannot be sorted first; a hash map of complements answers instead.
Grow a run on the right and shrink it from the left while it breaks the rule: O(n), worst case.
Avoid when
Values can be negative, so dropping one from the left can raise the sum; prefix sums answer instead.
Running totals make any range sum one subtraction: O(n) to build and O(1) per range, every case.
Avoid when
The values change between questions, since every later total must then be rebuilt.
A stack of unanswered positions; each new value answers every smaller one on top: O(n), worst case.
Avoid when
The question asks for the largest value anywhere, not the nearest larger one on one side.
Read an integer as a row of switches: AND tests, OR sets, AND NOT clears, and XOR cancels pairs.
Avoid when
The flags outnumber the bits: 32 in a Java int and in TypeScript's operators, 64 in a Java long.
Linked lists
2 entriesBoth walk a linked list once with constant extra memory: one finds a position, and the other reorders the nodes.
Slow steps one node and fast two; they meet in a cycle, or slow ends mid-list: O(n), worst case.
Avoid when
The input is an array, where an index finds the middle, or memory allows a set of the nodes seen.
Save the next node, point the current one backwards, then step both on: O(n), every case.
Avoid when
A copy is allowed, or the original order is still needed after the reversal.
Sorting, searching and priority
3 entriesEach relies on an order: intervals sorted by start, a test that turns true once, or a heap ordered by size.
Sort by start, then merge each interval into the last one when they overlap: O(n log n), worst case.
Avoid when
The times are whole units in a small range, where an array with one slot per unit is simpler.
Halve the candidates down to the first that passes a yes-or-no test: O(log n) tests, worst case.
Avoid when
The test changes between false and true more than once, so there is no single boundary.
A min-heap capped at k holds the k largest so far, the weakest on top: O(n log k), worst case.
Avoid when
The k items must form one contiguous run, which is a sliding window, not a heap.
Trees, grids and graphs
3 entriesEach walks linked things, and they differ in whether the links are given, implied by a grid, or still to be found.
Pass what the path knows down as an argument, and return what the subtree found: O(n), every case.
Avoid when
A node can be reached two ways, so the structure is a graph and needs a visited set.
Each cell is a vertex and its four neighbours its edges, never stored: O(R · C), worst case.
Avoid when
Moves cost different amounts, such as road and mud, where Dijkstra's algorithm replaces the queue.
Decide the vertex, the edge, its direction and its weight; then the question names the algorithm.
Avoid when
The links are already given as a list, tree or grid, whose own pattern applies directly.
Side by side
1 table| Pattern | Needs | Question it answers | Cost | Breaks when |
|---|---|---|---|---|
| Two pointers | Sorted input | Pairs, or a split of the array | O(n) after any sort | The input is unsorted and sorting would lose what is asked, such as positions |
| Sliding window | A fixed length, or a condition that moves one way as the run grows | The best contiguous run | O(n) | Values can be negative, so a longer run can have a smaller sum |
| Prefix sums | Data that does not change between questions | Range sums; runs with a given sum, with a hash map of earlier totals | O(n) to build, O(1) a question | Values change between questions |
| Binary search | A test that changes once, from false to true | The boundary where it changes | O(log n) tests | The test changes more than once |
Common mistakes
7 mistakesChoosing a pattern from a word in the question, as largest suggests a heap, instead of a property the problem has.
Recording an item before looking up its complement, so 6 pairs with itself when the target is 12.
Reading the range from i to j as p[j] − p[i], which drops the last item; it is p[j + 1] − p[i].
Storing values on a monotonic stack when the answer is a distance, which fails once a value repeats.
Merging intervals sorted by end, so a long one that starts early arrives last and joins the wrong neighbour.
Keeping the k largest in a max-heap capped at k, which throws the best item away and keeps the k smallest.
Returning the path that bends through a node as its height, so the parent joins two branches that cannot meet.
Learn it
14 topicsHash Map Patterns4 questions
PractiseTwo Pointers4 questions
PractiseSliding Window5 questions
PractisePrefix Sums4 questions
PractiseMonotonic Stack4 questions
PractiseBit Manipulation4 questions
PractiseFast and Slow Pointers4 questions
PractiseLinked List Reversal4 questions
PractiseIntervals4 questions
PractiseModified Binary Search4 questions
PractiseHeap Patterns4 questions
PractiseTree Patterns4 questions
PractiseGrid Traversal4 questions
PractiseGraph Modelling4 questions
Practise