The Coding Interview Cheat Sheet: Skim This Before You Walk In

You've done the prep. You've ground the problems. You've convinced yourself you understand merge sort. Then the interviewer says "given an array" and your brain plays the Windows XP shutdown sound.

The thirty minutes before an interview isn't for learning anything new. It's for loading the right facts into working memory before the clock starts. This is that reference. Complexity tables, pattern signals, math you cannot derive under pressure, and the gotchas that sink correct code.

Know Which Complexity Class You're In

Commit these to memory as gut-check phrases, not just labels. The goal isn't to recite O-notation; it's to catch yourself before you confidently code an O(n²) solution and submit it at n = 10⁶.

Class	Gut-check	n = 10⁶	Example
O(1)	Instant	1 op	Hash map lookup
O(log n)	Fast	~20 ops	Binary search
O(n)	One sweep	10⁶ ops	Linear scan
O(n log n)	Sorting tier	2×10⁷ ops	Merge sort
O(n²)	Nested loops	10¹² ops	Bubble sort
O(2^n)	Exponential	Way too many	Brute-force subsets

At n = 10⁶, an O(n²) solution runs roughly 10¹² operations. Modern computers do around 10⁸ to 10⁹ operations per second. That's a thousand seconds. Your interviewer won't wait. They will, however, write "candidate did not consider time complexity" in the feedback box.

Time complexity growth curves comparing O(1), O(log n), O(n), O(n log n), O(n²), and O(2^n), showing how exponential and quadratic complexity diverge sharply from linear as input size grows

O(2^n) doesn't just grow fast. It exits the visible universe and keeps going.

Data Structure Operations

Structure	Access	Search	Insert	Delete	Space
Array	O(1)	O(n)	O(n)	O(n)	O(n)
Linked list	O(n)	O(n)	O(1) head	O(1) with ptr	O(n)
Hash map	O(1) avg	O(1) avg	O(1) avg	O(1) avg	O(n)
BST	O(log n) avg	O(log n) avg	O(log n) avg	O(log n) avg	O(n)
Heap	O(1) top	O(n)	O(log n)	O(log n)	O(n)
Stack / Queue	O(1) top	O(n)	O(1)	O(1)	O(n)

The "avg" footnote is a landmine. Hash maps degrade to O(n) with a bad hash function or adversarial keys. Unbalanced BSTs degrade to O(n) on sorted input. A self-balancing tree (AVL, red-black) fixes that at the cost of a bigger constant. Say this out loud during the interview, because "I'm aware of the worst case" is evidence. Silence isn't.

For more detail see the data structures complexity cheat sheet.

Sorting Algorithm Cheat Sheet: Know the Worst Case

Algorithm	Best	Avg	Worst	Space	Stable
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Heap sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Counting sort	O(n+k)	O(n+k)	O(n+k)	O(n+k)	Yes
Radix sort	O(d·n)	O(d·n)	O(d·n)	O(n)	Yes

Where k = value range, d = digit count. Counting sort only beats comparison sorts when k is small relative to n. Radix sort on 32-bit integers uses d = 4 passes over a 256-bucket counting sort: O(4n) in practice.

The comparison sort floor is O(n log n). If you claim to sort general data faster, you're wrong unless you exploit value constraints. See sorting algorithms cheat sheet.

Match the Signal Before You Code

This is the hardest skill and the one practice problems train least. The problem description hides the pattern. You have to read the signal.

When you see "longest/shortest subarray satisfying X" with contiguous elements, it's sliding window. When you see sorted input and pair sums or palindrome checks, it's two pointers. These aren't guesses. They're deductions from structural constraints.

Sliding window Signal: "longest/shortest subarray/substring satisfying X", contiguous elements. Trigger: variable or fixed window over a sequence.

Two pointers Signal: sorted input, pair sums, palindrome check, partition. Trigger: two indexes moving toward each other or in tandem.

Binary search Signal: sorted or monotone-condition array, "find minimum/maximum X where condition holds". Trigger: can you eliminate half the space per step? Then binary search, even on the answer not just the array.

BFS Signal: shortest path, minimum number of steps, "closest", level-by-level. Trigger: unweighted graph or grid where you need the nearest thing.

DFS / backtracking Signal: enumerate all solutions, combinations, permutations, "does a path exist". Trigger: decision tree where each node branches and you want all leaves.

Heap (priority queue) Signal: "kth largest", "k closest", "streaming median", running top-k. Trigger: you need the min or max of a changing set without sorting everything.

Dynamic programming Signal: "number of ways", "minimum cost", "maximum value", overlapping subproblems. Trigger: recursion with repeated sub-calls. If memoizing a DFS makes it fast, it's DP.

Union-find Signal: "connected components", "same group", incremental merge queries. Trigger: "are these two nodes in the same set?" asked many times.

See the full breakdown in DSA patterns cheat sheet.

Math You Cannot Derive Under Pressure

These come up often enough that blanking on them wastes time you don't have. Write them once, close the tab, then see if you can recall them from scratch. That's the actual test.

Sum of first n integers

1 + 2 + ... + n = n(n+1)/2

Number of pairs from n elements

C(n, 2) = n(n-1)/2

Number of subsets of n elements

2^n

Number of permutations of n elements

n!

Log rules (for complexity analysis)

log(ab)  = log(a) + log(b)
log(a/b) = log(a) - log(b)
log(a^k) = k·log(a)
log base change: log_b(x) = log(x) / log(b)

Modular arithmetic

(a + b) % m = ((a % m) + (b % m)) % m
(a * b) % m = ((a % m) * (b % m)) % m

Modular inverse (when m is prime, use Fermat's little theorem)

a^(-1) mod m = a^(m-2) mod m

For the full reference see coding interview math cheat sheet.

Gotchas That Sink Correct Code

You solved the problem. The logic is right. Then one of these kills you anyway.

Integer overflow Java and C/C++ integers wrap silently. Python auto-extends to arbitrary precision. In Java, use long for anything multiplied or summed over n elements, and compute mid = lo + (hi - lo) / 2 not (lo + hi) / 2. The Java standard library shipped this bug for nine years. Joshua Bloch found it in 2006 in code he'd written himself. Nobody is immune.

Modulo sign on negatives Python returns a positive remainder: (-5) % 3 == 1. Java/C/Go return a negative one: (-5) % 3 == -2. If you need a non-negative remainder in Java, write ((n % m) + m) % m. Memorize this now so you don't rediscover it during your coding round.

Off-by-one in binary search Most binary search bugs are boundary bugs. Write lo <= hi or lo < hi consistently, and decide whether your mid belongs to the left half or right half. Pick one template and memorize it exactly. Mixing templates mid-problem is how you write an infinite loop with a smile on your face.

Copy vs reference in backtracking When you add path to your results list, add path[:] (a copy), not path (the reference). Python's list is mutable. Every result will show the final empty state of path if you pass the reference. This is the most common backtracking bug and it produces output that looks technically non-empty but contains only empty lists. You will stare at it for two minutes before understanding what happened.

# Wrong: all results point to the same list
results.append(path)

# Right: snapshot the list at this moment
results.append(path[:])

Checking None/null on tree nodes Recursive tree functions almost always need a base case of if not node: return. Forgetting it causes a null pointer exception on the first empty subtree. This is the kind of bug that works fine on your test case and fails on the interviewer's input.

Stack overflow on deep recursion Python's default recursion limit is 1,000 frames. Any DFS on a path-shaped graph with n = 10⁴ will crash it. Use iterative DFS with an explicit stack, or set sys.setrecursionlimit at the top of your solution. Say out loud that you're aware of the limit. That's a point.

Budget Your 45 Minutes

Treat each phase as a hard allocation, not a suggestion. Interviews fail in the transition zones: people spend 20 minutes on design and 5 minutes on code, then discover a bug with 2 minutes left.

Phase	Minutes	What you're doing
Clarify	3 to 5	Input types, edge cases, expected output, constraints
Brute force	5 to 8	State the naive O(n²) or O(2^n) approach out loud
Optimize	8 to 12	Work toward the target complexity, talk through trade-offs
Code	15 to 18	Write cleanly, narrate while you type
Test	4 to 5	Trace through one example, check edge cases

If you hit minute 20 without a line of code written, you've spent too long in design. Write the brute force. A working suboptimal solution gives you a conversation about optimization. Silence gives you nothing. Literally. The interviewer has nothing to write.

Before You Go In

A quick checklist of the things that matter most, in the order you're most likely to forget them:

O(n²) at n = 10⁶ is a thousand seconds. Know when you're in the wrong tier.
Hash maps average O(1) but degrade. BSTs average O(log n) but degrade. Know the worst cases.
Quicksort is O(n²) worst case. Merge sort is always O(n log n).
Match the pattern before you code. BFS for shortest unweighted path. Heap for kth-largest. DP for overlapping subproblems.
Python's % is always non-negative. Java's is signed. Memorize the fix.
In backtracking, copy path[:] before appending to results.
Budget your 45 minutes. Unstarted code scores zero.

If you want to test whether these patterns actually come out of your mouth under interview pressure, SpaceComplexity runs live voice mock interviews with rubric-based feedback on exactly this kind of knowledge. Reading a cheat sheet loads the facts. Speaking through a problem under a timer is what trains the retrieval.