SWE Interview Preparation MOC

Map of Content for software-engineering interview preparation. Covers algorithms, data structures, system-design building blocks, and the interview process itself. Each leaf is an atomic note; this page is the index — follow the wikilinks. Notes that don’t yet exist appear gray in Obsidian and act as a TODO list.

How to Use This MOC

1. Start at Foundations if you don’t already have an internal model of asymptotic analysis. Every other note assumes it.
2. Pick a category and go deep rather than skimming everything. Interviews reward depth.
3. Each leaf note follows the same structure: plain-English intuition → tiny worked example → pseudocode → Python → complexity analysis with proof sketch → variants → common interview problems → pitfalls. Read the whole note; the pitfalls section is where the interview-relevant nuance lives.
4. Code in two forms: pseudocode (for the algorithm structure, language-agnostic) and Python (for a runnable example you can paste into an editor and probe).

Uncertain

Interview content evolves with hiring trends. The list below reflects the current consensus of what shows up in 2024–2026 FAANG-style and broader-tech-company loops, but specific company practices drift. Verify against recent (last 12 months) interview reports for any specific employer before committing prep time to a niche topic.

---

0. Foundations — Asymptotic Reasoning

The vocabulary every other note uses. If you can’t read these comfortably, the rest will not stick.

• Big-O Notation — upper-bound asymptotic notation; what “drop constants” really means
• Big-Omega and Big-Theta — lower-bound and tight-bound notation; less-asked but matters for correctness
• Master Theorem — closed-form solutions for divide-and-conquer recurrences
• Amortized Analysis — banker’s, accountant’s, aggregate methods; why dynamic-array push is O(1) amortized
• Recurrence Relations — how to set up and solve recurrence equations from recursive code
• Recursion vs Iteration — stack frames, tail-call status, conversion patterns
• Space Complexity — auxiliary vs total; recursion-stack accounting

1. Sorting

The single most over-asked category historically. Modern interviews have shifted away from “implement quicksort” toward “use a sort and reason about its cost,” but every variant below is fair game.

Comparison Sorts

• Bubble Sort — pedagogical only; never used in production but interviewers ask “what’s wrong with it”
• Insertion Sort — O(n²) worst, but O(n) on nearly-sorted; used as base case in real sort libs
• Selection Sort — O(n²) always; useful only for write-minimization (rare)
• Merge Sort — D&C; stable; O(n log n) guaranteed; O(n) extra space
• Quicksort — in-place; O(n log n) average, O(n²) worst; pivot strategy matters
• Heap Sort — O(n log n) worst; in-place; not stable
• Tim Sort — Python and Java’s default; merge + insertion hybrid; adaptive
• Intro Sort — C++ std::sort; quicksort + heap-sort fallback

Non-Comparison Sorts

• Counting Sort — O(n + k) where k is the value range; only for bounded integers
• Radix Sort — O(d · (n + b)) for d-digit numbers in base b; can beat O(n log n) for fixed-width keys
• Bucket Sort — O(n) expected for uniformly distributed inputs

Selection (related to sorting)

• Quickselect — find k-th smallest in O(n) average; Hoare’s algorithm
• Median of Medians — O(n) worst-case k-th selection; theoretically beautiful, rarely used

2. Searching

• Linear Search — baseline; mention in interviews when O(log n) isn’t possible
• Binary Search — the workhorse; three templates (exact / leftmost / rightmost); off-by-one minefield
• Binary Search on Answer — when the answer space is monotonic, binary-search the answer (e.g., “minimum capacity to ship in D days”)
• Ternary Search — for unimodal functions; rare in interviews
• Exponential Search — for unbounded or unknown-length sorted sequences
• Interpolation Search — for uniformly distributed sorted data

3. Arrays & Strings — Core Patterns

Patterns more than algorithms. Recognizing the pattern from the problem statement is the skill.

• Two Pointers — opposite-end and same-direction; pair-sum, partition, dedup
• Sliding Window — fixed-size and variable-size; longest-substring problems
• Prefix Sums — O(1) range-sum after O(n) preprocessing; subarray-sum-equals-k
• Difference Arrays — range-update in O(1), point-query in O(n) after preprocessing
• Kadane’s Algorithm — max subarray sum in O(n); textbook DP
• Cyclic Sort — for “missing number in 1..n” family
• Dutch National Flag — three-way partition; sort 0/1/2 in one pass

4. Hashing

• Hash Table — open addressing vs chaining; load factor; amortized O(1)
• Hash Function Design — universal hashing, MurmurHash, SipHash; what makes a hash “good”
• Bloom Filter — probabilistic membership; no false negatives, controllable false positives — also in System Design
• Count-Min Sketch — probabilistic frequency counting
• HyperLogLog — probabilistic cardinality estimation

5. Linked Lists

• Singly Linked List — basic operations and complexity
• Doubly Linked List — when bidirectional traversal earns its memory cost
• Linked List Reversal — iterative and recursive; foundational subroutine
• Linked List Cycle Detection — Floyd’s tortoise and hare; one of the most-asked
• Merge Two Sorted Lists — building block for merge sort on lists
• LRU Cache — doubly-linked list + hash map — also in System Design

6. Stacks, Queues, Deques

• Stack — LIFO; recursion’s data-structure twin
• Queue — FIFO; BFS’s substrate
• Deque — double-ended; sliding-window-maximum substrate
• Monotonic Stack — next-greater / next-smaller patterns; histogram problems
• Monotonic Deque — sliding-window min/max in O(n)
• Min Stack — O(1) min query; classic interview warm-up
• Stack from Two Queues / Queue from Two Stacks — interview classics

7. Trees

Binary Trees

• Binary Tree — terminology, properties
• Tree Traversals — in/pre/post-order (recursive + iterative); level-order; Morris traversal
• Binary Search Tree — BST invariant; insert/delete/search; degenerate cases
• Lowest Common Ancestor — naive, parent-pointer, Tarjan offline, binary lifting
• Tree Diameter — longest path; two-BFS or DFS-with-return
• Serialize and Deserialize Binary Tree — pre-order + null markers; common interview problem

Self-Balancing Trees

• AVL Tree — strict balance via rotations; tighter than RB
• Red-Black Tree — balanced via color invariants; backs Java’s TreeMap, C++ std::map
• B-Tree / B+ Tree — multi-way; backs database indexes
• Treap — randomized BST + heap on priority; simple to reason about
• Splay Tree — amortized O(log n); recently-accessed near root

Tries

• Trie — prefix tree; autocomplete, dictionary problems
• Compressed Trie / Radix Tree — space-optimized trie
• Suffix Tree — all suffixes of a string; substring queries

Range Query Trees

• Segment Tree — range-query and point/range-update in O(log n)
• Segment Tree with Lazy Propagation — range-update in O(log n) amortized
• Fenwick Tree — Binary Indexed Tree; simpler than segment tree for prefix-sum-style queries
• Sparse Table — O(1) idempotent range queries (min/max/gcd) after O(n log n) preprocessing

8. Heaps & Priority Queues

• Binary Heap — array-backed; sift-up / sift-down; O(n) build
• Heap Sort — listed under sorting too
• K-Way Merge — merge k sorted lists in O(N log k)
• Top K Elements — heap of size k pattern
• Two Heaps Pattern — running median (max-heap of lower half + min-heap of upper)
• Fibonacci Heap — theoretical O(1) decrease-key; rarely beats binary heap in practice

9. Graphs

Representations

• Graph Representations — adjacency list vs adjacency matrix; edge list; trade-offs

Traversal

• Breadth-First Search — shortest path in unweighted graph; level-by-level
• Depth-First Search — recursive backbone for many graph algorithms
• Bidirectional BFS — meet-in-the-middle for shortest path
• Multi-Source BFS — start from many sources simultaneously
• 01-BFS — deque-based BFS for graphs with edge weights ∈ {0, 1}
• Iterative Deepening DFS — DFS depth-bounded, then increase depth; combines DFS memory with BFS optimality

Shortest Paths

• Dijkstra’s Algorithm — non-negative weights; O((V+E) log V) with binary heap
• Bellman-Ford — handles negative edges; detects negative cycles; O(VE)
• Floyd-Warshall — all-pairs shortest paths; O(V³)
• Johnson’s Algorithm — all-pairs with negative edges; reweights then Dijkstra
• A* Search — heuristic-guided; optimal with admissible heuristic

Minimum Spanning Tree

• Kruskal’s Algorithm — sort edges, union-find; O(E log E)
• Prim’s Algorithm — grow tree from a seed; O((V+E) log V)
• Borůvka’s Algorithm — parallelizable MST; historical interest

Connectivity

• Union-Find — disjoint-set; near-O(1) per op with path compression + union by rank
• Connected Components — DFS or BFS or union-find
• Strongly Connected Components — Tarjan’s algorithm; Kosaraju’s algorithm
• Bridges and Articulation Points — Tarjan’s bridge-finding
• Bipartite Check — 2-coloring with BFS/DFS

Topological Order & DAGs

• Topological Sort — Kahn’s (BFS-based) and DFS-based
• Longest Path — O(V+E) via topo order
• Hamiltonian Path — NP-hard in general; bitmask DP for small n

Flow & Matching

• Maximum Flow — Ford-Fulkerson framework
• Edmonds-Karp — Ford-Fulkerson with BFS; O(VE²)
• Dinic’s Algorithm — faster max flow; O(V²E)
• Min-Cut Max-Flow Theorem — duality
• Bipartite Matching — Hopcroft-Karp; reduces to max flow

10. Dynamic Programming

The category most candidates fear. The pattern is: identify state, write recurrence, choose top-down (memoization) or bottom-up (tabulation), optionally compress space.

Foundational Patterns

• DP State Identification — meta-skill: how to decide what the state is
• Memoization vs Tabulation — top-down vs bottom-up; when each wins

1D Sequence DP

• Fibonacci DP — the canonical first DP problem
• Climbing Stairs — Fibonacci in disguise
• House Robber — pick-or-skip pattern
• Longest Increasing Subsequence — O(n²) and O(n log n) variants

2D Sequence DP

• Longest Common Subsequence — string DP archetype
• Edit Distance — Levenshtein; insertion/deletion/substitution
• Distinct Subsequences — LCS variant
• Regular Expression Matching — string DP with wildcards

Knapsack Family

• 01 Knapsack — each item once; capacity DP
• Unbounded Knapsack — each item unlimited
• Partition Equal Subset Sum — knapsack reduction
• Coin Change — minimum coins / number of ways

Interval DP

• Matrix Chain Multiplication — minimum-cost parenthesization
• Burst Balloons — interval-DP archetype
• Palindromic Substrings / Longest Palindromic Subsequence

DP on Trees

• Tree DP — children-then-parent post-order DP
• Rerooting DP — answer for every root in O(n) total

DP on Graphs / Bitmask DP

• Bitmask DP — state ∈ subsets; for n ≤ 20-ish
• Travelling Salesman DP — Held-Karp; O(n² 2ⁿ)

Digit DP & Other Specialized

• Digit DP — count numbers ≤ N with property P
• Probability DP — expected value problems
• Game Theory DP — minimax-style; Nim, Stone Game

DP Optimizations

• Monotonic Queue Optimization — sliding-window min over DP transitions
• Convex Hull Trick — for linear-form transitions
• Knuth’s Optimization — quadrangle inequality
• Divide and Conquer DP — for “monotone optimum” transitions

11. Greedy

• Greedy Algorithms — Proof Techniques — exchange argument, greedy stays ahead
• Activity Selection — interval scheduling; sort by end time
• Interval Merging — sort by start; merge overlapping
• Job Scheduling with Deadlines — sort by profit, latest free slot
• Huffman Coding — optimal prefix-free code; greedy with heap
• Fractional Knapsack — sort by value/weight; the rare fractional variant where greedy is optimal
• Gas Station — circuit problem; one-pass greedy
• Jump Game — reach end of array; greedy reach update

12. Divide and Conquer

• Divide and Conquer Paradigm — three-step recipe; recurrence analysis
• Closest Pair of Points — O(n log n) via D&C with strip
• Karatsuba Multiplication — O(n^1.585) integer multiplication
• Strassen’s Algorithm — O(n^2.807) matrix multiplication; rarely beats naive in practice
• FFT — Fast Fourier Transform — O(n log n) polynomial multiplication; convolution

13. Backtracking

• Backtracking Framework — DFS + state-mutate + undo template
• Permutations — generate all orderings
• Combinations — generate all k-subsets
• Subsets — generate all 2ⁿ subsets
• N-Queens — classic constraint-satisfaction
• Sudoku Solver — constraint propagation + backtracking
• Word Search / Word Search II — grid-DFS with trie pruning
• Generate Parentheses — count-constrained generation

14. String Algorithms

• String Hashing — polynomial rolling hash; foundation for Rabin-Karp
• KMP — Knuth-Morris-Pratt — prefix function; O(n+m) substring search
• Z-Algorithm — Z-array; alternative O(n+m) substring search
• Rabin-Karp — rolling hash substring search
• Manacher’s Algorithm — O(n) longest palindromic substring
• Aho-Corasick — multi-pattern matching; trie + KMP failure links
• Suffix Array — sorted suffix indices; O(n log n) construction
• Suffix Automaton — minimal DFA recognizing all substrings; powerful but advanced

15. Bit Manipulation

• Bit Manipulation Tricks — common idioms (set/clear/toggle bit, isolate lowest set bit)
• XOR Properties — find unique element; missing number
• Brian Kernighan’s Algorithm — count set bits in O(popcount)
• Subset Enumeration with Bitmasks — iterate all subsets / all submasks of a mask
• Bit Tricks for Powers of Two — n & (n-1), alignment, etc.

16. Math & Number Theory

• GCD and Extended Euclidean — Euclid’s algorithm; Bézout coefficients
• Sieve of Eratosthenes — primes up to n in O(n log log n)
• Linear Sieve — primes + smallest prime factor in O(n)
• Modular Arithmetic — addition / multiplication / inverse under modulus
• Modular Inverse — Fermat’s little theorem; extended Euclidean
• Fast Exponentiation — O(log n) a^n mod m
• Miller-Rabin Primality Test — probabilistic primality
• Chinese Remainder Theorem — solving systems of modular equations
• Combinatorics Basics — nCr, nPr, stars and bars, inclusion-exclusion
• Catalan Numbers — counts of balanced-paren / BST-shape / triangulation

17. Computational Geometry

• Vector Cross Product — orientation test; foundation
• Convex Hull — Graham Scan / Convex Hull — Andrew’s Monotone Chain — O(n log n)
• Line Sweep — interval intersection, segment intersection
• Closest Pair of Points — also under D&C
• Polygon Area — shoelace formula

18. Concurrency (Interview Subset)

• Producer-Consumer — bounded buffer with semaphores / monitors
• Reader-Writer Problem — fairness variants
• Dining Philosophers — classic deadlock problem
• Deadlock Detection and Avoidance — Banker’s algorithm; resource ordering
• Mutex vs Semaphore vs Condition Variable

19. System Design Adjuncts

For complete industry-scale system designs (URL shortener, Twitter, YouTube, Uber, S3, Kafka, etc.), see Major System Designs MOC. For architectural styles and patterns (monolithic, microservices, event-driven, hexagonal, CQRS, sagas, circuit breakers, etc.), see System Architectures MOC. This section catalogs the components you assemble; those MOCs catalog the assembled systems and the organizational shapes respectively.

Algorithmic building blocks of system-design rounds. These are not full system designs — they’re the components.

Caching

• LRU Cache — doubly-linked list + hash map
• LFU Cache — frequency tracking; harder than LRU
• ARC — Adaptive Replacement Cache — adaptive LRU/LFU hybrid
• Write-Through vs Write-Back — caching write semantics

Hashing & Sketches

• Consistent Hashing — hash ring; minimizes rehashing on node churn
• Rendezvous Hashing — alternative to consistent hashing
• Bloom Filter — probabilistic set membership
• Count-Min Sketch — heavy-hitter / frequency estimation
• HyperLogLog — distinct-cardinality estimation
• MinHash — set similarity estimation

Rate Limiting

• Token Bucket — burst-tolerant rate limiting
• Leaky Bucket — smoothed rate limiting
• Fixed Window Rate Limiter — simple but bursty at boundaries
• Sliding Window Rate Limiter — accurate, slightly more state

Distributed Systems Algorithms

• Skip List — probabilistic balanced structure; backs Redis sorted sets
• CRDTs Basics — eventually-consistent state replication
• Vector Clocks — causal ordering across nodes
• Raft — consensus protocol; understandable Paxos
• Paxos High-Level — the original consensus protocol
• Two-Phase Commit — atomic distributed transactions
• Gossip Protocol — eventually-consistent membership

Storage

• LSM Tree — log-structured merge tree; backs LevelDB, RocksDB, Cassandra
• B+ Tree — also under trees; backs traditional RDBMS indexes
• Inverted Index — text search backbone

20. Behavioral & Interview Process

The non-coding half. Often the differentiator for senior roles.

Storytelling

• STAR Framework — Situation, Task, Action, Result; structuring behavioral answers
• CAR Framework — Context, Action, Result; lighter alternative
• Picking Stories — Coverage Matrix — mapping stories to common behavioral themes (conflict, leadership, ambiguity, failure)

Coding-Interview Process

• Problem Decomposition in Interviews — clarify → examples → brute force → optimize → code → test
• Talking Through Code — narrating without going silent or droning
• Time Management in Interviews — pacing across the four phases of a typical 45-min coding round
• Edge Cases Checklist — empty input, single element, duplicates, negatives, overflow, cycles
• Debugging Under Pressure — read your own code aloud; rubber-duck the interviewer

System Design Rounds

• System Design Interview Framework — requirements → estimation → API → data model → architecture → deep-dive
• Back-of-Envelope Estimation — common numbers every engineer should know
• Scaling Patterns — vertical → horizontal → caching → CDN → sharding → async

Process & Negotiation

• FAANG Interview Loops — typical structure (phone screen, onsite, debrief)
• Levels and Calibration — how levelling works at major employers
• Negotiating Offers — leverage, signal, what’s negotiable
• Resume for SWE Roles — accomplishment-driven bullets; keyword density
• How to Practice — Spaced Repetition for Algorithms — Leitner system applied to LeetCode

---

Cross-Cutting Pitfall Notes

Notes that apply across many algorithms:

• Off-By-One Errors — Survival Guide
• Integer Overflow in Interviews — mid = lo + (hi-lo)/2; Java/C++ caveats; Python’s arbitrary precision
• Recursion Depth Limits — CPython default 1000; iterative conversion patterns
• Mutability and Aliasing Bugs — sharing references in DP tables, default-argument trap

---

Open Threads

• Coverage gap: This MOC currently lists ~150 leaf notes; the bolded ones (foundations + most-asked) are the priority for the first wave of writing.
• Company-specific addenda: separate sub-MOCs for company-specific patterns (e.g., “Google-style optimization round,” “Meta-style product-sense round”) if there’s enough material.
• Verify & date-stamp: every claim about “currently used in production at X” needs a citation and a year — these rot fast.
• Visual aids: heavy-diagram notes (segment tree, suffix array) need either mermaid sequences or PNG attachments in Attachments/.

---

See Also

• Recommender Systems MOC — sibling vault MOC; useful as a style reference for note depth
• Authentication MOC — ditto
• Home — vault index