Patterns

Common Interview Patterns

PatternsFREELast updated: May 2026 · By gitGood Editorial

The recurring shapes - sliding window, two pointers, fast/slow, BFS/DFS, backtracking, DP, divide & conquer, binary search variants, union-find, topological sort. Each entry: when to reach for it, the template, complexity, and which classic problems use it.

How to use this sheet

When a problem looks new, the trick is rarely a new algorithm - it's recognizing which of these ~12 shapes it maps onto. For each pattern, the first instinct is the trigger condition ("contiguous subarray with constraint" -> sliding window; "shortest path in unweighted graph" -> BFS). Memorize the trigger first, the template second.

The patterns

Sliding window

When to use: Contiguous subarray / substring satisfying a constraint (max sum of size k, longest substring without repeating chars, smallest subarray with sum >= S, longest substring with at most k distinct chars).
Template: left = 0 state = empty best = identity for right in 0..n-1: state.add(arr[right]) while not valid(state): state.remove(arr[left]) left += 1 best = combine(best, right - left + 1) return best
Complexity: O(n) time, O(k) space (k = window contents - often O(1) or O(alphabet)).
Examples: Longest Substring Without Repeating Characters
Minimum Window Substring
Longest Substring with At Most K Distinct Characters
Maximum Sum Subarray of Size K (fixed window)
Permutation in String

Two pointers (opposite ends)

When to use: Sorted array, palindrome check, pair / triplet with target sum, container-with-most-water-style optimization.
Template: left = 0 right = n - 1 while left < right: s = combine(arr[left], arr[right]) if s == target: return ... elif s < target: left += 1 else: right -= 1
Complexity: O(n) after an O(n log n) sort if input is unsorted. 3-Sum is O(n^2) (outer loop + 2-pointer inner).
Examples: Two Sum II (sorted)
Valid Palindrome
Container With Most Water
3-Sum / 4-Sum
Trapping Rain Water (two-pointer variant)

Fast / slow pointers (Floyd's tortoise & hare)

When to use: Cycle detection in linked list / functional graph, finding the middle of a list, finding the cycle entry, duplicate detection in [1..n] array (treated as linked list).
Template: slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: cycle detected # To find cycle entry: reset one pointer to head, advance both by 1 until they meet again.
Complexity: O(n) time, O(1) space.
Examples: Linked List Cycle / Linked List Cycle II
Find the Duplicate Number
Middle of the Linked List
Happy Number
Palindrome Linked List

BFS (breadth-first search)

When to use: Shortest path in an unweighted graph or grid, level-order traversal of a tree, multi-source shortest path (rotting oranges, 01-matrix), word ladder.
Template: queue = deque([start]) visited = {start} dist = {start: 0} while queue: node = queue.popleft() for nxt in neighbors(node): if nxt not in visited: visited.add(nxt) dist[nxt] = dist[node] + 1 queue.append(nxt)
Complexity: O(V + E) time, O(V) space.
Examples: Word Ladder
Rotting Oranges
Shortest Path in Binary Matrix
Binary Tree Level Order Traversal
01 Matrix

DFS (depth-first search)

When to use: Tree / graph traversal, connectivity, cycle detection, path enumeration, topological sort, articulation points / bridges, flood fill.
Template: def dfs(node, visited): if node in visited: return visited.add(node) pre_order_work(node) for nxt in neighbors(node): dfs(nxt, visited) post_order_work(node) # Iterative variant: use an explicit stack.
Complexity: O(V + E) time, O(V) space (recursion depth).
Examples: Number of Islands
Clone Graph
Course Schedule (cycle detection in directed graph)
Path Sum II
All Paths From Source to Target

Backtracking

When to use: Enumerate / search a combinatorial space (subsets, permutations, combinations, n-queens, sudoku, word search). Recurse, mutate, recurse, undo.
Template: def backtrack(state, choices): if is_solution(state): record(state) return for choice in choices: if not feasible(state, choice): continue apply(state, choice) backtrack(state, remaining(choices, choice)) undo(state, choice)
Complexity: Exponential in the worst case (subsets O(2^n), permutations O(n!)). Pruning is the difference between accepted and TLE.
Examples: Subsets / Subsets II
Permutations / Permutations II
Combination Sum
N-Queens
Word Search
Sudoku Solver

Dynamic programming - 1D

When to use: State depends on a single index. Examples: "longest / count / min / max" over a sequence with overlapping subproblems.
Template: dp = [base_case for _ in range(n)] for i in 1..n-1: dp[i] = recurrence(dp[i-1], dp[i-2], ..., arr[i]) return dp[n-1] (or max(dp))
Complexity: O(n) time, O(n) space (often collapses to O(1) with rolling variables).
Examples: Climbing Stairs
House Robber
Maximum Subarray (Kadane)
Longest Increasing Subsequence (O(n^2) DP or O(n log n) patience)
Decode Ways

Dynamic programming - 2D

When to use: Two strings, two sequences, or a grid. State is (i, j).
Template: dp = [[base for _ in range(m+1)] for _ in range(n+1)] for i in 1..n: for j in 1..m: dp[i][j] = recurrence(dp[i-1][j], dp[i][j-1], dp[i-1][j-1], a[i], b[j]) return dp[n][m]
Complexity: O(n * m) time, O(n * m) space (often collapses to O(min(n, m))).
Examples: Edit Distance
Longest Common Subsequence
Unique Paths / Unique Paths II
Distinct Subsequences
Interleaving String

DP - state machine

When to use: The problem is naturally a finite-state automaton: each state encodes "what mode are we in" (holding stock vs not, just sold vs cooled-down vs free, k transactions remaining).
Template: # Define explicit states. For "Best Time to Buy and Sell Stock with Cooldown": # states: holding, sold (cooldown), rest # transitions: # holding[i] = max(holding[i-1], rest[i-1] - price[i]) # sold[i] = holding[i-1] + price[i] # rest[i] = max(rest[i-1], sold[i-1]) return max(sold[n-1], rest[n-1])
Complexity: O(n * S) time where S = number of states (often constant), O(S) space.
Examples: Best Time to Buy/Sell Stock series (with cooldown / fee / k transactions)
Paint House III
String matching DP (regex / wildcard)
Maximum Profit in Job Scheduling

Divide and conquer

When to use: Problem can be split into independent subproblems whose solutions combine cheaply. Merge sort, quicksort, closest-pair, fast exponentiation, segment tree build.
Template: def solve(arr, lo, hi): if hi - lo <= base_case_size: return base(arr, lo, hi) mid = (lo + hi) // 2 left = solve(arr, lo, mid) right = solve(arr, mid+1, hi) return combine(left, right)
Complexity: Master theorem: T(n) = a*T(n/b) + f(n). For merge sort a=2, b=2, f(n)=O(n) -> T(n) = O(n log n).
Examples: Merge Sort / Count of Smaller Numbers After Self
Quicksort / Quickselect
Maximum Subarray (D&C variant)
Pow(x, n) by binary exponentiation
Median of Two Sorted Arrays

Binary search variants

When to use: Sorted (or implicitly sorted) input, OR the answer space is monotonic ("can we do it with capacity C? smaller C -> harder, larger C -> easier" -> binary-search on C).
Template: # Classic: find target. lo, hi = 0, n - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1 # Lower bound (first index >= target): lo, hi = 0, n while lo < hi: mid = (lo + hi) // 2 if arr[mid] < target: lo = mid + 1 else: hi = mid # Search-on-answer: def feasible(x): ... # monotonic in x lo, hi = lo_bound, hi_bound while lo < hi: mid = (lo + hi) // 2 if feasible(mid): hi = mid else: lo = mid + 1 return lo
Complexity: O(log n) per search; O(n log n) for n searches; O(log range * cost(feasible)) for search-on-answer.
Examples: Search in Rotated Sorted Array
Find First and Last Position
Capacity to Ship Packages within D Days (search-on-answer)
Koko Eating Bananas (search-on-answer)
Median of Two Sorted Arrays
Find Peak Element

Union-find (disjoint set)

When to use: Dynamic connectivity, grouping by equivalence relation, Kruskal MST, detecting redundant edges in an undirected graph, accounts merge, friend circles.
Template: parent = list(range(n)) rank = [0] * n def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # path compression x = parent[x] return x def union(a, b): ra, rb = find(a), find(b) if ra == rb: return False if rank[ra] < rank[rb]: ra, rb = rb, ra parent[rb] = ra if rank[ra] == rank[rb]: rank[ra] += 1 return True
Complexity: Effectively O(1) amortized per op (inverse Ackermann alpha(n)).
Examples: Number of Connected Components
Redundant Connection
Accounts Merge
Kruskal's MST
Most Stones Removed With Same Row or Column

Topological sort

When to use: Order tasks with prerequisites, build orderings, course schedule, package install order, expression evaluation in DAGs. Two flavors: Kahn (BFS / in-degree) and DFS post-order.
Template: # Kahn's algorithm: indeg = [0] * n for u, v in edges: indeg[v] += 1 q = deque([u for u in range(n) if indeg[u] == 0]) order = [] while q: u = q.popleft() order.append(u) for v in adj[u]: indeg[v] -= 1 if indeg[v] == 0: q.append(v) if len(order) != n: cycle detected return order
Complexity: O(V + E) time, O(V) space.
Examples: Course Schedule / Course Schedule II
Alien Dictionary
Minimum Height Trees
Sequence Reconstruction
Build dependency resolver

Greedy

When to use: Local-optimal choice at each step yields global optimum. Always justify why greedy is provably correct (exchange argument). Common: interval scheduling, Huffman coding, jump game.
Template: sort by some key result = init for item in sorted_items: if compatible(result, item): take(item) return result
Complexity: O(n log n) usually dominated by the sort. O(n) once sorted.
Examples: Jump Game / Jump Game II
Non-overlapping Intervals
Minimum Number of Arrows to Burst Balloons
Task Scheduler
Gas Station

Monotonic stack / deque

When to use: "Next greater / next smaller" queries, sliding window max/min, largest rectangle in histogram, stock span.
Template: # Next greater element (right): stack = [] # stores indices, values strictly decreasing from bottom to top ans = [-1] * n for i in range(n): while stack and arr[stack[-1]] < arr[i]: j = stack.pop() ans[j] = i stack.append(i)
Complexity: O(n) time, O(n) space.
Examples: Next Greater Element I/II
Daily Temperatures
Largest Rectangle in Histogram
Sliding Window Maximum (deque)
Trapping Rain Water (stack variant)

Other cheat sheets

Big-O Reference

Algorithms

Time and space complexity for the data structures, sorting algorithms, and search routines that show up in coding interviews. Skim the row, remember the row, defend the row in an interview.

Design Tradeoffs

Systems

The recurring forks in system design interviews. CAP, PACELC, sync vs async, push vs pull, SQL vs NoSQL, sharding shapes, consistency models, cache strategies, idempotency, and rate limiting. For each, the options and when to choose each.

Unix Essentials

Tools

Filesystem layout, the commands you actually use (find / grep / awk / sed / xargs), processes and signals, networking, permissions, basic shell scripting, and a vi survival kit.

SQL Essentials

Tools

Query clause order, every JOIN type and when to use it, aggregates vs window functions, what indexes actually buy you, transaction isolation levels, and the NULL / WHERE-vs-HAVING / EXISTS-vs-IN gotchas interviewers fish for.

Git Essentials

Tools

The everyday commands, every undo scenario mapped to its fix, rebase vs merge with a side to pick, interactive rebase, bisect, the reflog safety net, stash, and the flags worth aliasing.

Docker & K8s

Tools

The docker and kubectl commands you reach for daily, Dockerfile best practices, how layer caching actually works, the core k8s objects in one screen, requests vs limits, liveness vs readiness, and a step-by-step CrashLoopBackOff debug flow.

REST API Design

Systems

Method semantics and idempotency, the ~15 status codes that matter, resource naming rules, offset vs cursor pagination, versioning and auth tradeoffs, error body conventions, rate-limit headers, and the smells reviewers flag.

STAR Method

Patterns

The STAR structure with timing, what interviewers actually grade, eight question archetypes and how to frame each, the anti-patterns that sink answers (rambling, "we" instead of "I", no metrics), and a 30-second answer skeleton.

Networking

Systems

TCP vs UDP, the TLS and TCP handshakes, HTTP versions, status codes, DNS resolution, the OSI and TCP/IP layer models, and the ports you are expected to know in an interview.

Regex

Tools

Anchors, character classes, quantifiers, groups, alternation, lookarounds, backreferences, and flags - plus practical patterns and the gotchas that trip people up in interviews.

Linux Perf

Tools

The USE method, a first-five-minutes triage runbook, and the CPU, memory, disk, network, and tracing commands you reach for when a Linux box is misbehaving.

Concurrency

Patterns

A fast reference for concurrency primitives, synchronization tradeoffs, the memory model, and the classic bugs that show up in systems interviews and real code.

Distributed Systems

Systems

A reference for the theorems, consistency models, replication and partitioning strategies, delivery guarantees, and resilience patterns that come up in system design interviews.

Kafka & Messaging

Systems

Topics, partitions, and consumer groups, the three delivery semantics and how Kafka actually achieves each, ordering guarantees, rebalancing, retention vs compaction, and a straight Kafka vs SQS vs RabbitMQ vs Kinesis comparison.

GraphQL

Systems

Schema, types, and resolvers, the three operation kinds, the N+1 problem and DataLoader, cursor vs offset pagination, error handling that actually works, security (depth limiting, query cost), and an honest answer to 'when does REST beat GraphQL'.

Terraform & IaC

Tools

State and why it must be remote and locked, the init/plan/apply lifecycle, modules and variables, count vs for_each, workspaces, import and drift, a command table, and the gotchas (prevent_destroy, secrets in state) that mark real production experience.

LLMs & Prompting

Systems

How LLMs work in one paragraph, the knobs (context window, temperature, top-p), system vs user prompts, few-shot and chain-of-thought, RAG and embeddings, the fine-tune-vs-prompt decision, tool calling, eval basics, and the interview questions teams actually ask now.

SQL Query Tuning

Tools

How B-tree indexes actually work, composite index column order, covering indexes, reading EXPLAIN ANALYZE, why the planner ignores your index, join algorithms, N+1, keyset pagination, and the 'why is this query slow' scenarios interviews are built on.

AWS CLI

Tools

Profiles and credential resolution, the --query vs --filters distinction that trips people up, and the EC2 / S3 / IAM / VPC / Lambda / CloudWatch commands you actually reach for under time pressure.

Azure CLI

Tools

Login and subscription juggling, the resource-group model everything hangs off, JMESPath --query, and the VM / storage / AKS / Key Vault / App Service commands worth knowing cold.

gcloud CLI

Tools

Configurations and the project/ADC model, gcloud vs gsutil vs bq, and the Compute Engine / GKE / Cloud Run / IAM / BigQuery commands that carry the ACE and Professional exams.

Helm

Tools

Chart anatomy, the values precedence order that explains every "why did my override not apply", install vs upgrade --install, template vs dry-run vs diff, and rollback.

GitHub CLI

Tools

The gh commands that remove the browser round-trip: PR create/review/merge, issues, run watching and log digging on Actions, releases, and gh api for anything without a command.

Cloud CLI Comparison

Tools

The same operation in all three CLIs, side by side - compute, storage, networking, IAM, Kubernetes, serverless and logging - plus the service-name mapping and the model differences the equivalences hide.

Practice the patterns

Reading is the floor. The signal in interviews comes from working problems out loud and defending your tradeoffs. Spin up an AI mock interview or run a coding challenge to put these to work.

Coding challenges AI mock interview