# Complete Coding Interview (Blind 75 / NeetCode DSA), System Design & Advanced SQL Study Guide

> Software engineering technical interview mastery: Big-O complexity, Arrays, Sliding Window, Two Pointers, Trees, Graphs (BFS, DFS, Dijkstra, Topological Sort), Dynamic Programming (Blind 75 / NeetCode 150), Advanced SQL Window Functions/CTEs/Indexing, and Distributed System Design

- **Canonical URL:** https://flashcards.world/guides/en/pillar-coding-interviews-blind-75-neetcode-dsa-system-design-sql-study-guide/
- **Markdown URL:** https://flashcards.world/guides/en/pillar-coding-interviews-blind-75-neetcode-dsa-system-design-sql-study-guide.md
- **Topic / Curriculum:** Coding Interviews (Blind 75 / NeetCode DSA), Distributed System Design & Advanced SQL
- **Language:** en

# Complete Coding Interview (Blind 75 / NeetCode DSA), System Design & Advanced SQL Study Guide

> **Comprehensive Active-Recall Curriculum**: Software engineering technical interview mastery: Big-O complexity, Arrays, Sliding Window, Two Pointers, Trees, Graphs (BFS, DFS, Dijkstra, Topological Sort), Dynamic Programming (Blind 75 / NeetCode 150), Advanced SQL Window Functions/CTEs/Indexing, and Distributed System Design. Practice **6 progressive flashcard decks (192 cards total)** spanning foundational principles (`basic`), intermediate problem-solving (`intermediate`), and advanced exam mastery (`advanced`).

👉 **[Explore All Coding Interviews (Blind 75 / NeetCode DSA), Distributed System Design & Advanced SQL Flashcard Decks on Flashcards.World →](https://flashcards.world/flashcards/?q=Coding%20Interviews%20%28Blind%2075%20/%20NeetCode%20DSA%29%2C%20Distributed%20System%20Design%20%26%20Advanced%20SQL&back_lng=en)**

---

## Why Active Recall & Spaced Repetition Work for This Exam

Mastering **Coding Interviews (Blind 75 / NeetCode DSA), Distributed System Design & Advanced SQL** requires retrieving precise definitions, formulas, diagnostic rules, and edge-case distinctions under timed pressure. Passive re-reading creates an illusion of competence; **active recall** (testing yourself before viewing the answer) and **spaced repetition** strengthen long-term synaptic retrieval pathways.

| Study Phase | Decks Covered | Target Mastery Level | Daily Active-Recall Protocol |
| :--- | :--- | :--- | :--- |
| **Phase 1: Foundations (Weeks 1–2)** | Decks 1 & 2 (`Basic`) | 90%+ Instant Recall | 32 new cards/day + full review of missed concepts |
| **Phase 2: Application (Weeks 3–5)** | Decks 3 & 4 (`Intermediate`) | Multi-step synthesis | 32 new cards/day + interleaved Phase 1 review |
| **Phase 3: Exam Mastery (Weeks 6–8)** | Decks 5 & 6 (`Advanced`) | Timed exam readiness | Full 192-card spaced-repetition rotation + weak-spot drills |

---

## Deck 1: Big-O Complexity, Arrays, Two Pointers, Sliding Window & Hashing Patterns (32 Cards — Basic)

**What this deck covers**: Foundational Software Engineering interview mastery covering Big-O time and space complexity, the Master Theorem, amortized dynamic array analysis, Prefix Sums, Difference Arrays, Kadane's Algorithm, Boyer-Moore Majority Vote, Dutch National Flag, Two Pointers, Sliding Window templates, Hash Table collision resolution, and Rabin-Karp Rolling Hash.

| High-Yield Prompt / Question | Verified Answer & Exam Application |
| :--- | :--- |
| **Define Big-O ($O$), Big-Omega ($\Omega$), and Big-Theta ($\Theta$) asymptotic notations.** | $O(f(n))$ (Asymptotic Upper Bound): The growth rate is no faster than $c \cdot f(n)$ for $n \ge n_0$. $\Omega(f(n))$ (Asymptotic Lower Bound): The growth rate is at least $c \cdot f(n)$. $\Theta(f(n))$ (Asymptotic Tight Bound): The function is bounded both above and below by $f(n)$. Note: In coding interviews, candidates say 'Big-O' to refer to the tightest upper bound of the worst-case (or expected) runtime. |
| **Order the common complexity classes from fastest to slowest growth, and map maximum input size $N$ that passes within a ~1-second ($10^8$ ops) interview limit.** | $O(1) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$. Input size guide: $N \le 11 \implies O(n!)$; $N \le 20 \implies O(2^n)$ or $O(n 2^n)$ (backtracking/bitmask DP); $N \le 500 \implies O(n^3)$; $N \le 5,000 \implies O(n^2)$; $N \le 2 \times 10^5 \implies O(n \log n)$ (sorting/heap/divide & conquer); $N \le 10^6–10^7 \implies O(n)$; $N > 10^9 \implies O(\log n)$ or $O(1)$. |
| **State the three cases of the Master Theorem for divide-and-conquer recurrences $T(n) = a T(n/b) + f(n)$ where $a \ge 1, b > 1$.** | Let $c_{\text{crit}} = \log_b a$ (so work at leaves is $n^{\log_b a}$): Case 1 (Leaf-heavy): If $f(n) = O(n^{c_{\text{crit}} - \epsilon})$, then $T(n) = \Theta(n^{\log_b a})$ (e.g., binary tree traversal $2T(n/2) + O(1) = \Theta(n)$). Case 2 (Balanced across levels): If $f(n) = \Theta(n^{c_{\text{crit}}} \log^k n)$, then $T(n) = \Theta(n^{c_{\text{crit}}} \log^{k+1} n)$ (e.g., Merge Sort $2T(n/2) + \Theta(n) = \Theta(n \log n)$, Binary Search $T(n/2) + \Theta(1) = \Theta(\log n)$). Case 3 (Root-heavy): If $f(n) = \Omega(n^{c_{\text{crit}} + \epsilon})$, then $T(n) = \Theta(f(n))$ (e.g., Quickselect average $T(n/2) + O(n) = \Theta(n)$). |
| **Why is appending to a Dynamic Array (`std::vector`, Python `list`, Java `ArrayList`) $O(1)$ amortized time even though resizing takes $O(n)$?** | When capacity is reached at powers of 2 ($1, 2, 4, 8, \dots, n$), the array allocates a new buffer of size $2n$ and copies $n$ elements. Across $n$ total `append` operations, the total cost is $n$ individual writes plus the geometric sum of copies: $1 + 2 + 4 + 8 + \dots + n/2 + n < 2n$. Dividing total work $< 3n$ by $n$ operations yields $O(1)$ amortized time per append! (If it grew by a constant $+k$ instead of $\times 2$, total work would be arithmetic $\Theta(n^2)$, or $O(n)$ amortized per append). |
| **What is Auxiliary Space Complexity vs. Total Space Complexity, and how does the recursion call stack affect it?** | Total Space Complexity includes both the input storage and extra memory; Auxiliary Space Complexity counts ONLY the extra memory allocated by the algorithm beyond the input (plus output if required). Every active recursive call frame stays on the call stack simultaneously—so a DFS on a skewed binary tree of $n$ nodes uses $O(n)$ auxiliary call-stack space, whereas on a balanced tree it uses $O(\log n)$ space. |
| **Explain the 1D Prefix Sum pattern and how it answers arbitrary range sum queries `sum(L, R)` in $O(1)$ time.** | Precompute an array `P` of length $n + 1$ in $O(n)$ time where `P[0] = 0` and `P[i + 1] = P[i] + nums[i]` (so `P[k]` is the sum of the first $k$ elements). Then the sum of any contiguous subarray `nums[L..R]` (inclusive, 0-indexed) is simply `P[R + 1] - P[L]` in $O(1)$ time. |
| **How do you solve 'Subarray Sum Equals K' (`LeetCode 560`) in $O(n)$ time and $O(n)$ space when the array contains negative numbers?** | Because the array can contain negative numbers, a sliding window does NOT work (expanding/shrinking is non-monotonic). Instead, combine Prefix Sums with a Hash Map `freq` initialized to `{0: 1}` (recording how many times each prefix sum has occurred so far). As you iterate and maintain `curr_sum += x`, a subarray ending at the current index sums to $K$ whenever `curr_sum - K` already exists in `freq` (`ans += freq[curr_sum - K]`), then increment `freq[curr_sum] += 1`. |
| **How does a 2D Prefix Sum matrix compute the sum of any rectangular subgrid `(r1, c1)` to `(r2, c2)` in $O(1)$ time?** | Using Inclusion-Exclusion, build `P` of size $(R+1) \times (C+1)$ where `P[r+1][c+1] = grid[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]`. Then for any query rectangle `(r1, c1)` to `(r2, c2)` (inclusive, 0-indexed): `sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]` in $O(1)$ time (`LeetCode 304`). |
| **What is a Difference Array and how does it apply $Q$ range addition updates `[L, R, +val]` in $O(1)$ per update?** | The Difference Array `D` is the inverse of Prefix Sums (`D[0] = A[0]`, `D[i] = A[i] - A[i-1]`). To add `val` to every element in `A[L..R]`, simply set `D[L] += val` and `D[R + 1] -= val` in $O(1)$ time! After all $Q$ updates are applied, take the prefix sum of `D` in $O(n)$ time to reconstruct the final array (`LeetCode 370 Range Addition`, `1094 Car Pooling`, `1109 Corporate Flight Bookings`). |
| **Explain Kadane's Algorithm for Maximum Subarray Sum (`LeetCode 53`) and how it extends to Maximum Circular Subarray (`LeetCode 918`).** | Kadane's Algorithm maintains the maximum subarray sum ending at index $i$: `curr_max = max(x, curr_max + x)` and `best = max(best, curr_max)` in $O(n)$ time and $O(1)$ space. For a Circular Array, the max subarray either: 1. Does NOT wrap around (standard `max_kadane`), or 2. Wraps around both ends, which equals `total_sum - min_kadane` (where `min_kadane` is the minimum contiguous subarray sum). Handle the edge case where all numbers are negative (if `max_kadane < 0`, return `max_kadane`). |
| **How do you solve 'Product of Array Except Self' (`LeetCode 238`) in $O(n)$ time and $O(1)$ auxiliary space without using the division operator?** | Make two passes over the output array `res` (initialized to `1`s): 1. Left-to-right pass: maintain a running `prefix_prod = 1`; at each index $i$, set `res[i] = prefix_prod` and then update `prefix_prod *= nums[i]`. 2. Right-to-left pass: maintain a running `suffix_prod = 1`; at each index $i$, multiply `res[i] *= suffix_prod` and then update `suffix_prod *= nums[i]`. |
| **Explain the Boyer-Moore Majority Vote Algorithm (`LeetCode 169` & `229`) for finding elements appearing $> \lfloor n/2 \rfloor$ or $> \lfloor n/3 \rfloor$ times in $O(n)$ time and $O(1)$ space.** | Intuition: Pairing each occurrence of the majority element with a distinct non-majority element cancels them out, leaving the majority element standing. Maintain `candidate = None, count = 0`. For each `x`: if `count == 0`, set `candidate = x`; then `count += (1 if x == candidate else -1)`. (If a majority isn't guaranteed, verify `candidate` with a second counting pass). For $> \lfloor n/3 \rfloor$ (`LC 229`), there can be at most 2 such elements—maintain 2 candidates and 2 counters, decrementing both only when `x` matches neither. |

👉 **[Practice Deck 1: Big-O Complexity, Arrays, Two Pointers, Sliding Window & Hashing Patterns (32 Flashcards) →](https://flashcards.world/flashcards/sets/68e289db-c158-461d-a144-5bcad4aaf6d7/)**  
🔍 **[Browse All Basic Coding Interviews (Blind 75 / NeetCode DSA), Distributed System Design & Advanced SQL Sets →](https://flashcards.world/flashcards/?q=Coding%20Interviews%20%28Blind%2075%20/%20NeetCode%20DSA%29%2C%20Distributed%20System%20Design%20%26%20Advanced%20SQL&back_lng=en&expertise_level=basic)**

---

## Deck 2: Linked Lists, Stacks, Monotonic Queues, Binary Search & Heaps (32 Cards — Basic)

**What this deck covers**: Core data structures and algorithmic patterns for coding interviews covering Floyd's Cycle Detection proof, in-place Linked List manipulation, LRU & LFU Cache internals, Monotonic Stacks (Next Greater Element, Largest Rectangle in Histogram), Monotonic Deques, Binary Search on Answer Space, O(n) Heapify proof, Quickselect, and Two Heaps.

| High-Yield Prompt / Question | Verified Answer & Exam Application |
| :--- | :--- |
| **Prove mathematically why Floyd's Tortoise and Hare algorithm (`LeetCode 142 Linked List Cycle II`) finds the exact cycle entry node when resetting one pointer to `head`.** | Let $L$ be the distance from `head` to the cycle entry, $C$ be the cycle length, and $x$ be the distance from the cycle entry to the meeting point inside the cycle. When `slow` (1x speed) and `fast` (2x speed) meet: $2 \cdot d_{\text{slow}} = d_{\text{fast}} \implies 2(L + x) = L + x + kC \implies L + x = kC \implies L = kC - x = (k-1)C + (C - x)$. Since $(C - x)$ is the remaining distance from the meeting point forward to the cycle entry, advancing one pointer from `head` ($L$ steps) and the other from the meeting point at 1x speed guarantees they collide at the exact cycle entry! |
| **Which non-linked-list array problem can be solved in $O(n)$ time and $O(1)$ space using Floyd's Cycle Detection without modifying the array (`LeetCode 287 Find the Duplicate Number`)?** | Given an array `nums` of $n + 1$ integers where each value is in $[1, n]$, treat the array as a functional directed graph $i \to \text{nums}[i]$ starting from index `0` (which has in-degree 0 since no value is 0). Because two indices point to the same duplicate value $v$, node $v$ has in-degree $\ge 2$, forming the entry point of a cycle! Run Floyd's `slow = nums[slow]` and `fast = nums[nums[fast]]` until they meet, then reset `slow = 0` and step both by 1 (`slow = nums[slow]; fast = nums[fast]`) until they meet at the duplicate number. |
| **What is the iterative 3-pointer pattern for reversing a singly linked list in-place (`LeetCode 206`), and why is a `dummy` sentinel node useful in `Reverse Nodes in k-Group` (`LeetCode 25`)?** | To reverse in-place: initialize `prev = None, curr = head`; while `curr`: save `nxt = curr.next`, reverse pointer `curr.next = prev`, advance `prev = curr`, and `curr = nxt` (returns `prev`). In problems where the `head` node itself changes (such as `Reverse Nodes in k-Group`, `Remove Nth Node From End`, or `Partition List`), prepending `dummy = ListNode(0, head)` eliminates all special-case `if head` branching—you simply return `dummy.next`. |
| **How do you check if a Singly Linked List is a Palindrome (`LeetCode 234`) or `Reorder List` (`L0 -> Ln -> L1 -> Ln-1`, `LeetCode 143`) in $O(n)$ time and $O(1)$ space?** | Both problems share the same 3-step $O(1)$-space composition: 1. Find the middle of the linked list using `slow` (`+1`) and `fast` (`+2`) pointers; 2. Reverse the second half of the linked list in-place starting at `slow.next` (and sever `slow.next = None`); 3. Walk two pointers from `head` and the reversed second half simultaneously—either comparing values for Palindrome (then optionally re-reversing to restore the list) or alternatingly weaving nodes (`first.next = second; second.next = tmp1`) for `Reorder List`. |
| **How do you find the intersection node of two singly linked lists (`LeetCode 160`) in $O(m + n)$ time and $O(1)$ space without calculating lengths first?** | Initialize `pA = headA` and `pB = headB`. At each step, advance `pA = pA.next if pA else headB` and `pB = pB.next if pB else headA`. Why it works: if the lists have lengths $a + c$ and $b + c$ (where $c$ is the shared tail), both pointers travel the exact same total distance $a + c + b$ before meeting at the intersection node (or both reach `None` simultaneously at distance $m + n$ if $c = 0$). |
| **How do you deep-copy a Linked List with `next` and arbitrary `random` pointers (`LeetCode 138`) in $O(n)$ time and $O(1)$ auxiliary space (without a Hash Map)?** | Use the 3-Pass Interweaving Trick: Pass 1: For every original node `A`, insert its cloned node `A'` immediately after it (`A -> A' -> B -> B'`). Pass 2: Set random pointers on the clones using the adjacent mapping: `if curr.random: curr.next.random = curr.random.next`. Pass 3: Unweave the list to restore original `next` pointers (`A -> B`) and extract the cloned list (`A' -> B'`). |
| **How do you design an `LRU Cache` (`LeetCode 146`) where both `get(key)` and `put(key, value)` run in strict $O(1)$ time?** | Combine a **Hash Map** (`key -> Node*`) with a **Doubly Linked List** bounded by two sentinel dummy nodes (`head` and `tail`). The Hash Map provides $O(1)$ lookup of any node by key; the Doubly Linked List allows removing a node from the middle (`node.prev.next = node.next; node.next.prev = node.prev`) and inserting it at the Most-Recently-Used (MRU) end in $O(1)$ time (a singly linked list would take $O(n)$ to find `prev`!). On capacity overflow, evict `head.next` (or `tail.prev`, the Least-Recently-Used node) and delete its `node.key` from the Hash Map (which is why each DLL `Node` must store BOTH `key` and `val`!). |
| **How do you design an `LFU Cache` (Least Frequently Used, `LeetCode 460`) with strict $O(1)$ `get` and `put` operations?** | Maintain: 1. `key_to_node` Hash Map (`key -> Node(key, val, freq)`); 2. `freq_to_dll` Hash Map (`freq -> DoublyLinkedList` of nodes currently having that exact access frequency, ordered by recency to break ties via LRU); and 3. An integer `min_freq` tracking the lowest existing frequency. On `get(key)` or update: remove `node` from `freq_to_dll[f]`, increment `node.freq` to `f + 1`, append to `freq_to_dll[f + 1]`, and if `f == min_freq` and `freq_to_dll[f]` is now empty, increment `min_freq += 1`. On new key insertion when full: evict the LRU node from `freq_to_dll[min_freq]` and reset `min_freq = 1`. |
| **How does a `Min Stack` (`LeetCode 155`) support `push`, `pop`, `top`, and `getMin` in $O(1)$ time?** | Store pairs `(val, current_min)` on the stack (or maintain a parallel `min_stack` that only pushes when `val <= min_stack[-1]`): at each `push(val)`, the new `current_min` is `min(val, stack[-1][1])`. Because stack additions/removals follow LIFO order, the minimum of all elements below any stack depth is invariant until that element itself is popped! |
| **Explain the Monotonic Stack pattern and how it finds the `Next Greater Element` (or `Daily Temperatures`, `LeetCode 739`) for every element in $O(n)$ time.** | Maintain a stack of array indices whose values are in **monotonically decreasing** order from bottom to top. As you iterate `i` from `0` to `n - 1`: `while stack and nums[i] > nums[stack[-1]]:` pop `prev_idx = stack.pop()`—then `nums[i]` is the first strictly greater element to the right of `prev_idx` (`ans[prev_idx] = i - prev_idx`)! Then push `i` onto `stack`. Because each index is pushed once and popped at most once, the amortized time across all $n$ elements is $O(n)$. |
| **How does a Monotonic Increasing Stack solve 'Largest Rectangle in Histogram' (`LeetCode 84`) in $O(n)$ time?** | For each bar `h = heights[idx]`, the widest rectangle of height `h` extends left to the Previous Smaller Element (`PSE`) and right to the Next Smaller Element (`NSE`). Maintain a **monotonically increasing** stack of indices (append a sentinel height `0` at the end of `heights` to flush all remaining bars). When `heights[i] < heights[stack[-1]]`, pop `top = stack.pop()`: its height is `H = heights[top]`, its right boundary (exclusive) is `i`, its left boundary (exclusive) is `stack[-1]` (or `-1` if stack is empty), so `width = i - stack[-1] - 1` and `area = H * width`! |
| **How can you reduce 'Maximal Rectangle' of `1`s in a 2D binary matrix (`LeetCode 85`) to 'Largest Rectangle in Histogram'?** | Process the $R \times C$ binary matrix row by row from top to bottom, maintaining a 1D array `heights` of length $C$: for each column $c$, if `matrix[r][c] == '1'`, increment `heights[c] += 1`, else reset `heights[c] = 0`. After updating `heights` for row $r$, run the $O(C)$ Monotonic Stack 'Largest Rectangle in Histogram' algorithm on `heights`, yielding an overall $O(R \times C)$ time and $O(C)$ space solution. |

👉 **[Practice Deck 2: Linked Lists, Stacks, Monotonic Queues, Binary Search & Heaps (32 Flashcards) →](https://flashcards.world/flashcards/sets/51725164-b515-42e0-a6b2-850f1d36f3fc/)**  
🔍 **[Browse All Basic Coding Interviews (Blind 75 / NeetCode DSA), Distributed System Design & Advanced SQL Sets →](https://flashcards.world/flashcards/?q=Coding%20Interviews%20%28Blind%2075%20/%20NeetCode%20DSA%29%2C%20Distributed%20System%20Design%20%26%20Advanced%20SQL&back_lng=en&expertise_level=basic)**

---

## Deck 3: Trees, Tries, Graph Traversal (BFS/DFS/Dijkstra/Topological Sort) & Union-Find (32 Cards — Intermediate)

**What this deck covers**: Intermediate-to-advanced Tree and Graph algorithm patterns covering iterative and Morris O(1)-space tree traversals, BST validation, LCA, Tree Serialization, Prefix & Bitwise Tries, 0-1 and Multi-Source BFS, 3-color DFS cycle detection, Kahn's & DFS Topological Sort, Dijkstra, Bellman-Ford, Floyd-Warshall, Union-Find (DSU), MST (Kruskal/Prim), and Tarjan's Bridges.

| High-Yield Prompt / Question | Verified Answer & Exam Application |
| :--- | :--- |
| **How do you perform Iterative Preorder, Inorder, and Postorder Binary Tree traversals using an explicit Stack?** | Preorder (`Root, L, R`): Push `root`; while stack: pop `node`, visit it, then push `node.right` followed by `node.left` (so `left` is popped first). Inorder (`L, Root, R`): Initialize `curr = root`; while `curr or stack`: drill left (`while curr: stack.append(curr); curr = curr.left`), pop `curr = stack.pop()`, visit `curr`, then step right `curr = curr.right`. Postorder (`L, R, Root`): Either reverse a Modified Preorder (`Root, R, L`), or track `last_visited` when peeking at the stack top before popping. |
| **How does Morris Traversal achieve $O(n)$ time and $O(1)$ auxiliary space (no recursion or stack!) for Inorder Binary Tree traversal?** | Morris Traversal temporarily threads the right pointer of each node's **inorder predecessor** (the rightmost node in `curr.left`'s subtree) back to `curr`: 1. If `curr.left is None`, visit `curr` and advance `curr = curr.right`. 2. Otherwise, find `pred = curr.left` (`while pred.right and pred.right is not curr: pred = pred.right`): (a) If `pred.right is None`, create thread `pred.right = curr` and move `curr = curr.left`; (b) If `pred.right is curr` (left subtree finished!), remove thread `pred.right = None`, visit `curr`, and move `curr = curr.right`. Each edge is traversed at most 3 times ($O(n)$ time, $O(1)$ space). |
| **Why does simply checking `node.left.val < node.val < node.right.val` fail to validate a Binary Search Tree (`LeetCode 98 Validate BST`), and what is the correct $O(n)$ approach?** | Checking only immediate children fails when a deeper descendant violates an ancestor's bound (e.g., root `5`, right child `7`, and `7`'s left child is `3`—`3 < 7` locally, but `3 < 5` violates the root's right subtree invariant!). Correct approaches: 1. Pass `(low, high)` bounds top-down: `validate(node, low, high)` checks `low < node.val < high` and recurses `validate(node.left, low, node.val)` and `validate(node.right, node.val, high)`; OR 2. Verify that an Inorder Traversal produces strictly increasing values (`prev < curr.val`). |
| **How do you compute the `Diameter of a Binary Tree` (`LeetCode 543`) and `Binary Tree Maximum Path Sum` (`LeetCode 124`) in a single $O(n)$ Post-Order DFS pass?** | In both problems, carefully distinguish between: (a) what a node **updates in the global answer** (a path that bends/peaks at `node` using BOTH `left_gain + right_gain`), versus (b) what `dfs(node)` **returns to its parent** (a straight path that can only pick ONE branch: `max(left_gain, right_gain)`!). In `Max Path Sum` (`LC 124`), clamp negative child contributions to zero (`left_gain = max(0, dfs(node.left))`), update `best = max(best, node.val + left_gain + right_gain)`, and return `node.val + max(left_gain, right_gain)`. |
| **Compare finding the Lowest Common Ancestor (LCA) in a general Binary Tree (`LeetCode 236`) vs. a Binary Search Tree (`LeetCode 235`).** | In a BST (`LC 235`, $O(H)$ time, $O(1)$ space): Use value ordering! While `curr`: if both `p.val < curr.val` and `q.val < curr.val`, go left (`curr = curr.left`); if both `> curr.val`, go right; otherwise `curr` is the split point (the LCA!). In a general Binary Tree (`LC 236`, $O(n)$ time): If `not root or root == p or root == q: return root`. Recurse `L = lca(root.left, p, q)` and `R = lca(root.right, p, q)`. If both `L and R` are non-null, `root` is the LCA; otherwise return `L or R`. |
| **How do you uniquely reconstruct a Binary Tree from `Preorder + Inorder` (`LeetCode 105`) in $O(n)$ time instead of $O(n^2)$?** | `Preorder`'s first element is always the subtree root; locating that value inside `Inorder` splits `Inorder` into the left subtree (`[in_left .. idx - 1]`) and right subtree (`[idx + 1 .. in_right]`). Prebuild a Hash Map `in_map = {val: i for i, val in enumerate(inorder)}` so looking up `idx` takes $O(1)$ instead of $O(n)$, and pass index bounds `(in_left, in_right)` rather than slicing arrays—achieving strict $O(n)$ time and $O(n)$ space. Note: `Preorder + Postorder` CANNOT uniquely reconstruct a general binary tree (unless every internal node has 2 children)! |
| **How do you `Serialize and Deserialize a Binary Tree` (`LeetCode 297`) in $O(n)$ time?** | Use Preorder DFS with explicit null markers (`"#"`) and comma delimiters: `serialize(node)` outputs `"#"` if `node is None`, else `f"{node.val},{serialize(node.left)},{serialize(node.right)}"`. To `deserialize(data)`: create an iterator `vals = iter(data.split(","))`; define `build()`: take `v = next(vals)`; if `v == "#"`, return `None`; else create `node = TreeNode(int(v))`, set `node.left = build()`, `node.right = build()`, and return `node`! |
| **How do you implement a Prefix `Trie` (`LeetCode 208`) and how does it accelerate backtracking in `Word Search II` (`LeetCode 212`)?** | Each `TrieNode` holds a dictionary/26-array `children` and an `is_word` flag (or stores the completed `word` string). Inserting and searching a word of length $L$ takes $O(L)$ time. In `Word Search II` (finding 30,000 dictionary words on an $M \times N$ board), running separate DFS for each word is way too slow; instead, insert all words into one Prefix Trie and traverse the board and the Trie simultaneously—pruning any board path immediately when `board[r][c]` is not in `trie_node.children` (and deleting leaf Trie nodes once a word is found)! |
| **How does a Bitwise Trie (0/1 Binary Trie) solve 'Maximum XOR of Two Numbers in an Array' (`LeetCode 421`) in $O(32n)$ time?** | Insert the 32-bit binary representation of every number into a binary Trie from Most Significant Bit (bit 31) down to Least Significant Bit (bit 0). To maximize $x \oplus y$ for a given $x$, walk down the Trie from bit 31 to 0, greedily choosing the **opposite bit** `1 - bit` at each level whenever that child branch exists (since $2^{31} > \sum_{k=0}^{30} 2^k$, setting a single higher bit beats all lower bits combined!). |
| **Compare Adjacency List and Adjacency Matrix graph representations in terms of space, edge lookup, and neighbor iteration complexity.** | Adjacency List (`dict`/`vector` of neighbor lists): $O(V + E)$ space; $O(\text{deg}(u))$ to iterate over neighbors of $u$; $O(\text{deg}(u))$ (or $O(1)$ with hash sets) to check if edge $(u, v)$ exists; optimal for **sparse graphs** ($E \ll V^2$), which includes almost all interview graphs. Adjacency Matrix ($V \times V$ grid): $O(V^2)$ space; $O(1)$ to check if edge $(u, v)$ exists; $O(V)$ to iterate over neighbors of $u$; used only for **dense graphs** ($E \approx V^2$) or Floyd-Warshall. |
| **How does Multi-Source BFS work (`Rotting Oranges` `LC 994`, `01 Matrix` `LC 542`, `Walls and Gates` `LC 286`), and why must you mark nodes `visited` at ENQUEUE time rather than DEQUEUE time?** | Instead of running a separate BFS from every source (which would take $O(V \cdot (V+E))$), push **all starting source nodes simultaneously into the queue at distance `0`** before starting the BFS loop—computing shortest distance from every cell to its nearest source in a single $O(V + E)$ pass! CRITICAL: Always mark a neighbor as `visited` the moment you push it onto `deque` (enqueue time), NOT when you pop it! Marking on pop allows the same unpopped node to be pushed into the queue multiple times by different neighbors, causing Memory/Time Limit Exceeded. |
| **Explain 0-1 BFS (`Minimum Obstacle Removal to Reach Corner`, `LeetCode 2290`) and why it runs in $O(V + E)$ instead of $O((V + E) \log V)$ Dijkstra.** | When all edge weights in a graph are strictly `0` or `1`, we don't need a priority queue! Use a `collections.deque`: when relaxing an edge $(u, v)$ with weight `w` that improves `dist[v] = dist[u] + w`: if `w == 0`, push `v` to the **FRONT** of the deque (`dq.appendleft(v)`); if `w == 1`, push `v` to the **BACK** of the deque (`dq.append(v)`). This preserves the monotonic distance invariant in the deque in $O(1)$ per edge ($O(V + E)$ total time)! |

👉 **[Practice Deck 3: Trees, Tries, Graph Traversal (BFS/DFS/Dijkstra/Topological Sort) & Union-Find (32 Flashcards) →](https://flashcards.world/flashcards/sets/d0ce4dc3-0352-4ed9-ac22-f6c41472b76c/)**  
🔍 **[Browse All Intermediate Coding Interviews (Blind 75 / NeetCode DSA), Distributed System Design & Advanced SQL Sets →](https://flashcards.world/flashcards/?q=Coding%20Interviews%20%28Blind%2075%20/%20NeetCode%20DSA%29%2C%20Distributed%20System%20Design%20%26%20Advanced%20SQL&back_lng=en&expertise_level=intermediate)**

---

## Deck 4: Dynamic Programming, Backtracking & Greedy Algorithm Patterns (32 Cards — Intermediate)

**What this deck covers**: Intermediate-to-advanced algorithmic problem solving covering Top-Down Memoization vs Bottom-Up Tabulation, 0/1 and Unbounded Knapsack, Coin Change, LCS, Edit Distance, O(n log n) LIS (Patience Sorting), Manacher's Palindrome algorithm, Interval DP, Bitmask DP, Backtracking pruning templates, and Greedy proofs.

| High-Yield Prompt / Question | Verified Answer & Exam Application |
| :--- | :--- |
| **What two mathematical properties must a problem have to be solvable by Dynamic Programming, and how do Top-Down (Memoization) and Bottom-Up (Tabulation) compare?** | 1. **Optimal Substructure** (an optimal solution to the problem can be constructed from optimal solutions of its subproblems); and 2. **Overlapping Subproblems** (recursive exploration solves the exact same subproblems repeatedly). Top-Down (`@functools.lru_cache(None)`): Natural recursive formulation that only computes reachable states, but incurs recursion call-stack overhead ($O(H)$ stack space). Bottom-Up (Tabulation): Iteratively fills a table in topological order of states with zero recursion overhead and allows **Space Optimization** (rolling rows, e.g., $O(N \cdot W) \to O(W)$). |
| **How do you solve `House Robber` (`LeetCode 198`), `House Robber II` (Circular, `LC 213`), and `House Robber III` (Binary Tree, `LC 337`)?** | `House Robber I` (1D): `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`, optimized to two variables `prev2, prev1 = prev1, max(prev1, prev2 + x)` in $O(n)$ time, $O(1)$ space. `House Robber II` (Circular): Since house `0` and `n-1` are adjacent, you cannot rob both—take `max(rob_linear(nums[:-1]), rob_linear(nums[1:]))`. `House Robber III` (Tree DP): Post-order `dfs(node)` returns a 2-tuple `(rob_this_node, skip_this_node)` where `rob = node.val + L.skip + R.skip` and `skip = max(L) + max(R)` in $O(n)$ time. |
| **Explain the crucial inner-loop direction difference between 1D Space-Optimized **0/1 Knapsack** (`Partition Equal Subset Sum` `LC 416`) and **Unbounded Knapsack** (`Coin Change` `LC 322`).** | In **0/1 Knapsack** (each item can be used **at most ONCE**), the inner capacity loop MUST iterate **BACKWARDS** (`for w in range(W, weight - 1, -1): dp[w] = max(dp[w], dp[w - weight] + val)`) so that `dp[w - weight]` still holds the value from the *previous* item's row (`i - 1`), preventing the same item from being picked multiple times! In **Unbounded Knapsack** (each item/coin can be reused **UNLIMITED times**), the inner loop iterates **FORWARDS** (`for w in range(weight, W + 1): ...`) so `dp[w - weight]` intentionally reuses the *current* item (`i`). |
| **Why does the loop order (`coins` outer vs. `amount` outer) change the answer between `Coin Change II` (Combinations, `LeetCode 518`) and `Combination Sum IV` (Permutations, `LeetCode 377`)?** | 1. **Combinations** (order does NOT matter, so `1+2` and `2+1` count as 1 way, `LC 518`): Put **`for coin in coins:` on the OUTER loop** and `for a in range(coin, amount + 1): dp[a] += dp[a - coin]` on the INNER loop—this forces coins to be used in canonical order (`coin_1`s then `coin_2`s). 2. **Permutations** (order DOES matter, so `1+2` and `2+1` count as 2 ways, `LC 377`): Put **`for a in range(1, amount + 1):` on the OUTER loop** and `for coin in coins:` on the INNER loop! |
| **How do you reduce `Target Sum` (assigning `+` or `-` to every number in `nums` to reach `target`, `LeetCode 494`) to a 1D 0/1 Subset Sum DP?** | Partition `nums` into positive subset $P$ and negative subset $N$. We know $\sum P - \sum N = \text{target}$ and $\sum P + \sum N = \text{total\_sum}$. Adding the two equations gives $2 \sum P = \text{target} + \text{total\_sum} \implies \sum P = \frac{\text{target} + \text{total\_sum}}{2}$. If $\text{target} + \text{total\_sum}$ is odd or $< 0$, return `0`; otherwise count the number of subsets of `nums` that sum to $S = (\text{target} + \text{total\_sum}) // 2$ using 1D backwards 0/1 Knapsack in $O(n \cdot S)$ time and $O(S)$ space! |
| **State the recurrence relation and space optimization for `Longest Common Subsequence` (LCS, `LeetCode 1143`) of strings `s1` ($m$) and `s2` ($n$).** | If `s1[i] == s2[j]`, then `dp[i + 1][j + 1] = 1 + dp[i][j]`; otherwise (`s1[i] != s2[j]`), `dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])`. Runs in $O(m \cdot n)$ time. Since row `i + 1` only depends on row `i` and row `i + 1`, we can optimize space to a single 1D row of length $\min(m, n) + 1$ ($O(\min(m, n))$ auxiliary space). |
| **State the recurrence relation for Levenshtein `Edit Distance` (`LeetCode 72`) converting `word1` into `word2` using Insert, Delete, and Replace.** | Base cases: `dp[i][0] = i` (delete $i$ chars) and `dp[0][j] = j` (insert $j$ chars). For $i, j \ge 1$: if `word1[i - 1] == word2[j - 1]`, no operation is needed: `dp[i][j] = dp[i - 1][j - 1]`. Otherwise, take $1 + \min($ `dp[i - 1][j]` (Delete from `word1`), `dp[i][j - 1]` (Insert into `word1`), `dp[i - 1][j - 1]` (Replace char)$)$ in $O(m \cdot n)$ time and $O(\min(m, n))$ optimized space. |
| **How do you solve `Longest Increasing Subsequence` (LIS, `LeetCode 300`) in $O(n \log n)$ time instead of $O(n^2)$ DP using Patience Sorting + Binary Search?** | Maintain a strictly increasing array `tails`, where `tails[k]` stores the **smallest possible tail element** of any increasing subsequence of length `k + 1` seen so far. For each `x` in `nums`: find insertion index `idx = bisect_left(tails, x)` (use `bisect_right` for non-decreasing subsequence). If `idx == len(tails)`, append `x` to `tails`; otherwise overwrite `tails[idx] = x` (keeping the tail of length `idx + 1` as small as possible to accommodate more future elements!). At the end, `len(tails)` is the exact LIS length in $O(n \log n)$ time! |
| **In `Russian Doll Envelopes` (`LeetCode 354`, 2D LIS on `(width, height)`), why do we sort by `width` ASCENDING and `height` DESCENDING on ties?** | Because an envelope `(w1, h1)` can only fit inside `(w2, h2)` if BOTH $w_1 < w_2$ AND $h_1 < h_2$ (strict inequalities). Sorting by `width` ascending reduces the problem to 1D LIS on `height`. However, if two envelopes share the same width (e.g., `(3, 4)` and `(3, 5)`), sorting `height` ascending would allow the 1D LIS on `heights` (`[4, 5]`) to illegally pick both! Sorting `height` **descending** on width ties (`(3, 5)` before `(3, 4)`) guarantees at most one envelope per distinct width can ever be picked in a strictly increasing height subsequence! |
| **Compare Expand-Around-Center ($O(n^2)$ time, $O(1)$ space) and Manacher's Algorithm ($O(n)$ time) for `Longest Palindromic Substring` (`LeetCode 5`) and `Palindromic Substrings` (`LC 647`).** | Expand-Around-Center: A palindrome of length $n$ has $2n - 1$ possible centers ($n$ single-character centers `(i, i)` for odd-length palindromes, and $n - 1$ between-character centers `(i, i + 1)` for even-length palindromes). Expanding outward from each center while `s[L] == s[R]` takes $O(n^2)$ worst-case time and $O(1)$ space. Manacher's Algorithm inserts `'#'` sentinels (`#a#b#a#`) so all palindromes become odd-length, and reuses previously computed palindrome radii mirrored across the rightmost palindrome's center `C` (`P[i] = min(R - i, P[2*C - i])`), achieving strict $O(n)$ linear time. |
| **Explain the Interval DP pattern and why you must iterate by **interval length `len` from 1 to $n$** (e.g., `Burst Balloons` `LC 312`, `Longest Palindromic Subsequence` `LC 516`).** | In Interval DP, state `dp[i][j]` represents the optimal answer for subarray `s[i..j]`, which depends on smaller sub-intervals inside `[i..j]` (`dp[i+1][j]`, `dp[i][j-1]`, or `dp[i][k] + dp[k+1][j]`). Therefore, you must loop outer over `length` from `2` to `n` (or loop `i` backwards from `n-1` down to `0` and `j` forwards from `i+1` to `n-1`). In `Burst Balloons` (`LC 312`), instead of picking which balloon in `(i, j)` to burst *first* (which makes adjacent neighbors change dynamically!), pick which balloon `k` in `(i, j)` is burst **LAST**—so its neighbors at burst time are guaranteed to be the fixed boundaries `nums[i]` and `nums[j]`! |
| **Explain the universal Finite State Machine DP for all six `Best Time to Buy and Sell Stock` problems (`Cooldown` `LC 309`, `Transaction Fee` `LC 714`, `At Most K Transactions` `LC 188`).** | At each day, track two states: `cash` (max profit holding 0 stock) and `hold` (max profit holding 1 share of stock, initialized to `-inf`). With Transaction Fee (`LC 714`): `cash, hold = max(cash, hold + price - fee), max(hold, cash - price)`. With 1-Day Cooldown (`LC 309`): add `prev_cash` (cash from 2 days ago) so buying uses `prev_cash - price`. With at most $K$ transactions (`LC 188`): maintain arrays `cash[1..K]` and `hold[1..K]` updated in $O(n \cdot K)$ time and $O(K)$ space. |

👉 **[Practice Deck 4: Dynamic Programming, Backtracking & Greedy Algorithm Patterns (32 Flashcards) →](https://flashcards.world/flashcards/sets/4861151b-40bf-49d7-a381-98ff6884a2bb/)**  
🔍 **[Browse All Intermediate Coding Interviews (Blind 75 / NeetCode DSA), Distributed System Design & Advanced SQL Sets →](https://flashcards.world/flashcards/?q=Coding%20Interviews%20%28Blind%2075%20/%20NeetCode%20DSA%29%2C%20Distributed%20System%20Design%20%26%20Advanced%20SQL&back_lng=en&expertise_level=intermediate)**

---

## Deck 5: SQL Mastery: Joins, Window Functions (ROW_NUMBER, LAG), CTEs, Indexing & ACID Isolation Levels (32 Cards — Advanced)

**What this deck covers**: Advanced SQL and Database Internals mastery for Software Engineering, Data Engineering, and Backend interviews covering SQL logical execution order, Joins, the NOT IN NULL trap, Window Functions & Frame Clauses, Recursive CTEs, B+ Tree vs LSM-Tree vs GIN indexes, EXPLAIN ANALYZE query plans, and ACID Isolation Levels & MVCC.

| High-Yield Prompt / Question | Verified Answer & Exam Application |
| :--- | :--- |
| **What is the exact Logical Query Processing (Execution) Order of SQL clauses, and why can't you reference a `SELECT` alias inside `WHERE`?** | 1. `FROM` & `JOIN` (with `ON` predicates); 2. `WHERE` (filters individual rows); 3. `GROUP BY` (buckets rows into groups); 4. Aggregate Functions (`COUNT`, `SUM`, `AVG`); 5. `HAVING` (filters aggregated groups); 6. Window Functions (`OVER (...)`); 7. `SELECT` (projects columns and creates aliases); 8. `DISTINCT`; 9. `UNION` / `INTERSECT` / `EXCEPT`; 10. `ORDER BY` (can use `SELECT` aliases!); 11. `OFFSET` & `LIMIT` / `FETCH`. Because `WHERE` (step 2) executes long BEFORE `SELECT` (step 7), aliases defined in `SELECT` do not exist yet during `WHERE` evaluation (and Window Functions cannot be used directly in `WHERE`/`HAVING` without a CTE/subquery!). |
| **Compare `INNER JOIN`, `LEFT OUTER JOIN`, `FULL OUTER JOIN`, `CROSS JOIN`, and `LATERAL JOIN` (`CROSS/OUTER APPLY`).** | `INNER JOIN`: Returns only rows with matching keys in both tables. `LEFT JOIN`: Returns all rows from the left table, filling `NULL`s for right-table columns when no match exists. `FULL OUTER JOIN`: Returns matched rows plus unmatched rows from both left and right tables (`NULL`-padded). `CROSS JOIN`: Cartesian product ($M \times N$ rows). `LATERAL JOIN` (PostgreSQL `JOIN LATERAL`, SQL Server `CROSS/OUTER APPLY`): Like a correlated `for-each` loop—allows the right-side subquery to reference columns from the left-side table row-by-row (e.g., fetching the top 3 latest orders per customer). |
| **In a `LEFT JOIN`, what is the critical difference between placing a filter condition on the right table inside the `ON` clause vs. inside the `WHERE` clause?** | 1. Filter in `ON` (`FROM users u LEFT JOIN orders o ON u.id = o.user_id AND o.year = 2026`): The predicate is evaluated *before/during* the outer join—all users are STILL returned, with `NULL`s for users who placed no orders in 2026. 2. Filter in `WHERE` (`... LEFT JOIN orders o ON u.id = o.user_id WHERE o.year = 2026`): `WHERE` filters *after* the join; since `NULL = 2026` evaluates to `UNKNOWN` (falsy), all unmatched `NULL`-padded rows are filtered out, silently turning your `LEFT JOIN` into an `INNER JOIN`! |
| **Explain the infamous `NOT IN` NULL Trap in SQLthree-valued logic (`TRUE`, `FALSE`, `UNKNOWN`), and why `NOT EXISTS` or `LEFT JOIN ... WHERE id IS NULL` is safer.** | `WHERE x NOT IN (1, 2, NULL)` expands logically to `x != 1 AND x != 2 AND x != NULL`. In SQL 3-valued logic, `x != NULL` evaluates to `UNKNOWN`, and `TRUE AND UNKNOWN` evaluates to `UNKNOWN`—so **`NOT IN` returns ZERO rows whenever the subquery contains even a single `NULL` value**! By contrast, `WHERE NOT EXISTS (SELECT 1 FROM b WHERE b.id = a.id)` and `LEFT JOIN b ON a.id = b.id WHERE b.id IS NULL` (Anti-Join) safely ignore `NULL`s in `b` and often optimize to an efficient Hash Anti-Join. |
| **Compare `ROW_NUMBER()`, `RANK()`, `DENSE_RANK()`, and `NTILE(k)` Window Functions when ranking values `[100, 90, 90, 80]`.** | `ROW_NUMBER()`: Assigns unique sequential integers with arbitrary tie-breaking: `1, 2, 3, 4`. `RANK()`: Assigns the same rank to ties, then skips ranks (`olympic medal style`): `1, 2, 2, 4`. `DENSE_RANK()`: Assigns the same rank to ties WITHOUT skipping any subsequent integer ranks: `1, 2, 2, 3` (always use `DENSE_RANK()` for 'Nth Highest Salary' problems (`LeetCode 177`/`185`) when distinct salary levels are requested!). `NTILE(k)`: Divides ordered partition into `k` roughly equal buckets (quartiles/deciles). |
| **How do you write the classic 'Top N Per Group' query (e.g., `Department Top Three Salaries`, `LeetCode 185`) and 'Second Highest Salary' (`LC 176` returning `NULL` if missing)?** | Top 3 Salaries per Department (`LC 185`): `WITH ranked AS (SELECT d.name AS Department, e.name AS Employee, e.salary AS Salary, DENSE_RANK() OVER (PARTITION BY e.departmentId ORDER BY e.salary DESC) AS rnk FROM Employee e JOIN Department d ON e.departmentId = d.id) SELECT Department, Employee, Salary FROM ranked WHERE rnk <= 3;`. For `Second Highest Salary` (`LC 176`) returning `NULL` when `< 2` distinct salaries exist: wrap the query as a scalar subquery `SELECT (SELECT DISTINCT salary FROM Employee ORDER BY salary DESC LIMIT 1 OFFSET 1) AS SecondHighestSalary;` (or use `MAX(salary)`). |
| **How do `LAG(col, offset, default)` and `LEAD(col, offset, default)` solve time-series comparison problems (e.g., `Rising Temperature` `LC 197`, YoY growth, session durations)?** | `LAG(val, 1, 0) OVER (PARTITION BY user_id ORDER BY event_date)` accesses the row `1` position BEFORE the current row within the partition without needing a self-join; `LEAD(val, 1) OVER (...)` accesses the row `1` position AFTER the current row. Note: If a table can have missing calendar dates (e.g., `Rising Temperature` `LC 197` where `2026-05-01` is followed by `2026-05-03`), `LAG(temperature, 1)` looks at the previous *row*, not strictly yesterday's *date*—so check `DATEDIFF(recordDate, LAG(recordDate) OVER (ORDER BY recordDate)) = 1`! |
| **What is the default Window Frame in SQL when `ORDER BY` is present inside `OVER (PARTITION BY ... ORDER BY ...)`, and why does `LAST_VALUE()` surprise developers?** | When `ORDER BY` is specified inside `OVER (...)` without an explicit frame clause, the SQL standard default frame is **`RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`** (NOT the whole partition!). Therefore, `SUM(amount) OVER (ORDER BY dt)` automatically computes a running total, AND `LAST_VALUE(amount) OVER (ORDER BY dt)` simply returns the `CURRENT ROW`'s value! To get the true last value of the entire partition with `LAST_VALUE`, you must explicitly specify `ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING`. |
| **Compare `ROWS BETWEEN` and `RANGE BETWEEN` in SQL Window Frame clauses, and show how to compute a 7-day rolling average.** | `ROWS BETWEEN 6 PRECEDING AND CURRENT ROW` counts strictly by **physical row offsets** (the current row plus the 6 physical rows immediately before it—if 2 days had no data, it spans 9 calendar days!). `RANGE BETWEEN INTERVAL '6 days' PRECEDING AND CURRENT ROW` bounds the window by **logical value distance** in the `ORDER BY` column (all rows whose date falls within `[current_date - 6 days, current_date]`, also grouping duplicate peer timestamps together). |
| **Explain the 'Gaps and Islands' SQL pattern (`Consecutive Numbers` `LC 180`, finding start/end of contiguous streaks of daily logins).** | Key mathematical invariant: If a sequence of dates or integers increases by 1 (`2026-05-01, 05-02, 05-03`) and `ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY login_date)` also increases by 1 (`1, 2, 3`), then their **difference** (`login_date - INTERVAL '1 day' * ROW_NUMBER()...` or `id - ROW_NUMBER()...`) is **CONSTANT across every row belonging to the same contiguous island**, and jumps whenever there is a gap! Group by `(user_id, island_grp)` and select `MIN(login_date) AS start_date, MAX(login_date) AS end_date, COUNT(*) AS streak_len`. |
| **How do you calculate the Exact Median in SQL using Window Functions (`Median Employee Salary`, `LeetCode 569`)?** | In a CTE, compute both `rn = ROW_NUMBER() OVER (PARTITION BY company ORDER BY salary, id)` and `cnt = COUNT(*) OVER (PARTITION BY company)`. For both odd and even partition sizes $N$, the middle one or two rows satisfy **`WHERE rn BETWEEN cnt / 2.0 AND cnt / 2.0 + 1`** (e.g., for $N=4$, `rn BETWEEN 2.0 AND 3.0` selects rows `2` and `3`; for $N=5$, `rn BETWEEN 2.5 AND 3.5` selects row `3`)! Alternatively in PostgreSQL/Oracle, use the ordered-set aggregate `PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER BY salary)`. |
| **How do you write a Pivot / Conditional Aggregation query in SQL (`COUNT(*) FILTER (WHERE ...)` vs `SUM(CASE WHEN ...)`), and how do `ROLLUP`, `CUBE`, and `GROUPING SETS` work?** | Conditional Aggregation pivots rows into columns in a single table scan: `SUM(CASE WHEN status = 'paid' THEN amount ELSE 0 END) AS paid_total` (or Postgres standard SQL `SUM(amount) FILTER (WHERE status = 'paid')`). `GROUP BY ROLLUP (year, quarter, month)` generates hierarchical subtotals (`(year, quarter, month)`, `(year, quarter)`, `(year)`, and grand total `()`) in one pass; `CUBE (a, b)` generates all $2^k$ dimensional combinations; `GROUPING SETS ((a), (b), ())` computes exact specified groupings. |

👉 **[Practice Deck 5: SQL Mastery: Joins, Window Functions (ROW_NUMBER, LAG), CTEs, Indexing & ACID Isolation Levels (32 Flashcards) →](https://flashcards.world/flashcards/sets/2b8af12d-fa1c-4d41-af77-1969eddfd894/)**  
🔍 **[Browse All Advanced Coding Interviews (Blind 75 / NeetCode DSA), Distributed System Design & Advanced SQL Sets →](https://flashcards.world/flashcards/?q=Coding%20Interviews%20%28Blind%2075%20/%20NeetCode%20DSA%29%2C%20Distributed%20System%20Design%20%26%20Advanced%20SQL&back_lng=en&expertise_level=advanced)**

---

## Deck 6: System Design Interviews: Load Balancing, Caching (Redis), Sharding, CAP/PACELC, Message Queues (Kafka) & Rate Limiting (32 Cards — Advanced)

**What this deck covers**: Staff/Senior System Design interview mastery covering L4 vs L7 Load Balancing, Consistent Hashing with Virtual Nodes, Caching strategies & Thundering Herd prevention, Redis internals & Redlock, Database Replication (Leaderless Quorum W+R>N) & Sharding, CAP/PACELC, 2PC vs Saga & Outbox, Kafka internals, Rate Limiting algorithms, Snowflake IDs, and Bloom Filters.

| High-Yield Prompt / Question | Verified Answer & Exam Application |
| :--- | :--- |
| **Compare Layer 4 (Transport) and Layer 7 (Application) Load Balancers in System Design, including how connection termination works.** | **Layer 4 Load Balancer** (e.g., AWS NLB, IPVS, Linux LVS, Maglev): Operates on TCP/UDP 5-tuple `(src_ip, src_port, dst_ip, dst_port, proto)` using NAT or Direct Server Return (DSR); does NOT inspect HTTP headers or decrypt TLS, achieving millions of packets/sec with sub-millisecond latency. **Layer 7 Load Balancer** (e.g., NGINX, Envoy, HAProxy, AWS ALB): Terminates the client's TCP and TLS connection, inspects decrypted HTTP/gRPC headers, cookies, and URL paths (`/api/v1/chat`), and pools separate persistent backend TCP connections—enabling smart routing, WAF, rate limiting, and gRPC per-RPC load balancing. |
| **Why does naive `hash(key) % N` fail for distributed caches/shards when nodes scale, and how does **Consistent Hashing with Virtual Nodes** solve it?** | With `hash(key) % N`, when a single cache node crashes or is added ($N \to N \pm 1$), almost **100% of keys** ($(N-1)/N$) remap to a different server, triggering a catastrophic cache miss storm! **Consistent Hashing** maps both servers and keys onto a $2^{32}$ hash ring `[0, 2^32 - 1]`; each key routes clockwise to the first server on the ring, so adding/removing 1 server only remaps **$1/N$ of keys**! Because placing only 1 physical point per server on the ring causes uneven load skew, each physical server is assigned $100–200$ **Virtual Nodes (vnodes)** scattered across the ring, ensuring uniform standard deviation and allowing heterogeneous hardware weights. |
| **Compare the four Caching Strategies: `Cache-Aside`, `Read-Through`, `Write-Through`, and `Write-Behind (Write-Back)`.** | 1. **Cache-Aside (Lazy Loading)**: App checks cache first; on miss, app reads from DB, writes to cache with a TTL, and returns data (on write, app updates DB and **deletes/invalidates** the cache key rather than updating it to avoid race conditions!). 2. **Read-Through**: Cache library/proxy sits inline and fetches from DB transparently on miss. 3. **Write-Through**: Every write synchronously updates BOTH cache and DB before returning (strong cache consistency, higher write latency). 4. **Write-Behind (Write-Back)**: App writes only to fast in-memory cache and returns immediately; cache asynchronously batches writes to DB (highest write throughput for counters/likes, risks data loss if cache crashes before flush). |
| **What is a **Cache Stampede (Thundering Herd)** vs. **Cache Penetration** vs. **Cache Avalanche**, and how do you mitigate each?** | 1. **Cache Stampede (Hot Key Expiry)**: A celebrity/homepage cache key expires and 50,000 concurrent requests miss simultaneously and hammer the database. Mitigations: **Singleflight / Request Coalescing / Mutex Lock** (only 1 thread queries DB while 49,999 wait on the shared promise), logical early expiration (Probabilistic Early Recomputation / XFetch), or background refresh before TTL expires. 2. **Cache Penetration**: Requests for non-existent IDs (`id = -999`) always miss cache and hit DB. Mitigations: Cache `NULL` sentinel with short TTL (30s) or place a **Bloom Filter** in front of the cache. 3. **Cache Avalanche**: Thousands of keys expire at the exact same second (or Redis node fails). Mitigation: Add random **TTL Jitter** (`TTL = 3600 + random(0, 600)`). |
| **Why is Redis single-threaded for command execution yet capable of 100,000+ ops/sec, and what core Redis data structures power System Design interviews?** | Redis executes commands on a single main event-loop thread using **in-memory data structures** and **I/O Multiplexing (`epoll`/`kqueue`)** (with multi-threaded network I/O read/write in Redis 6+), completely avoiding OS thread context-switching and lock contention! Essential structures: 1. `String` (atomic counters `INCR`, distributed locks `SET key val NX PX 10000`); 2. `Hash` (user profiles/sessions); 3. `Sorted Set` (`ZSET`: Skip List + Hash Table for **Real-Time Leaderboards** `ZADD`/`ZREVRANGE` and **Sliding Window Rate Limiters** in $O(\log N)$); 4. `HyperLogLog` (`PFADD`/`PFCOUNT`: counts billions of unique visitors in **12 KB** with $0.81\%$ standard error); 5. `Streams` / `PubSub`; 6. `Geo` (`GEOADD`/`GEORADIUS` geohashes). |
| **Compare Redis Persistence options (`RDB` Snapshots vs. `AOF` Append-Only File) and Redis High Availability (`Replication + Sentinel` vs. `Redis Cluster`).** | Persistence: **RDB** forks a child process (`fork()` copy-on-write) to dump a compact point-in-time binary snapshot (fast restarts, but loses minutes of data on crash); **AOF** logs every write command with `appendfsync everysec` (at most 1 second of data loss, larger files with background rewrite; production combines RDB + AOF). High Availability: **Redis Sentinel** monitors a single-shard Primary + Replicas for automatic failover; **Redis Cluster** shards data across multiple masters using **16,384 deterministic Hash Slots** (`CRC16(key) % 16384`) with gossip protocol and built-in replica failover. |
| **How do you implement a safe Distributed Lock in Redis, and what is Martin Kleppmann's critique of `Redlock` regarding GC pauses and Fencing Tokens?** | Single-instance lock: Acquire via `SET resource_name my_random_uuid NX PX 30000` (atomic set-if-not-exists with 30s TTL); release ONLY via an **atomic Lua script** that checks `if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1])` (so a slow worker whose lock expired never deletes another worker's newly acquired lock!). `Redlock` acquires locks across $\ge 3/5$ independent Redis masters for HA. Kleppmann's critique: If Client 1 hits a long stop-the-world GC pause after acquiring the lock, the lock expires and Client 2 acquires it—for true correctness, the lock service must issue a monotonically increasing **Fencing Token** verified by the downstream storage server (e.g., via etcd/ZooKeeper Raft/ZAB). |
| **Compare Database Replication topologies: **Single-Leader**, **Multi-Leader (Master-Master)**, and **Leaderless (Dynamo-style Quorum)**.** | 1. **Single-Leader**: All writes go to 1 Primary; Read Replicas serve read-heavy traffic via async/semi-sync replication (requires handling **replication lag** via Read-Your-Own-Writes routing or Monotonic Reads). 2. **Multi-Leader**: Multiple datacenters each have a writable leader replicating asynchronously to each other; lower cross-region write latency, but requires conflict resolution (Last-Write-Wins, custom merge, or CRDTs). 3. **Leaderless (Amazon Dynamo, Cassandra, Riak)**: Client sends writes to all $N$ replicas in parallel ($W$ must acknowledge) and reads from $R$ replicas in parallel; when **$W + R > N$** (Strict Quorum, e.g., $N=3, W=2, R=2$), the read set and write set are guaranteed to overlap by at least 1 replica holding the latest version! |
| **In Leaderless (Dynamo-style) databases, how do **Read Repair**, **Hinted Handoff / Sloppy Quorum**, and **Anti-Entropy with Merkle Trees** work?** | 1. **Read Repair**: When a client reads from $R$ replicas and detects that replica C returned a stale version `v1` while A and B returned `v2`, the coordinator asynchronously writes `v2` back to C. 2. **Anti-Entropy with Merkle Trees**: Background processes compare hierarchical cryptographic hash trees of key ranges between replicas to pinpoint and sync out-of-date key ranges in $O(\log K)$ network transfers. 3. **Sloppy Quorum & Hinted Handoff**: During a network partition when true home nodes aren't reachable, writes are temporarily accepted on healthy neighbor nodes ('hints') and handed back once the home nodes recover (maximizing write availability $A$ at the expense of strict $W+R>N$ consistency). |
| **Compare Horizontal Database Sharding strategies (`Range-Based`, `Hash-Based`, `Directory-Based`) and how you mitigate the **Celebrity / Hot-Shard Problem**.** | 1. **Range-Based Sharding**: Shards contiguous key ranges (`A-F`, `G-M`, or timestamps); supports efficient range scans, but suffers from hot spots if all recent writes hit the latest time range. 2. **Hash-Based Sharding**: `consistent_hash(shard_key) -> shard`; distributes load uniformly, but scatter-gather is required for range queries. 3. **Directory-Based**: Lookup service maps keys to shards. **Celebrity / Hot-Shard Mitigation**: If Justin Bieber's `user_id` receives 100,000 writes/sec on one shard, append a random shard suffix `0..99` (`bieber_id#42`, **Key Salting / Write Sharding**) to spread writes across 100 shards, and aggregate across `0..99` on read (or isolate hot tenants onto dedicated shards). |
| **How do you handle **Secondary Indexes** in a Sharded Database: `Document-Partitioned (Local)` vs. `Term-Partitioned (Global)` Indexes?** | 1. **Local Index (Document-Partitioned)**: Each shard maintains a secondary index covering ONLY the documents stored on that local shard. Writes are fast (touch only 1 shard), but querying by secondary index requires a **Scatter-Gather** query across ALL shards in parallel (tail latency bottleneck!). 2. **Global Index (Term-Partitioned)**: The secondary index itself is sharded by the indexed attribute (`email` or `status`) across shards separately from the primary table. Reads by secondary index hit only 1 index shard, but a single document write now has to update multiple index shards asynchronously (eventual consistency) or via distributed transaction. |
| **Why is **Two-Phase Commit (2PC)** an anti-pattern across distributed microservices, and how does the **Transactional Outbox + CDC Pattern** solve dual-write bugs?** | **2PC** is a blocking atomic commitment protocol: if the Coordinator crashes after participants vote `YES` in Phase 1, participants must hold database row locks indefinitely until the coordinator recovers, destroying availability and throughput. Furthermore, writing to your DB and publishing to Kafka in app code (`db.save(); kafka.send()`) is a **Dual-Write Bug** (if the app crashes in between, DB and Kafka diverge!). **Transactional Outbox Pattern**: Inside the *exact same local ACID database transaction* as `INSERT INTO orders`, insert the event into an `outbox` table (`INSERT INTO outbox`); a separate **CDC (Change Data Capture, e.g., Debezium)** process tails the DB's WAL/binlog and publishes `outbox` rows to Kafka with at-least-once delivery! |

👉 **[Practice Deck 6: System Design Interviews: Load Balancing, Caching (Redis), Sharding, CAP/PACELC, Message Queues (Kafka) & Rate Limiting (32 Flashcards) →](https://flashcards.world/flashcards/sets/53881522-023b-43ab-ae24-59cfce71d09b/)**  
🔍 **[Browse All Advanced Coding Interviews (Blind 75 / NeetCode DSA), Distributed System Design & Advanced SQL Sets →](https://flashcards.world/flashcards/?q=Coding%20Interviews%20%28Blind%2075%20/%20NeetCode%20DSA%29%2C%20Distributed%20System%20Design%20%26%20Advanced%20SQL&back_lng=en&expertise_level=advanced)**

---

## Complete 6-Deck Quick-Access Directory

| Deck # | Deck Title | Level | Cards | Direct Practice Link |
| :--- | :--- | :--- | :--- | :--- |
| **Deck 1** | Big-O Complexity, Arrays, Two Pointers, Sliding Window & Hashing Patterns | `basic` | 32 | [Open Deck 1 →](https://flashcards.world/flashcards/sets/68e289db-c158-461d-a144-5bcad4aaf6d7/) |
| **Deck 2** | Linked Lists, Stacks, Monotonic Queues, Binary Search & Heaps | `basic` | 32 | [Open Deck 2 →](https://flashcards.world/flashcards/sets/51725164-b515-42e0-a6b2-850f1d36f3fc/) |
| **Deck 3** | Trees, Tries, Graph Traversal (BFS/DFS/Dijkstra/Topological Sort) & Union-Find | `intermediate` | 32 | [Open Deck 3 →](https://flashcards.world/flashcards/sets/d0ce4dc3-0352-4ed9-ac22-f6c41472b76c/) |
| **Deck 4** | Dynamic Programming, Backtracking & Greedy Algorithm Patterns | `intermediate` | 32 | [Open Deck 4 →](https://flashcards.world/flashcards/sets/4861151b-40bf-49d7-a381-98ff6884a2bb/) |
| **Deck 5** | SQL Mastery: Joins, Window Functions (ROW_NUMBER, LAG), CTEs, Indexing & ACID Isolation Levels | `advanced` | 32 | [Open Deck 5 →](https://flashcards.world/flashcards/sets/2b8af12d-fa1c-4d41-af77-1969eddfd894/) |
| **Deck 6** | System Design Interviews: Load Balancing, Caching (Redis), Sharding, CAP/PACELC, Message Queues (Kafka) & Rate Limiting | `advanced` | 32 | [Open Deck 6 →](https://flashcards.world/flashcards/sets/53881522-023b-43ab-ae24-59cfce71d09b/) |

👉 **[Launch Full Coding Interviews (Blind 75 / NeetCode DSA), Distributed System Design & Advanced SQL Spaced-Repetition Track →](https://flashcards.world/flashcards/?q=Coding%20Interviews%20%28Blind%2075%20/%20NeetCode%20DSA%29%2C%20Distributed%20System%20Design%20%26%20Advanced%20SQL&back_lng=en)**

## Curated Flashcard Decks & Practice Sets

- **Big-O Complexity, Arrays, Two Pointers, Sliding Window & Hashing Patterns**: [Interactive Deck](https://flashcards.world/flashcards/sets/68e289db-c158-461d-a144-5bcad4aaf6d7/) | [Markdown (.md)](https://flashcards.world/flashcards/sets/68e289db-c158-461d-a144-5bcad4aaf6d7.md)
- **Linked Lists, Stacks, Monotonic Queues, Binary Search & Heaps**: [Interactive Deck](https://flashcards.world/flashcards/sets/51725164-b515-42e0-a6b2-850f1d36f3fc/) | [Markdown (.md)](https://flashcards.world/flashcards/sets/51725164-b515-42e0-a6b2-850f1d36f3fc.md)
- **Trees, Tries, Graph Traversal (BFS/DFS/Dijkstra/Topological Sort) & Union-Find**: [Interactive Deck](https://flashcards.world/flashcards/sets/d0ce4dc3-0352-4ed9-ac22-f6c41472b76c/) | [Markdown (.md)](https://flashcards.world/flashcards/sets/d0ce4dc3-0352-4ed9-ac22-f6c41472b76c.md)
- **Dynamic Programming, Backtracking & Greedy Algorithm Patterns**: [Interactive Deck](https://flashcards.world/flashcards/sets/4861151b-40bf-49d7-a381-98ff6884a2bb/) | [Markdown (.md)](https://flashcards.world/flashcards/sets/4861151b-40bf-49d7-a381-98ff6884a2bb.md)
- **SQL Mastery: Joins, Window Functions (ROW_NUMBER, LAG), CTEs, Indexing & ACID Isolation Levels**: [Interactive Deck](https://flashcards.world/flashcards/sets/2b8af12d-fa1c-4d41-af77-1969eddfd894/) | [Markdown (.md)](https://flashcards.world/flashcards/sets/2b8af12d-fa1c-4d41-af77-1969eddfd894.md)
- **System Design Interviews: Load Balancing, Caching (Redis), Sharding, CAP/PACELC, Message Queues (Kafka) & Rate Limiting**: [Interactive Deck](https://flashcards.world/flashcards/sets/53881522-023b-43ab-ae24-59cfce71d09b/) | [Markdown (.md)](https://flashcards.world/flashcards/sets/53881522-023b-43ab-ae24-59cfce71d09b.md)