手写与纸上推演题

• 掌握 x & (x-1) 判断 2 的幂
• 掌握 Brian Kernighan 统计 1 的个数
• 掌握异或交换两数及其局限

判断 2 的幂：2 的幂只有最高位为 1，其余为 0，故 n>0 且 n & (n-1) == 0。统计 1 的个数用 Brian Kernighan：每次 n &= (n-1) 会去掉最低位的 1，循环次数即为 1 的个数，复杂度 O(位数中 1 的个数)。交换两数用异或：a ^= b; b ^= a; a ^= b，三条异或即可交换，无需临时变量。局限：异或交换要求两变量地址不同（同一变量会置零），且对同一变量交换会出错，实际生产建议用临时变量或 std::swap。

核心技巧是 x & (x-1) 能清除最低位 1，是判断 2 的幂与统计 1 个数的共同基础。异或交换利用了异或的自反性（a^b^b=a）。这些是位运算的经典基础题，需理解原理而非死记。

• 理解 free list 与 first-fit 分配策略
• 掌握边界标记（boundary tag）与相邻合并
• 理解内部碎片与外部碎片

基于 free list 的 first-fit：维护一个按地址排序的空闲块链表，分配时从头遍历找到第一个足够大的块，命中则从中切出所需大小，剩余部分作为新空闲块插入链表。释放时需合并相邻空闲块：为快速判断相邻块是否空闲，用边界标记（boundary tag）在每个块的头尾记录 size 与空闲标志，释放时检查左右邻居，若空闲则合并成一个更大的块。碎片处理：first-fit 会产生外部碎片（空闲块间散布的小空洞），可通过合并缓解；内部碎片是切块后剩余不足一个块头的部分，难以避免。first-fit 分配快、倾向保留大块在尾部，但可能累积碎片，可配合 best-fit(更少碎片但更慢)或 coalescing 定期合并。

核心是"分配时切块、释放时合并"。边界标记让合并邻居只需 O(1) 检查。first-fit 简单快速，碎片靠合并与合适策略缓解。面试重点在理解合并的机制与碎片的成因。

• 理解 Raft 的 term、选举超时与随机化
• 掌握选票分裂与 leader 选举流程
• 理解旧 leader 恢复后的日志/term 冲突处理

Raft 选举：每个节点维护 term（任期），follower 在选举超时（随机化，如 150-300ms）内未收到 leader 心跳则转 candidate，term+1 并投票给自己，向其他节点请求投票。若选票分裂（多个 candidate 同时发起、term 相同，各得部分票），本轮无多数派，超时后进入下一轮，term 再 +1 重新选举，随机超时避免长期分裂。当选出 leader 后，leader 通过心跳维持 term。旧 leader 网络恢复：旧 leader 的 term 低于新 leader，收到新 leader 心跳会立即退位为 follower；旧 leader 上未提交的日志（term 旧）在新 leader 上是"不匹配"的，会被新 leader 以强制覆盖（follower 回退到与 leader 匹配的前任日志）的方式修正，保证日志一致性。关键：term 是全局递增的，多数派选举确保同一 term 只有一个 leader。

选举核心是"随机超时打破平票 + term 防止旧 leader"。旧 leader 恢复后因 term 落后自动降级，其多余的未提交日志被新 leader 覆盖，这正是 Raft 通过"日志匹配 + 多数派"保证一致性的体现。

• 理解虚拟地址到物理地址的翻译
• 掌握多级页表的逐级索引
• 理解 TLB 命中与未命中的差异

以两级页表为例：虚拟地址分为页目录索引（PDI）、页表索引（PTI）与页内偏移（offset）。翻译时，CPU 先查 TLB（快表），若命中则直接得到物理页框号，加上 offset 得到物理地址，仅一次访问。若 TLB 未命中，则从页目录基址寄存器（CR3）开始，用 PDI 查页目录得到页表基址，用 PTI 查页表得到物理页框号，再与 offset 拼接得到物理地址；此时需访问 2 次内存（页目录+页表），若页表项不在内存还需触发缺页（page fault）从磁盘加载。多级页表的好处是节省内存（无需为不用的地址范围预分配页表），代价是翻译多几次内存访问，因此用 TLB 缓存加速。

多级页表把"大线性表"拆成多层稀疏结构省内存，TLB 缓存最常用的翻译结果。未命中时要逐级访存，比命中慢，所以 TLB 命中率是关键。缺页异常则进一步引入磁盘访问。

• 掌握三次握手与四次挥手的流程与状态
• 理解各状态如 SYN_SENT、ESTABLISHED、TIME_WAIT 等
• 分析异常场景的处理

三次握手：客户端发 SYN 进入 SYN_SENT，服务端收 SYN 回 SYN+ACK 进入 SYN_RCVD，客户端收 SYN+ACK 发 ACK 进入 ESTABLISHED，服务端收 ACK 进入 ESTABLISHED。四次挥手：主动关闭方发 FIN 进入 FIN_WAIT_1，被动方收 FIN 回 ACK 进入 CLOSE_WAIT，主动方收 ACK 进入 FIN_WAIT_2；被动方发 FIN 进入 LAST_ACK，主动方收 FIN 回 ACK 进入 TIME_WAIT（等待 2MSL 后关闭），被动方收 ACK 进入 CLOSED。异常场景：握手 SYN 丢失（重传 SYN，超时无响应）；SYN 洪泛（服务端 SYN_RCVD 半连接队列被打满，可用 SYN Cookie 缓解）；半关闭（一半连接只发 FIN 一半，TCP 支持 shutdown 单向关闭）；四次挥手时被动方 ACK 丢失会触发重传 FIN。TIME_WAIT 用于保证旧报文消失与 ACK 可重传。

状态机是时序图，重点记忆各状态与转移条件。异常场景考察对可靠性机制（重传、超时、半连接队列、TIME_WAIT）的理解。TIME_WAIT 的 2MSL 是保证可靠关闭的关键。

• 理解无锁栈的 CAS 操作
• 掌握 ABA 问题的成因
• 理解用版本号/标记位解决 ABA

Treiber 栈用 CAS 实现 push/pop：链表中 head 指向栈顶。push 时读 head 为新节点 next，CAS(head, old, new) 成功则入栈，失败（head 被并发修改）则重读重试。pop 时读 head 与 head->next，CAS(head, head, next) 成功则出栈。ABA 问题：线程 A 读到 head=X，准备 CAS 时，线程 B pop 掉 X 又 push 回 X（值相同但对象可能已被复用），A 的 CAS 误判没变而成功，导致逻辑错误。解决：用带版本号的原子指针（AtomicStampedReference 或 ABA 计数器），每次 CAS 同时比较值+版本号，或用 hazard pointer 延迟回收节点，避免节点被复用。

无锁栈核心是 CAS 循环，ABA 是"值相同但中间被改过"的时序问题。解决思路是"给 CAS 加版本号"或"延迟回收/避免复用"，让中间的变化可被察觉。

• 理解 LRU 的淘汰策略
• 掌握哈希表+双向链表的实现结构
• 能手动模拟访问序列的插入与淘汰

LRU 用哈希表存 key 与节点映射，双向链表表示访问顺序（头部最近使用、尾部最久未使用）。访问时：若 key 在哈希表，把节点移到链表头部（删除原位置并插入头部）；若不在，若缓存未满则插入头部，若已满则淘汰链表尾部节点（最久未使用）并从哈希表删除。以容量 3、序列 1,2,3,4,1,2,5 为例：1,2,3 依次插入头部（链表 3-2-1）；访问 4 时满，淘汰尾部 1，插入 4（链表 4-3-2）；访问 1 不存在，满，淘汰尾部 2，插入 1（链表 1-4-3）；访问 2 不存在，满，淘汰尾部 3，插入 2（链表 2-1-4）；访问 5 不存在，满，淘汰尾部 4，插入 5（链表 5-2-1）。最终缓存为 5,2,1。

核心是"每次访问把节点提到头部，淘汰时删尾部"。哈希表保证 O(1) 查找，双向链表保证 O(1) 移动与删除。手动模拟时跟踪链表顺序即可。

• 理解生产者-消费者模型
• 掌握信号量/条件变量/Park-Unpark 实现
• 能推演竞争与唤醒时序

用信号量实现：空位信号量 empty（初始为容量）、满位信号量 full（初始 0），生产者先 empty.P() 再入队、full.V()；消费者先 full.P() 再出队、empty.V()。用 Park-Unpark：生产者/消费者在队列满/空时阻塞（park），另一方唤醒（unpark）。推演时序：生产者 A 入队后如果此前队列已满，消费者 B 阻塞，A 入队后应 unpark B；消费者 B 出队后若队列此前为空，生产者 A 阻塞，B 出队后应 unpark A。关键点：检查"是否满/空"与"入队/出队"必须在同一临界区内，避免竞态——即先判断是否阻塞，再操作，再唤醒，全程用锁保护。若判断与操作分离，可能出现"生产者看到满而阻塞，却被消费者同时唤醒丢失"的丢失唤醒问题。

生产者-消费者核心是"容量控制 + 互斥 + 唤醒"。难点在丢失唤醒：阻塞判断与操作必须原子，Park/Unpark 需在锁内先判断再 park，避免唤醒丢失。用信号量则天然有计数语义。

• 掌握快排与归并的算法实现
• 理解稳定性的概念
• 掌握时间与空间复杂度

快速排序：选基准（pivot），把小于基准的放左边、大于的放右边，递归左右子数组。平均 O(n log n)、最坏 O(n^2)（如已有序），空间 O(log n)（递归栈），不稳定（交换可能改变相等元素相对顺序）。归并排序：把数组分成两半，递归排序后合并，合并时比较两半头部，稳定，时间固定 O(n log n)，空间 O(n)（需辅助数组）。稳定性指相等元素排序后相对顺序不变。快排不稳定通常因为交换时可能把相等元素跨过；归并按顺序比较合并，相等元素保持相对顺序，故稳定。

快排"原地分区、递归"，平均快但最坏 O(n^2)、不稳定；归并"分治合并"，稳定但需 O(n) 空间。选择依据：要求稳定用归并，追求平均性能与原地用快排。

• 理解线程池的组件结构
• 掌握任务队列与工作线程的实现
• 理解优雅关闭语义

固定大小线程池：核心是任务队列（阻塞队列）+ 固定数量的工作线程。初始化时创建 N 个工作线程，每个线程循环从队列取任务执行；提交任务时放入队列，若队列满则阻塞或拒绝（取决于策略）。工作线程用条件变量/信号量在队列空时等待，在提交时唤醒。关闭语义：优雅关闭（shutdown）不再接受新任务，但等已在队列的任务执行完，通过让工作线程在队列空且 shutdown 后退出；强制关闭（shutdownNow）则中断并清空队列。设计要点：用 volatile/Atomic 标记 shutdown 状态，停止时唤醒所有等待线程并让其检查状态退出，避免线程泄漏。

线程池 = 任务队列 + 工作线程池 + 生命周期管理。关键在关闭语义：优雅关闭要"排空队列再退出"，且需唤醒阻塞的线程避免卡死。生产实践对应 ThreadPoolExecutor 的 shutdown/shutdownNow。

• 理解 LFU 的淘汰策略（按访问频率）
• 掌握频率计数与同频淘汰（LRU 兜底）
• 能手动模拟访问序列

LFU 淘汰访问频率最低的项，频率相同时淘汰最久未使用的（LRU 兜底，LeetCode 460 要求）。数据结构：每个 key 记录访问频次 freq，用"频次 → 双向链表"的嵌套结构，访问时频次加 1 并移动到对应频次链表头部；淘汰时找最小频次链表的尾部。以容量 3、序列 1,2,3,2,1,4 为例：1,2,3 各频次 1（链表 3-2-1）；访问 2 频次 2；访问 1 频次 2；访问 4 时，最小频次为 1 的项是 3（链表剩 3），淘汰 3，插入 4 频次 1。最终缓存 4(f1),2(f2),1(f2)。核心：优先淘汰频次最小者，频次相同淘汰最久未用。

LFU 与 LRU 区别：LRU 看"最近"，LFU 看"频率"。LFU 用频次分组 + 组内 LRU 保证同频时淘汰最久未用。手动模拟要跟踪每个 key 的频次与组内顺序。

• 理解一致性哈希的哈希环
• 掌握虚拟节点的作用
• 推演节点增减的迁移范围

一致性哈希把哈希值空间映射成一个环，节点与数据 key 都哈希到环上，数据沿顺时针找最近的节点存储。新增或删除节点时，只有受影响的一小段数据需要迁移：删除节点时，该节点负责的环段数据迁移到下一个节点；新增节点时，其哈希位置到前一个节点之间的数据从原节点迁移到新节点。典型实现用 TreeMap（有序哈希环）存节点，查找 key 的顺时针后继节点。为均衡分布，每个真实节点映射多个虚拟节点（对 node#i 哈希），避免节点分布不均。迁移范围：设 n 个节点，删除/新增一个节点只迁移约 1/n 的数据（理想情况），远小于普通哈希的重新哈希全部数据。

一致性哈希的核心价值是"最小化迁移"。普通取模哈希在节点增减时几乎全部数据需迁移，一致性哈希只迁移受影响环段。虚拟节点解决"节点少时分布不均"与"负载倾斜"。

• 掌握 TCP 状态机各状态与转移
• 掌握 FIFO/LRU/OPT 页面置换
• 理解缺页率与 Belady 异常

TCP 状态机：连接建立时，客户端从 CLOSED 发 SYN 进入 SYN_SENT，收到 SYN+ACK 后进入 ESTABLISHED；服务端从 LISTEN 收 SYN 进入 SYN_RCVD，收 ACK 后进入 ESTABLISHED。连接关闭时，主动方从 ESTABLISHED 发 FIN 进入 FIN_WAIT_1，收 ACK 进入 FIN_WAIT_2，收 FIN 回 ACK 进入 TIME_WAIT（2MSL 后到 CLOSED）；被动方收 FIN 进入 CLOSE_WAIT，发 FIN 进入 LAST_ACK，收 ACK 后到 CLOSED。关键状态包括 LISTEN、SYN_RCVD、ESTABLISHED、FIN_WAIT_1/2、CLOSE_WAIT、LAST_ACK、TIME_WAIT、CLOSED。页面置换：给定页框数 3 与访问序列，FIFO 按进入顺序淘汰（最早进入的先淘汰），LRU 按最近使用淘汰（最久未用淘汰），OPT 淘汰未来最久不再使用的页（无法实现，仅作理论最优）。LRU 缺页率通常低于 FIFO；FIFO 可能出现 Belady 异常（增加页框数反而缺页率升高），LRU 与 OPT 无此异常。推演时逐页判断是否缺页、淘汰哪一页。

两种"状态机/置换"推演都是"逐事件更新状态"。TCP 状态机跟踪连接状态转移；页面置换跟踪页框中页的进入/淘汰顺序。区别在于淘汰规则（FIFO 按时间、LRU 按最近使用、OPT 按未来）。

• 掌握二分查找的边界处理
• 理解左闭右闭/左闭右开写法
• 识别死循环与越界陷阱

二分查找：在有序数组 low=0、high=n-1（左闭右闭），while(low<=high)，mid=low+(high-low)/2，若 a[mid]==target 返回；若 a[mid]<target 则 low=mid+1，否则 high=mid-1。常见坑：一是死循环——若用 while(low<high) 且查不到时更新为 low=mid 或 high=mid，可能永远不收敛（如 low=mid 且 mid 不变），需确保每次更新能缩小范围；二是溢出——用 low+(high-low)/2 避免 low+high 溢出；三是边界——low<=high 与 low<high 的选择对应不同的退出条件，需与 mid+1/mid-1 配套；四是查找第一个/最后一个目标时边界需特殊处理。一旦 mid 更新未改变 low/high 就可能死循环。

二分查找的坑集中在"边界是否收敛"。必须保证每次循环 low/high 至少移动一位，否则死循环。用 <= 配合 mid±1 是经典安全写法，注意 mid 计算防溢出。

• 掌握 LRU 与 LFU 的实现
• 理解两种策略的适用场景
• 分析各自的优缺点

LRU 按"最近访问时间"淘汰，实现为哈希表+双向链表，适合访问模式局部性好（近期访问的很可能再次访问）的场景，如缓存热数据。LFU 按"访问频率"淘汰，实现为频次桶+链表，适合"高频稳定访问"的场景，能保留长期热点。权衡：LRU 对突发访问敏感（偶发大量访问会挤掉热点），且可能因"扫一遍"（sequence scan）污染缓存；LFU 能抵抗突发，但对"新热点升温慢"（新数据频率低，需时间累积频次），且历史频率高的数据即使不再活跃也难被淘汰，需频率衰减/时间窗。选择：访问模式局部性明显用 LRU，长期热点稳定用 LFU，实际可结合（如 LFU-LRU 混合）。

权衡本质是"预测未来访问"。LRU 假设"最近用过的还会用"，LFU 假设"用得多的还会用"。LRU 简单、对突发敏感，LFU 稳定但升温慢、需衰减。根据业务访问模式选择。

• 理解 SPSC 环形队列的单读单写特性
• 掌握内存序（release/acquire）与索引语义
• 理解 cache line 假共享与 padding

SPSC 环形队列：生产者只写 tail 索引、消费者只读 tail，消费者只写 head、生产者只读 head，因此无竞争、无需锁。实现：数组容量为 2 的幂，生产者写 data[tail & mask] 后 release 更新 tail（用 atomic 的 release 保证写数据先于更新 tail 可见）；消费者 acquire 读 tail，若 head != tail 则有数据，读 data[head & mask] 后 acquire 更新 head。内存序：生产者的数据写入用 release 发布，消费者的读取用 acquire 获取，保证"先写数据后更新 tail"的顺序，避免消费者读到未初始化数据。假共享：head 与 tail 若在同一 cache line，生产/消费各自更新会让另一侧缓存失效，应把 head 与 tail 分别放入独立 cache line（用 alignas(64) 或 padding 分隔），避免互相污染。

SPSC 无锁的关键是"单写单读索引 + 释放/获取内存序"。索引更新用 release 发布数据、acquire 获取数据，保证可见性顺序。假共享用 padding 把 head/tail 隔离到不同 cache line，提升性能。

• 掌握堆实现 Top-K
• 掌握快速选择实现 Top-K
• 比较复杂度与适用场景

基于堆：维护大小为 K 的最小堆（求最大 K 个）或最大堆（求最小 K 个），遍历元素，若堆未满则入堆，若堆满且新元素比堆顶更优则替换堆顶并调整。时间复杂度 O(n log K)，空间 O(K)，适合数据流/大规模数据（只需 O(K) 内存，可在线处理）。基于快速选择：利用快速排序的 partition，每次确定一个元素的位置，若位置等于 K-1 则左边 K 个即答案，否则只在包含第 K 个的区间递归。平均 O(n)、最坏 O(n^2)，空间 O(log n)（递归栈），适合一次性全量数据、需要全部 Top-K 且数据可载入内存、追求最优平均时间。选择：数据流/内存受限用堆，静态大数组且追求平均性能用快速选择。

堆"渐进 log K、在线、省内存"，快速选择"平均 O(n)、但需全量数据且最坏退化"。堆适合流式与内存受限，快速选择适合静态数据求平均最优。实际 Top-K 常结合两者（如先用堆）或根据数据规模。

• 掌握 FCFS、SSTF、SCAN、C-SCAN 算法
• 能计算总寻道距离
• 理解饥饿与等待均匀性

假设磁头初始位置 50，请求序列 82,170,43,140,24,16,190。FCFS 按到达顺序：|50-82|+|82-170|+|170-43|+|43-140|+|140-24|+|24-16|+|16-190|=32+88+127+97+116+8+174=642。SSTF 每次找最近的：50→43(7)→24(19)→16(8)→82(66)→140(58)→170(30)→190(20)，总 7+19+8+66+58+30+20=208。SCAN（电梯）：假设向大方向移动，50→82→140→170→190→(到 199 后反向)→43→24→16，距离=|190-50|+|199-190|+|199-16|... 需按具体方向计算。C-SCAN 单向循环：50→82→140→170→190→到最右端→回最左端→16→24→43。SSTF 可能导致饥饿：因为总是选择最近的，远处的请求可能长期得不到服务（不断被新近请求插队）。C-SCAN 等待更均匀：单向扫描，磁头到达一端后回最左端再继续，所有请求获得大致均匀的服务时间，避免两端请求长时间等待。

FCFS 简单但寻道距离大；SSTF 平均寻道短但可能饥饿；SCAN（电梯）双向扫描、较公平；C-SCAN 单向循环、等待更均匀。计算时按算法逐步模拟磁头移动并累加差值。

• 理解令牌桶限流模型
• 掌握令牌的补充与消耗逻辑
• 推演突发流量下允许的令牌数

令牌桶：以速率 r 持续补充令牌，桶容量为 b（最大积攒令牌数）。请求到达时，若桶中有令牌则消耗一个令牌放行，否则拒绝或排队。推演：设 r=1 令牌/秒、b=5，初始桶满 5。突发流量：若一段时间没人请求，桶积攒到 5 个，随后瞬间来 6 个请求，前 5 个用桶中令牌放行，第 6 个因桶空被拒绝（或等待补充）。补充：桶以速率 r 补充，但不会超过容量 b，多余令牌丢弃。令牌桶允许"突发"（最多 b 个瞬间通过），同时长期平均速率不超 r。与漏桶（固定速率出水、不容忍突发）对比：令牌桶允许突发、适合突发的 Web 流量；漏桶平滑、固定速率。

令牌桶核心是"容量决定瞬时突发上限，速率决定长期平均速率"。推演时看增加一个请求时桶中令牌是否足够，以及令牌随时间按 r 补充、封顶 b。突发流量下最多连续放行 b 个。