Data Structures and Algorithms Roadmap — Fundamentals to Advanced

1. Prerequisites

1.1 Programming fundamentals

  • Variables
  • Data types
  • Control flow
  • Functions
  • Recursion
  • Loops
  • Arrays
  • Objects
  • Classes
  • Interfaces
  • Generics
  • Error handling
  • Memory basics
  • Input/output basics

1.2 Mathematical foundations

  • Arithmetic
  • Algebra basics
  • Logarithms
  • Exponents
  • Modular arithmetic
  • Set theory
  • Relations
  • Functions
  • Sequences
  • Series
  • Summations
  • Factorials
  • Permutations
  • Combinations
  • Probability basics
  • Discrete mathematics
  • Mathematical induction
  • Proof by contradiction

1.3 Computer science foundations

  • Binary representation
  • Bits
  • Bytes
  • Signed integers
  • Unsigned integers
  • Overflow
  • Floating-point representation
  • Memory addresses
  • Stack memory
  • Heap memory
  • Pointers
  • References
  • Cache locality
  • CPU basics
  • I/O cost
  • Network cost

1.4 Problem-solving fundamentals

  • Understand the problem
  • Identify inputs
  • Identify outputs
  • Identify constraints
  • Identify edge cases
  • Build examples
  • Build counterexamples
  • Start with brute force
  • Optimize bottlenecks
  • Prove correctness
  • Analyze complexity
  • Test thoroughly
  • Refactor solution

1.5 Tooling

  • IDE
  • Debugger
  • Unit testing framework
  • Benchmarking tool
  • Online judge
  • LeetCode
  • HackerRank
  • Codeforces
  • AtCoder
  • Kattis
  • Local test runner
  • Visualization tools

2. Complexity Analysis

2.1 Asymptotic notation

  • Big O notation
  • Big Omega notation
  • Big Theta notation
  • Little o notation
  • Little omega notation
  • Upper bound
  • Lower bound
  • Tight bound
  • Worst case
  • Average case
  • Best case
  • Amortized case

2.2 Common complexity classes

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n)
  • O(n²)
  • O(n³)
  • O(2ⁿ)
  • O(n!)
  • O(sqrt n)
  • O(kⁿ)
  • Pseudo-polynomial complexity
  • Polynomial complexity
  • Exponential complexity

2.3 Time complexity analysis

  • Single loop analysis
  • Nested loop analysis
  • Sequential operations
  • Conditional branches
  • Recursion analysis
  • Divide and conquer recurrence
  • Master theorem
  • Substitution method
  • Recursion tree method
  • Amortized time analysis
  • Aggregate method
  • Accounting method
  • Potential method

2.4 Space complexity analysis

  • Auxiliary space
  • Input space
  • Output space
  • In-place algorithm
  • Call stack space
  • Recursion depth
  • Heap allocation
  • Data structure overhead
  • Memory trade-offs
  • Space-time trade-offs

2.5 Practical performance

  • Constant factors
  • Cache locality
  • Branch prediction
  • Memory allocation cost
  • Hashing cost
  • Sorting cost
  • I/O bottlenecks
  • Network bottlenecks
  • Benchmarking pitfalls
  • Microbenchmarking
  • Performance regression detection

3. Arrays and Strings

3.1 Arrays

  • Static array
  • Dynamic array
  • Indexing
  • Traversal
  • Insertion
  • Deletion
  • Search
  • Update
  • Resizing
  • Capacity
  • Length
  • Contiguous memory
  • Cache locality
  • Multi-dimensional arrays
  • Jagged arrays

3.2 Array techniques

  • Two pointers
  • Sliding window
  • Prefix sums
  • Suffix sums
  • Difference array
  • Frequency array
  • In-place modification
  • Partitioning
  • Rotation
  • Reversal
  • Deduplication
  • Stable transformation
  • Cyclic placement
  • Index mapping

3.3 Strings

  • Character array
  • Immutable string
  • Mutable string builder
  • String traversal
  • Substring
  • Concatenation
  • Character frequency
  • Palindrome
  • Anagram
  • Lexicographic order
  • ASCII
  • Unicode
  • UTF-8
  • Case sensitivity
  • Normalization

3.4 String algorithms

  • Naive pattern matching
  • Rabin-Karp
  • Knuth-Morris-Pratt
  • Z algorithm
  • Boyer-Moore
  • Trie-based matching
  • Rolling hash
  • Longest common prefix
  • Longest common substring
  • Longest palindromic substring
  • Manacher’s algorithm
  • String compression
  • Edit distance
  • Suffix array
  • Suffix tree
  • Suffix automaton

3.5 Common array and string patterns

  • Find duplicates
  • Find missing number
  • Find first unique character
  • Reverse words
  • Merge sorted arrays
  • Move zeroes
  • Remove duplicates
  • Rotate array
  • Maximum subarray
  • Product except self
  • Longest substring without repeating characters
  • Minimum window substring
  • Group anagrams
  • Valid palindrome
  • String decoding

4. Linked Lists

4.1 Linked list fundamentals

  • Node
  • Head
  • Tail
  • Pointer/reference
  • Singly linked list
  • Doubly linked list
  • Circular linked list
  • Sentinel node
  • List traversal
  • List insertion
  • List deletion
  • List search
  • Memory overhead
  • Cache locality trade-off

4.2 Singly linked list

  • Insert at head
  • Insert at tail
  • Insert at position
  • Delete by value
  • Delete by position
  • Reverse list
  • Find middle node
  • Find kth node
  • Detect cycle
  • Remove cycle
  • Merge lists
  • Split list
  • Reorder list

4.3 Doubly linked list

  • Previous pointer
  • Next pointer
  • Insert before node
  • Insert after node
  • Delete node in O(1)
  • Bidirectional traversal
  • LRU cache usage
  • Deque implementation
  • Memory overhead
  • Sentinel-based design

4.4 Linked list techniques

  • Fast and slow pointers
  • Dummy node
  • Previous-current-next tracking
  • Recursive reversal
  • Iterative reversal
  • Cycle detection
  • Merge technique
  • Pointer manipulation
  • In-place transformation
  • List partitioning

4.5 Common linked list problems

  • Reverse linked list
  • Reverse nodes in k-group
  • Merge two sorted lists
  • Merge k sorted lists
  • Remove nth node from end
  • Detect cycle
  • Find cycle start
  • Add two numbers
  • Copy list with random pointer
  • Intersection of linked lists
  • Palindrome linked list
  • Sort linked list
  • Reorder list
  • LRU cache

5. Stacks and Queues

5.1 Stack

  • LIFO
  • Push
  • Pop
  • Peek
  • Is empty
  • Array-backed stack
  • Linked-list-backed stack
  • Stack overflow
  • Call stack
  • Monotonic stack
  • Min stack
  • Max stack

5.2 Queue

  • FIFO
  • Enqueue
  • Dequeue
  • Peek
  • Is empty
  • Array-backed queue
  • Linked-list-backed queue
  • Circular queue
  • Bounded queue
  • Unbounded queue
  • Double-ended queue
  • Priority queue
  • Blocking queue

5.3 Deque

  • Add first
  • Add last
  • Remove first
  • Remove last
  • Peek first
  • Peek last
  • Sliding window maximum
  • Monotonic deque
  • BFS frontier
  • Queue-stack hybrid usage

5.4 Stack patterns

  • Parentheses validation
  • Expression evaluation
  • Infix notation
  • Prefix notation
  • Postfix notation
  • Reverse Polish notation
  • Next greater element
  • Previous greater element
  • Next smaller element
  • Previous smaller element
  • Histogram rectangle
  • Remove duplicate letters
  • Decode string
  • Backtracking simulation

5.5 Queue patterns

  • BFS
  • Level-order traversal
  • Sliding window
  • Producer-consumer
  • Task scheduling
  • Round-robin scheduling
  • Topological processing
  • Shortest path unweighted graph
  • Multi-source BFS
  • Stream processing

6. Hashing and Hash Tables

6.1 Hashing fundamentals

  • Hash function
  • Hash code
  • Hash table
  • Bucket
  • Collision
  • Load factor
  • Rehashing
  • Table resizing
  • Uniform distribution
  • Deterministic hashing
  • Hash equality contract
  • Mutable key problem

6.2 Collision resolution

  • Separate chaining
  • Open addressing
  • Linear probing
  • Quadratic probing
  • Double hashing
  • Robin Hood hashing
  • Cuckoo hashing
  • Tombstones
  • Clustering
  • Resize strategy

6.3 Hash-based structures

  • HashSet
  • HashMap
  • LinkedHashMap
  • LinkedHashSet
  • ConcurrentHashMap
  • Identity hash map
  • Weak hash map
  • Hash multiset
  • Hash multimap
  • Frequency map

6.4 Hashing techniques

  • Frequency counting
  • Prefix hash
  • Rolling hash
  • Polynomial hash
  • Pair hashing
  • State hashing
  • Memoization keys
  • Consistent hashing
  • Bloom filter hashing
  • Hashing for deduplication

6.5 Common hashing problems

  • Two sum
  • Three sum with hash set
  • Group anagrams
  • Longest consecutive sequence
  • First missing positive
  • Subarray sum equals k
  • Contains duplicate
  • Isomorphic strings
  • Valid Sudoku
  • LRU cache
  • Randomized set
  • Detect cycle by visited state

7. Recursion and Backtracking

7.1 Recursion fundamentals

  • Base case
  • Recursive case
  • Call stack
  • Stack frame
  • Recursion depth
  • Direct recursion
  • Indirect recursion
  • Tail recursion
  • Tree recursion
  • Mutual recursion
  • Recurrence relation
  • Recursive correctness proof

7.2 Recursion patterns

  • Divide and conquer
  • DFS recursion
  • Generate all combinations
  • Generate all permutations
  • Generate subsets
  • Recursive tree traversal
  • Recursive linked list processing
  • Recursive dynamic programming
  • Recursive parsing
  • Recursion with memoization

7.3 Backtracking fundamentals

  • Decision tree
  • Choice
  • Constraint
  • Candidate
  • Path
  • State
  • Undo choice
  • Pruning
  • Feasibility check
  • Goal check
  • Exhaustive search
  • Search space
  • Branching factor

7.4 Backtracking patterns

  • Subsets
  • Combinations
  • Permutations
  • Combination sum
  • N-Queens
  • Sudoku solver
  • Word search
  • Palindrome partitioning
  • Restore IP addresses
  • Generate parentheses
  • Hamiltonian path
  • Constraint satisfaction

7.5 Recursion optimization

  • Memoization
  • Pruning
  • Branch ordering
  • Iterative conversion
  • Explicit stack
  • Tail-recursive refactoring
  • Avoid repeated work
  • Avoid excessive copying
  • Pass by reference carefully
  • State compression

8. Sorting

8.1 Sorting fundamentals

  • Comparison sort
  • Non-comparison sort
  • Stable sort
  • Unstable sort
  • In-place sort
  • External sort
  • Adaptive sort
  • Online sort
  • Sorting lower bound
  • Comparator
  • Natural order
  • Custom order

8.2 Basic sorting algorithms

  • Bubble sort
  • Selection sort
  • Insertion sort
  • Complexity analysis
  • Stability analysis
  • In-place analysis
  • Educational use cases
  • Small array optimization

8.3 Efficient comparison sorting

  • Merge sort
  • Quick sort
  • Heap sort
  • TimSort
  • IntroSort
  • Shell sort
  • Dual-pivot quicksort
  • Randomized quicksort
  • Three-way quicksort
  • Stable merge sort
  • External merge sort

8.4 Non-comparison sorting

  • Counting sort
  • Radix sort
  • Bucket sort
  • Pigeonhole sort
  • Counting constraints
  • Stable counting sort
  • LSD radix sort
  • MSD radix sort
  • Numeric sorting
  • String sorting

8.5 Sorting patterns

  • Sort then scan
  • Sort then two pointers
  • Custom comparator
  • Interval sorting
  • Event sorting
  • Coordinate sorting
  • Top-k after sort
  • Deduplication after sort
  • Grouping after sort
  • Sweep line preprocessing

8.6 Common sorting problems

  • Merge intervals
  • Meeting rooms
  • Sort colors
  • Kth largest element
  • Top k frequent elements
  • Largest number
  • Queue reconstruction
  • Minimum number of arrows
  • Non-overlapping intervals
  • H-index
  • Relative sort array

9.1 Search fundamentals

  • Linear search
  • Binary search
  • Ternary search
  • Exponential search
  • Interpolation search
  • Search space
  • Monotonic predicate
  • Lower bound
  • Upper bound
  • First occurrence
  • Last occurrence

9.2 Binary search basics

  • Sorted array search
  • Midpoint calculation
  • Left boundary
  • Right boundary
  • Inclusive range
  • Exclusive range
  • Infinite loop prevention
  • Overflow-safe midpoint
  • Return insertion point
  • Duplicate handling

9.3 Binary search patterns

  • Search exact value
  • Search first true
  • Search last false
  • Search minimum feasible value
  • Search maximum feasible value
  • Binary search on answer
  • Binary search on rotated array
  • Binary search in matrix
  • Binary search on real numbers
  • Binary search with custom predicate
  • Unimodal function
  • Discrete ternary search
  • Continuous ternary search
  • Optimization problem
  • Convex function
  • Concave function
  • Precision control
  • Iteration limit

9.5 Common binary search problems

  • Search insert position
  • Find first and last position
  • Search rotated sorted array
  • Find minimum in rotated sorted array
  • Median of two sorted arrays
  • Koko eating bananas
  • Capacity to ship packages
  • Split array largest sum
  • Find peak element
  • Search 2D matrix
  • Square root
  • Aggressive cows

10. Trees

10.1 Tree fundamentals

  • Node
  • Root
  • Parent
  • Child
  • Sibling
  • Leaf
  • Internal node
  • Edge
  • Path
  • Depth
  • Height
  • Level
  • Degree
  • Subtree
  • Ancestor
  • Descendant

10.2 Binary trees

  • Binary tree
  • Full binary tree
  • Complete binary tree
  • Perfect binary tree
  • Balanced binary tree
  • Skewed binary tree
  • Binary tree representation
  • Recursive representation
  • Array representation
  • Pointer representation

10.3 Tree traversal

  • Preorder traversal
  • Inorder traversal
  • Postorder traversal
  • Level-order traversal
  • DFS recursive
  • DFS iterative
  • BFS
  • Morris traversal
  • Vertical traversal
  • Boundary traversal
  • Zigzag traversal
  • Euler tour

10.4 Binary Search Trees

  • BST property
  • Search
  • Insert
  • Delete
  • Find minimum
  • Find maximum
  • Predecessor
  • Successor
  • Validate BST
  • Balanced BST
  • Degenerate BST
  • BST iterator
  • Kth smallest
  • Range query

10.5 Balanced trees

  • AVL tree
  • Red-black tree
  • B-tree
  • B+ tree
  • 2-3 tree
  • Treap
  • Splay tree
  • Weight-balanced tree
  • Rotations
  • Rebalancing
  • Height guarantees
  • Database index usage

10.6 Tree algorithms

  • Lowest common ancestor
  • Diameter of tree
  • Height calculation
  • Balanced tree check
  • Path sum
  • Root-to-leaf paths
  • Serialize tree
  • Deserialize tree
  • Construct tree from traversals
  • Flatten tree
  • Mirror tree
  • Invert tree
  • Tree dynamic programming

10.7 Advanced trees

  • Segment tree
  • Lazy propagation segment tree
  • Fenwick tree
  • Trie
  • Suffix tree
  • Suffix array
  • Heavy-light decomposition
  • Link-cut tree
  • Cartesian tree
  • Interval tree
  • Range tree
  • KD-tree

11. Heaps and Priority Queues

11.1 Heap fundamentals

  • Heap property
  • Min heap
  • Max heap
  • Binary heap
  • Complete binary tree
  • Array representation
  • Parent index
  • Left child index
  • Right child index
  • Heap height
  • Heapify
  • Sift up
  • Sift down

11.2 Heap operations

  • Insert
  • Extract min
  • Extract max
  • Peek
  • Decrease key
  • Increase key
  • Delete
  • Build heap
  • Merge heaps
  • Replace root
  • Heap sort
  • Complexity analysis

11.3 Priority queue

  • Priority
  • Comparator
  • Stable priority queue
  • Min priority queue
  • Max priority queue
  • Bounded priority queue
  • Lazy deletion
  • Indexed priority queue
  • Double-ended priority queue
  • Priority update

11.4 Heap variants

  • Binary heap
  • D-ary heap
  • Binomial heap
  • Fibonacci heap
  • Pairing heap
  • Leftist heap
  • Skew heap
  • Min-max heap
  • Soft heap
  • Brodal queue

11.5 Heap patterns

  • Top k elements
  • Kth largest
  • Kth smallest
  • Merge k sorted lists
  • Running median
  • Sliding window median
  • Task scheduling
  • Dijkstra priority queue
  • A* open set
  • Event simulation
  • Greedy selection

12. Tries and Prefix Structures

12.1 Trie fundamentals

  • Trie node
  • Root node
  • Character edge
  • End-of-word marker
  • Insert word
  • Search word
  • Prefix search
  • Delete word
  • Memory usage
  • Alphabet size
  • Compressed trie
  • Radix tree

12.2 Trie variants

  • Standard trie
  • Compressed trie
  • Radix tree
  • Patricia trie
  • Ternary search tree
  • Suffix trie
  • Binary trie
  • Persistent trie
  • DAWG
  • Aho-Corasick automaton

12.3 Trie applications

  • Autocomplete
  • Spell checker
  • Prefix matching
  • Word dictionary
  • IP routing
  • XOR queries
  • Word search
  • Search suggestions
  • Multiple pattern matching
  • Longest prefix match

12.4 Common trie problems

  • Implement trie
  • Word search II
  • Search suggestions system
  • Replace words
  • Design add and search words
  • Maximum XOR of two numbers
  • Longest word in dictionary
  • Concatenated words
  • Stream of characters
  • Prefix and suffix search

13. Graphs

13.1 Graph fundamentals

  • Vertex
  • Edge
  • Directed graph
  • Undirected graph
  • Weighted graph
  • Unweighted graph
  • Cyclic graph
  • Acyclic graph
  • Connected graph
  • Disconnected graph
  • Dense graph
  • Sparse graph
  • Degree
  • In-degree
  • Out-degree
  • Path
  • Cycle
  • Component

13.2 Graph representation

  • Adjacency list
  • Adjacency matrix
  • Edge list
  • Incidence matrix
  • Hash-based adjacency
  • Weighted adjacency list
  • Compressed sparse row
  • Memory complexity
  • Time complexity
  • Representation trade-offs

13.3 Graph traversal

  • Depth-first search
  • Breadth-first search
  • Recursive DFS
  • Iterative DFS
  • BFS queue
  • Visited set
  • Parent tracking
  • Distance tracking
  • Connected components
  • Cycle detection
  • Bipartite check
  • Flood fill

13.4 Directed graph algorithms

  • Directed cycle detection
  • Topological sort
  • Kahn’s algorithm
  • DFS topological sort
  • Strongly connected components
  • Kosaraju’s algorithm
  • Tarjan’s algorithm
  • Condensation graph
  • Course schedule pattern
  • Dependency resolution

13.5 Undirected graph algorithms

  • Connected components
  • Cycle detection
  • Bipartite graph
  • Bridges
  • Articulation points
  • Tarjan bridge algorithm
  • Tarjan articulation algorithm
  • Eulerian path
  • Eulerian circuit
  • Hamiltonian path
  • Graph coloring

13.6 Shortest path algorithms

  • BFS shortest path
  • Dijkstra’s algorithm
  • Bellman-Ford algorithm
  • Floyd-Warshall algorithm
  • Johnson’s algorithm
  • A* search
  • 0-1 BFS
  • Multi-source BFS
  • Negative edge handling
  • Negative cycle detection
  • Path reconstruction

13.7 Minimum spanning tree

  • Spanning tree
  • Minimum spanning tree
  • Kruskal’s algorithm
  • Prim’s algorithm
  • Union-Find usage
  • Cut property
  • Cycle property
  • MST uniqueness
  • Maximum spanning tree
  • Clustering applications

13.8 Network flow

  • Flow network
  • Source
  • Sink
  • Capacity
  • Flow conservation
  • Residual graph
  • Augmenting path
  • Ford-Fulkerson
  • Edmonds-Karp
  • Dinic’s algorithm
  • Min-cut max-flow theorem
  • Bipartite matching
  • Min-cost max-flow

13.9 Advanced graph algorithms

  • Union-Find
  • Lowest common ancestor in trees
  • Heavy-light decomposition
  • Euler tour technique
  • Centroid decomposition
  • Tree diameter
  • Tree rerooting DP
  • Dominator tree
  • Strong orientation
  • 2-SAT
  • Maximum matching
  • Minimum vertex cover

14. Union-Find / Disjoint Set Union

14.1 DSU fundamentals

  • Disjoint sets
  • Parent array
  • Find operation
  • Union operation
  • Representative
  • Connected query
  • Component count
  • Set size
  • Path compression
  • Union by rank
  • Union by size
  • Amortized complexity

14.2 DSU variants

  • Basic DSU
  • DSU with size
  • DSU with rank
  • DSU with metadata
  • Rollback DSU
  • Persistent DSU
  • DSU on tree
  • Weighted DSU
  • Parity DSU
  • Offline DSU

14.3 DSU applications

  • Connected components
  • Cycle detection
  • Kruskal’s algorithm
  • Dynamic connectivity offline
  • Accounts merge
  • Number of islands
  • Redundant connection
  • Minimum spanning tree
  • Percolation
  • Equation satisfiability
  • Bipartiteness with parity

15. Greedy Algorithms

15.1 Greedy fundamentals

  • Local optimum
  • Global optimum
  • Greedy choice property
  • Optimal substructure
  • Exchange argument
  • Cut property
  • Matroid intuition
  • Proof of correctness
  • Counterexample construction
  • Greedy vs dynamic programming

15.2 Greedy patterns

  • Sort then choose
  • Pick minimum
  • Pick maximum
  • Earliest finish time
  • Latest start time
  • Interval scheduling
  • Activity selection
  • Fractional knapsack
  • Huffman coding
  • Jump game
  • Gas station
  • Task scheduling
  • Two-pointer greedy
  • Heap-based greedy

15.3 Interval greedy

  • Merge intervals
  • Non-overlapping intervals
  • Meeting rooms
  • Minimum arrows to burst balloons
  • Insert interval
  • Interval covering
  • Maximum number of events
  • Minimum platforms
  • Sweep line with greedy

15.4 Graph greedy

  • Kruskal’s algorithm
  • Prim’s algorithm
  • Dijkstra’s algorithm
  • Greedy coloring heuristic
  • Set cover approximation
  • Shortest path non-negative weights
  • Minimum spanning tree correctness
  • Cut property proof

15.5 Common greedy problems

  • Jump Game
  • Jump Game II
  • Gas Station
  • Candy
  • Assign Cookies
  • Partition Labels
  • Queue Reconstruction
  • Task Scheduler
  • Minimum Number of Arrows
  • Non-overlapping Intervals
  • Boats to Save People
  • Remove K Digits
  • Huffman Coding

16. Dynamic Programming

16.1 DP fundamentals

  • Optimal substructure
  • Overlapping subproblems
  • State
  • Transition
  • Base case
  • Recurrence
  • Memoization
  • Tabulation
  • Top-down DP
  • Bottom-up DP
  • State compression
  • Reconstruction
  • DP correctness proof

16.2 1D DP

  • Fibonacci
  • Climbing stairs
  • House robber
  • Min cost climbing stairs
  • Decode ways
  • Coin change
  • Perfect squares
  • Word break
  • Jump game DP
  • Maximum subarray DP

16.3 2D DP

  • Grid paths
  • Minimum path sum
  • Unique paths
  • Dungeon game
  • Edit distance
  • Longest common subsequence
  • Longest common substring
  • Interleaving string
  • Regex matching
  • Wildcard matching
  • Matrix DP
  • Triangle DP

16.4 Knapsack DP

  • 0/1 knapsack
  • Unbounded knapsack
  • Bounded knapsack
  • Subset sum
  • Partition equal subset sum
  • Target sum
  • Coin change combinations
  • Coin change minimum coins
  • Multiple-choice knapsack
  • Space optimization

16.5 Sequence DP

  • Longest increasing subsequence
  • Longest decreasing subsequence
  • Longest bitonic subsequence
  • Longest common subsequence
  • Edit distance
  • Palindromic subsequence
  • Palindromic substring
  • Distinct subsequences
  • Russian doll envelopes
  • Maximum sum increasing subsequence

16.6 Interval DP

  • Matrix chain multiplication
  • Burst balloons
  • Minimum cost to cut stick
  • Palindrome partitioning
  • Stone game
  • Merge stones
  • Optimal binary search tree
  • Strange printer
  • Interval merging DP
  • Gap-based iteration

16.7 Tree DP

  • Diameter DP
  • Maximum path sum
  • House robber on tree
  • Binary tree cameras
  • Subtree size DP
  • Rerooting DP
  • Independent set on tree
  • Tree matching
  • Tree coloring
  • Lowest cost tree transformation

16.8 Graph DP

  • DP on DAG
  • Topological order DP
  • Shortest path in DAG
  • Longest path in DAG
  • Bitmask DP
  • Traveling Salesman Problem
  • Hamiltonian path DP
  • Steiner tree DP
  • DP with SCC condensation
  • State graph search

16.9 Bitmask DP

  • Subset representation
  • Set bit
  • Clear bit
  • Test bit
  • Iterate subsets
  • Iterate submasks
  • Assignment problem
  • TSP
  • Minimum cost matching
  • Grid state compression
  • Hamiltonian path
  • Profile DP

16.10 Digit DP

  • Digit constraints
  • Tight flag
  • Leading zero flag
  • Position state
  • Sum state
  • Modulo state
  • Count numbers in range
  • Number property counting
  • Memoization with tight state
  • Range query transformation

16.11 DP optimization

  • Space optimization
  • Rolling array
  • Monotonic queue optimization
  • Divide and conquer optimization
  • Knuth optimization
  • Convex hull trick
  • Slope trick
  • Matrix exponentiation
  • Bitset optimization
  • Meet-in-the-middle
  • Pruning states

17. Divide and Conquer

17.1 Divide and conquer fundamentals

  • Divide step
  • Conquer step
  • Combine step
  • Recurrence relation
  • Recursion tree
  • Master theorem
  • Base case
  • Balanced split
  • Unbalanced split
  • Merge cost
  • Correctness proof

17.2 Classic algorithms

  • Merge sort
  • Quick sort
  • Binary search
  • Closest pair of points
  • Strassen matrix multiplication
  • Karatsuba multiplication
  • Fast Fourier Transform
  • Quickselect
  • Median of medians
  • Divide and conquer DP optimization

17.3 Divide and conquer patterns

  • Split array
  • Split search space
  • Sort and merge
  • Partition around pivot
  • Recursive geometry
  • Recursive matrix processing
  • Recursive tree building
  • Reduce problem size
  • Combine partial answers

18. Bit Manipulation

18.1 Bit fundamentals

  • Binary representation
  • Bitwise AND
  • Bitwise OR
  • Bitwise XOR
  • Bitwise NOT
  • Left shift
  • Right shift
  • Signed shift
  • Unsigned shift
  • Two’s complement
  • Overflow
  • Sign bit

18.2 Bit operations

  • Set bit
  • Clear bit
  • Toggle bit
  • Check bit
  • Count set bits
  • Lowest set bit
  • Highest set bit
  • Power of two check
  • Clear lowest set bit
  • Extract bit range
  • Build bitmask
  • Iterate set bits

18.3 Bit tricks

  • x & (x - 1)
  • x & -x
  • XOR swap
  • XOR missing number
  • XOR single number
  • Bitmask subset enumeration
  • Submask iteration
  • Gray code
  • Parity
  • Population count
  • Bit compression

18.4 Bitmask applications

  • Subset generation
  • State compression
  • DP over subsets
  • Permissions flags
  • Bloom filter
  • N-Queens optimization
  • Graph subset DP
  • String character mask
  • Maximum product of word lengths
  • Traveling Salesman Problem

18.5 Common bit problems

  • Single Number
  • Number of 1 Bits
  • Counting Bits
  • Reverse Bits
  • Missing Number
  • Sum of Two Integers
  • Power of Two
  • Bitwise AND of Numbers Range
  • Maximum XOR
  • Subsets with bitmask
  • Gray Code

19. Math Algorithms

19.1 Number theory basics

  • Divisibility
  • Prime numbers
  • Composite numbers
  • Factors
  • Multiples
  • Greatest common divisor
  • Least common multiple
  • Euclidean algorithm
  • Extended Euclidean algorithm
  • Modular arithmetic
  • Modular inverse
  • Modular exponentiation
  • Chinese remainder theorem

19.2 Prime algorithms

  • Trial division
  • Sieve of Eratosthenes
  • Segmented sieve
  • Linear sieve
  • Primality testing
  • Miller-Rabin test
  • Prime factorization
  • Pollard’s rho
  • Smallest prime factor array
  • Count divisors
  • Sum of divisors

19.3 Combinatorics

  • Permutations
  • Combinations
  • Binomial coefficients
  • Pascal’s triangle
  • Inclusion-exclusion
  • Stars and bars
  • Pigeonhole principle
  • Catalan numbers
  • Derangements
  • Burnside’s lemma
  • Counting paths
  • Counting with constraints

19.4 Modular combinatorics

  • Modular addition
  • Modular subtraction
  • Modular multiplication
  • Modular division
  • Fast exponentiation
  • Modular inverse with Fermat
  • Modular inverse with extended gcd
  • Factorials modulo prime
  • nCr modulo prime
  • Lucas theorem
  • Chinese remainder theorem

19.5 Matrix algorithms

  • Matrix multiplication
  • Matrix exponentiation
  • Identity matrix
  • Transition matrix
  • Fibonacci with matrix exponentiation
  • Linear recurrence
  • Gaussian elimination
  • Determinant
  • Rank
  • Inverse matrix
  • Sparse matrix

19.6 Geometry algorithms

  • Point
  • Vector
  • Line
  • Segment
  • Polygon
  • Cross product
  • Dot product
  • Orientation test
  • Convex hull
  • Graham scan
  • Monotonic chain
  • Line intersection
  • Segment intersection
  • Point in polygon
  • Closest pair
  • Rotating calipers

19.7 Probability algorithms

  • Random number generation
  • Uniform distribution
  • Weighted random selection
  • Reservoir sampling
  • Randomized quicksort
  • Randomized selection
  • Monte Carlo method
  • Las Vegas algorithm
  • Expected value
  • Probabilistic data structures

20. Advanced Data Structures

20.1 Segment tree

  • Range query
  • Point update
  • Range update
  • Lazy propagation
  • Min query
  • Max query
  • Sum query
  • GCD query
  • Custom merge
  • Segment tree with coordinate compression
  • Dynamic segment tree
  • Persistent segment tree
  • 2D segment tree

20.2 Fenwick tree

  • Binary Indexed Tree
  • Prefix sum
  • Point update
  • Range query
  • Range update
  • Range update range query
  • Lowest set bit
  • Order statistics with Fenwick
  • Inversion count
  • Coordinate compression usage

20.3 Sparse table

  • Idempotent operation
  • Range minimum query
  • Range maximum query
  • GCD query
  • Preprocessing
  • Query in O(1)
  • Log table
  • Static array limitation
  • Disjoint sparse table

20.4 Balanced search structures

  • AVL tree
  • Red-black tree
  • Treap
  • Splay tree
  • Order statistic tree
  • Interval tree
  • Range tree
  • KD-tree
  • B-tree
  • B+ tree

20.5 Persistent data structures

  • Persistence
  • Partial persistence
  • Full persistence
  • Path copying
  • Persistent stack
  • Persistent queue
  • Persistent segment tree
  • Persistent trie
  • Versioned queries
  • Memory complexity

20.6 Probabilistic data structures

  • Bloom filter
  • Counting Bloom filter
  • Cuckoo filter
  • HyperLogLog
  • Count-Min Sketch
  • MinHash
  • Skip list
  • Treap
  • False positive
  • Error bound
  • Space efficiency

20.7 Specialized structures

  • LRU cache
  • LFU cache
  • Min stack
  • Max queue
  • Median finder
  • Time-based key-value store
  • Randomized set
  • All O(1) data structure
  • Disjoint interval structure
  • Calendar booking structure
  • Rate limiter data structure

21. Algorithmic Paradigms

21.1 Brute force

  • Exhaustive search
  • Generate all possibilities
  • Try all pairs
  • Try all subsets
  • Try all permutations
  • Baseline solution
  • Correctness baseline
  • Complexity bottleneck
  • Optimization target

21.2 Two pointers

  • Opposite direction pointers
  • Same direction pointers
  • Fast and slow pointers
  • Partitioning pointers
  • Merge pointers
  • Window boundary pointers
  • Sorted array usage
  • Linked list usage
  • Palindrome checking
  • Duplicate removal

21.3 Sliding window

  • Fixed-size window
  • Variable-size window
  • Expand window
  • Shrink window
  • Window invariant
  • Frequency map window
  • Monotonic deque window
  • Minimum window
  • Maximum window
  • Subarray counting

21.4 Prefix and suffix computation

  • Prefix sum
  • Prefix product
  • Prefix maximum
  • Prefix minimum
  • Suffix sum
  • Suffix maximum
  • Suffix minimum
  • Difference array
  • Range query preprocessing
  • Contribution technique

21.5 Sweep line

  • Event point
  • Event sorting
  • Active set
  • Interval overlap
  • Meeting rooms
  • Skyline problem
  • Line segment intersection
  • Range add/remove
  • Coordinate compression
  • Geometry sweep

21.6 Meet-in-the-middle

  • Split search space
  • Enumerate halves
  • Combine results
  • Subset sum
  • Closest sum
  • K-sum
  • Exponential reduction
  • Sorting half results
  • Binary search combination
  • Hash-based combination

21.7 Randomized algorithms

  • Randomized quicksort
  • Randomized quickselect
  • Reservoir sampling
  • Randomized hashing
  • Monte Carlo algorithm
  • Las Vegas algorithm
  • Randomized balancing
  • Expected time analysis
  • Probability of failure
  • Reproducible randomness

22. Competitive Programming Techniques

22.1 Input/output optimization

  • Fast input
  • Fast output
  • Buffered reading
  • Buffered writing
  • Scanner limitations
  • StringTokenizer
  • Custom fast scanner
  • Large input handling
  • Output batching
  • Precision formatting

22.2 Implementation discipline

  • Template setup
  • Constants
  • Utility functions
  • Edge case tests
  • Overflow prevention
  • Modular arithmetic helpers
  • Comparator correctness
  • Custom pair class
  • Custom tuple class
  • Debug helpers
  • Local testing

22.3 Common competitive patterns

  • Coordinate compression
  • Offline queries
  • Mo’s algorithm
  • Binary lifting
  • Lowest common ancestor
  • Euler tour
  • Difference constraints
  • Prefix function
  • Z-function
  • Rolling hash
  • DSU rollback
  • Divide and conquer optimization

22.4 Contest strategy

  • Read all problems
  • Classify difficulty
  • Identify known patterns
  • Solve easy first
  • Estimate complexity
  • Avoid overengineering
  • Build sample tests
  • Stress test
  • Submit carefully
  • Debug wrong answer
  • Debug TLE
  • Debug MLE

23. Interview Problem-Solving

23.1 Interview approach

  • Clarify problem
  • Restate problem
  • Ask about constraints
  • Ask about input size
  • Ask about duplicates
  • Ask about null/empty input
  • Provide examples
  • Discuss brute force
  • Optimize step by step
  • Explain trade-offs
  • Code cleanly
  • Test manually
  • Analyze complexity

23.2 Interview pattern recognition

  • Array pattern
  • Hash map pattern
  • Two pointers pattern
  • Sliding window pattern
  • Stack pattern
  • Binary search pattern
  • Tree DFS pattern
  • Tree BFS pattern
  • Graph BFS pattern
  • Graph DFS pattern
  • Topological sort pattern
  • Heap pattern
  • Backtracking pattern
  • Dynamic programming pattern
  • Greedy pattern

23.3 Coding quality

  • Meaningful variable names
  • Small helper functions
  • Clear conditionals
  • Boundary handling
  • Avoid duplicated logic
  • Avoid hidden state
  • Avoid unnecessary mutation
  • Avoid excessive abstraction
  • Simplicity
  • Readability
  • Correctness
  • Complexity awareness

23.4 Testing in interviews

  • Empty input
  • Single element
  • Two elements
  • Duplicates
  • Negative numbers
  • Large numbers
  • Sorted input
  • Reverse sorted input
  • All equal elements
  • No solution case
  • Multiple solution case
  • Boundary values

23.5 Common interview topics

  • Arrays
  • Strings
  • Hash maps
  • Linked lists
  • Stacks
  • Queues
  • Trees
  • Binary search trees
  • Heaps
  • Graphs
  • Recursion
  • Backtracking
  • Dynamic programming
  • Greedy algorithms
  • Sorting
  • Binary search
  • Bit manipulation

24. Java-Specific DSA

24.1 Java collections

  • ArrayList
  • LinkedList
  • ArrayDeque
  • PriorityQueue
  • HashMap
  • LinkedHashMap
  • TreeMap
  • HashSet
  • LinkedHashSet
  • TreeSet
  • Collections
  • Arrays
  • Comparator
  • Comparable

24.2 Java implementation details

  • Primitive arrays
  • Object arrays
  • Autoboxing cost
  • int vs Integer
  • long vs Long
  • String immutability
  • StringBuilder
  • HashCode contract
  • Equals contract
  • PriorityQueue comparator
  • TreeMap comparator
  • Integer overflow
  • Recursion stack limits

24.3 Java performance considerations

  • Fast input
  • Avoid Scanner in contests
  • Use BufferedReader
  • Use StringBuilder for output
  • Avoid excessive object creation
  • Avoid boxing in hot loops
  • Prefer arrays for performance
  • Use primitive collections if available
  • Pre-size HashMap
  • Pre-size ArrayList
  • Comparator overhead
  • Recursion-to-iteration conversion

24.4 Java DSA templates

  • FastScanner
  • Pair class
  • Tuple class
  • Graph adjacency list
  • DSU class
  • Segment tree class
  • Fenwick tree class
  • Trie class
  • BFS template
  • DFS template
  • Dijkstra template
  • Topological sort template
  • Binary search template
  • DP memoization template

25. System Design Connections

25.1 Data structure usage in systems

  • Hash table in caches
  • Linked list in LRU cache
  • Heap in schedulers
  • Queue in messaging
  • Stack in parsers
  • Trie in autocomplete
  • Bloom filter in databases
  • B-tree in indexes
  • LSM-tree in storage engines
  • Graph in dependency systems
  • Segment tree in analytics
  • Consistent hashing in distributed systems

25.2 Algorithm usage in systems

  • Rate limiting algorithms
  • Load balancing algorithms
  • Cache eviction algorithms
  • Scheduling algorithms
  • Consensus algorithms
  • Replication algorithms
  • Compression algorithms
  • Search ranking algorithms
  • Recommendation algorithms
  • Pathfinding algorithms
  • Deduplication algorithms

25.3 Practical algorithms for backend engineering

  • LRU cache
  • LFU cache
  • Token bucket
  • Leaky bucket
  • Sliding window rate limiter
  • Consistent hashing
  • Rendezvous hashing
  • Bloom filter
  • Top-k heavy hitters
  • Count-Min Sketch
  • Reservoir sampling
  • Retry backoff
  • Circuit breaker state machine

26. Learning Path

26.1 Phase 1 — Foundations

  • Complexity analysis
  • Arrays
  • Strings
  • Linked lists
  • Stacks
  • Queues
  • Hash maps
  • Basic recursion
  • Basic sorting
  • Basic binary search

26.2 Phase 2 — Core patterns

  • Two pointers
  • Sliding window
  • Prefix sums
  • Difference arrays
  • Monotonic stack
  • Monotonic queue
  • Fast and slow pointers
  • Backtracking
  • Basic tree DFS
  • Basic tree BFS

26.3 Phase 3 — Trees and heaps

  • Binary trees
  • Binary search trees
  • Tree traversal
  • Tree recursion
  • Lowest common ancestor
  • Heap
  • Priority queue
  • Top-k patterns
  • Trie
  • Segment tree basics
  • Fenwick tree basics

26.4 Phase 4 — Graphs

  • Graph representation
  • BFS
  • DFS
  • Connected components
  • Cycle detection
  • Topological sort
  • Bipartite check
  • Union-Find
  • Shortest paths
  • Minimum spanning tree
  • Strongly connected components

26.5 Phase 5 — Dynamic programming

  • 1D DP
  • 2D DP
  • Knapsack DP
  • Sequence DP
  • String DP
  • Grid DP
  • Tree DP
  • Interval DP
  • Bitmask DP
  • DP optimization basics

26.6 Phase 6 — Advanced algorithms

  • Advanced graph algorithms
  • Network flow
  • Advanced string algorithms
  • Advanced trees
  • Computational geometry
  • Number theory
  • Combinatorics
  • Probabilistic algorithms
  • Meet-in-the-middle
  • Sweep line
  • Offline algorithms

26.7 Phase 7 — Interview readiness

  • Pattern classification
  • Timed practice
  • Explanation practice
  • Complexity explanation
  • Edge case testing
  • Clean implementation
  • Medium-level problem fluency
  • Hard-level problem exposure
  • Mock interviews
  • Review weak topics

26.8 Phase 8 — Engineering-level DSA

  • Cache design
  • Rate limiter algorithms
  • Consistent hashing
  • Bloom filters
  • Storage engine structures
  • Database index structures
  • Search data structures
  • Streaming algorithms
  • Approximate algorithms
  • Distributed algorithms basics

27. Practice Projects

27.1 Project 1 — Data Structure Library

  • Dynamic array
  • Singly linked list
  • Doubly linked list
  • Stack
  • Queue
  • Deque
  • Hash map
  • Binary search tree
  • Heap
  • Trie
  • Unit tests
  • Benchmark tests

27.2 Project 2 — Algorithm Visualizer

  • Sorting visualization
  • Binary search visualization
  • BFS visualization
  • DFS visualization
  • Dijkstra visualization
  • Union-Find visualization
  • Backtracking visualization
  • DP table visualization
  • Time complexity display
  • Step-by-step execution

27.3 Project 3 — Competitive Programming Template

  • Fast input
  • Fast output
  • DSU template
  • Graph template
  • Segment tree template
  • Fenwick tree template
  • Modular arithmetic template
  • Binary search template
  • BFS template
  • DFS template
  • Dijkstra template
  • Testing harness

27.4 Project 4 — Search Autocomplete Engine

  • Trie
  • Prefix search
  • Ranking
  • Top-k suggestions
  • Frequency updates
  • Fuzzy matching
  • Memory optimization
  • Benchmarking
  • Test cases
  • API wrapper

27.5 Project 5 — Cache System

  • LRU cache
  • LFU cache
  • TTL cache
  • Concurrent access
  • Eviction policy
  • Hit ratio tracking
  • Capacity management
  • Expiration cleanup
  • Unit tests
  • Load tests

27.6 Project 6 — Graph Toolkit

  • Graph representation
  • BFS
  • DFS
  • Topological sort
  • Dijkstra
  • Bellman-Ford
  • Floyd-Warshall
  • Kruskal
  • Prim
  • SCC algorithms
  • Bridges
  • Articulation points
  • Unit tests

27.7 Project 7 — Rate Limiter Library

  • Fixed window
  • Sliding window log
  • Sliding window counter
  • Token bucket
  • Leaky bucket
  • Distributed counter simulation
  • Memory analysis
  • Throughput analysis
  • Unit tests
  • Benchmark tests

27.8 Project 8 — Text Search Engine

  • Tokenizer
  • Inverted index
  • Term frequency
  • Document frequency
  • BM25 scoring
  • Boolean search
  • Phrase search
  • Prefix search
  • Ranking
  • Index persistence
  • Query benchmark

27.9 Project 9 — Pathfinding Simulator

  • Grid graph
  • BFS
  • DFS
  • Dijkstra
  • A*
  • Heuristic function
  • Obstacle handling
  • Weighted terrain
  • Path reconstruction
  • Visualization
  • Performance comparison

27.10 Project 10 — Streaming Analytics

  • Running average
  • Running median
  • Top-k frequent elements
  • Count-Min Sketch
  • Bloom filter
  • Reservoir sampling
  • Sliding window metrics
  • Heavy hitter detection
  • Memory-bounded processing
  • Benchmarking

28. Problem Sets by Topic

28.1 Arrays and strings

  • Two Sum
  • Best Time to Buy and Sell Stock
  • Maximum Subarray
  • Product of Array Except Self
  • Contains Duplicate
  • Move Zeroes
  • Rotate Array
  • Valid Anagram
  • Group Anagrams
  • Longest Substring Without Repeating Characters
  • Minimum Window Substring
  • Longest Palindromic Substring

28.2 Linked lists

  • Reverse Linked List
  • Merge Two Sorted Lists
  • Linked List Cycle
  • Remove Nth Node From End
  • Add Two Numbers
  • Copy List with Random Pointer
  • Reorder List
  • Palindrome Linked List
  • Intersection of Two Linked Lists
  • Sort List

28.3 Stacks and queues

  • Valid Parentheses
  • Min Stack
  • Evaluate Reverse Polish Notation
  • Daily Temperatures
  • Next Greater Element
  • Largest Rectangle in Histogram
  • Sliding Window Maximum
  • Implement Queue using Stacks
  • Implement Stack using Queues
  • Decode String

28.4 Trees

  • Maximum Depth of Binary Tree
  • Invert Binary Tree
  • Diameter of Binary Tree
  • Balanced Binary Tree
  • Same Tree
  • Subtree of Another Tree
  • Lowest Common Ancestor
  • Binary Tree Level Order Traversal
  • Validate Binary Search Tree
  • Kth Smallest Element in BST
  • Construct Binary Tree from Traversals
  • Binary Tree Maximum Path Sum

28.5 Graphs

  • Number of Islands
  • Clone Graph
  • Course Schedule
  • Pacific Atlantic Water Flow
  • Word Ladder
  • Graph Valid Tree
  • Number of Connected Components
  • Alien Dictionary
  • Network Delay Time
  • Cheapest Flights Within K Stops
  • Redundant Connection
  • Critical Connections

28.6 Dynamic programming

  • Climbing Stairs
  • House Robber
  • Coin Change
  • Longest Increasing Subsequence
  • Longest Common Subsequence
  • Word Break
  • Combination Sum IV
  • Decode Ways
  • Unique Paths
  • Edit Distance
  • Burst Balloons
  • Regular Expression Matching

28.7 Greedy

  • Jump Game
  • Jump Game II
  • Gas Station
  • Candy
  • Partition Labels
  • Task Scheduler
  • Non-overlapping Intervals
  • Minimum Number of Arrows
  • Queue Reconstruction
  • Remove K Digits
  • Binary Search
  • Search Insert Position
  • Find First and Last Position
  • Search Rotated Sorted Array
  • Find Minimum in Rotated Sorted Array
  • Median of Two Sorted Arrays
  • Koko Eating Bananas
  • Capacity To Ship Packages
  • Split Array Largest Sum
  • Find Peak Element

28.9 Heaps

  • Kth Largest Element
  • Top K Frequent Elements
  • Find Median from Data Stream
  • Merge K Sorted Lists
  • Task Scheduler
  • Reorganize String
  • Last Stone Weight
  • K Closest Points to Origin
  • Sliding Window Median
  • IPO

28.10 Backtracking

  • Subsets
  • Permutations
  • Combinations
  • Combination Sum
  • Generate Parentheses
  • Word Search
  • Palindrome Partitioning
  • N-Queens
  • Sudoku Solver
  • Restore IP Addresses

29. Competency Checklist

29.1 Junior DSA competency

  • Analyze simple time complexity
  • Analyze simple space complexity
  • Use arrays correctly
  • Use strings correctly
  • Use hash maps correctly
  • Use stacks correctly
  • Use queues correctly
  • Implement linked list basics
  • Implement recursion basics
  • Implement binary search basics
  • Solve easy array problems
  • Solve easy string problems
  • Solve easy linked list problems

29.2 Mid-level DSA competency

  • Recognize common patterns
  • Use two pointers
  • Use sliding window
  • Use prefix sums
  • Use monotonic stack
  • Use heaps
  • Traverse trees
  • Traverse graphs
  • Implement BFS
  • Implement DFS
  • Implement Union-Find
  • Implement topological sort
  • Solve medium interview problems
  • Explain complexity clearly

29.3 Senior DSA competency

  • Design correct algorithms from constraints
  • Prove greedy correctness
  • Design dynamic programming states
  • Optimize DP space
  • Analyze complex recurrence relations
  • Implement shortest path algorithms
  • Implement MST algorithms
  • Use advanced tree structures
  • Use segment trees
  • Use Fenwick trees
  • Use tries effectively
  • Debug hard algorithmic bugs
  • Solve hard interview problems

29.4 Advanced DSA competency

  • Implement advanced graph algorithms
  • Implement network flow
  • Implement advanced string algorithms
  • Implement persistent data structures
  • Implement probabilistic data structures
  • Use computational geometry
  • Use number theory algorithms
  • Use combinatorics algorithms
  • Use advanced DP optimization
  • Use offline algorithms
  • Connect DSA to system design
  • Build reusable algorithm libraries
  • Benchmark and optimize implementations