Coding Interview Cheat Sheet 2026

This is the cheat sheet we'd want printed next to our laptop the night before a coding interview. Bookmark it. The goal is recall, not learning — this isn't a tutorial. If you're encountering any of these concepts for the first time, start with the patterns guide first, then come back here for the quick reference.

1. Big-O complexity reference

Notation	Name	Example operation	1M elements
O(1)	Constant	Hash lookup, array index	1 op
O(log n)	Logarithmic	Binary search	~20 ops
O(n)	Linear	Single pass, linear scan	1M ops
O(n log n)	Linearithmic	Comparison sort, merge sort	~20M ops
O(n²)	Quadratic	Nested loop, bubble sort	1T ops — will time out
O(2ⁿ)	Exponential	Naive recursion (Fibonacci), subset generation	Stack overflow at n=30
O(n!)	Factorial	Permutations, naive TSP	Impossible past n=12

The practical cutoffs at 1-second time limit (~10^8 ops):

• n ≤ 11: O(n!) is OK (most permutation problems)
• n ≤ 25: O(2^n) is OK (subset, brute force backtracking)
• n ≤ 500: O(n^3) is OK (Floyd-Warshall, some DP)
• n ≤ 5000: O(n^2) is OK
• n ≤ 10^6: O(n log n) is OK
• n ≤ 10^8: O(n) is OK

2. Data structure quick-reference

Structure	Lookup	Insert	Delete	Use when…
Array / list	O(1) idx, O(n) val	O(n) middle, O(1) end	O(n)	Random access, indexed iteration
Hash map / set	O(1) avg	O(1) avg	O(1) avg	Membership test, dedup, counting
Stack	O(n)	O(1) push	O(1) pop	Reversal, parsing, DFS, monotonic problems
Queue / deque	O(n)	O(1) ends	O(1) ends	BFS, sliding window
Heap / priority queue	O(1) min/max	O(log n)	O(log n)	Top-K, scheduling, Dijkstra
Binary search tree	O(log n) balanced	O(log n)	O(log n)	Ordered queries, range searches
Trie	O(m) m=key len	O(m)	O(m)	Prefix queries, autocomplete, word problems
Union-Find	~O(1)	~O(1)	N/A	Connected components, cycle detection
Graph (adj list)	O(V+E) traverse	O(1)	O(V+E)	Connectivity, paths, shortest paths

3. Python toolkit (recommended default)

from collections import deque, Counter, defaultdict, OrderedDict
from heapq import heappush, heappop, heapify, nlargest, nsmallest
from bisect import bisect_left, bisect_right, insort
from functools import lru_cache, reduce
from itertools import combinations, permutations, product, accumulate
import math  # math.inf, math.gcd, math.isqrt
import sys; sys.setrecursionlimit(10**6)  # for deep recursion problems

# Common idioms
counter = Counter(arr)              # frequency map
sorted_keys = sorted(d.keys())      # ordered iteration
arr.sort(key=lambda x: (-x[1], x[0]))  # custom sort, primary desc + secondary asc
nums.sort(reverse=True)             # descending
deque(arr, maxlen=k)                # bounded deque

# Heap: Python's heapq is MIN-heap. Max-heap = negate values
heap = []
heappush(heap, -value)              # max-heap by negating
top_k_max = nlargest(k, arr)        # top-K largest, often easier than maintaining heap
top_k_min = nsmallest(k, arr)

# Memoization
@lru_cache(maxsize=None)
def fn(x, y): ...

# Binary search on sorted array
i = bisect_left(arr, target)        # leftmost insertion point
i = bisect_right(arr, target)       # one past rightmost match

4. Java toolkit

import java.util.*;

// Standard collections
List<Integer> list = new ArrayList<>();
Deque<Integer> stack = new ArrayDeque<>();   // prefer over Stack
Deque<Integer> queue = new ArrayDeque<>();   // double-ended
Map<String, Integer> map = new HashMap<>();
Set<Integer> set = new HashSet<>();

// Ordered map / set (red-black tree under the hood)
TreeMap<Integer, Integer> tmap = new TreeMap<>();
tmap.floorKey(k);       // largest key <= k
tmap.ceilingKey(k);     // smallest key >= k
tmap.subMap(lo, hi);    // range view

// Priority queue (min-heap by default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Sorting
Arrays.sort(arr);                    // primitive
Arrays.sort(arr, (a,b) -> a - b);    // boxed, lambda comparator

// StringBuilder for concat in loops (mandatory in interviews)
StringBuilder sb = new StringBuilder();

5. JavaScript toolkit

// JS doesn't ship a true heap or balanced BST in the language; use a library
// or implement min-heap inline (interviewers expect this if you choose JS).

// Useful built-ins
const map = new Map();             // ORDERED by insertion, preserve order
const set = new Set();
arr.sort((a, b) => a - b);          // numeric sort (default is lexicographic!)
arr.indexOf(x);                    // O(n), do not use for membership; use Set
new Set(arr);                      // dedup
[...new Set(arr)];                 // dedup & back to array

// Common patterns
const memo = new Map();
const key = `${a},${b}`;           // tuple-as-key trick for memoization

// Min-heap implementation (often needed - interviewers know JS doesn't ship one)
class MinHeap {
  constructor() { this.heap = []; }
  push(v) { /* sift up */ }
  pop() { /* sift down */ }
  peek() { return this.heap[0]; }
}

6. C++ toolkit

#include <bits/stdc++.h>   // competitive programmers' all-in-one
using namespace std;

vector<int> v;
unordered_map<int, int> m;       // hash map, O(1) avg
map<int, int> ordered_m;          // sorted, O(log n)
set<int> s;                       // sorted set
unordered_set<int> us;
priority_queue<int> max_heap;     // max-heap by default
priority_queue<int, vector<int>, greater<int>> min_heap;
deque<int> dq;
stack<int> st; queue<int> q;

// Sorting
sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<int>());            // descending
sort(v.begin(), v.end(), [](int a, int b){ return a < b; });  // lambda

// Binary search on sorted vector
auto it = lower_bound(v.begin(), v.end(), x);   // first >= x
auto it = upper_bound(v.begin(), v.end(), x);   // first > x

7. Pattern templates (copy-paste ready)

Sliding window (variable size)

def sliding_window(s):
    left = 0
    state = {}  # or counter, set, sum, etc.
    best = 0
    for right in range(len(s)):
        # ADD s[right] to state
        # WHILE window is invalid: shrink from left
        while invalid(state):
            # REMOVE s[left] from state
            left += 1
        best = max(best, right - left + 1)
    return best

Two pointers (sorted array)

def two_pointers(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target: return (left, right)
        if s < target: left += 1
        else: right -= 1
    return None

BFS (shortest path on unweighted)

from collections import deque

def bfs(start, target):
    queue = deque([(start, 0)])  # (node, distance)
    visited = {start}
    while queue:
        node, dist = queue.popleft()
        if node == target: return dist
        for nei in neighbors(node):
            if nei not in visited:
                visited.add(nei)
                queue.append((nei, dist + 1))
    return -1

DFS / backtracking

def backtrack(state, choices):
    if is_goal(state):
        results.append(state[:])  # COPY, don't append the reference
        return
    for choice in choices:
        if valid(state, choice):
            state.append(choice)
            backtrack(state, choices)
            state.pop()  # undo choice

Binary search (lower bound)

def bsearch(arr, target):
    lo, hi = 0, len(arr)  # half-open [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo  # first index where arr[i] >= target

Top-K via heap

import heapq

def top_k_largest(arr, k):
    heap = []
    for x in arr:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)  # pop smallest, keep k largest
    return heap  # k largest, unordered

Dynamic programming (1D bottom-up)

def dp_1d(n):
    dp = [0] * (n + 1)
    dp[0] = base_case
    for i in range(1, n + 1):
        dp[i] = recurrence(dp, i)
    return dp[n]

Union-Find

class UF:
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]  # path compression
            x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True

8. Clarifying questions you should ALWAYS ask

Before writing a single line of code:

1. What's the input size? n=100 changes acceptable complexity from n=10^9.
2. What's the input range? Are values non-negative? Bounded? This rules patterns in or out.
3. Can the input be empty? Or have one element? Edge case the interviewer wants you to ask about.
4. Are there duplicates? Changes hash-map / set logic.
5. What output format? Index? Value? Boolean? Modify in place?
6. Can I modify the input? If yes, in-place algorithms are unlocked.
7. If multiple valid answers, return which? Any? Smallest? All?
8. Specific edge case: "What if the array has all the same element?" Picking one specific edge case to call out shows you think rigorously.

9. Signal words to pattern map

Signal in problem statement	Likely pattern
"Contiguous", "subarray", "substring"	Sliding window
"Pair", "two indices that sum to..."	Two pointers / hash map
"Top K", "k-th largest", "k-closest"	Heap / quickselect
"Shortest path", "minimum hops"	BFS (unweighted) / Dijkstra (weighted)
"All paths", "permutations", "subsets"	Backtracking
"Sorted array" + "search"	Binary search
"Overlapping subproblems", "optimal", "minimum/maximum cost"	Dynamic programming
"Connected", "groups", "merge sets"	Union-Find / DFS
"Prefix", "starts with"	Trie
"Schedule", "interval", "meeting room"	Greedy + sort by start/end
"Cycle detection in linked list / graph"	Floyd's tortoise & hare / DFS coloring
"Stream of data"	Two heaps, queue + hash

10. The 5 mistakes to avoid in the first 5 minutes

1. Jumping to code before clarifying. Burns time and signals poor process.
2. Asking only one clarifying question. Two is the minimum, three is the sweet spot.
3. Approaching the problem with no narration. Even silent thinking should have one-line summaries: "I'm thinking sliding window because we need contiguous..."
4. Writing code without an example. Walk through a tiny example with the interviewer to confirm understanding.
5. Choosing the optimal solution before sanity-checking the brute force. Even if you know the optimal, say "the brute force would be X with complexity Y, but we can do better by...". This shows reasoning, not memorization.

FAQ

What language is best for coding interviews in 2026?

Python is the best default for most candidates because of low syntax overhead, dict/list comprehensions, and the deque/heapq stdlib. Java is preferred at companies that explicitly require it (some Amazon teams, finance). C++ is necessary for systems/competitive backgrounds. Pick one language and use it consistently throughout prep.

Do I need to know amortized complexity?

Know it conceptually for two cases: dynamic array append (amortized O(1)) and union-find with path compression (amortized near-O(1)). You won't be asked to derive amortized analysis, but recognize these are NOT worst-case bounds.

What's the trick to identifying which pattern a problem uses?

Look for signal words (see section 9 above). "Contiguous"/"subarray" = sliding window. "K-th"/"top K" = heap. "Shortest path" = BFS. "All paths"/"permutations" = backtracking. With practice these signals become automatic in under 30 seconds.