# 1. 手写位运算，判断 2 的幂、统计 1 的个数（Brian Kernighan）、交换两数如何实现？ A n & (n-1) 用于统计 1 的个数，循环次数为比特位数 B 判断 2 的幂需要额外临时变量 C 异或交换可以在同一变量上安全使用 D n & (n-1)==0 可判断 2 的幂，Brian Kernighan 每次去掉最低位 1、循环次数等于 1 的个数，异或交换在相同变量时出错 ✓ 正确答案
# 2. 手写一个基于 free list 的 first-fit 内存分配器，分配与释放时如何处理相邻块合并与碎片？ A 释放时无需合并相邻空闲块 B free list 无法产生外部碎片 C 边界标记只用于分配不用于释放 D first-fit 从头遍历找第一个够大的块并切分，释放时用边界标记检查邻居并合并；外部碎片靠合并缓解，边界标记使合并 O(1) ✓ 正确答案
# 3. 纸上推演 Raft 选举，给定节点数与随机超时，推演选票分裂、term 递增与旧 leader 网络恢复后的日志复制异常？ A 随机超时用于提高选票分裂概率 B 同一 term 允许多个 leader C 旧 leader 恢复后仍可继续提交日志 D 随机化超时避免选票分裂，term 递增保证唯一 leader；旧 leader 恢复后 term 落后自动降级，其未提交日志被新 leader 覆盖修正 ✓ 正确答案
# 4. 纸上推演一个多级页表的地址翻译过程（含 TLB 未命中）？ A TLB 未命中时只需一次内存访问 B 多级页表与 TLB 无关 C 多级页表节省内存，TLB 命中时一次访存，未命中时需逐级访问页表（甚至触发缺页），TLB 命中率是关键 ✓ 正确答案 D 页表翻译不需要页内偏移
# 5. 推演 TCP 三次握手与四次挥手的完整状态机（含异常场景）？ A 服务端握手时先进入 ESTABLISHED 再回 SYN+ACK B 三次握手建立连接（SYN/SYN+ACK/ACK），四次挥手关闭（FIN/ACK/FIN/ACK），TIME_WAIT 用于保证旧报文消失与 ACK 可重传，SYN 洪泛可打满半连接队列 ✓ 正确答案 C 关闭连接只需一次 FIN D TIME_WAIT 由被动关闭方进入
# 6. 手写一个无锁栈（Treiber 栈）并说明 ABA 问题与解决？ A Treiber 栈用加锁实现 push/pop B Treiber 栈用 CAS 循环实现，ABA 是值变回原样导致 CAS 误判，可用版本号/AtomicStampedReference 或 hazard pointer 解决 ✓ 正确答案 C ABA 问题通过加锁可以完美解决 D CAS 无需重试
# 7. 纸上推演 LRU 缓存，给出访问序列，手动模拟哈希表+双向链表的淘汰过程？ A LRU 淘汰最近使用的节点 B LRU 只需哈希表即可 C LRU 用哈希表 O(1) 查找 + 双向链表维护访问顺序，访问时移到头部、满时淘汰尾部，即可模拟淘汰过程 ✓ 正确答案 D LRU 不需要记录访问顺序
# 8. 手写生产者-消费者（信号量/Park-Unpark）并推演竞争时序？ A 生产者-消费者需空/满信号量控制容量，判断与操作要在临界区内原子完成，避免丢失唤醒 ✓ 正确答案 B 判断队列满/空与操作不需要在临界区内 C Park-Unpark 不会出现丢失唤醒 D 生产者消费者无需互斥
# 9. 手写快速排序与归并排序，稳定性与空间复杂度如何对比？ A 快排是稳定的 B 归并空间复杂度 O(1) C 快排平均 O(n log n)、不稳定、空间 O(log n)；归并稳定、时间固定 O(n log n)、空间 O(n) ✓ 正确答案 D 快排最坏也是 O(n log n)
# 10. 手写一个固定大小线程池，任务队列、工作线程与关闭语义如何设计？ A 关闭时无需处理队列中的任务 B 关闭语义与线程池无关 C 工作线程在队列空时自旋不等待 D 线程池由任务队列+固定工作线程组成，优雅关闭需排空队列并唤醒阻塞线程，强制关闭则中断清空 ✓ 正确答案
# 11. 纸上推演 LFU 缓存（LeetCode 460），给定访问序列，手动模拟频率计数与淘汰过程？ A LFU 淘汰最近使用的项 B LFU 不需要记录频次 C LFU 与 LRU 淘汰策略相同 D LFU 优先淘汰访问频次最低的项，频次相同时淘汰最久未用的（LRU 兜底），需跟踪每个 key 的频率 ✓ 正确答案
# 12. 手写一致性哈希并推演节点增减时的数据迁移范围？ A 节点增减时所有数据都要迁移 B 虚拟节点会增加迁移量 C 一致性哈希不需要哈希环 D 一致性哈希把节点和数据映射到哈希环，上新/删除节点只迁移受影响环段（约 1/n 数据），虚拟节点用于均衡分布 ✓ 正确答案
# 13. 纸上推演 TCP 状态机与页面置换？ A TCP 状态机跟踪连接状态转移，页面置换按 FIFO/LRU/OPT 规则淘汰页；FIFO 可能出现 Belady 异常，LRU/OPT 不会 ✓ 正确答案 B FIFO 与 LRU 的淘汰规则相同 C OPT 可以实际实现 D 页面置换与缺页率无关
# 14. 手写二分查找，边界与死循环的坑如何避开？ A mid 用 low+high 计算更安全 B 二分查找不会有死循环 C 需用 low+(high-low)/2 防溢出，且保证每次循环 low/high 至少移动一位避免死循环，边界选择要与 mid±1 配套 ✓ 正确答案 D 边界条件不影响结果
# 15. 手写 LRU 与 LFU，淘汰策略如何权衡？ A LRU 按最近访问淘汰、对局部性友好但对突发敏感；LFU 按频率淘汰、能抗突发但新热点升温慢，需频率衰减 ✓ 正确答案 B LRU 适合长期稳定热点，LFU 适合突发访问 C 两种策略完全等价 D LFU 对突发访问更敏感
# 16. 手写 SPSC 无锁环形队列，head/tail 索引与 release/acquire 语义，如何避免 cache line 假共享？ A SPSC 需要锁保护共享索引 B SPSC 单生产者单写 head/tail、单消费者单读，用 release/acquire 内存序保证数据可见性顺序，并用 padding 隔离 head/tail 避免假共享 ✓ 正确答案 C release/acquire 与数据可见性无关 D 假共享不影响性能
# 17. 手写 Top-K，基于堆与快速选择的两种实现，时间/空间复杂度与适用场景如何？ A 堆实现空间 O(n) B 堆实现 O(n log K)、空间 O(K)、适合数据流；快速选择平均 O(n)、最坏 O(n^2)、适合静态全量数据 ✓ 正确答案 C 快速选择空间 O(n) D 两种实现复杂度完全相同
# 18. 纸上推演磁盘调度，给定磁道请求序列与磁头初始位置，分别计算 FCFS、SSTF、SCAN、C-SCAN 的总寻道距离，并说明 SSTF 为何可能饥饿、C-SCAN 为何等待时间更均匀？ A FCFS 寻道距离最短 B SSTF 平均寻道短但可能饥饿；SCAN 双向扫描；C-SCAN 单向循环使等待更均匀；FCFS 按到达顺序但寻道距离大 ✓ 正确答案 C C-SCAN 比 SSTF 更容易饥饿 D SCAN 两端请求等待必定最短
# 19. 纸上推演令牌桶限流，给定速率与容量，推演突发流量下令牌消耗与补充的过程？ A 令牌桶以速率 r 补充、容量 b 封顶，突发流量下最多连续放行 b 个请求，长期平均速率不超 r ✓ 正确答案 B 令牌桶不允许任何突发 C 令牌桶容量无限 D 令牌桶补充没有任何上限
