study-index.md

🎯 Data Structures & Algorithms (DSA) — Complete Mastery Roadmap

Goal: Master DSA from absolute zero to FAANG / Top-Tier Tech Interview-Ready
Language: C++ (Modern C++17 / C++20 standard, STL deep-dives + custom implementations)
Total Estimated Time: 12–16 weeks (part-time) or 6–8 weeks (intensive)

🗺️ Visual Learning Path

┌──────────────────────────────────────────────┐ │ 00: The Master Problem-Solving Engine │ │ (Pattern Diagnostic Tree, Signals, Big-O) │ └──────────────────────┬───────────────────────┘ │ ▼ ┌──────────────────────────────────────────────┐ │ 01: Time & Space Complexity Analysis │ │ (Big O, Omega, Theta, Amortized, Recursion) │ └──────────────────────┬───────────────────────┘ │ ▼ ┌──────────────────────────────────────────────┐ │ 02: Arrays & Strings │ │ (Two Pointers, Sliding Window, Prefix Sum) │ └──────────────────────┬───────────────────────┘ │ ┌────────────────────┴────────────────────┐ ▼ ▼ ┌───────────────────────────┐ ┌───────────────────────────┐ │ 03: Linked Lists │ │ 04: Stacks & Queues │ │ (Fast/Slow, Reversal, K) │ │ (Monotonic, Min-Stack, Q) │ └─────────────┬─────────────┘ └─────────────┬─────────────┘ │ │ └────────────────────┬────────────────────┘ ▼ ┌──────────────────────────────────────────────┐ │ 05: Hash Tables │ │ (Collisions, Chaining, Open Addressing) │ └──────────────────────┬───────────────────────┘ │ ┌────────────────────┴────────────────────┐ ▼ ▼ ┌───────────────────────────┐ ┌───────────────────────────┐ │ 06: Trees │ │ 07: Heaps & Priority Queues│ │ (BST, AVL, LCA, Morris) │ │ (Heapify O(N), Top-K, Strm)│ └─────────────┬─────────────┘ └─────────────┬─────────────┘ │ │ └────────────────────┬────────────────────┘ ▼ ┌──────────────────────────────────────────────┐ │ 08: Graphs │ │ (BFS/DFS, TopoSort, Dijkstra, MST, Cycles) │ └──────────────────────┬───────────────────────┘ │ ▼ ┌──────────────────────────────────────────────┐ │ 09: Dynamic Programming │ │ (1D/2D, Knapsack, LCS, LIS, Intervals, Trees)│ └──────────────────────┬───────────────────────┘ │ ▼ ┌──────────────────────────────────────────────┐ │ 10: Advanced Data Structures │ │ (Tries, Segment Trees, DSU, Bitmasks, Back) │ └──────────────────────┬───────────────────────┘ │ ▼ ┌──────────────────────────────────────────────┐ │ 11: Interview Patterns & 100+ Problem Bank │ │ (20 Patterns, Strategy, FAANG Walkthroughs) │ └──────────────────────────────────────────────┘

📚 Module Curriculum Overview

#ModuleCore TopicsFocus / OutcomeEst. Time
00How to Solve Any DSA ProblemThe Grand Diagnostic Decision Tree, 25+ Linguistic Signals, Constraint-to-Complexity Matrix, 6-Step ProtocolMaster pattern recognition for unseen problems2–3 Days
01Time & Space ComplexityBig $O$, $\Omega$, $\Theta$, Amortized Analysis (Vector expansion), Master Theorem, Call Stack Memory5 Problems3–4 Days
02Arrays & StringsCache Locality, Two Pointers, Sliding Window, Prefix Sum, Difference Array, Kadane's, String Rolling Hash6 Problems7–9 Days
03Linked ListsSingly/Doubly/Circular, Floyd's Cycle Detection, In-place Reversal, K-Group Reversal, LRU Cache internal list5 Problems5–7 Days
04Stacks & QueuesMonotonic Stack, Min Stack $O(1)$, Monotonic Deque, Sliding Window Maximum, Circular Buffer5 Problems5–7 Days
05Hash TablesMurmurHash, Collision Resolution (Chaining vs Open Addressing), unordered_map vs map, Subarray Sum Patterns5 Problems5–7 Days
06TreesDFS/BFS Traversals, Morris Traversal, BST Operations, LCA, Tree Diameter, Path Sums, Serialization6 Problems8–10 Days
07Heaps & Priority QueuesMin/Max Heap from scratch, $O(N)$ buildHeap mathematical proof, Top-K, Two Heaps (Median Stream), K-Way Merge5 Problems5–7 Days
08GraphsAdjacency Repr, BFS/DFS, Cycle Detection, Kahn's TopoSort, Dijkstra, Bellman-Ford, Prim/Kruskal MST, Bipartite6 Problems10–12 Days
09Dynamic ProgrammingMemoization $\to$ Tabulation $\to$ Space Optimization, 1D/2D, 0/1 & Unbounded Knapsack, LCS, LIS, Interval DP, Tree DP6 Problems12–14 Days
10Advanced DS & AlgorithmsTrie & Bitwise Trie, Disjoint Set Union (DSU with Rank & Path Compression), Segment Tree, Bitmask DP, Backtracking6 Problems10–12 Days
11Interview Patterns & Problem Bank20 Must-Know Algorithmic Patterns, 100+ Categorized Problems with Solutions, Whiteboard Strategy100+ ProblemsOngoing
12Segment Tree & Fenwick Tree (Deep Dive)Build, Range Query, Point Update, Lazy Propagation, BIT with i & (-i) trick, 2D BIT, When to use which10 Problems7–9 Days

⚡ Big-O Complexity Quick Reference

Data Structure Operations

Data StructureAccessSearchInsertionDeletionSpace Complexity
Array / Vector$O(1)$$O(N)$$O(N)$ (amortized $O(1)$ at end)$O(N)$$O(N)$
Singly Linked List$O(N)$$O(N)$$O(1)$ (with pointer)$O(1)$ (with pointer)$O(N)$
Doubly Linked List$O(N)$$O(N)$$O(1)$$O(1)$$O(N)$
Stack / Queue$O(N)$$O(N)$$O(1)$ (push/enqueue)$O(1)$ (pop/dequeue)$O(N)$
Hash Table (unordered_map)N/A$O(1)$ avg / $O(N)$ worst$O(1)$ avg / $O(N)$ worst$O(1)$ avg / $O(N)$ worst$O(N)$
BST (Balanced - AVL/Red-Black)$O(\log N)$$O(\log N)$$O(\log N)$$O(\log N)$$O(N)$
Binary Heap / Priority Queue$O(1)$ (top)$O(N)$$O(\log N)$$O(\log N)$ (pop)$O(N)$
TrieN/A$O(L)$ ($L = \text{length}$)$O(L)$$O(L)$$O(N \cdot L)$
Disjoint Set Union (DSU)N/A$O(\alpha(N)) \approx O(1)$$O(\alpha(N)) \approx O(1)$N/A$O(N)$
Segment TreeN/A$O(\log N)$ (Range Query)$O(\log N)$ (Point Update)$O(\log N)$$O(N)$

📋 Comprehensive Interview Readiness Checklist

1. Pattern Recognition & Foundations

  • Able to identify the required Big-O within 15 seconds from input constraints $N$.
  • Can navigate the Problem-to-Pattern decision tree from scratch without hesitation.
  • Mastered the 25+ linguistic signal triggers.
  • Understand why $O(2N) = O(N)$ and why constants matter in real hardware (cache misses).
  • Able to prove dynamic array amortized $O(1)$ insertion using aggregate and potential methods.
  • Can solve recurrence relations with the Master Theorem ($T(N) = aT(N/b) + f(N)$).

2. Linear Structures & Techniques

  • Two pointers on sorted arrays (collision, slow/fast, opposite ends).
  • Variable vs Fixed sliding window template memorized and understood.
  • 1D and 2D prefix sums for instant range queries.
  • Kadane's algorithm and its extension to indices & maximum product subarray.
  • Reversing singly linked list iteratively and recursively in $O(1)$ auxiliary space.
  • Floyd's Tortoise and Hare algorithm for cycle detection and meeting point math ($2k - k = \text{loop length}$).
  • Monotonic stack template for Next Greater Element and Largest Rectangle in Histogram.
  • Monotonic deque for Sliding Window Maximum in $O(N)$ total time.

3. Non-Linear Structures

  • Internal working of Hash Tables: hash codes, bucket compression, load factor $> 0.7$, and Robin Hood / Chaining.
  • Binary Tree traversals: Pre-order, In-order, Post-order, Level-order, and Morris Traversal ($O(1)$ space).
  • Binary Search Tree: Search, Insert, and 3-case Deletion (leaf, single child, two children with inorder successor).
  • Binary Heap array math: parent = $(i-1)/2$, left = $2i+1$, right = $2i+2$.
  • Mathematical proof of why buildHeap is $O(N)$ and not $O(N \log N)$.
  • Median of Data Stream using two balancing heaps (Max-Heap + Min-Heap).

4. Graphs & Dynamic Programming

  • Graph representations: Adjacency List vs Matrix tradeoffs.
  • Kahn's algorithm for Topological Sort and Cycle Detection in DAGs.
  • Dijkstra's Algorithm using Min-Heap priority queue ($O((V + E) \log V)$).
  • Bellman-Ford algorithm for negative edge weights and negative cycle detection.
  • Union-Find / DSU with path compression and rank optimization ($\alpha(N)$ inverse Ackermann).
  • DP Transition identification: State definition $\to$ Recurrence Relation $\to$ Base Cases $\to$ Space Optimization.
  • 0/1 Knapsack vs Unbounded Knapsack state array compression ($1D$ reverse iteration vs forward iteration).
  • Longest Common Subsequence (LCS) and Edit Distance 2D table construction.
  • Longest Increasing Subsequence (LIS) in $O(N \log N)$ via Binary Search / Patience Sorting.

5. Advanced Topics

  • Trie construction, search, prefix matching, and Bitwise Trie for maximum XOR sub-arrays.
  • Segment Tree range queries and point updates in $O(\log N)$.
  • Bit manipulation tricks: n & (n - 1) (clearing lowest set bit), n & -n (isolating lowest set bit).
  • Backtracking template: Base Case $\to$ Loop candidates $\to$ Pruning $\to$ Choose $\to$ Recurse $\to$ Unchoose.

6. Segment Tree & Fenwick Tree (Module 12 Deep Dive)

  • Segment Tree build in $O(N)$ — understand the recursive structure and the 1-indexed flat array representation.
  • Segment Tree range query: memorize the 3 cases (no overlap, complete overlap, partial overlap).
  • Segment Tree point update: trace the path from root to leaf and back.
  • Lazy Propagation: range update in $O(\log N)$ — understand pushDown() and when to call it.
  • Fenwick Tree i & (-i) trick: know which range BIT[i] covers.
  • Fenwick prefix sum query: walk left by removing LSB.
  • Fenwick point update: walk right by adding LSB.
  • Advanced BIT (two BITs for range update + range sum query).
  • 2D Fenwick Tree for matrix range sum queries.
  • Decision: when to use Fenwick Tree vs Segment Tree.

🛠️ Recommended Daily Study Routine

┌────────────────────────────────────────────────────────────────────────┐ │ Phase 1: Pattern Recognition & Blueprint Reading (20 mins) │ │ - Study Module 00 & Module-specific decision logic. │ │ - Identify linguistic signals and template invariants. │ ├────────────────────────────────────────────────────────────────────────┤ │ Phase 2: Code Implementation from Scratch (30-40 mins) │ │ - Implement the core data structure or pattern template in C++. │ │ - Write down the invariant rules in comments. │ ├────────────────────────────────────────────────────────────────────────┤ │ Phase 3: Deliberate Practice (3-Pass Solving) (60-90 mins) │ │ - Attempt unseen problems without looking at hints for 25 mins. │ │ - Tag the problem with its pattern in your personal study log. │ ├────────────────────────────────────────────────────────────────────────┤ │ Phase 4: Verbal Mock Interviewing (20 mins) │ │ - Walk through the 6-Step Dissection Protocol out loud. │ └────────────────────────────────────────────────────────────────────────┘