Module 11: Interview Patterns & 100+ Problem Bank

Goal: Master the 20 universal coding interview patterns, systematic frameworks for tackling unknown problems under pressure in 45-minute technical interviews, and a curated 100+ LeetCode problem bank categorized by pattern.
Language: C++ (C++17/C++20)
Prerequisites: Modules 01 to 10.

📑 Table of Contents

The 45-Minute Coding Interview Framework
The 20 Essential Coding Patterns Matrix
Deep Pattern Blueprints & Triggers
100+ Categorized Problem Bank (with Solutions & Tips)
Whiteboard Communication & Production Coding Tips

1. The 45-Minute Coding Interview Framework

 00:00 ──► [ Phase 1: Clarification & Constraints (5 mins) ]
           • Ask about input bounds (N <= 10^5?), duplicates, negative numbers, empty input.
           • Confirm return format and in-place vs extra memory allowances.
           
 05:00 ──► [ Phase 2: Test Cases & Edge Cases (3 mins) ]
           • Formulate 1 standard test case, 1 empty/minimal case, 1 extreme case.
           
 08:00 ──► [ Phase 3: Brainstorm & Pattern Identification (7 mins) ]
           • State the brute force solution first ($O(N^2)$).
           • Propose optimized pattern ($O(N \log N)$ or $O(N)$). Explain why it works.
           • Get interviewer confirmation before writing any code!
           
 15:00 ──► [ Phase 4: Clean Coding (15 mins) ]
           • Write modular, idiomatic C++ code with descriptive variable names.
           • Handle boundary conditions gracefully.
           
 30:00 ──► [ Phase 5: Manual Trace & Dry Run (5 mins) ]
           • Step through code line-by-line using your test cases.
           • Catch off-by-one errors and pointer bugs before the interviewer points them out.
           
 35:00 ──► [ Phase 6: Complexity Analysis & Follow-ups (5 mins) ]
           • State exact Big-O Time & Auxiliary Space complexity.
           • Discuss potential tradeoffs, scale-up scenarios, or concurrency implications.
           
 40:00 ──► [ Phase 7: Questions for the Interviewer (5 mins) ]

2. The 20 Essential Coding Patterns Matrix

#	Pattern Name	Typical Input Structure	Common Problem Keywords
1	Two Pointers	Sorted array, Linked list, String	"Pair with target sum", "In-place reverse", "Trap water"
2	Fast & Slow Pointers	Linked list, Cyclic array	"Detect cycle", "Find middle", "Happy number"
3	Sliding Window	Array, String, Subarray	"Longest substring with...", "Subarray of size K", "Min window"
4	Merge Intervals	Array of ranges/intervals	"Overlapping intervals", "Meeting rooms", "Insert interval"
5	Cyclic Sort	Array with numbers in range $[1, N]$	"Find missing number", "Find all duplicates in $[1, N]$"
6	In-Place LinkedList Reversal	Linked list	"Reverse sublist", "Reverse in K-groups"
7	Tree BFS (Level-Order)	Binary tree, N-ary tree	"Level order", "Zigzag traversal", "Shortest depth"
8	Tree DFS / Subtree DP	Binary tree, Graph DAG	"Path sum", "Tree diameter", "Maximum path sum", "LCA"
9	Two Heaps	Continuous data stream	"Find median", "Sliding window median", "Maximize capital"
10	Subsets & Backtracking	Array, String	"Generate all combinations", "Permutations", "N-Queens"
11	Modified Binary Search	Sorted/Rotated array	"Search in rotated array", "Find peak", "Median of two sorted"
12	Top 'K' Elements	Unsorted collection	"K most frequent", "Kth largest element", "K closest points"
13	K-Way Merge	Sorted lists / arrays / matrices	"Merge K sorted lists", "Kth smallest in sorted matrix"
14	0/1 & Unbounded Knapsack	Items with weights & values	"Partition equal subset sum", "Coin change", "Target sum"
15	Topological Sort	Directed Acyclic Graph (DAG)	"Course prerequisites", "Build order", "Alien dictionary"
16	Monotonic Stack / Queue	Array, Histogram	"Next greater element", "Largest rectangle in histogram"
17	Matrix Graph Traversal	2D Grid / Matrix	"Number of islands", "Word search", "Rotting oranges"
18	Bit Manipulation	Integers	"Single number", "Bitwise XOR", "Power of two"
19	Union Find (DSU)	Undirected graph, Equivalence sets	"Connected components", "Accounts merge", "Redundant connection"
20	Prefix Sum + Hash Map	Array with positive/negative numbers	"Subarray sum equals K", "Contiguous array", "Product except self"

3. Deep Pattern Blueprints & Triggers

Pattern 5 Blueprint: Cyclic Sort

Trigger: The input contains numbers in the continuous range $[1, N]$ or $[0, N]$, and the problem asks for missing or duplicate numbers in $O(N)$ time and $O(1)$ space.

// Cyclic Sort Template
int i = 0;
while (i < nums.size()) {
    int correctIndex = nums[i] - 1; // For 1 to N range
    if (nums[i] > 0 && nums[i] <= nums.size() && nums[i] != nums[correctIndex]) {
        std::swap(nums[i], nums[correctIndex]);
    } else {
        i++;
    }
}

Pattern 11 Blueprint: Modified Binary Search

Trigger: Finding a boundary or searching an array sorted or rotated in logarithmic time.

// Template: Binary Search for First True Condition
int low = 0, high = n - 1, ans = -1;
while (low <= high) {
    int mid = low + (high - low) / 2;
    if (condition(mid)) {
        ans = mid;
        high = mid - 1; // Look for earlier occurrence in left half
    } else {
        low = mid + 1;
    }
}

4. 100+ Categorized Problem Bank (with Solutions & Tips)

1. Two Pointers (8 Problems)

LC #1: Two Sum (Easy) — Hash map or Two pointers on sorted array.
LC #15: 3Sum (Medium) — Sort array, fix first element, two pointers for remaining two. Skip duplicates.
LC #16: 3Sum Closest (Medium) — Sort + Two pointers tracking minimum absolute difference.
LC #18: 4Sum (Medium) — Generalized $K$-Sum recursive reducer with two pointers base case.
LC #11: Container With Most Water (Medium) — Move pointer with smaller height inward.
LC #42: Trapping Rain Water (Hard) — Left and right max boundaries converging inward.
LC #977: Squares of a Sorted Array (Easy) — Two pointers at ends comparing absolute values.
LC #844: Backspace String Compare (Easy) — Two pointers traversing backwards counting backspaces.

2. Sliding Window (8 Problems)

LC #3: Longest Substring Without Repeating Characters (Medium) — Map tracking last seen character index.
LC #76: Minimum Window Substring (Hard) — Frequency match counter with expanding right, shrinking left.
LC #209: Minimum Size Subarray Sum (Medium) — Expand right until sum $\ge$ target, shrink left to minimize.
LC #424: Longest Repeating Character Replacement (Medium) — Max frequency in window + $K$.
LC #1004: Max Consecutive Ones III (Medium) — At most $K$ zeros in window.
LC #992: Subarrays with K Different Integers (Hard) — Exact($K$) = AtMost($K$) - AtMost($K-1$).
LC #567: Permutation in String (Medium) — Fixed window of size $|s_1|$ with 26-char frequency match.
LC #438: Find All Anagrams in a String (Medium) — Fixed sliding window.

3. Fast & Slow Pointers (5 Problems)

LC #141: Linked List Cycle (Easy) — Floyd's Tortoise and Hare.
LC #142: Linked List Cycle II (Medium) — Meeting point math ($L = kC - a$).
LC #287: Find the Duplicate Number (Medium) — Array values as next pointer references.
LC #202: Happy Number (Easy) — Sum of squared digits cycle detection.
LC #876: Middle of the Linked List (Easy) — Fast moves 2, slow moves 1.

4. Merge Intervals (6 Problems)

LC #56: Merge Intervals (Medium) — Sort by start time, merge overlapping.
LC #57: Insert Interval (Medium) — 3-phase merge (before, overlapping, after).
LC #435: Non-overlapping Intervals (Medium) — Greedy sort by end time.
LC #252: Meeting Rooms (Easy) — Sort by start time, check adjacent overlap.
LC #253: Meeting Rooms II (Medium) — Min-Heap of end times or Chronological Sweep.
LC #986: Interval List Intersections (Medium) — Two pointers taking max(start) and min(end).

5. Cyclic Sort (5 Problems)

LC #268: Missing Number (Easy) — Place $x$ at index $x$.
LC #448: Find All Numbers Disappeared in an Array (Easy) — In-place negation or cyclic sort.
LC #442: Find All Duplicates in an Array (Medium) — Negate visited indices.
LC #41: First Missing Positive (Hard) — Cyclic sort on $[1, N]$, first index $i$ where nums[i] != i + 1.
LC #645: Set Mismatch (Easy) — Find duplicate and missing number.

6. Linked List In-Place Reversal (5 Problems)

LC #206: Reverse Linked List (Easy) — Standard 3-pointer iterative reversal.
LC #92: Reverse Linked List II (Medium) — Reverse sublist between left and right.
LC #25: Reverse Nodes in k-Group (Hard) — Group check and reversal.
LC #61: Rotate List (Medium) — Form circle, find new tail at $N - (K \pmod N) - 1$.
LC #24: Swap Nodes in Pairs (Medium) — Pointer rewiring with dummy node.

7. Monotonic Stack & Queue (7 Problems)

LC #84: Largest Rectangle in Histogram (Hard) — Monotonic increasing stack.
LC #85: Maximal Rectangle (Hard) — 2D matrix converted to running histogram on each row.
LC #739: Daily Temperatures (Medium) — Monotonic decreasing stack.
LC #503: Next Greater Element II (Medium) — Monotonic stack on circular array ($2N$).
LC #496: Next Greater Element I (Easy) — Monotonic stack + Hash map.
LC #239: Sliding Window Maximum (Hard) — Monotonic deque of indices.
LC #907: Sum of Subarray Minimums (Medium) — Previous smaller + Next smaller element.

8. Hash Maps & Prefix Sums (8 Problems)

LC #560: Subarray Sum Equals K (Medium) — Prefix sum frequency hash map.
LC #525: Contiguous Array (Medium) — Replace 0 with -1, find longest subarray with sum 0.
LC #128: Longest Consecutive Sequence (Medium) — Set lookup with sequence start check.
LC #49: Group Anagrams (Medium) — Sorted string / char count as canonical key.
LC #380: Insert Delete GetRandom O(1) (Medium) — Vector + Map with swap-to-back erase.
LC #146: LRU Cache (Medium) — Doubly linked list + Hash map.
LC #454: 4Sum II (Medium) — Pairwise sum map.
LC #238: Product of Array Except Self (Medium) — Prefix and suffix product passes.

9. Binary Trees & BST (12 Problems)

LC #104: Maximum Depth of Binary Tree (Easy) — DFS recursion.
LC #102: Binary Tree Level Order Traversal (Medium) — BFS with queue.
LC #98: Validate Binary Search Tree (Medium) — Range propagation (low, high).
LC #236: Lowest Common Ancestor of a Binary Tree (Medium) — Subtree split point.
LC #235: LCA of a Binary Search Tree (Medium) — Value-based branch steering.
LC #124: Binary Tree Maximum Path Sum (Hard) — Global max with single branch return.
LC #297: Serialize and Deserialize Binary Tree (Hard) — Preorder string with # nulls.
LC #105: Construct BT from Preorder and Inorder (Medium) — Preorder root + Inorder partition.
LC #543: Diameter of Binary Tree (Easy) — Max left depth + right depth.
LC #199: Binary Tree Right Side View (Medium) — BFS last element or DFS depth check.
LC #114: Flatten Binary Tree to Linked List (Medium) — Morris traversal or postorder.
LC #99: Recover Binary Search Tree (Medium) — Inorder traversal finding swapped pair.

10. Heaps & Priority Queues (6 Problems)

LC #215: Kth Largest Element in an Array (Medium) — Min-Heap of size K or QuickSelect.
LC #295: Find Median from Data Stream (Hard) — Max-Heap & Min-Heap balance.
LC #23: Merge k Sorted Lists (Hard) — Min-Heap of size K.
LC #347: Top K Frequent Elements (Medium) — Frequency map + Min-Heap.
LC #621: Task Scheduler (Medium) — Max-Heap with cooldown queue.
LC #373: Find K Pairs with Smallest Sums (Medium) — Min-Heap priority queue over matrix.

11. Graphs: BFS, DFS & TopoSort (10 Problems)

LC #200: Number of Islands (Medium) — Grid DFS/BFS sink pattern.
LC #133: Clone Graph (Medium) — DFS/BFS with node-to-clone hash map.
LC #207: Course Schedule (Medium) — Cycle detection via Kahn's / 3-color DFS.
LC #210: Course Schedule II (Medium) — Kahn's topological sort.
LC #127: Word Ladder (Hard) — BFS shortest path in word graph.
LC #743: Network Delay Time (Medium) — Dijkstra's algorithm.
LC #785: Is Graph Bipartite? (Medium) — 2-Coloring BFS.
LC #269: Alien Dictionary (Hard) — Letter precedence graph + TopoSort.
LC #994: Rotting Oranges (Medium) — Multi-source BFS.
LC #417: Pacific Atlantic Water Flow (Medium) — Reverse BFS/DFS from ocean edges.

12. Dynamic Programming (12 Problems)

LC #70: Climbing Stairs (Easy) — Fibonacci DP.
LC #198: House Robber (Medium) — 1D DP with 2 variables.
LC #213: House Robber II (Medium) — Circle split into two 1D subproblems.
LC #62: Unique Paths (Medium) — 2D grid DP.
LC #64: Minimum Path Sum (Medium) — 2D grid DP in-place.
LC #300: Longest Increasing Subsequence (Medium) — $O(N \log N)$ patience sort.
LC #322: Coin Change (Medium) — Unbounded knapsack.
LC #518: Coin Change II (Medium) — Combinations unbounded knapsack.
LC #416: Partition Equal Subset Sum (Medium) — 0/1 knapsack with reverse 1D loop.
LC #1143: Longest Common Subsequence (Medium) — 2D string matching.
LC #72: Edit Distance (Medium/Hard) — 3-operation Levenshtein matrix.
LC #312: Burst Balloons (Hard) — Interval DP.

13. Backtracking & Advanced (10 Problems)

LC #78: Subsets (Medium) — Cascading / Backtracking / Bitmask.
LC #90: Subsets II (Medium) — Sort + Skip duplicate elements.
LC #46: Permutations (Medium) — In-place swap backtracking.
LC #39: Combination Sum (Medium) — Backtracking with reused elements.
LC #51: N-Queens (Hard) — Bitmask / Array diagonal pruning.
LC #37: Sudoku Solver (Hard) — 9x9 board backtracking.
LC #208: Implement Trie (Medium) — 26-pointer array Trie.
LC #421: Maximum XOR of Two Numbers (Medium) — Bitwise Trie.
LC #721: Accounts Merge (Medium) — Disjoint Set Union (DSU).
LC #307: Range Sum Query - Mutable (Medium) — Segment Tree / Fenwick Tree.

5. Whiteboard Communication & Production Coding Tips

5.1 Communication Best Practices

Think Out Loud: Never write code in silence. Announce: "I'm going to maintain two pointers here to avoid allocating an extra buffer..."
Verify Edge Cases Before Running: Walk through:
1. Empty input / null pointers.
2. Single element collection.
3. All duplicate values.
4. Extreme value ranges (integer overflow risks $\to$ use long long).

5.2 Modern C++ Idioms in Interviews

Use std::string_view for non-allocating string slicing.
Use structured bindings (auto [u, weight] = pq.top()) for clean readable code.
Prefer std::vector over raw dynamic arrays (new[] / delete[]) to guarantee RAII and eliminate memory leaks.
Always use size_t or cast to prevent signed/unsigned comparison compiler warnings.

11-interview-patterns-and-problem-bank.md