Data Structures & Algorithms
Complete on its own: the core data structures and algorithms from the ground up (complexity, arrays/lists/stacks/queues, hash tables, trees and heaps, graphs, sorting, searching, recursion, greedy, backtracking, dynamic programming), then everything computer-science doesn't cover — advanced trees and range-query structures, disjoint sets and graph-structure algorithms, shortest-path algorithms that handle negative weights and heuristics, non-comparison sorting, the design techniques behind divide-and-conquer and randomization, advanced string matching, and the full interview pattern catalog: two pointers, sliding window, merge intervals, cyclic sort, top-k/two-heaps, subsets and permutations, classic DP, and the rest of what LeetCode-style problems are actually built from.
Complexity & math foundations
- Asymptotic Notation: Big-O, Big-Theta, and Big-OmegaHow Big-O, Big-Theta, and Big-Omega describe an algorithm's growth rate, and how to work out which one applies to your own code.
- Complexity Classes: P, NP, and NP-CompleteWhat it means for a problem to be in P or NP, what NP-complete and NP-hard add on top, and what the P=NP question actually asks.
- Probability and Combinatorics for AlgorithmsHow expected value, linearity of expectation, and counting arguments explain why randomized quicksort is fast on average, no matter the input.
Core data structures
- Arrays, Linked Lists, Stacks, and QueuesThe four linear data structures every other structure builds on, and the time-complexity tradeoffs that decide which one to reach for.
- Hash Tables and TriesHow hash tables turn a key into near-instant lookup, how collisions get resolved, and when a trie beats a hash table for strings.
- Trees, BSTs, and HeapsBinary trees, the binary search tree property, the three traversal orders, and how a heap keeps the smallest or largest element one step away.
- Balanced Search TreesWhy an unbalanced BST can degrade to a linked list, and how AVL trees, red-black trees, and B-trees stay fast through rotations.
- Graph RepresentationDirected vs undirected graphs, adjacency lists vs adjacency matrices, and what a spanning tree is.
Sorting, searching & recursion
- Comparison-Based Sorting: Six Algorithms, Two ShapesBubble, selection, insertion, merge, quick, and heap sort compared on time complexity, space, stability, and when each one actually wins.
- Linear Search, Binary Search, and RecursionWhy binary search needs sorted data, how recursion replaces a loop with a call stack, and what makes a recursive call "tail" or not.
Graph algorithms
- Graph Traversal: BFS and DFSBreadth-first and depth-first search explore a graph in opposite orders — what each visits first, and when that difference matters.
- Shortest Paths: Dijkstra, Bellman-Ford, A*Three ways to find the cheapest path through a weighted graph, and why you can't always reach for the simplest one.
- Minimum Spanning Trees: Prim's and Kruskal'sConnecting every node in a weighted graph as cheaply as possible, two different ways — grow a tree, or sort the edges.
- Network Flow: Max-Flow and Ford-FulkersonHow much can move from a source to a sink through a capacity-limited network, and the augmenting-path method that finds out.
Algorithm design paradigms
- Greedy AlgorithmsMaking the locally best choice at every step, why that provably works for some problems, and why it quietly fails for others.
- BacktrackingBuilding a solution one piece at a time and abandoning a branch the moment it can't work, worked through the N-Queens problem.
- Dynamic Programming & NP-Hard ProblemsSolving overlapping subproblems exactly once with memoization and tabulation, applied to knapsack and the traveling salesman problem.
Advanced linear structures
- Dynamic Arrays and Amortized AnalysisHow doubling-based growth turns an occasional O(n) resize into O(1) amortized append, and why shrinking too eagerly destroys that guarantee.
- Skip ListsA probabilistic layered linked list that gets expected O(log n) search, insert, and delete without any tree-rebalancing logic.
- Monotonic Stacks and QueuesA stack or deque kept strictly increasing or decreasing turns O(n²) "find the next bigger/smaller element" scans into a single O(n) pass.
- Deques and Circular BuffersHow a double-ended queue is implemented as a ring buffer over a fixed array, and why wraparound indices make that fast.
Priority structures & range queries
- D-ary Heaps and Indexed Priority QueuesGiving a heap more than two children per node trades comparisons for height — and an "indexed" heap adds the one operation Dijkstra actually needs.
- Segment TreesA binary tree over an array that answers any range sum/min/max query in O(log n) and, with lazy propagation, applies range updates just as fast.
- Fenwick Trees (Binary Indexed Trees)A single bit trick, i & -i, turns a plain array into a structure that does prefix sums and point updates in O(log n) with a fraction of a segment tree's code.
- Interval Trees and Range QueriesAugment a BST with one extra field — the max endpoint in its subtree — and it can report every interval overlapping a query in O(log n + k).
Union-find & graph structure
- Union-Find & Disjoint SetsTwo small optimizations turn a tree-of-sets data structure into one of the fastest tools in algorithms — near-constant-time union and find.
- Topological SortingOrdering a DAG so every dependency comes before what depends on it — two different algorithms reach the same ordering from opposite directions.
- Strongly Connected ComponentsFinding the maximal clusters of a directed graph where every node can reach every other — and collapsing them into a clean DAG.
- Bipartite Graphs & MatchingTesting whether a graph splits into two independent sides, then pairing up nodes across that split as efficiently as possible.
Advanced graph algorithms
- Bellman-Ford & Negative WeightsWhy Dijkstra's greedy finalization breaks with negative edges, and how repeated edge relaxation finds shortest paths anyway — and detects negative cycles.
- Floyd-Warshall & All-Pairs Shortest PathsThe O(V^3) DP recurrence that computes shortest paths between every pair of vertices at once, by considering each vertex in turn as a possible waypoint.
- A* SearchDijkstra plus a goal-directed heuristic — how f = g + h skips exploring every direction, and the admissibility/consistency conditions that keep it optimal.
Advanced sorting & selection
- Non-Comparison Sorts: Counting, Radix, and Bucket SortHow counting, radix, and bucket sort break the Ω(n log n) barrier by never comparing elements, and when that trick applies.
- Order Statistics & QuickselectFinding the kth smallest element without fully sorting, via Quickselect's partition-and-recurse trick, and why median-of-medians guarantees O(n).
Algorithm design techniques
- Divide & Conquer and the Master TheoremGeneralizing divide/conquer beyond mergesort and binary search, and using the Master Theorem to read off a recurrence's runtime by inspection.
- Amortized Analysis: Aggregate, Accounting & PotentialThe three formal techniques for proving an amortized bound — aggregate, accounting, and potential — worked through a binary counter and a multipop stack.
- Randomized Algorithms: Las Vegas vs Monte CarloHow randomness turns adversarial worst cases into expected-case guarantees, splitting algorithms into always-correct Las Vegas and bounded-time Monte Carlo.
- Branch and BoundPruning a search tree with an optimality bound instead of a feasibility check, applied to 0/1 knapsack and the traveling salesman problem.
Advanced string algorithms
- String Matching: Brute Force to Rabin-KarpFour ways to find a pattern inside a text — brute force, KMP, Boyer-Moore, and Rabin-Karp — plus suffix arrays for repeated queries.
- The Z-Array and Manacher's Algorithm: Two More Linear-Time String TricksTwo independent O(n) ideas — the Z-array for pattern matching without a failure function, and Manacher's algorithm for the longest palindromic substring.
- Suffix Trees: Ukkonen's Algorithm and the Longest Common SubstringSuffix trees as a distinct structure from suffix arrays — Ukkonen's construction, conceptually, and generalized trees for cross-string matching.
- Aho-Corasick: Matching Thousands of Patterns in One PassA trie with failure links generalizes KMP to search for many patterns against a text simultaneously, in one linear-time scan.
Problem-solving patterns
- Two pointers & fast/slow pointersTwo coordinated index variables turn O(n^2) array problems into O(n), and the same trick at different speeds detects a linked list cycle with no extra memory.
- Sliding window techniqueA window that only expands and shrinks at its edges, instead of re-scanning substrings from scratch, turns an O(n^2) brute force into a single O(n) pass.
- Binary search on the answerWhen "does X work?" is monotonic in X, you can binary-search the space of possible answers directly, instead of binary-searching a sorted array.
- Meet in the middleSplitting a 2^n search space into two independent 2^(n/2) halves and combining the results turns an exponential brute force into something fast for n up to ~40.
- Bitmask dynamic programmingPacking a subset of up to ~20 elements into one integer as DP state solves problems like the traveling salesman problem exactly, in better-than-factorial time.
More interview patterns
- Prefix sums and difference arraysPrecomputing running totals turns range-sum queries into O(1) lookups, and its mirror image, a difference array, turns range updates into O(1) edits.
- Merge intervals patternSorting intervals by start time turns overlapping ranges into a single left-to-right sweep that merges, inserts, or counts overlaps.
- Cyclic sort patternPlacing each value at its "home" index in one O(n) pass exposes missing or duplicate numbers in an array with no extra space.
- In-place linked list reversalRewiring next pointers with a prev/curr/next triple reverses a singly linked list, or any sub-range of one, in O(n) time and O(1) space.
- Subsets, Permutations, and CombinationsOne backtracking template generates every subset, permutation, and k-combination — plus the sort-and-skip trick for duplicate elements.
- Top-K Elements and the Two Heaps PatternTracking the k largest items with a fixed-size min-heap in O(n log k), and the max-heap/min-heap split that maintains a running median in a stream.
- Matrix Traversal PatternsThree recurring 2D-grid techniques — spiral traversal, in-place rotation, and flood-fill over connected regions — and how each handles boundaries.
- Bitwise XOR Tricks for InterviewsThe XOR self-cancellation trick behind single-number problems, plus using a small bitmask as a stand-in for small-set membership.
- Greedy interval schedulingSorting activities by end time and greedily taking the next compatible one provably maximizes non-overlapping intervals; sorting by start time does not.
- Classic Dynamic Programming Patterns: LCS, LIS, and Interval DPThe DP table shapes beyond knapsack — LCS and LIS table-filling, and interval DP over ranges — and how to spot which shape a problem needs.
Number theory for algorithms
- Sieve of Eratosthenes and Primality TestingFind every prime up to n in O(n log log n) with the sieve, and test a single number for primality in O(sqrt n) with trial division.
- GCD and Modular ArithmeticThe Euclidean algorithm finds GCD in O(log) steps via gcd(a,b) = gcd(b, a mod b), the foundation for modular arithmetic and inverses.
- Fast ExponentiationCompute a^b mod m in O(log b) time with repeated squaring instead of O(b) naive multiplication, worked through a numeric example.
More graph algorithms
- Eulerian Paths & CircuitsVisiting every edge of a graph exactly once, the odd-degree-vertex test for when it's possible, and Hierholzer's algorithm for building one.
- Articulation Points & BridgesFinding the single vertices and edges whose removal disconnects a graph, using one DFS pass that tracks discovery time and low-link values.
- Graph ColoringAssigning colors to vertices so no edge joins two same-colored ones, why greedy coloring is fast but not optimal, and its use in compiler register allocation.
- Lowest Common Ancestor TechniquesFinding the deepest shared ancestor of two tree nodes fast, via binary lifting's O(n log n) preprocessing and O(log n) queries.
More advanced structures
- Tries and AutocompleteBuild a full autocomplete system on a trie with word-end markers and prefix word counts, and weigh the tradeoffs against a hash set.
- LRU Cache Design and ImplementationImplement an LRU cache with O(1) get and put by pairing a hash map for lookup with a doubly linked list for eviction order.
- Sparse Tables and Static Range QueriesAnswer range-minimum queries in O(1) on a never-updated array using a sparse table built in O(n log n) from overlapping power-of-two ranges.
More patterns & tricks
- Kadane's algorithm and maximum subarrayFinding the maximum-sum contiguous subarray in O(n) by framing each position as a tiny 1D dynamic-programming decision.
- Dutch national flag and three-way partitioningPartitioning an array into three groups in one O(n) pass with three pointers, and how it generalizes quicksort's partition step.
- Boyer-Moore voting algorithmFinding the element that appears more than n/2 times in O(n) time and O(1) space via candidate-and-counter cancellation.
- Reservoir samplingSelecting a uniform random sample of size k from a stream of unknown length in one pass and O(k) space.
- Rolling hash and string hashingUpdating a sliding-window string hash in O(1) per shift, and how it powers Rabin-Karp-style pattern matching.