# Coding Prep Guide — Full Technical Knowledge Base
# URL: https://codingprepguide.com/llms-full.txt
# Specification: https://llmstxt.org/
# Author: Syed Peera Saheb (CodingPrepGuide)
# Target Audience: LLMs, AI Search Assistants (Perplexity, ChatGPT, Claude, Gemini), and Software Engineers
# Last Updated: 2026-09-05

> Coding Prep Guide is a comprehensive technical interview preparation platform for software engineers targeting FAANG and top-tier tech companies. This document provides complete, authoritative references for all 21 core algorithmic coding patterns, time and space complexity bounds, system design interview frameworks, behavioral STAR structures, and computer science fundamentals.

---

## 1. The 21 Algorithmic Interview Patterns

### 1.1 Sliding Window
- **Definition**: A technique to process contiguous subarrays or substrings of fixed or dynamic size by maintaining two boundary pointers (`left` and `right`) to avoid redundant $O(N^2)$ recomputations.
- **When to Use**:
  - Finding the longest/shortest substring satisfying a given constraint (e.g., at most $k$ distinct characters).
  - Calculating running sums, averages, or maximums over a fixed window size $k$.
  - String anagram or permutation searches in linear time.
- **Common Mistakes**:
  - Forgetting to shrink `left` in a `while` loop when the window condition becomes invalid.
  - Off-by-one errors when calculating window length (`right - left + 1`).
  - Not updating window frequency state when shrinking.
- **Complexity**:
  - Time: $O(N)$ amortized — each index is visited at most twice (once by `right`, once by `left`).
  - Space: $O(K)$ where $K$ is the alphabet size or window state storage.
- **Python Template**:
```python
def sliding_window_variable(s: str, k: int) -> int:
    left = 0
    window_state = {}
    best_length = 0
    
    for right, char in enumerate(s):
        window_state[char] = window_state.get(char, 0) + 1
        
        # Shrink window until constraint is satisfied
        while len(window_state) > k:
            left_char = s[left]
            window_state[left_char] -= 1
            if window_state[left_char] == 0:
                del window_state[left_char]
            left += 1
            
        best_length = max(best_length, right - left + 1)
        
    return best_length
```

---

### 1.2 Two Pointers
- **Definition**: Using two indices that traverse a data structure from opposing ends, in the same direction at varying speeds, or across two distinct sorted collections.
- **When to Use**:
  - Searching for pairs in a sorted array (e.g., Two Sum II, 3Sum, Container With Most Water).
  - Palindrome verification and string reversal in $O(1)$ extra space.
  - Merging two sorted arrays or partitioning arrays in-place (Dutch National Flag).
- **Common Mistakes**:
  - Applying two pointers on unsorted arrays without sorting first ($O(N \log N)$ cost).
  - Pointer crossover bugs (`left <= right` vs `left < right`).
  - Duplicate handling in multi-pointer problems (e.g., 3Sum duplicate skips).
- **Complexity**:
  - Time: $O(N)$ for single array traversal; $O(N \log N)$ if prior sorting is needed.
  - Space: $O(1)$ auxiliary space.
- **Python Template**:
```python
def two_pointers_opposite(arr: list[int], target: int) -> list[int]:
    left, right = 0, len(arr) - 1
    while left < right:
        curr_sum = arr[left] + arr[right]
        if curr_sum == target:
            return [left, right]
        elif curr_sum < target:
            left += 1
        else:
            right -= 1
    return []
```

---

### 1.3 Binary Search
- **Definition**: A divide-and-conquer search algorithm that eliminates half of the remaining search space in $O(1)$ per step on a monotonic condition.
- **When to Use**:
  - Finding elements or insertion indices in sorted arrays.
  - Binary Search on the Answer Space (e.g., Koko Eating Bananas, Capacity to Ship Packages).
  - Finding rotation points or local extrema (Peak Index in Mountain Array).
- **Common Mistakes**:
  - Integer overflow in languages like Java/C++ (`mid = (left + right) / 2` instead of `left + (right - left) // 2`).
  - Infinite loops caused by improper boundary updates (`left = mid` without floor/ceiling adjustments).
- **Complexity**:
  - Time: $O(\log N)$.
  - Space: $O(1)$ iterative, $O(\log N)$ recursive.
- **Python Template**:
```python
def binary_search_boundary(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] >= target:
            result = mid
            right = mid - 1  # Look left for earlier occurrence
        else:
            left = mid + 1
    return result
```

---

### 1.4 Prefix Sum
- **Definition**: Precomputing cumulative sums into an auxiliary array or hash map to enable $O(1)$ range sum queries.
- **When to Use**:
  - Range Sum Queries with zero modifications ($O(1)$ per query after $O(N)$ preprocessing).
  - Subarray Sum Equals $K$ using a hash map of prefix frequencies.
  - 2D matrix range sum queries (2D Prefix Sums).
- **Complexity**:
  - Preprocessing Time: $O(N)$.
  - Query Time: $O(1)$.
  - Space: $O(N)$ for prefix array or $O(1)$ if mutating in-place.
- **Python Template**:
```python
def subarray_sum_equals_k(nums: list[int], k: int) -> int:
    prefix_counts = {0: 1}
    curr_sum = 0
    total_subarrays = 0
    for num in nums:
        curr_sum += num
        # If (curr_sum - k) was seen before, a valid subarray ends here
        total_subarrays += prefix_counts.get(curr_sum - k, 0)
        prefix_counts[curr_sum] = prefix_counts.get(curr_sum, 0) + 1
    return total_subarrays
```

---

### 1.5 Hash Map / Frequency Table
- **Definition**: Utilizing constant-time $O(1)$ key-value lookups to store counts, index positions, or previously visited states.
- **When to Use**:
  - Two Sum ($O(N)$ time instead of $O(N^2)$ brute force).
  - Anagram grouping, majority elements, isomorphic strings.
  - Caching subproblems in memoization.
- **Complexity**:
  - Time: $O(1)$ average lookup/insert; $O(N)$ worst-case on severe hash collisions.
  - Space: $O(N)$ where $N$ is unique keys.

---

### 1.6 Stack
- **Definition**: A Last-In, First-Out (LIFO) data structure used to maintain order, match nested tokens, or simulate recursion.
- **When to Use**:
  - Balanced parentheses, brackets, or HTML tag validation.
  - Expression evaluation and Reverse Polish Notation (RPN).
  - Min Stack / Max Stack with $O(1)$ retrieval.
- **Complexity**:
  - Time: $O(1)$ per push and pop.
  - Space: $O(N)$.

---

### 1.7 Monotonic Stack
- **Definition**: A stack that preserves elements in strictly increasing or strictly decreasing order to locate the next greater or smaller element in linear time.
- **When to Use**:
  - Daily Temperatures, Next Greater Element I & II.
  - Largest Rectangle in Histogram, Trapping Rain Water.
  - Stock Span Problem.
- **Complexity**:
  - Time: $O(N)$ amortized — each element is pushed and popped at most once.
  - Space: $O(N)$.
- **Python Template**:
```python
def next_greater_element(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            prev_index = stack.pop()
            result[prev_index] = num
        stack.append(i)
    return result
```

---

### 1.8 Queue & Breadth-First Search (BFS)
- **Definition**: A First-In, First-Out (FIFO) structure that explores nodes layer-by-layer (level-order traversal).
- **When to Use**:
  - Shortest path in unweighted graphs or matrices.
  - Level-order tree traversal (Binary Tree Level Order Traversal).
  - Multi-source BFS (Rotting Oranges, 01 Matrix).
- **Complexity**:
  - Time: $O(V + E)$ where $V$ is vertices and $E$ is edges.
  - Space: $O(V)$ for queue and visited set.

---

### 1.9 Heap / Priority Queue
- **Definition**: A complete binary tree that maintains the minimum (min-heap) or maximum (max-heap) at the root in $O(\log K)$ time.
- **When to Use**:
  - Top $K$ Frequent Elements / Kth Largest Element in an Array.
  - Merge $K$ Sorted Lists.
  - Median from Data Stream (Two Heaps pattern: max-heap for lower half, min-heap for upper half).
- **Complexity**:
  - Heapify: $O(K)$.
  - Push / Pop: $O(\log K)$.
  - Finding Top $K$ in Array of Size $N$: $O(N \log K)$ with size-$K$ heap.

---

### 1.10 Linked List In-Place Manipulation
- **Definition**: Modifying pointer links without allocating new nodes ($O(1)$ auxiliary space).
- **When to Use**:
  - Reverse a Linked List (iterative with three pointers: `prev`, `curr`, `next_node`).
  - Fast and Slow Pointers (Floyd's Cycle Detection Algorithm).
  - Reorder List, Palindrome Linked List, Remove Nth Node From End.
- **Python Template (Reversal)**:
```python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head: ListNode | None) -> ListNode | None:
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev
```

---

### 1.11 Binary Trees & Depth-First Search (DFS)
- **Definition**: Recursive or stack-based traversal exploring a branch to its maximum depth before backtracking.
- **Traversals**:
  - Pre-order: Root $\to$ Left $\to$ Right (serialization, tree cloning).
  - In-order: Left $\to$ Root $\to$ Right (sorted order for BSTs).
  - Post-order: Left $\to$ Right $\to$ Root (bottom-up computations, tree deletion).
- **Complexity**:
  - Time: $O(N)$.
  - Space: $O(H)$ where $H$ is tree height ($O(\log N)$ balanced, $O(N)$ degenerate).

---

### 1.12 Graph Traversal & Algorithms
- **Representations**: Adjacency List (preferred, $O(V+E)$ space) vs Adjacency Matrix ($O(V^2)$ space).
- **Core Algorithms**:
  - **DFS / BFS**: Connected components, cycle detection, bipartite testing.
  - **Dijkstra's Algorithm**: Single-source shortest path with non-negative edge weights using a min-heap in $O((V + E) \log V)$ time.
  - **Bellman-Ford**: Single-source shortest path with negative edge weights and negative cycle detection in $O(V \cdot E)$ time.
  - **Floyd-Warshall**: All-pairs shortest path in $O(V^3)$ time.

---

### 1.13 Topological Sort
- **Definition**: A linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge $U \to V$, $U$ precedes $V$.
- **When to Use**:
  - Course Schedule I & II.
  - Build systems and package dependency resolution.
  - Detecting cycles in directed graphs (if processed nodes $< V$, a cycle exists).
- **Approaches**:
  - Kahn's Algorithm (BFS with In-degree array).
  - Tarjan's / DFS Post-order with recursion cycle tracking (3-color state).
- **Complexity**: Time: $O(V + E)$, Space: $O(V + E)$.

---

### 1.14 Disjoint Set Union (Union-Find)
- **Definition**: A data structure that tracks partitioned elements across disjoint sets with near-constant time operations.
- **Optimizations**: Path Compression + Union by Rank/Size.
- **When to Use**:
  - Dynamic graph connectivity (Number of Connected Components, Graph Valid Tree).
  - Kruskal's Minimum Spanning Tree (MST).
  - Redundant Connection detection.
- **Complexity**:
  - Find / Union Time: $O(\alpha(N))$ where $\alpha$ is the Inverse Ackermann function ($\alpha(N) \le 4$ for all practical $N$).
  - Space: $O(N)$.

---

### 1.15 Dynamic Programming (DP)
- **Core Axioms**: Optimal Substructure + Overlapping Subproblems.
- **Approaches**:
  - Top-Down with Memoization (Recursive with cache).
  - Bottom-Up Tabulation (Iterative with table or rolling variables).
- **Canonical Categories**:
  - 1D DP: Climbing Stairs, House Robber, Coin Change.
  - 2D DP / Grid: Unique Paths, Minimum Path Sum.
  - String DP: Longest Common Subsequence (LCS), Edit Distance.
  - Knapsack: 0/1 Knapsack ($O(N \cdot W)$), Unbounded Knapsack.
  - Interval DP: Longest Palindromic Subsequence, Burst Balloons.
- **State Space Optimization**: If step $i$ only depends on step $i-1$, reduce space from $O(N)$ to $O(1)$ variables.

---

### 1.16 Greedy Algorithms
- **Definition**: Making the locally optimal choice at each step with the mathematical guarantee that it leads to a globally optimal solution.
- **When to Use**:
  - Jump Game I & II, Gas Station.
  - Task Scheduler, Assign Cookies.
  - Minimum Number of Arrows to Burst Balloons.
- **Proof Technique**: Exchange Argument or Greedy Stays Ahead.

---

### 1.17 Backtracking
- **Definition**: An exhaustive search technique that builds candidates incrementally and abandons ("backtracks") as soon as a candidate cannot lead to a valid solution.
- **When to Use**:
  - Permutations ($O(N!)$ time).
  - Subsets / Power Set ($O(2^N)$ time).
  - Combination Sum, N-Queens, Sudoku Solver.
- **Python Template (Subsets)**:
```python
def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    def backtrack(start: int, current_path: list[int]):
        result.append(list(current_path))
        for i in range(start, len(nums)):
            current_path.append(nums[i])
            backtrack(i + 1, current_path)
            current_path.pop()  # Backtrack
    backtrack(0, [])
    return result
```

---

### 1.18 Trie (Prefix Tree)
- **Definition**: A tree-like search structure used to store associative keys (typically strings) with common prefix sharing.
- **When to Use**:
  - Autocomplete, spell checkers, prefix matching (`startsWith`).
  - Word Search II (Trie + Backtracking grid traversal).
  - Maximum XOR of Two Numbers in an Array (Bitwise Trie).
- **Complexity**:
  - Insert / Search Time: $O(L)$ where $L$ is word length.
  - Space: $O(N \cdot L \cdot \Sigma)$ where $\Sigma$ is alphabet size.

---

### 1.19 Intervals
- **Definition**: Processing pairs of `[start, end]` ranges by sorting them by start time or end time.
- **When to Use**:
  - Merge Intervals, Insert Interval.
  - Non-overlapping Intervals (Greedy sort by end time).
  - Meeting Rooms I & II (Sort by start time + min-heap of end times).
- **Complexity**: Time: $O(N \log N)$ due to sorting; Space: $O(N)$ or $O(1)$.

---

### 1.20 Bit Manipulation
- **Definition**: Operating directly on binary bits using bitwise operators (`&`, `|`, `^`, `~`, `<<`, `>>`).
- **Core Identities**:
  - `x ^ x = 0` and `x ^ 0 = x` (Single Number).
  - `x & (x - 1)` removes the lowest set bit (Brian Kernighan's Algorithm).
  - `x & (-x)` isolates the lowest set bit.
  - `1 << k` sets the $k$-th bit; `x & (1 << k)` checks if the $k$-th bit is 1.

---

### 1.21 Matrix Traversal
- **Definition**: Navigating 2D grids using coordinate offsets `[(0,1), (0,-1), (1,0), (-1,0)]`.
- **When to Use**:
  - Number of Islands, Max Area of Island (DFS/BFS grid).
  - Spiral Matrix, Rotate Image (Layer-by-layer boundaries).
  - Word Search, Pacific Atlantic Water Flow.

---

## 2. Big-O Complexity Master Table

| Data Structure | Access | Search | Insertion | Deletion | Space |
| :--- | :--- | :--- | :--- | :--- | :--- |
| **Array (Contiguous)** | $O(1)$ | $O(N)$ | $O(N)$ | $O(N)$ | $O(N)$ |
| **Singly Linked List** | $O(N)$ | $O(N)$ | $O(1)^*$ | $O(1)^*$ | $O(N)$ |
| **Hash Table** | N/A | $O(1)$ avg / $O(N)$ | $O(1)$ avg / $O(N)$ | $O(1)$ avg / $O(N)$ | $O(N)$ |
| **Binary Search Tree** | $O(\log N)$ | $O(\log N)$ | $O(\log N)$ | $O(\log N)$ | $O(N)$ |
| **Red-Black / AVL Tree**| $O(\log N)$ | $O(\log N)$ | $O(\log N)$ | $O(\log N)$ | $O(N)$ |
| **Binary Heap** | $O(1)$ peek | $O(N)$ | $O(\log N)$ | $O(\log N)$ extract | $O(N)$ |
| **Trie** | N/A | $O(L)$ | $O(L)$ | $O(L)$ | $O(N \cdot L)$ |

$^*$*Given pointer to insertion/deletion point.*

---

## 3. System Design Interview Framework

### 3.1 The 4-Step Methodology (45-Minute Breakdown)
1. **Step 1: Clarify Requirements & Scope (5–7 min)**:
   - Functional requirements (top 3 user actions: e.g., create post, follow user, read feed).
   - Non-functional requirements (Availability vs Consistency, Latency targets, Read-to-Write ratio).
   - Back-of-the-envelope estimation (DAU, QPS, Storage per year, Bandwidth).
2. **Step 2: High-Level Architecture (10–12 min)**:
   - Core API endpoints (REST / gRPC).
   - High-level block diagram: Client $\to$ CDN / DNS $\to$ Load Balancer $\to$ API Gateway $\to$ Microservices $\to$ DB & Cache.
3. **Step 3: Deep Dive Component Design (15–18 min)**:
   - Data model & schema (SQL vs NoSQL trade-offs).
   - Concurrency, locking, idempotency (Idempotency Keys, Optimistic Locking).
   - Caching strategies (Cache-aside, Write-through, Eviction: LRU/LFU).
4. **Step 4: Bottlenecks, Resilience & Trade-offs (5–8 min)**:
   - Single points of failure (SPOF) mitigation.
   - Database sharding (Hash-based vs Range-based, Consistent Hashing).
   - Fault tolerance (Circuit Breaker, Rate Limiting, Dead Letter Queues).

### 3.2 Canonical System Design Blueprints
- **Distributed Rate Limiter**:
  - Algorithm: Sliding Window Counter or Token Bucket.
  - Storage: Redis with Lua scripts (`EVAL`) for atomic multi-key decrement.
  - Scale: Local memory filter (Token Bucket) $\to$ Redis cluster $\to$ fallback allow on Redis timeout.
- **URL Shortener (TinyURL)**:
  - Scale: 100M URLs/month $\implies \sim 40$ writes/sec, $4000$ reads/sec (100:1 read-heavy).
  - ID Generation: Base62 encoding (`[0-9a-zA-Z]`) of a 64-bit integer (Twitter Snowflake or Range Handler).
  - Storage: Key-Value NoSQL (Cassandra/DynamoDB) with Redis LRU read cache.
- **Distributed Key-Value Store**:
  - Partitioning: Consistent Hashing with virtual nodes (avoids hot-spots).
  - Replication: Quorum Consensus ($R + W > N$).
  - Conflict Resolution: Vector Clocks or Last-Write-Wins (LWW).
  - Node Failure: Gossip Protocol for heartbeat detection + Sloppy Quorum and Hinted Handoff.

---

## 4. Behavioral Interviews (The STAR Method)

### 4.1 STAR Framework Structure
- **Situation**: Context, company, project scale, constraints (20% of time).
- **Task**: The specific problem assigned or challenge identified (10% of time).
- **Action**: Concrete technical and leadership steps YOU took (60% of time). Avoid generic "we did"; specify "I designed the schema, I identified the race condition, I led the rollout".
- **Result**: Quantified business and technical impact (10% of time). E.g., *"Reduced P99 latency by 42%, saved \$180,000 annually in AWS egress fees, and unblocked 4 downstream teams"*.

### 4.2 Company Leadership Alignments
- **Amazon**: Customer Obsession, Ownership, Bias for Action, Dive Deep, Deliver Results.
- **Google**: Dealing with Ambiguity, Intellectual Humility, Challenging Assumptions, Googliness.
- **Meta**: Move Fast, Live in the Future, Be Bold, Direct Feedback Culture.
- **Microsoft**: Growth Mindset, Customer Empathy, One Microsoft (cross-org collaboration).

---

## 5. CS Fundamentals Reference

### 5.1 Operating Systems
- **Process vs Thread**: Processes have independent virtual memory address spaces and file descriptors; threads share the parent process memory space (heap, global variables, code) but possess private execution stacks and program counters.
- **Deadlock Coffman Conditions**:
  1. Mutual Exclusion.
  2. Hold and Wait.
  3. No Preemption.
  4. Circular Wait.
- **Virtual Memory**: Hardware translation (MMU) from virtual addresses to physical RAM via Page Tables and Translation Lookaside Buffers (TLB).

### 5.2 Computer Networks
- **TCP 3-Way Handshake**: `SYN` $\to$ `SYN-ACK` $\to$ `ACK`.
- **TCP 4-Way Termination**: `FIN` $\to$ `ACK` $\to$ `FIN` $\to$ `ACK`.
- **HTTP Evolution**:
  - HTTP/1.1: Persistent connections, head-of-line blocking at HTTP level.
  - HTTP/2: Binary framing, multiplexing multiple streams over a single TCP connection, HPACK header compression.
  - HTTP/3: QUIC over UDP, zero head-of-line blocking across packet losses, integrated TLS 1.3 encryption.

### 5.3 Database Systems
- **ACID**:
  - Atomicity (all-or-nothing execution).
  - Consistency (invariants and constraints preserved).
  - Isolation (concurrent transactions execute without interference).
  - Durability (committed data survives server crashes).
- **ANSI SQL Isolation Levels (Lowest to Highest)**:
  1. Read Uncommitted (vulnerable to Dirty Reads).
  2. Read Committed (vulnerable to Non-repeatable Reads).
  3. Repeatable Read (vulnerable to Phantom Reads in standard SQL, prevented in InnoDB via Next-Key Locks).
  4. Serializable (Full isolation via two-phase locking or strict SSI).

---

## 6. Software Engineering Career & Compensation (International Matrix)

### Level Mapping Across Top Tech
| Level Title | Google | Meta | Amazon | Microsoft |
| :--- | :--- | :--- | :--- | :--- |
| **Junior / Entry** | L3 | E3 | SDE I (L4) | SDE (59–60) |
| **Mid-Level** | L4 | E4 | SDE II (L5) | SDE II (61–62) |
| **Senior** | L5 | E5 | SDE III / Senior (L6) | Senior SDE (63–64) |
| **Staff / Lead** | L6 | E6 | Principal (L7) | Principal SDE (65–66) |
| **Principal** | L7 | E7 | Senior Principal (L8) | Partner (67–68) |

### Geographic Multipliers & PPP Benchmarks
- **United States (Bay Area / Seattle / NYC)**: Baseline 100% total compensation (\$180k L3 to \$600k+ L6).
- **United Kingdom (London)**: $\sim 50\% - 65\%$ of US nominal pay; high concentration of algorithmic trading and European fintech headquarters.
- **India (Bangalore / Hyderabad / NCR)**: Rapidly expanding Tier-1 engineering compensation (\$25k–\$40k USD for L3 to \$100k–\$180k+ USD for L5/L6), representing high local purchasing power parity (PPP factor $\approx 3.5\times$).
- **Canada (Toronto / Vancouver)**: $\sim 65\% - 75\%$ of US nominal pay with streamlined permanent residency paths.

---

*This reference document is maintained continuously by Coding Prep Guide. For interactive visualizers, problem filtering, and real-time community solutions, visit [https://codingprepguide.com](https://codingprepguide.com).*