算法与编程面试实战¶

一句话总结: AI 面试的编程环节 = LeetCode 算法题 + ML 手撕代码 + 面向对象设计三条腿，40 分钟高压时间盒下，边想边说 + 模式识别 + 可跑代码是拿 offer 的通行证。

前几节讲的是系统设计——推荐、风控、对话、RAG. 但即使是候选人以"系统设计强"著称的公司 (Meta、Google、字节、阿里)，编程环节依然是硬门槛。不会写代码的候选人，系统设计再天花乱坠也进不去。这一节我们把 AI 系统面试里高频出现的算法 + ML 手撕 + 系统编程题一网打尽，每一题都给完整走查 + 复杂度 + 变种.

0. 编程面试全景：三种类型，三种打法¶

不要以为"AI 面试 = 系统设计". 中美主流公司 (Meta、Google、字节、阿里、DeepSeek、月之暗面) 招 AI/ML 工程师时，coding 面至少 2 轮，而且直接淘汰 40% 以上候选人。

0.1 三种 coding 面¶

类型	时长	考察点	中英文别名
算法题 (Algorithmic)	40-45 min	LeetCode (LC) 中等/困难；模式识别 + 复杂度分析	"白板题" / "刷题面"
面向对象设计 (Object-Oriented Design, OOD)	45 min	类设计 + 数据结构组合 + 接口拆分	"手撕系统" / "小系统设计"
系统编程 (System Coding)	45-60 min	手撕 ML 组件 (Attention/K-Means/Adam)，或写并发/网络代码	"ML 手撕" / "framework 手撕"

AI/ML 岗位的独特之处：除了传统的 LC 类，面试官会额外要求手撕 Attention、Optimizer、Layer Normalization、Dropout，目的是验证候选人是否真正读过 Transformer 论文，而不是只会调 API.

0.2 40 分钟时间盒 (硬性)¶

   面试 40 分钟标准时间盒
   ┌─────────────────────────────────────────────────┐
   │                                                 │
   │  0-5 min  澄清 (Clarify)                       │
   │  ─────────                                     │
   │  • 输入范围? (n 多大? 数据类型? 有负数吗?)      │
   │  • 输出格式? (返回什么? in-place vs 新数组?)   │
   │  • 边界条件? (空输入? 单元素? 重复元素?)        │
   │                                                 │
   │  5-20 min  思路 (Approach)                     │
   │  ─────────                                     │
   │  • 先给暴力解 (brute force), 分析复杂度         │
   │  • 优化: 空间换时间 / 排序 / 双指针 / DP        │
   │  • 说出思路后写伪代码, 再让面试官确认           │
   │                                                 │
   │  20-35 min  写码 (Code)                       │
   │  ─────────                                     │
   │  • 边写边讲, 不要沉默                          │
   │  • 变量名清晰 (i, j 只用于最内层)              │
   │  • 处理边界, 不要留 TODO                       │
   │                                                 │
   │  35-40 min  测试 (Test)                       │
   │  ─────────                                     │
   │  • 主动过一遍样例 (包括 edge cases)             │
   │  • 手动 trace 至少一个中等复杂样例             │
   │  • 提到复杂度: 时间 O(?) 空间 O(?)              │
   │                                                 │
   └─────────────────────────────────────────────────┘

0.3 沟通铁律：边想边说 (Think Aloud)¶

沉默 = 死刑. 面试官看不到你脑子里在想什么，只能看你说什么。常见的沉默陷阱:

❌ 拿到题目，盯着屏幕 5 分钟，一言不发
❌ 卡壳时，停下来发呆
❌ 写代码时，不解释为什么这么写

正确姿势:

✅ "我先分析一下输入，假设数组长度 \(n\)，元素是整数，可能有负数..."
✅ "暴力解是 \(O(n^2)\)，遍历所有二元组。但用哈希表能优化到 \(O(n)\)，我先试试这个思路..."
✅ "这里我用一个 while 循环，因为..."

面试官希望看到的是思考过程，不是最终答案。就算你没做出来，讲清楚思路也能拿到 partial credit.

1. LeetCode 分组高频题清单¶

LeetCode 上的题目虽多，但核心模式只有 15-20 个. 掌握每个模式的代表题，遇到变种就能识别。

1.1 数组与哈希¶

代表题:

LC #	题名	难度	模式
1	Two Sum	Easy	哈希表
15	3Sum	Medium	排序 + 双指针
121	Best Time to Buy and Sell Stock	Easy	一次遍历
128	Longest Consecutive Sequence	Medium	哈希集合

完整走查 1: LC 1 Two Sum (哈希表):

给定整数数组 nums 和目标值 target，返回两个数的下标，使它们之和等于 target. 假设有且仅有一个解。

澄清:

元素是否可以重复使用？(不能，一个数只能用一次)
是否有多个解？(题目保证唯一解)
元素范围？(可能有负数，需支持负数)

思路演进:

暴力：两层循环，\(O(n^2)\) 时间，\(O(1)\) 空间。能过，但慢
排序 + 双指针：排序 \(O(n \log n)\)，但会破坏原下标。需要额外记录
哈希表：遍历时，检查 target - x 是否在哈希表中。 \(O(n)\) 时间，\(O(n)\) 空间。最优

def twoSum(nums: list[int], target: int) -> list[int]:
    """LC 1: 用哈希表一次遍历."""
    seen = {}  # 值 -> 下标
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return []  # 题目保证有解, 理论不到这里

复杂度：时间 \(O(n)\)，空间 \(O(n)\).

面试官常问追问:

"如果数组已排序?" — 双指针法 \(O(n)\) 时间 \(O(1)\) 空间
"如果要返回所有解?" — 需去重，参考 LC 15
"如果不允许哈希表?" — 排序 + 双指针 \(O(n \log n)\)

完整走查 2: LC 15 3Sum (排序 + 双指针):

给定数组 nums，找出所有三元组 \((a, b, c)\) 使 \(a + b + c = 0\)，结果不含重复三元组。

关键点：去重 + 双指针 + 固定一个数扫另外两个。

def threeSum(nums: list[int]) -> list[list[int]]:
    """LC 15: 排序 + 双指针, 去重."""
    nums.sort()
    n = len(nums)
    result = []
    for i in range(n - 2):
        # 剪枝: 若第一个数已 > 0, 后面不可能凑出 0
        if nums[i] > 0:
            break
        # 去重: 跳过重复的第一个数
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                # 跳过重复的 left / right
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return result

复杂度：时间 \(O(n^2)\) (排序 \(O(n \log n)\) + 双指针 \(O(n^2)\))，空间 \(O(1)\) (不算返回).

常见追问:

"4Sum 怎么做?" — 再套一层循环，\(O(n^3)\)
"K-Sum 通用解法?" — 递归 + 双指针，\(O(n^{K-1})\)

1.2 双指针¶

代表题:

LC #	题名	难度	模式
11	Container With Most Water	Medium	双指针向内收缩
42	Trapping Rain Water	Hard	双指针 / 单调栈

完整走查 3: LC 11 Container With Most Water:

给定非负整数数组 height，每个元素是一条垂线的高度。找出两条线，使它们与 x 轴形成的容器能容纳最多的水。

思路：双指针从两端向内收缩。关键：每次移动短的那根——因为容量由短板决定，移动长的那根不可能变大。

def maxArea(height: list[int]) -> int:
    """LC 11: 双指针, 每次移动短板."""
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h = min(height[left], height[right])
        best = max(best, h * (right - left))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

复杂度：时间 \(O(n)\)，空间 \(O(1)\).

为什么正确 (数学证明)：假设最优解在 \((i^*, j^*)\). 反证：若指针在移动过程中经过 \((i^*, ?)\) 或 \((?, j^*)\) 的其中一个，就会命中。而移动短板保证了不会跳过最优解——因为移动长板只会让容器变小。

1.3 滑动窗口¶

代表题:

LC #	题名	难度	模式
3	Longest Substring Without Repeating Characters	Medium	滑动窗口 + 哈希
76	Minimum Window Substring	Hard	滑动窗口 + 双哈希

完整走查 4: LC 3 Longest Substring Without Repeating:

给定字符串 s，找出不含重复字符的最长子串长度。

def lengthOfLongestSubstring(s: str) -> int:
    """LC 3: 滑动窗口, 右指针扩张 + 左指针收缩."""
    last_pos = {}  # 字符 -> 最后一次出现的下标
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_pos and last_pos[ch] >= left:
            left = last_pos[ch] + 1  # 收缩左边界
        last_pos[ch] = right
        best = max(best, right - left + 1)
    return best

复杂度：时间 \(O(n)\)，空间 \(O(\min(n, |\Sigma|))\) (字符集大小).

1.4 树¶

代表题:

LC #	题名	难度	模式
104	Maximum Depth of Binary Tree	Easy	DFS 递归
236	Lowest Common Ancestor of a Binary Tree	Medium	DFS 后序
297	Serialize and Deserialize Binary Tree	Hard	BFS / 前序遍历

LC 236 LCA 关键代码 (面试超高频):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    """LC 236: 递归后序. 只要左右子树各含一个目标, 当前节点即为 LCA."""
    if root is None or root is p or root is q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root  # p 和 q 分居左右子树, 当前节点是 LCA
    return left if left else right

复杂度：时间 \(O(n)\)，空间 \(O(h)\) (\(h\) 为树高，递归栈).

1.5 图¶

代表题:

LC #	题名	难度	模式
200	Number of Islands	Medium	DFS/BFS 连通分量
207	Course Schedule	Medium	拓扑排序
743	Network Delay Time	Medium	Dijkstra 最短路

完整走查 5: LC 200 Number of Islands (DFS):

def numIslands(grid: list[list[str]]) -> int:
    """LC 200: DFS 淹没相连的 '1'."""
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(r: int, c: int) -> None:
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # 淹没, 标记已访问
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

复杂度：时间 \(O(mn)\)，空间 \(O(mn)\) (最坏递归栈).

常见追问:

"grid 太大，递归会栈溢出怎么办?" — 改 BFS，用 queue
"如何统计岛屿面积?" — DFS 返回值累计
"如果动态加水/挖水?" — 并查集 (Union-Find)

完整走查 6: LC 207 Course Schedule (拓扑排序):

给定课程数 numCourses 和先修关系 prerequisites = [[a, b], ...] (学 \(a\) 前需先学 \(b\))，判断能否完成全部课程。

本质：判断有向图有无环。拓扑排序法 (Kahn 算法) — 反复取入度为 0 的节点。

from collections import deque

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    """LC 207: Kahn 拓扑排序. 若排序结果覆盖所有课程 → 无环 → 可完成."""
    graph = [[] for _ in range(numCourses)]
    indeg = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)  # b -> a
        indeg[a] += 1

    queue = deque([i for i in range(numCourses) if indeg[i] == 0])
    visited = 0
    while queue:
        u = queue.popleft()
        visited += 1
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return visited == numCourses

复杂度：时间 \(O(V + E)\)，空间 \(O(V + E)\).

1.6 动态规划¶

代表题:

LC #	题名	难度	模式
198	House Robber	Medium	1D DP
322	Coin Change	Medium	完全背包
300	Longest Increasing Subsequence	Medium	DP / 二分
72	Edit Distance	Hard	2D DP

完整走查 7: LC 300 Longest Increasing Subsequence (LIS):

给定数组 nums，返回最长严格递增子序列的长度。

思路:

朴素 DP: dp[i] = 以 nums[i] 结尾的最长 LIS 长度。转移 dp[i] = max(dp[j] + 1) for all j < i and nums[j] < nums[i]. \(O(n^2)\)
二分优化：维护 tails[k] = 长度为 k+1 的所有 LIS 中，尾部最小值。用二分找插入位置。 \(O(n \log n)\)

from bisect import bisect_left

def lengthOfLIS(nums: list[int]) -> int:
    """LC 300: patience sorting, 二分优化 O(n log n)."""
    tails = []  # tails[k] = 长度为 k+1 的 LIS 中最小尾元素
    for x in nums:
        idx = bisect_left(tails, x)
        if idx == len(tails):
            tails.append(x)
        else:
            tails[idx] = x
    return len(tails)

注意: tails 本身不是 LIS 的一个具体解，但长度就是 LIS 长度。若需还原具体子序列，需额外记录前驱。

完整走查 8: LC 72 Edit Distance (2D DP):

给定两个单词 word1、word2，返回把 word1 转成 word2 所需的最小编辑操作数 (插入、删除、替换).

状态: dp[i][j] = 把 word1[:i] 转成 word2[:j] 的最小代价。

转移:

\[ dp[i][j] = \begin{cases} j & \text{if } i = 0 \\ i & \text{if } j = 0 \\ dp[i-1][j-1] & \text{if } w_1[i-1] = w_2[j-1] \\ 1 + \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) & \text{otherwise} \end{cases} \]

def minDistance(word1: str, word2: str) -> int:
    """LC 72: 经典 2D DP."""
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # 删除
                    dp[i][j - 1],      # 插入
                    dp[i - 1][j - 1],  # 替换
                )
    return dp[m][n]

复杂度：时间 \(O(mn)\)，空间 \(O(mn)\) (可滚动数组降到 \(O(n)\)).

1.7 回溯¶

代表题:

LC #	题名	难度	模式
78	Subsets	Medium	选/不选
46	Permutations	Medium	used 数组
51	N-Queens	Hard	列/对角线冲突集

完整走查 9: LC 51 N-Queens (经典回溯):

在 \(n \times n\) 棋盘上放 \(n\) 个皇后，使得任意两个皇后不在同一行、同一列、同一对角线上。返回所有方案数。

关键：用 3 个集合分别记录已占的列、主对角线 (r - c)、副对角线 (r + c)，冲突检查 \(O(1)\).

def solveNQueens(n: int) -> list[list[str]]:
    """LC 51: 逐行放皇后 + 三集合剪枝."""
    result = []
    cols = set()      # 已占的列
    diag1 = set()     # 主对角线: r - c
    diag2 = set()     # 副对角线: r + c
    board = [['.'] * n for _ in range(n)]

    def backtrack(r: int) -> None:
        if r == n:
            result.append([''.join(row) for row in board])
            return
        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue
            board[r][c] = 'Q'
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            backtrack(r + 1)
            board[r][c] = '.'
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)

    backtrack(0)
    return result

复杂度：时间约 \(O(n!)\) (剪枝后远小于 \(n^n\))，空间 \(O(n)\) (递归栈 + 三集合).

1.8 贪心¶

代表题:

LC #	题名	难度	模式
55	Jump Game	Medium	记录能到的最远位置
435	Non-overlapping Intervals	Medium	按结束时间贪心

LC 55 关键代码:

def canJump(nums: list[int]) -> bool:
    """LC 55: 记录能到达的最远下标, 一次遍历."""
    furthest = 0
    for i, jump in enumerate(nums):
        if i > furthest:
            return False  # 到不了 i, 直接失败
        furthest = max(furthest, i + jump)
    return True

复杂度：时间 \(O(n)\)，空间 \(O(1)\).

1.9 优先队列¶

代表题:

LC #	题名	难度	模式
215	Kth Largest Element in an Array	Medium	小根堆 / QuickSelect
253	Meeting Rooms II	Medium	按开始排序 + 最小堆维护结束时间

LC 215 两种解法:

import heapq

def findKthLargest_heap(nums: list[int], k: int) -> int:
    """LC 215 解法 1: 维护大小为 k 的小根堆, O(n log k)."""
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

def findKthLargest_quickselect(nums: list[int], k: int) -> int:
    """LC 215 解法 2: QuickSelect 平均 O(n)."""
    import random
    def select(lo: int, hi: int, target: int) -> int:
        if lo == hi:
            return nums[lo]
        pivot = nums[random.randint(lo, hi)]
        # 三路划分
        lt, gt = lo, hi
        i = lo
        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1; i += 1
            elif nums[i] > pivot:
                nums[gt], nums[i] = nums[i], nums[gt]
                gt -= 1
            else:
                i += 1
        # 求第 k 大 = 求第 (n-k) 小
        if target < lt:
            return select(lo, lt - 1, target)
        elif target > gt:
            return select(gt + 1, hi, target)
        return pivot
    n = len(nums)
    return select(0, n - 1, n - k)

复杂度对比:

堆法：时间 \(O(n \log k)\)，空间 \(O(k)\)，稳定
QuickSelect：平均 \(O(n)\)，最坏 \(O(n^2)\)，期望空间 \(O(\log n)\)

面试首选堆法 (代码短、稳定)，有余力提 QuickSelect 加分。

2. ML 相关手撕题 (AI 面试独家)¶

这一部分是AI/ML 岗位独有的手撕题。面试官想验证：你是否真正读过论文，是否理解每个 nn.Module 背后的数学。

2.1 手撕多头注意力 (Multi-Head Self-Attention, MHA)¶

Scaled Dot-Product Attention 公式 (Vaswani et al., 2017):

\[ \text{Attention}(Q, K, V) = \text{softmax}\left(\frac{Q K^\top}{\sqrt{d_k}} + M\right) V \]

其中 \(Q, K \in \mathbb{R}^{n \times d_k}\), \(V \in \mathbb{R}^{n \times d_v}\), \(M\) 是可选的掩码 (对填充位置或因果位置置 \(-\infty\)).

多头注意力 (Multi-Head Attention, MHA)：把 \(d_{\text{model}}\) 拆成 \(h\) 个头，每头独立做 attention，再拼接:

\[ \text{MHA}(Q, K, V) = \text{Concat}(\text{head}_1, \dots, \text{head}_h) W^O \]

其中 \(\text{head}_i = \text{Attention}(Q W_i^Q, K W_i^K, V W_i^V)\).

完整 PyTorch 实现 (含 causal mask):

import torch
import torch.nn as nn
import torch.nn.functional as F
import math

class MultiHeadSelfAttention(nn.Module):
    """多头自注意力, 支持因果掩码 (causal mask) 与 padding mask."""

    def __init__(self, d_model: int, num_heads: int, dropout: float = 0.0):
        super().__init__()
        assert d_model % num_heads == 0, "d_model 必须能被 num_heads 整除"
        self.d_model = d_model
        self.num_heads = num_heads
        self.d_k = d_model // num_heads  # 每个头的维度

        # 一个大矩阵一次算 Q, K, V, 再拆开 (工程上更快)
        self.qkv_proj = nn.Linear(d_model, 3 * d_model, bias=False)
        self.out_proj = nn.Linear(d_model, d_model, bias=False)
        self.dropout = nn.Dropout(dropout)

    def forward(
        self,
        x: torch.Tensor,           # (B, T, d_model)
        mask: torch.Tensor = None, # (B, 1, T, T) 或 (T, T), 加性掩码 (0 或 -inf)
        causal: bool = False,
    ) -> torch.Tensor:
        B, T, _ = x.shape
        # 1. Q, K, V 投影, 分头
        qkv = self.qkv_proj(x)                                # (B, T, 3*d_model)
        qkv = qkv.reshape(B, T, 3, self.num_heads, self.d_k)  # (B, T, 3, h, d_k)
        qkv = qkv.permute(2, 0, 3, 1, 4)                      # (3, B, h, T, d_k)
        q, k, v = qkv[0], qkv[1], qkv[2]                      # 各 (B, h, T, d_k)

        # 2. Scaled dot-product: (B, h, T, T)
        scores = torch.matmul(q, k.transpose(-2, -1)) / math.sqrt(self.d_k)

        # 3. 掩码
        if causal:
            # 上三角 mask (自回归 LM)
            causal_mask = torch.triu(
                torch.ones(T, T, device=x.device, dtype=torch.bool),
                diagonal=1,
            )
            scores = scores.masked_fill(causal_mask, float('-inf'))
        if mask is not None:
            scores = scores + mask  # 加性掩码, padding 位置为 -inf

        # 4. Softmax + dropout + 加权求和
        attn = F.softmax(scores, dim=-1)
        attn = self.dropout(attn)
        out = torch.matmul(attn, v)                           # (B, h, T, d_k)

        # 5. 合并头 + 输出投影
        out = out.transpose(1, 2).contiguous().reshape(B, T, self.d_model)
        return self.out_proj(out)


# 快速自测
if __name__ == "__main__":
    mha = MultiHeadSelfAttention(d_model=512, num_heads=8)
    x = torch.randn(2, 16, 512)
    y = mha(x, causal=True)
    assert y.shape == (2, 16, 512)
    print("MHA 输出:", y.shape)

复杂度:

时间 \(O(T^2 \cdot d_{\text{model}})\) (注意力矩阵是 \(T \times T\))
空间 \(O(T^2 \cdot h)\) (存注意力权重)

面试官常问追问:

"为什么除以 \(\sqrt{d_k}\)?" — 防止点积过大导致 softmax 饱和 (梯度消失). 直觉：\(Q, K\) 元素方差为 1 时，\(QK^\top\) 元素方差为 \(d_k\)，除以 \(\sqrt{d_k}\) 恢复方差为 1
"为什么用多个头?" — 每个头可以关注不同子空间的表示，类似 CNN 多个 filter
"causal mask 怎么写?" — 上三角为 True 的 bool 矩阵，用 masked_fill(-inf) 后 softmax 输出 0
"如何优化到 \(O(T \log T)\) 或线性?" — FlashAttention (I/O 优化不变复杂度) 或 Linear Attention (核化)

2.2 手撕 AdamW (从零)¶

AdamW (Loshchilov & Hutter, 2019)：在 Adam 的基础上把 weight decay 从梯度中解耦出来，直接作用于权重。完整更新公式:

\[ \begin{aligned} g_t &= \nabla_\theta L(\theta_{t-1}) \\ m_t &= \beta_1 m_{t-1} + (1 - \beta_1) g_t \\ v_t &= \beta_2 v_{t-1} + (1 - \beta_2) g_t^2 \\ \hat{m}_t &= \frac{m_t}{1 - \beta_1^t} \\ \hat{v}_t &= \frac{v_t}{1 - \beta_2^t} \\ \theta_t &= \theta_{t-1} - \eta \left( \frac{\hat{m}_t}{\sqrt{\hat{v}_t} + \epsilon} + \lambda \theta_{t-1} \right) \end{aligned} \]

关键差异 (vs Adam): weight decay 项 \(\lambda \theta_{t-1}\) 不进入 \(m_t\) 或 \(v_t\)，而是直接减在权重上。

从零实现 (PyTorch):

import torch
from torch.optim import Optimizer

class AdamW(Optimizer):
    """从零实现 AdamW (Loshchilov & Hutter, 2019, arXiv:1711.05101)."""

    def __init__(
        self,
        params,
        lr: float = 1e-3,
        betas: tuple = (0.9, 0.999),
        eps: float = 1e-8,
        weight_decay: float = 1e-2,
    ):
        if lr < 0:
            raise ValueError(f"学习率必须非负: {lr}")
        defaults = dict(lr=lr, betas=betas, eps=eps, weight_decay=weight_decay)
        super().__init__(params, defaults)

    @torch.no_grad()
    def step(self, closure=None):
        loss = None
        if closure is not None:
            with torch.enable_grad():
                loss = closure()

        for group in self.param_groups:
            lr = group['lr']
            beta1, beta2 = group['betas']
            eps = group['eps']
            weight_decay = group['weight_decay']

            for p in group['params']:
                if p.grad is None:
                    continue
                grad = p.grad
                if grad.is_sparse:
                    raise RuntimeError("AdamW 不支持稀疏梯度")

                state = self.state[p]
                # 状态初始化
                if len(state) == 0:
                    state['step'] = 0
                    state['m'] = torch.zeros_like(p)
                    state['v'] = torch.zeros_like(p)

                m, v = state['m'], state['v']
                state['step'] += 1
                t = state['step']

                # 1. 更新一阶、二阶矩估计
                m.mul_(beta1).add_(grad, alpha=1 - beta1)
                v.mul_(beta2).addcmul_(grad, grad, value=1 - beta2)

                # 2. 偏差修正
                bias_c1 = 1 - beta1 ** t
                bias_c2 = 1 - beta2 ** t
                m_hat = m / bias_c1
                v_hat = v / bias_c2

                # 3. AdamW 关键: weight decay 直接作用于 p, 不进 m/v
                update = m_hat / (v_hat.sqrt() + eps) + weight_decay * p
                p.add_(update, alpha=-lr)

        return loss

面试常问: "AdamW 和 Adam + L2 有什么区别?"

Adam + L2 把 \(\lambda \theta\) 加到 grad 里，会被 \(m, v\) 一起放大/衰减，实际衰减强度和学习率、\(\hat{v}\) 耦合，不可控
AdamW 把 \(\lambda \theta\) 独立减在权重上，衰减强度只由 \(\lambda\) 和 \(\eta\) 决定，更符合"正则化"本意
实验上 AdamW 在 Transformer 训练中泛化更好，已成 LLM 标配

2.3 手撕 K-Means (含 K-Means++ 初始化)¶

K 均值 (K-Means) 目标：把 \(n\) 个点分到 \(k\) 个簇，最小化簇内平方距离和 (Sum of Squared Errors, SSE):

\[ J = \sum_{i=1}^{n} \sum_{c=1}^{k} \mathbb{1}[z_i = c] \|x_i - \mu_c\|_2^2 \]

Lloyd 算法：交替 (a) 分配每个点到最近簇心，(b) 更新簇心为簇内均值。收敛到局部最优。

K-Means++ (Arthur & Vassilvitskii, 2007)：用带权采样初始化簇心，让初始簇心尽量分散，显著改善收敛质量。

import numpy as np

def kmeans_pp_init(X: np.ndarray, k: int, rng: np.random.Generator) -> np.ndarray:
    """K-Means++ 初始化 (Arthur & Vassilvitskii, 2007)."""
    n, _ = X.shape
    centers = np.empty((k, X.shape[1]), dtype=X.dtype)
    # 1. 均匀采样第一个中心
    idx = rng.integers(n)
    centers[0] = X[idx]
    # 2. 后续中心: 与已选中心距离平方成正比采样
    dist_sq = np.full(n, np.inf)
    for c in range(1, k):
        diff = X - centers[c - 1]
        d = np.einsum('ij,ij->i', diff, diff)
        dist_sq = np.minimum(dist_sq, d)
        # 按 dist_sq 归一化后带权采样
        probs = dist_sq / dist_sq.sum()
        idx = rng.choice(n, p=probs)
        centers[c] = X[idx]
    return centers


def kmeans(
    X: np.ndarray,
    k: int,
    max_iter: int = 300,
    tol: float = 1e-4,
    seed: int = 0,
) -> tuple:
    """K-Means with K-Means++ 初始化. 返回 (labels, centers, sse)."""
    rng = np.random.default_rng(seed)
    n, d = X.shape

    # 1. K-Means++ 初始化
    centers = kmeans_pp_init(X, k, rng)

    prev_sse = np.inf
    for it in range(max_iter):
        # 2. 分配: 每点到最近簇心 (广播计算距离矩阵)
        # (n, 1, d) - (1, k, d) -> (n, k, d) -> (n, k)
        dists = np.linalg.norm(X[:, None, :] - centers[None, :, :], axis=2)
        labels = dists.argmin(axis=1)

        # 3. 更新: 每簇的均值
        new_centers = np.empty_like(centers)
        for c in range(k):
            members = X[labels == c]
            if len(members) == 0:
                # 空簇: 随机重新采样一个点做中心
                new_centers[c] = X[rng.integers(n)]
            else:
                new_centers[c] = members.mean(axis=0)

        # 4. 收敛判断: SSE 变化 < tol
        sse = float((dists.min(axis=1) ** 2).sum())
        if abs(prev_sse - sse) < tol:
            centers = new_centers
            break
        centers = new_centers
        prev_sse = sse

    return labels, centers, sse

复杂度：每轮 \(O(n k d)\)，迭代 \(T\) 轮总 \(O(n k d T)\).

常见追问:

"K 怎么选?" — 肘部法 (Elbow Method) + 轮廓系数 (Silhouette) + Gap Statistic
"K-Means 对异常值敏感?" — 是，因为均值受极端值影响。改用 K-Medoids (PAM) 更鲁棒
"如何处理非凸簇?" — DBSCAN / 谱聚类

2.4 手撕 KNN + KD 树 (KD-Tree)¶

K 近邻 (K-Nearest Neighbors, KNN)：给定查询点 \(q\)，从训练集中找出 \(k\) 个最近邻，用它们的多数标签 (分类) 或均值 (回归) 作为预测。

朴素 KNN：遍历所有训练点算距离，\(O(nd)\) 查询。数据量大时不可接受。

KD 树 (KD-Tree)：递归按坐标轴划分空间，平均查询 \(O(\log n)\) (低维时). 高维退化到 \(O(n)\).

import numpy as np
from typing import Optional
import heapq

class KDNode:
    __slots__ = ('point', 'idx', 'axis', 'left', 'right')

    def __init__(self, point, idx, axis, left=None, right=None):
        self.point = point
        self.idx = idx
        self.axis = axis
        self.left = left
        self.right = right


class KDTree:
    """KD 树, 支持 K 近邻查询."""

    def __init__(self, X: np.ndarray):
        self.X = X
        self.n, self.d = X.shape
        indices = np.arange(self.n)
        self.root = self._build(indices, depth=0)

    def _build(self, indices: np.ndarray, depth: int) -> Optional[KDNode]:
        if len(indices) == 0:
            return None
        axis = depth % self.d
        # 按当前轴排序, 取中位数
        sorted_idx = indices[np.argsort(self.X[indices, axis])]
        mid = len(sorted_idx) // 2
        idx = sorted_idx[mid]
        return KDNode(
            point=self.X[idx],
            idx=int(idx),
            axis=axis,
            left=self._build(sorted_idx[:mid], depth + 1),
            right=self._build(sorted_idx[mid + 1:], depth + 1),
        )

    def query(self, q: np.ndarray, k: int = 1) -> list[tuple]:
        """返回 k 近邻的 (距离, 原始下标) 列表."""
        heap = []  # 最大堆, 存 (-dist, idx), 保持大小 <= k

        def dfs(node: Optional[KDNode]) -> None:
            if node is None:
                return
            dist = float(np.linalg.norm(q - node.point))
            if len(heap) < k:
                heapq.heappush(heap, (-dist, node.idx))
            elif dist < -heap[0][0]:
                heapq.heapreplace(heap, (-dist, node.idx))

            diff = q[node.axis] - node.point[node.axis]
            near, far = (node.left, node.right) if diff < 0 else (node.right, node.left)
            dfs(near)
            # 检查另一侧: 若当前 k 个候选中最大距离 > |diff|, 则另一侧可能有更近点
            if len(heap) < k or abs(diff) < -heap[0][0]:
                dfs(far)

        dfs(self.root)
        # 从最大堆转为按距离升序返回
        return sorted([(-d, i) for d, i in heap])


class KNNClassifier:
    """基于 KD 树的 KNN 分类器."""

    def __init__(self, k: int = 5):
        self.k = k

    def fit(self, X: np.ndarray, y: np.ndarray) -> "KNNClassifier":
        self.tree = KDTree(X)
        self.y = y
        return self

    def predict(self, X: np.ndarray) -> np.ndarray:
        preds = []
        for q in X:
            neighbors = self.tree.query(q, k=self.k)
            labels = [self.y[idx] for _, idx in neighbors]
            # 多数投票
            vals, counts = np.unique(labels, return_counts=True)
            preds.append(vals[counts.argmax()])
        return np.array(preds)

复杂度:

建树：\(O(n d \log n)\)
单次查询：平均 \(O(\log n)\) (低维)，高维退化 \(O(n)\)
高维数据推荐 Ball Tree 或 HNSW/FAISS 等 ANN 结构

2.5 手撕反向传播 (单层 MLP)¶

单层 MLP + Sigmoid + MSE 手推:

前向:

\[ z = W x + b, \quad a = \sigma(z), \quad L = \frac{1}{2}(a - y)^2 \]

反向 (链式法则):

\[ \frac{\partial L}{\partial a} = a - y, \quad \frac{\partial L}{\partial z} = (a - y) \cdot \sigma'(z) = (a - y) \cdot a (1 - a) \]

\[ \frac{\partial L}{\partial W} = \frac{\partial L}{\partial z} \cdot x^\top, \quad \frac{\partial L}{\partial b} = \frac{\partial L}{\partial z} \]

从零实现 (NumPy):

import numpy as np

class SingleLayerMLP:
    """单层 MLP + Sigmoid + MSE, 手写前向/反向."""

    def __init__(self, in_dim: int, out_dim: int, lr: float = 0.1, seed: int = 0):
        rng = np.random.default_rng(seed)
        # He / Xavier 初始化都行, 这里用简单的高斯
        self.W = rng.standard_normal((out_dim, in_dim)) * np.sqrt(1.0 / in_dim)
        self.b = np.zeros(out_dim)
        self.lr = lr

    @staticmethod
    def _sigmoid(z: np.ndarray) -> np.ndarray:
        return 1.0 / (1.0 + np.exp(-z))

    def forward(self, x: np.ndarray) -> np.ndarray:
        # x: (batch, in_dim), 输出 (batch, out_dim)
        self.x = x
        self.z = x @ self.W.T + self.b       # (batch, out_dim)
        self.a = self._sigmoid(self.z)
        return self.a

    def backward(self, y: np.ndarray) -> float:
        # y: (batch, out_dim). 返回 loss
        loss = 0.5 * float(np.mean((self.a - y) ** 2))
        # 反向: dL/dz = (a - y) * a * (1 - a)
        dz = (self.a - y) * self.a * (1 - self.a) / y.shape[0]
        dW = dz.T @ self.x                    # (out_dim, in_dim)
        db = dz.sum(axis=0)                   # (out_dim,)
        # 更新
        self.W -= self.lr * dW
        self.b -= self.lr * db
        return loss

2.6 手撕 Layer Normalization¶

层归一化 (Layer Normalization, Ba et al., 2016) 公式:

\[ \text{LN}(x) = \gamma \odot \frac{x - \mu}{\sqrt{\sigma^2 + \epsilon}} + \beta \]

其中 \(\mu, \sigma^2\) 沿特征维 (最后一维) 计算，每条样本各算各的:

\[ \mu = \frac{1}{d} \sum_{i=1}^{d} x_i, \quad \sigma^2 = \frac{1}{d} \sum_{i=1}^{d} (x_i - \mu)^2 \]

import torch
import torch.nn as nn

class LayerNorm(nn.Module):
    """手写 LayerNorm, 沿最后一维归一化."""

    def __init__(self, normalized_shape: int, eps: float = 1e-5):
        super().__init__()
        self.eps = eps
        self.gamma = nn.Parameter(torch.ones(normalized_shape))
        self.beta = nn.Parameter(torch.zeros(normalized_shape))

    def forward(self, x: torch.Tensor) -> torch.Tensor:
        # x: (..., d), 沿最后一维归一化
        mu = x.mean(dim=-1, keepdim=True)
        var = x.var(dim=-1, keepdim=True, unbiased=False)
        x_hat = (x - mu) / torch.sqrt(var + self.eps)
        return self.gamma * x_hat + self.beta

面试常追问:

"LN 和 BN 有什么区别?" — BN 沿 batch 维统计，LN 沿特征维统计。 Transformer 用 LN 因为序列长度可变、batch 内样本长度不同，BN 统计不稳定
"RMSNorm 是什么?" — LN 的简化版，只除以 RMS，不减均值。 LLaMA 系列在用

2.7 手撕 Dropout (train / eval 双模)¶

Dropout (Srivastava et al., 2014)：训练时以概率 \(p\) 随机置 0，保留位置放大 \(1/(1-p)\) (inverted dropout)，使期望不变。评估时直接透传。

import torch
import torch.nn as nn

class Dropout(nn.Module):
    """Inverted dropout. Train 时 mask + scale, Eval 时直通."""

    def __init__(self, p: float = 0.5):
        super().__init__()
        assert 0.0 <= p < 1.0, "p 必须在 [0, 1)"
        self.p = p

    def forward(self, x: torch.Tensor) -> torch.Tensor:
        if not self.training or self.p == 0.0:
            return x
        # Bernoulli mask, 保留概率 1 - p
        mask = (torch.rand_like(x) > self.p).to(x.dtype)
        # 缩放: 保留位置乘 1 / (1 - p), 使 E[out] = x
        return x * mask / (1.0 - self.p)

2.8 手撕简易 BPE tokenizer (骨架)¶

字节对编码 (Byte-Pair Encoding, BPE) 是 GPT / LLaMA 系列的核心 tokenizer 算法。训练流程:

初始词表 = 所有单字符 (含特殊符号)
统计训练语料中所有相邻字符对的频次
合并频次最高的对，加入词表
重复步骤 2-3，直到词表达到指定大小

from collections import Counter, defaultdict

def bpe_train(corpus: list[str], vocab_size: int) -> tuple[list[str], dict]:
    """BPE 训练骨架 (教学版, 生产用请查 HuggingFace tokenizers).

    Args:
        corpus: 训练语料, 每条是字符串
        vocab_size: 目标词表大小

    Returns:
        vocab: 最终词表 (token 列表)
        merges: 合并规则字典, (a, b) -> 合并后的 token
    """
    # 1. 每个词按字符切分, 末尾加 </w> 标记词尾
    word_freq = Counter()
    for line in corpus:
        for word in line.split():
            symbols = tuple(word) + ('</w>',)
            word_freq[symbols] += 1

    # 2. 初始词表
    vocab = set()
    for symbols in word_freq:
        vocab.update(symbols)

    merges = {}

    while len(vocab) < vocab_size:
        # 3. 统计所有相邻符号对的频次
        pair_freq = defaultdict(int)
        for symbols, freq in word_freq.items():
            for i in range(len(symbols) - 1):
                pair_freq[(symbols[i], symbols[i + 1])] += freq

        if not pair_freq:
            break

        # 4. 选频次最高的对
        best_pair = max(pair_freq, key=pair_freq.get)
        new_token = ''.join(best_pair)
        merges[best_pair] = new_token
        vocab.add(new_token)

        # 5. 更新 word_freq: 把出现的 best_pair 合并
        new_word_freq = Counter()
        a, b = best_pair
        for symbols, freq in word_freq.items():
            new_symbols = []
            i = 0
            while i < len(symbols):
                if i < len(symbols) - 1 and symbols[i] == a and symbols[i + 1] == b:
                    new_symbols.append(new_token)
                    i += 2
                else:
                    new_symbols.append(symbols[i])
                    i += 1
            new_word_freq[tuple(new_symbols)] = freq
        word_freq = new_word_freq

    return sorted(vocab), merges


def bpe_encode(text: str, merges: dict) -> list[str]:
    """把新文本按 merges 规则切成 BPE tokens."""
    tokens = []
    for word in text.split():
        symbols = list(word) + ['</w>']
        # 反复合并所有能合的对
        while True:
            merged = False
            i = 0
            new_symbols = []
            while i < len(symbols):
                if i < len(symbols) - 1 and (symbols[i], symbols[i + 1]) in merges:
                    new_symbols.append(merges[(symbols[i], symbols[i + 1])])
                    i += 2
                    merged = True
                else:
                    new_symbols.append(symbols[i])
                    i += 1
            symbols = new_symbols
            if not merged:
                break
        tokens.extend(symbols)
    return tokens

注意：这是教学骨架，生产环境请用 HuggingFace tokenizers 库或 Google SentencePiece. 真实实现涉及优先队列、字节级 fallback、正则预分词等大量细节。

3. 面向对象设计 (OOD) 手撕题¶

面向对象设计题的核心：用合适的数据结构组合出接口. 面试官在意的是 (a) 数据结构选型 (b) API 拆分 (c) 复杂度。

3.1 LC 146 LRU Cache (超高频)¶

设计一个数据结构，支持 get(key) 和 put(key, value)，两者都是 \(O(1)\). 当容量满时，淘汰最久未使用 (Least Recently Used) 的键。

核心思路：哈希表 + 双向链表。

哈希表：key -> node，查询 \(O(1)\)
双向链表：维护访问顺序，最近访问的移到头，尾部是最久未用

class LRUCache:
    """LC 146: 哈希 + 双向链表, get/put 都是 O(1)."""

    class _Node:
        __slots__ = ('key', 'value', 'prev', 'next')
        def __init__(self, key=0, value=0):
            self.key = key
            self.value = value
            self.prev = None
            self.next = None

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # key -> _Node
        # 哨兵头尾, 简化边界
        self.head = self._Node()
        self.tail = self._Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: '_Node') -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_head(self, node: '_Node') -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _move_to_head(self, node: '_Node') -> None:
        self._remove(node)
        self._add_to_head(node)

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
            return
        node = self._Node(key, value)
        self.cache[key] = node
        self._add_to_head(node)
        if len(self.cache) > self.cap:
            # 淘汰尾部
            victim = self.tail.prev
            self._remove(victim)
            del self.cache[victim.key]

复杂度: get、put 均摊 \(O(1)\)，空间 \(O(\text{cap})\).

常见追问:

"怎么支持并发?" — 用锁 (粗粒度) 或分段锁 (细粒度)，或改用 OrderedDict + threading.Lock
"LFU 怎么实现?" — 需 (频次，最近使用时间) 双维度，复杂度更高 (见 LC 460)
"带 TTL 呢?" — 加一个过期时间字段，惰性删除 (get 时检查) 或后台清理

3.2 LC 155 Min Stack (辅助栈)¶

设计一个栈，支持 push、pop、top，以及常数时间返回栈内最小值。

核心：主栈 + 辅助栈。辅助栈每一层存"截止当前的最小值".

class MinStack:
    """LC 155: 主栈 + 单调不增辅助栈."""

    def __init__(self):
        self.stack = []
        self.min_stack = []  # 与 stack 同步, 存"到当前位置为止的最小值"

    def push(self, val: int) -> None:
        self.stack.append(val)
        m = val if not self.min_stack else min(val, self.min_stack[-1])
        self.min_stack.append(m)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

3.3 LC 380 Insert Delete GetRandom O(1)¶

设计数据结构，支持插入、删除、随机取一个元素，三者都是 \(O(1)\).

核心：数组 + 哈希表。数组存值 (方便随机)，哈希表存 val -> idx (方便定位删除位置). 删除时把最后一个元素换到被删位置。

import random

class RandomizedSet:
    """LC 380: 数组 + 哈希, 均摊 O(1)."""

    def __init__(self):
        self.vals = []          # 存值
        self.idx = {}           # val -> idx in vals

    def insert(self, val: int) -> bool:
        if val in self.idx:
            return False
        self.idx[val] = len(self.vals)
        self.vals.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.idx:
            return False
        i = self.idx[val]
        last = self.vals[-1]
        # 把 last 换到 i 位置, 再 pop
        self.vals[i] = last
        self.idx[last] = i
        self.vals.pop()
        del self.idx[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.vals)

3.4 LC 981 Time-Based Key-Value Store¶

设计一个基于时间的键值存储，支持: - set(key, value, timestamp) - get(key, timestamp) — 返回不晚于 timestamp 的最新值

核心：每个 key 对应一个按时间排序的 (timestamp, value) 列表。 get 时二分查找。

from bisect import bisect_right
from collections import defaultdict

class TimeMap:
    """LC 981: key -> 按时间排序的 (ts, val) 列表, 二分查询."""

    def __init__(self):
        self.data = defaultdict(list)  # key -> [(ts, val), ...] (ts 单调增)

    def set(self, key: str, value: str, timestamp: int) -> None:
        # 题目保证 set 时 timestamp 严格递增
        self.data[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        arr = self.data.get(key)
        if not arr:
            return ""
        # 找第一个 ts > timestamp 的位置, 返回前一个
        i = bisect_right(arr, (timestamp, chr(127)))  # 一个技巧: 大字符做上界
        if i == 0:
            return ""
        return arr[i - 1][1]

复杂度: set \(O(1)\), get \(O(\log n)\).

3.5 设计 Rate Limiter (令牌桶)¶

令牌桶 (Token Bucket) 算法：桶以固定速率 \(r\) 补充令牌 (上限 \(b\))，每个请求消耗一个令牌，桶空时拒绝或等待。

关键点 (面试常问):

令牌不需要真的用定时线程补充，采用惰性计算 (lazy refill)：请求到来时按时间差补齐
补充公式：tokens = min(capacity, tokens + (now - last) * rate)

import time
import threading

class TokenBucketRateLimiter:
    """令牌桶限流器, 每 key 独立限流."""

    def __init__(self, capacity: int, rate: float):
        """
        Args:
            capacity: 令牌桶容量 (突发上限)
            rate: 每秒补充令牌数
        """
        self.capacity = capacity
        self.rate = rate
        # 每 key 存 (tokens, last_refill_ts)
        self.buckets = {}
        self.lock = threading.Lock()

    def allow(self, key: str, n: int = 1) -> bool:
        """尝试消费 n 个令牌. 返回是否允许."""
        now = time.monotonic()
        with self.lock:
            tokens, last = self.buckets.get(key, (self.capacity, now))
            # 惰性补充
            elapsed = now - last
            tokens = min(self.capacity, tokens + elapsed * self.rate)
            if tokens >= n:
                tokens -= n
                self.buckets[key] = (tokens, now)
                return True
            self.buckets[key] = (tokens, now)
            return False

面试追问:

"分布式怎么做?" — 用 Redis + Lua 脚本实现原子的"扫码 + 补充 + 扣减"
"令牌桶 vs 漏桶?" — 漏桶严格恒速输出，不允许突发；令牌桶允许短时突发 (最多桶容量)，更常用
"滑动窗口计数器怎么做?" — 用 Redis Sorted Set 存时间戳，查询窗口内条目数

4. 高频追问 cheat sheet¶

追问类型	常见问题	标准思路
复杂度	"能不能优化到 \(O(n)\)?"	常见路径：哈希表 / 双指针 / 单调栈 / DP
空间	"能不能 \(O(1)\) 空间?"	原地修改 / 双指针 / 状态压缩 DP
输入规模	"\(n = 10^9\) 怎么办?"	外部排序 / 分布式 / 采样
边界	"空输入？单元素？全相同?"	主动列出 3-5 个 edge case
并发	"多线程访问怎么办?"	粗粒度锁 → 细粒度锁 → 无锁 (CAS)
稳定性	"算法稳定吗?"	排序稳定性、随机化收敛性
ML 数值	"梯度消失/爆炸怎么办?"	LayerNorm / 残差 / 梯度裁剪 / 初始化
ML 泛化	"过拟合怎么办?"	Dropout / weight decay / 数据增强 / 提前停止

5. 学员常见卡顿点 + 解套¶

卡顿点	解套
拿到题就写代码	先澄清 5 分钟，再讲思路 15 分钟，最后 15 分钟写码
沉默思考	边想边说，说"这里我在想哈希表能不能行"胜过发呆
只给一个解	给暴力解 + 优化解，展示思路演进
变量名 a/b/c	用 `seen`, `left`, `right`, `count`, `dp` 等语义化名字
不测试	主动跑 2-3 个 case (含 edge)，手工 trace
不写复杂度	每题结束必须说"时间 \(O(?)\)，空间 \(O(?)\)"
Attention 不会写	背下 QKV 拆分 + softmax + mask 四步，反复默写
AdamW 和 Adam 分不清	记住 AdamW 把 weight decay 独立减在权重上，不进 m/v
K-Means++ 不会	第一个中心均匀采样，后续按 \(d^2\) 加权采样
LRU 卡在链表操作	用哨兵头尾节点简化边界，抽出 `_remove` / `_add_to_head` 辅助函数
令牌桶不会	惰性补充：`tokens = min(cap, tokens + Δt · rate)`

6. 建议图示¶

（生产版可补充下列 SVG/PNG）

图 1: LeetCode 分组树 — 15-20 个模式的树状总览，每个模式挂几道代表题
图 2: Multi-Head Attention 结构 — Input → QKV Proj → Split Heads → Scaled Dot Attention → Concat → Output Proj 的 5 层流程图
图 3: LRU 双向链表可视化 — 哨兵头尾 + 4 个真实节点 + 哈希表映射，展示 get / put / evict 三种操作的状态转移

📌 本节要点¶

三种 coding 面：算法题 (LC 类) + 面向对象设计 (LRU / RateLimiter) + ML 手撕 (Attention / AdamW), AI/ML 岗必考后两类。
40 分钟时间盒: 5 min 澄清 + 15 min 思路 + 15 min 写码 + 5 min 测试，沉默 = 死刑，边想边说是硬要求。
15-20 个核心模式覆盖 90% 题：数组哈希 / 双指针 / 滑动窗口 / 树 / 图 / DP / 回溯 / 贪心 / 优先队列，每模式记 1-2 道代表题。
手撕 Attention 五步: QKV 投影 → 分头 → scaled dot-product (\(QK^\top / \sqrt{d_k}\)) → mask + softmax → 合并头 + 输出投影。
AdamW 记忆点：一阶矩 \(m\) + 二阶矩 \(v\) + 偏差修正 + weight decay 独立减在权重上 (不进 \(m, v\)).
K-Means++ 初始化：首个中心均匀采样，后续按 \(D(x)^2 / \sum D(x)^2\) 加权采样，显著改善 Lloyd 收敛质量。
LRU O(1) 双结构：哈希表定位 + 双向链表维序，用哨兵头尾节点简化边界处理。
令牌桶惰性补充: tokens = min(cap, tokens + Δt · rate)，请求到来时按时间差一次性补齐，无需定时线程。

参考文献¶

McDowell, G. L. (2016). Cracking the Coding Interview: 189 Programming Questions and Solutions (6th ed.). CareerCup. (刷题面试圣经，时间盒 + 沟通技巧的原始出处.)
LeetCode. https://leetcode.com/ (本节所引所有题号均可在此验证，例如 https://leetcode.com/problems/two-sum/ 对应 LC 1.)
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., & Polosukhin, I. (2017). Attention Is All You Need. NeurIPS 2017. arXiv:1706.03762. (Transformer 与 scaled dot-product attention 的原始定义，手撕 MHA 的公式来源.)
Loshchilov, I., & Hutter, F. (2019). Decoupled Weight Decay Regularization. ICLR 2019. arXiv:1711.05101. (AdamW 原论文，明确 weight decay 应从梯度中解耦.)
Arthur, D., & Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding. SODA 2007. (K-Means++ 加权采样初始化的原始工作.)
Ba, J. L., Kiros, J. R., & Hinton, G. E. (2016). Layer Normalization. arXiv:1607.06450. (LayerNorm 原论文.)
Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., & Salakhutdinov, R. (2014). Dropout: A Simple Way to Prevent Neural Networks from Overfitting. JMLR 15(1). (Dropout 原论文.)
Sennrich, R., Haddow, B., & Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. ACL 2016. arXiv:1508.07909. (BPE 用于神经翻译分词的开山之作，HuggingFace tokenizers 库参考实现同源.)
HuggingFace tokenizers 官方文档. https://huggingface.co/docs/tokenizers (BPE/WordPiece/Unigram 生产级实现参考.)
Bentley, J. L. (1975). Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9). (KD 树的原始工作.)