Coding Interview Cheat Sheet for 2026: 14 Patterns, Templates, and Time Complexity Reference for CS New Grads

What a coding interview cheat sheet is in 2026

A coding interview cheat sheet is a one-page reference for the 14 algorithmic patterns, the time complexity of common data structures, the code templates you reach for under pressure, and the edge cases new grads forget. It is not a list of solved problems. It is the structural index you can rebuild from memory in 90 minutes, then drill into recall over the next two weeks.

The 2026 version differs from the 2020 version in three ways. First, the patterns themselves are stable. Two pointers is still two pointers. BFS is still BFS. Second, interview rubrics now grade communication and edge-case discipline more heavily than raw correctness. The cheat sheet must include the script for clarifying questions, not just the algorithm code. Third, AI-assisted prep has flooded the new-grad market with candidates who memorized solutions without internalizing patterns. The interview signal that separates you is whether you can articulate the pattern, not whether you can recall the solution.

This guide is the working version. Patterns. Code templates in Python and JavaScript. Anti-patterns. The script for the moment you freeze. A 30-day prep schedule. The complexity reference table you should be able to recite in under a minute. A glossary of terms most new grads have used a hundred times without being able to define cleanly.

I built the first version of this sheet at 2am the night before a Series B phone screen. The interviewer asked for the time complexity of inserting into the middle of a Python list. I said O(n). She nodded. I got the round. Then six more rounds went the same way. The point of the cheat sheet is the moment after, when you realize you knew the answer because you had written it on a page by hand the week before, not because you had read it somewhere.

The 14 patterns every coding interview tests

About 80% of CS new-grad coding rounds map to one of these 14 patterns. Topological sort and union-find sometimes get added as a 15th and 16th. Drill the 14 first.

The mistake new grads make: trying to memorize problem-by-problem. The mistake that wins them the round: reading the input shape and reaching for the pattern in under two minutes. Pattern recognition is the load-bearing skill.

The honest version of the table is that two pointers, sliding window, BFS, DFS, binary search, and DP show up in 70% of new-grad interviews. The other eight are the variations and the harder rounds. If you have one week, drill those six and skip the others.

Two pointers and sliding window: when and how

Two of the most-asked patterns and the easiest to confuse. Two pointers move based on a comparison condition. Sliding window expands or contracts based on a window invariant.

Two pointers (opposite-end variant)

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

The pattern: array is sorted. Two pointers start at opposite ends. Each comparison decides which pointer to move. Time O(n), space O(1). Variants: container with most water, valid palindrome with skipping, 3Sum (after sorting and outer loop).

Two pointers (same-direction variant)

function removeDuplicates(arr) {
  if (arr.length === 0) return 0;
  let slow = 0;
  for (let fast = 1; fast < arr.length; fast++) {
    if (arr[fast] !== arr[slow]) {
      slow++;
      arr[slow] = arr[fast];
    }
  }
  return slow + 1;
}

Both pointers move forward. The slow pointer tracks the next write position. Variants: move zeros, remove element by value, in-place compaction. Same pattern, different write rule.

Sliding window (fixed size)

def max_sum_fixed_window(arr, k):
    if len(arr) < k:
        return 0
    window_sum = sum(arr[:k])
    best = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        best = max(best, window_sum)
    return best

Window size k is fixed. Slide one position right per iteration. Variants: max average subarray, find anagrams (with a count comparison instead of a sum).

Sliding window (variable size)

def longest_unique_substring(s):
    seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

Window grows until invariant breaks, then shrinks. Trigger: "longest substring with at most K distinct chars," "minimum window containing all chars of T," "longest substring without repeating characters." The pattern is two while loops: outer expands right, inner contracts left until invariant restored.

The recognition signal: any problem that says "subarray" or "substring" with a constraint on the elements inside is almost always sliding window. If the constraint is a sorted-array search, it is two pointers instead.

BFS and DFS templates you should memorize

Tree and graph traversal. BFS for shortest path or level-by-level. DFS for path-based problems or when recursion depth is OK.

BFS template (Python)

from collections import deque

def bfs(start, graph):
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()
        # process node
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Three load-bearing details. First, deque not list. List pop(0) is O(n). Second, mark visited when you enqueue, not when you dequeue. Otherwise you enqueue the same node multiple times. Third, for level-order traversal, snapshot len(queue) at the start of each level and process exactly that many nodes.

BFS template with levels (Python)

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

DFS template (recursive, Python)

def dfs(node, visited, graph):
    if node in visited:
        return
    visited.add(node)
    # process node
    for neighbor in graph[node]:
        dfs(neighbor, visited, graph)

DFS template (iterative, JavaScript)

function dfs(start, graph) {
  const stack = [start];
  const visited = new Set([start]);
  while (stack.length) {
    const node = stack.pop();
    // process node
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);
      }
    }
  }
}

The choice between recursive and iterative DFS matters more than candidates realize. Python's default recursion limit is around 1000. Trees deeper than that crash. Use iterative DFS or call sys.setrecursionlimit() if you have a deep input. JavaScript has no enforced recursion limit but stack overflow happens around 10000 in most browsers. For interview purposes, recursive is cleaner for tree problems, iterative is safer for graph problems.

The signal: if the interviewer says "iterative DFS" they are testing whether you can write the explicit-stack version. If they say "DFS" without qualifying, recursive is fine and shorter.

Dynamic programming: the 5 sub-patterns

Most DP questions reduce to one of five sub-patterns. Once you can recognize which one, the recurrence falls out.

1D DP

State depends on the previous one or two values. Examples: climbing stairs, house robber, longest increasing subsequence.

def climbing_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

Space-optimization trick: most 1D DP problems do not need the full dp array. Keep the last 2-3 values in scalar variables.

2D DP

State depends on a row and a column. Examples: unique paths, edit distance, longest common subsequence.

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

The m+1 by n+1 table with a row of zeros and a column of zeros is the standard. The zero row and zero column represent the empty-string base case.

Knapsack (0/1)

Each item is either picked or skipped. Examples: subset sum, partition equal subset sum, target sum.

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

Iterate the inner loop in reverse to avoid using the same item twice. Forgetting the reverse iteration is the most common knapsack bug in new-grad interviews.

Longest Common Subsequence variants

LCS, edit distance, regular expression matching, wildcard matching. All 2D DP with a comparison-based recurrence. The skeleton is identical to the LCS code above. The recurrence inside the if and else branches changes per problem.

Interval DP

Problems where the recurrence is on a range [i, j]. Examples: matrix chain multiplication, burst balloons, palindrome partitioning. The signal: the answer depends on splitting the input at some index k and combining the left and right subproblems.

def palindrome_partition_min_cuts(s):
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if length == 2:
                is_pal[i][j] = s[i] == s[j]
            else:
                is_pal[i][j] = s[i] == s[j] and is_pal[i+1][j-1]
    cuts = [0] * n
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0
        else:
            cuts[i] = min(cuts[k] + 1 for k in range(i) if is_pal[k+1][i])
    return cuts[n - 1]

Interval DP shows up at the harder FAANG rounds. Most CS new-grad screens skip it. If you have 30 hours of prep total, deprioritize.

Graphs: representations and traversal

The graph question in a coding interview is usually one of three: is it connected, what is the shortest path, or what is the cheapest spanning tree. Representation choice affects everything.

Adjacency list (Python)

from collections import defaultdict

def build_graph(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # for undirected
    return graph

Use a defaultdict(list) so you do not have to check key existence. For weighted graphs, store tuples: graph[u].append((v, weight)).

Adjacency list (JavaScript)

function buildGraph(edges) {
  const graph = new Map();
  for (const [u, v] of edges) {
    if (!graph.has(u)) graph.set(u, []);
    if (!graph.has(v)) graph.set(v, []);
    graph.get(u).push(v);
    graph.get(v).push(u);
  }
  return graph;
}

Adjacency matrix

def build_matrix(n, edges):
    matrix = [[0] * n for _ in range(n)]
    for u, v in edges:
        matrix[u][v] = 1
        matrix[v][u] = 1
    return matrix

O(V^2) memory. Use only when the graph is dense (edges close to V^2) or when you need O(1) edge-existence queries. In a coding interview, almost always wrong unless the problem explicitly hands you the matrix.

Edge list

edges = [(u, v, weight), ...]

Useful for Kruskal's minimum spanning tree (sort by weight, union-find as you add). For everything else, convert to adjacency list first.

Dijkstra's algorithm (single-source shortest path)

import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist.get(node, float('inf')):
            continue
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist.get(neighbor, float('inf')):
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return dist

O((V+E) log V) with a binary heap. Works only with non-negative weights. For negative weights, switch to Bellman-Ford. For unweighted graphs, BFS is O(V+E) and shorter to write.

The interview rule: if asked for shortest path and the edges are unweighted, write BFS, not Dijkstra. Reaching for Dijkstra when BFS works is over-engineering, which is a downgrade signal.

Time complexity quick-reference table

Memorize this table. The interviewer will ask for the complexity of every solution. Five seconds is the acceptable answer time.

The single most-asked complexity question for CS new grads: "what is the worst case of a hash map?" The answer is O(n) because of hash collisions. Most candidates say O(1) and lose two points on the rubric for not knowing the worst case.

The second most-asked: "what is the time complexity of sorting in your language's standard library?" Python's sorted() is Timsort, O(n log n). JavaScript's Array.prototype.sort is engine-dependent but O(n log n) average in V8 (Chrome and Node.js). Both are stable.

Common data structure operations (Python and JavaScript)

The minimal API surface you need to recall under pressure. Push, pop, peek, contains.

Stack

Python (use a list):

stack = []
stack.append(x)           # push
top = stack[-1]            # peek
val = stack.pop()          # pop
exists = x in stack        # O(n) contains

JavaScript (use an Array):

const stack = [];
stack.push(x);             // push
const top = stack[stack.length - 1];  // peek
const val = stack.pop();   // pop
const exists = stack.includes(x);     // O(n) contains

Queue

Python (use collections.deque):

from collections import deque
queue = deque()
queue.append(x)            # enqueue
front = queue[0]           # peek
val = queue.popleft()      # dequeue (O(1))

JavaScript (no built-in deque; use an Array with caveat):

const queue = [];
queue.push(x);             // enqueue
const front = queue[0];    // peek
const val = queue.shift(); // dequeue (O(n), array reindex)

The JavaScript caveat is load-bearing. Array.shift() is O(n) because it reindexes the entire array. For queue-heavy problems in JavaScript, write a circular-buffer wrapper or use a linked list. This trips up new grads who treat both arrays the same across languages.

Min-heap

Python (use heapq):

import heapq
heap = []
heapq.heappush(heap, x)            # O(log n) insert
smallest = heap[0]                  # O(1) peek
val = heapq.heappop(heap)           # O(log n) extract-min
top_k = heapq.nlargest(k, arr)      # O(n log k) top-k

Python's heapq is min-heap. For max-heap, negate the values on push and on pop: heapq.heappush(heap, -x) and -heapq.heappop(heap).

JavaScript (no built-in heap):

// Bare-bones min-heap. For interview prep, memorize this.
class MinHeap {
  constructor() { this.data = []; }
  push(x) {
    this.data.push(x);
    this._siftUp(this.data.length - 1);
  }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) {
      this.data[0] = last;
      this._siftDown(0);
    }
    return top;
  }
  peek() { return this.data[0]; }
  _siftUp(i) {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.data[p] <= this.data[i]) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  _siftDown(i) {
    const n = this.data.length;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let smallest = i;
      if (l < n && this.data[l] < this.data[smallest]) smallest = l;
      if (r < n && this.data[r] < this.data[smallest]) smallest = r;
      if (smallest === i) break;
      [this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]];
      i = smallest;
    }
  }
}

If you are interviewing in JavaScript, memorize the MinHeap class. It comes up in top-K, median-of-stream, Dijkstra, and merge-K-sorted-lists problems. The absence of a built-in is the most-cited reason new grads switch to Python mid-prep.

Hash map

Python:

d = {}
d[key] = value                      # insert / update
val = d.get(key, default)           # safe lookup
exists = key in d                   # O(1) contains
del d[key]                           # delete
for k, v in d.items(): ...          # iterate

JavaScript:

const m = new Map();
m.set(key, value);                  // insert / update
const val = m.get(key);              // returns undefined if missing
const exists = m.has(key);           // O(1) contains
m.delete(key);                       // delete
for (const [k, v] of m) {}           // iterate

JavaScript object literals ({}) work as hash maps but stringify keys. Use Map instead unless you have a specific reason. The interview signal of fluency: reaching for Map over Object shows you know the difference.

Edge cases that trip up new grads (the eight-item list)

Before writing code, talk through these eight cases. Interviewers grade communication and edge-case discipline more heavily in 2026 rubrics than they did in 2020.

1. Empty input. Array [], string "", null tree, empty graph. Most problem statements do not specify; ask. The candidate who handles empty input gracefully (return early, return a sensible default) avoids the 5-point deduction on the rubric.

2. Single-element input. Array [x], single-character string. Many algorithms break on the boundary between "no comparison" and "first comparison." Test on the whiteboard with one element before moving on.

3. Duplicates allowed. "Find K elements" can mean K distinct or K including duplicates. "Two Sum" with nums = [3, 3] and target = 6 should return [0, 1]. Confirm.

4. Negative numbers. Many candidates write the algorithm assuming positive integers, then it breaks on [-1, -2, 3]. Especially common in subarray-sum and maximum-product problems. The classic gotcha: maximum-product-subarray has to track both max and min because two negatives multiply to a positive.

5. Integer overflow. Less common in Python (arbitrary precision) but real in JavaScript (Number.MAX_SAFE_INTEGER is about 9 quadrillion) and Java (32-bit int overflows around 2 billion). For competitive-programming problems with large inputs, mention overflow as a risk.

6. Off-by-one on indices. Loop bounds, especially range(n) versus range(n+1). Two-pointer movement rules. The fix: always trace the algorithm on a 3-element example by hand. Catches 90% of off-by-one bugs before you write code.

7. The problem's stated bounds. "Array length up to 10^5" tells you O(n^2) is fine and O(n^3) is not. "Array length up to 10^9" tells you you need a streaming or math-based approach, not a loop. Read the bounds before reaching for the algorithm.

8. Already-sorted or reverse-sorted input. Quicksort with a bad pivot strategy degrades to O(n^2) on sorted input. Some DP solutions short-circuit. Mention this when the problem says "input may be partially sorted."

The mistake new grads make: discovering these cases by stumbling into wrong answers mid-coding. The fix: list them out loud during the clarifying-questions phase. The interviewer notes "candidate identified edge cases proactively" on the rubric, which is a one-bump signal on most scoring sheets.

The "I do not know but here is how I would think about it" script

The moment you freeze is the moment you lose. The script below works because it converts "I do not know" into "I am reasoning through this," which is the actual signal interviewers grade.

Four steps. Memorize the order.

Step 1: Restate the problem in your own words. Slow down. "Let me make sure I understand. You want me to..." Half the problems that feel hard become normal once you say them back. The 10 seconds of restating buys you 10 seconds of thinking.

Step 2: Walk through a small example by hand. "Let me try this with [1, 3, 5, 7] and target 8." Use 3-5 elements. Trace it on the whiteboard or shared editor. The act of working an example often surfaces the pattern.

Step 3: Describe a brute-force solution and its complexity. Even if you know it is too slow. "The naive solution is to check every pair, which is O(n^2). That is too slow for the bounds, but let me start there and optimize." Brute force first is the senior-engineer move. The interviewer is looking for whether you can articulate the slow solution before chasing the fast one.

Step 4: Ask 'can I trade memory for time here' and brainstorm. Almost every speedup involves caching, hashing, or precomputation. "What if I store the seen values in a hash map as I go? That would give me O(1) lookups instead of O(n), making the total O(n)." Even if the hash-map answer is wrong, the question is the right one.

The script works because interview rubrics in 2026 explicitly grade problem decomposition over raw correctness. A candidate who gets the wrong answer with clean reasoning often beats a candidate who gets the right answer through guesswork. I have seen this play out a hundred times. Reasoning is the resilient signal. Correctness is the brittle one.

Where new grads break the script: they apologize too much. "Sorry I do not remember this one. Sorry I am thinking out loud. Sorry can I try a different approach?" Stop apologizing. Replace every "sorry" with "let me." It is the same time spent, signals the opposite confidence.

Seven anti-patterns interviewers downgrade for in 2026

These are the patterns I see most in mock-interview review sessions. Each one is a documented rubric downgrade at most companies that grade with a scoring sheet.

1. Silent coding. Writing code without narrating your reasoning. The interviewer cannot grade what you are thinking. Even if you get the right answer, you score lower on communication. The fix: verbalize the next 30 seconds of intent before you write each block. "I am going to use a hash map to track seen values, then iterate once and check for the complement."

2. Jumping to code before clarifying. Reading the problem and immediately typing. You should spend the first 2-3 minutes asking questions: input constraints, edge cases, expected output format. The candidate who clarifies signals senior-level thinking. The candidate who starts coding signals junior.

3. Skipping edge cases. Writing the happy path, getting it working, then handing back the round without ever mentioning empty inputs, single elements, or duplicates. The fix: list the edge cases out loud before coding, then mention each one again as you finish.

4. Reaching for the brute force without flagging it as such. Writing the O(n^2) nested loop without saying "this is the brute force, I know it is O(n^2), I will optimize next." The interviewer interprets undeclared brute force as the only approach you can think of, not the deliberate starting point.

5. Refusing the hint when offered. When an interviewer drops a hint, they are signaling "you are close." Take it. Build on it. The candidate who insists on their wrong approach instead of integrating the hint signals stubbornness. The candidate who says "oh, that is a great direction, let me think about how to apply it" signals coachability, which is the same signal a manager will look for on your first project.

6. Treating the interviewer as adversary. Defensive body language, terse answers to follow-up questions, arguing with feedback. The interviewer is grading whether they want to work with you. The candidate who treats the round as collaboration scores higher even when the technical answer is the same.

7. Writing Java-in-Python or Python-in-Java. Initializing an empty list and appending in a loop when a comprehension would do. Using range(len(arr)) instead of enumerate(arr). Building a counter dict manually instead of collections.Counter. Writing a for loop in JavaScript when arr.map would be cleaner. The interviewer reads non-idiomatic code as "candidate used this language but did not learn it." Idiom fluency is the senior signal at the new-grad bar.

The honest version of the list: most candidates have at least three of these. Pick the two you do most often (most candidates have silent coding and skipping edge cases) and drill them out in your next five mock interviews. The other five fix themselves once those two are gone.

30-day prep schedule (one you can finish)

Built for a CS new grad who has 2-3 hours per day and one confirmed interview in 30 days. Adjust if your timeline differs. Most plans on the internet assume 6 hours per day. That is not realistic for someone working part-time or balancing other applications.

Week 1: patterns (14 days compressed to 7)

• Day 1: two pointers + sliding window (read, write template from memory, solve 2 problems)
• Day 2: fast and slow pointers + in-place linked list reversal
• Day 3: tree BFS + tree DFS
• Day 4: merge intervals + cyclic sort
• Day 5: two heaps + top-K elements + K-way merge
• Day 6: modified binary search + subsets and combinations
• Day 7: dynamic programming (drill the 5 sub-patterns)

Two problems per pattern per day. Time-boxed at 30 minutes for easy, 45 for medium. If you cannot solve in the time box, read the solution, understand it, then redo from scratch the next morning.

Week 2: Mediums

40 medium problems across the 14 patterns. Pick from Blind 75 or NeetCode 150. Time-box every attempt at 45 minutes. Track which patterns are slow (over 45 minutes) and which are fast (under 30). The slow ones get the extra problems in week 4.

The goal in week 2 is pattern fluency. You should be able to read the problem, identify the pattern within 2 minutes, write the brute force in 5 minutes, and write the optimized solution in 30. Anything slower is a pattern you have not internalized yet.

Week 3: mocks

5-7 mock interviews. Each 45 minutes. Each with verbalized reasoning. Use a peer, a paid mock-interview service, or an AI-driven mock interview tool. The first mock will feel brutal. By the fifth, the structure of "clarify, brute force, optimize, edge cases" should feel automatic.

The signal you are ready: you can do a mock without referring to the cheat sheet, get the right answer 70% of the time, and articulate your reasoning the whole way through. If you hit 70% by mock 5, you are ready for the live round.

Week 4: weak spots and review

Two-day buffer. Two days of weak-pattern drills. Two days of review.

• Days 1-2: drill the patterns you flagged slow in week 2.
• Days 3-4: re-solve the 10 hardest problems from weeks 1-2 without looking at past solutions.
• Days 5-6: one final mock interview, then rebuild the cheat sheet from memory in one sitting.
• Day 7: rest. The day before the interview is for sleep, not study. Cramming the night before is a known anti-pattern.

The 30-day plan does not require 600 LeetCode problems. It requires 14 patterns plus 40 mediums plus 7 mocks. About 75 problems total. The candidate who does this plan and does the verbalized-reasoning work outperforms the candidate who does 400 problems silently.

One thing I would add: do not skip week 3. Solo grinding past problem 75 has steep diminishing returns. The next 20% of improvement lives in mocks. Most candidates skip mocks because they feel exposed. That is the point. The exposure is the prep.

Coding interview key terms glossary

Terms most new grads have used a hundred times without being able to define cleanly. The interviewer will sometimes ask for a definition mid-round. Be ready.

Time complexity

How runtime grows with input size, expressed in big-O notation. O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic (the sorting bar), O(n^2) quadratic, O(2^n) exponential. Memorize the order: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).

Space complexity

How memory usage grows with input size. Same notation as time. An algorithm can have O(n) time and O(1) space (two pointers) or O(n) time and O(n) space (hash-map two sum). Tradeoff between the two is the most common interview discussion.

Amortized complexity

The average cost per operation over a long sequence of operations, even when individual operations are sometimes expensive. Python list.append is O(1) amortized because most appends are cheap and the occasional resize is shared across many cheap operations. Hash-map insert is similar.

Stable sort

A sort that preserves the relative order of equal elements. Python's sorted is stable (Timsort). JavaScript's Array.prototype.sort is stable in modern V8. Merge sort is stable; quick sort and heap sort are not. The interview question: "is the standard-library sort stable in your language?" Know the answer.

In-place algorithm

An algorithm that modifies its input directly without allocating new memory proportional to the input size. Two-pointer remove-duplicates is in-place. Sorting a copy of the array is not. In-place algorithms have O(1) extra space.

Recurrence relation

A formula that defines the answer to a problem using the answers to smaller subproblems. The skeleton of every DP solution. The recurrence for Fibonacci: fib(n) = fib(n-1) + fib(n-2). The recurrence for edit distance is more complex but the same pattern.

Memoization

Top-down DP. Cache the result of each subproblem the first time it is computed; return the cached result on subsequent calls. Implemented in Python with @functools.lru_cache or a manual dict. The alternative is bottom-up tabulation, which fills a DP table iteratively.

Greedy algorithm

An algorithm that makes the locally optimal choice at each step. Works only when the local optimum leads to the global optimum (the "greedy choice property"). Examples: activity selection by earliest end time, coin change with denominations that have the greedy property. Greedy is wrong by default; you must prove it works before relying on it.

Divide and conquer

An algorithmic strategy that breaks the problem into smaller independent subproblems, solves each recursively, and combines the results. Examples: merge sort, quick sort, binary search, fast Fourier transform. Distinct from DP (which has overlapping subproblems) and from greedy (which does not recurse).

Topological sort

An ordering of the nodes of a directed acyclic graph such that for every edge u -> v, u comes before v in the order. Used in dependency resolution, course scheduling, build systems. Two algorithms: Kahn's (BFS with in-degree counting) and DFS-based (post-order traversal). One of the patterns sometimes added as a 15th to the canonical list.

Union-find (disjoint set)

A data structure that tracks elements partitioned into disjoint sets. Two operations: find (which set is this element in) and union (merge two sets). Used in Kruskal's MST, connectivity problems, dynamic connectivity. With path compression and union-by-rank, each operation is nearly O(1) amortized. The 16th pattern.

Backtracking

A general search technique that builds candidates incrementally and abandons (backtracks from) any candidate that cannot lead to a valid solution. Used in subsets, permutations, N-queens, Sudoku, word search. Implemented as recursive DFS with a "choose, explore, unchoose" pattern.

Bit manipulation

Algorithms that operate on the binary representation of integers using bitwise operators (&, |, ^, ~, <<, >>). Common patterns: check if a bit is set, count set bits, find the single non-duplicate in an array of pairs (XOR all). Less common in new-grad rounds; more common at senior levels.

Related guides

• Python interview questions: the language-specific layer on top of these algorithm patterns.
• LeetCode 75 vs Blind 75 vs NeetCode 150: which curated list to grind alongside this cheat sheet.
• System design basics for new grads: the next round after the coding screen at most large employers.
• Mock interview practice: how to drill these patterns under realistic timing pressure.
• Technical phone screen tactics: how to apply the cheat sheet under 45 minutes of live observation.
• HackerRank tech interview guide: the platform most likely to host your coding OA.
• CoderPad live coding interview: the platform most likely to host your live coding round.

About the author: Alex Chen is the founder of InterviewChamp.AI, building AI interview prep for the new-grad CS market and writing about the modern interview gauntlet from the inside.