CS-Notes全部笔记在阅读器中打开

学习路线 - 面试冲刺

本文目录

一、说明

适合两三周内就要面试、已经学过这些内容的读者，每天 1.5～2 小时，覆盖约 40 个核心考点，最后 1 天是大模型应用。应聘大模型应用岗位的读者，用大模型应用开发每天的自测题复习。

每天先不看笔记，把 3 个自测题各口述 1～2 分钟，再展开参考要点核对，答得不完整的读链接的小节；然后做两道算法题，每题限时 30 分钟，按面试的顺序作答：先用一两句说出暴力解和它的复杂度，再说瓶颈在哪、怎样优化，最后写出优化后的代码。

应聘前端、C++、客户端或测试开发岗位时，可以跳过第 1～4 天和第 12 天的 Spring 部分（Android 和以 Java 为主的测试开发保留第 1、4 天），把时间用在这些岗位更常问的小节：

二、每天的安排

天 主题 阅读 算法
Java
1 集合 HashMap、ConcurrentHashMap、与 ArrayList 的比较 1. 两数之和、56. 合并区间
2 线程池、锁与 volatile ThreadPoolExecutor、synchronized 与 ReentrantLock 的比较、内存模型三大特性、volatile 88. 合并两个有序数组、15. 三数之和
3 CAS、锁升级与 ThreadLocal 非阻塞同步、锁升级的过程、线程本地存储（Thread Local Storage） 3. 无重复字符的最长子串、206. 反转链表
4 JVM 运行时数据区域、判断一个对象是否可被回收、垃圾收集算法、CMS 收集器、G1 收集器、内存溢出与内存泄漏 21. 合并两个有序链表、141. 环形链表
MySQL
5 索引 B+ Tree 原理、MySQL 索引、索引优化、索引失效 92. 反转链表 II、146. LRU 缓存
6 事务、MVCC 与锁 并发一致性问题、隔离级别、多版本并发控制、封锁类型、Next-Key Locks 20. 有效的括号、33. 搜索旋转排序数组
7 SQL 优化、日志与分库分表 查询性能优化、MySQL 的日志、分库分表 215. 数组中的第 K 个最大元素、912. 排序数组（手写快速排序）
Redis 与缓存
8 Redis Redis 的数据类型、Redis 的数据结构、Redis 持久化、单线程为什么快 102. 二叉树的层序遍历、103. 二叉树的锯齿形层序遍历
9 缓存问题与 Redis 集群 缓存问题、Sentinel、Redis 分片 236. 二叉树的最近公共祖先、200. 岛屿数量
网络与操作系统
10 TCP 与 HTTPS UDP 和 TCP 的特点、TCP 的三次握手、TCP 的四次挥手、TCP 可靠传输、HTTPS 46. 全排列、121. 买卖股票的最佳时机
11 进程、死锁与 I/O 多路复用 进程与线程的区别、协程、必要条件、死锁预防、I/O 复用 53. 最大子数组和、5. 最长回文子串
框架、分布式与大模型
12 Spring 与设计模式 AOP、Bean 的生命周期、循环依赖、事务失效、设计模式前言、实现 300. 最长递增子序列、1143. 最长公共子序列
13 分布式锁、消息队列与秒杀 分布式锁、消息队列的可靠性、秒杀系统、限流、降级与熔断 42. 接雨水、25. K 个一组翻转链表
14 大模型应用 RAG 的流程、Agent 是什么、工具调用、MCP 23. 合并 K 个升序链表、72. 编辑距离

三、Java

第 1 天：集合

必学：HashMap、ConcurrentHashMap、与 ArrayList 的比较。

自测：

  1. HashMap 的 put() 过程是怎样的？什么时候扩容、什么时候转成红黑树？（见put 操作、扩容-基本原理、链表转红黑树）
  2. ConcurrentHashMap 怎样保证线程安全？JDK 1.7 和 1.8 有什么区别？（见JDK 1.8 的改动）
  3. ArrayList 和 LinkedList 有什么区别？（见与 ArrayList 的比较）
参考要点
  1. JDK 1.8：table 为空先 resize()，用 (n - 1) & hash 定位桶，空桶直接放入；否则头节点是 TreeNode 就在红黑树中查找或插入，是链表就逐个比较，键相同就替换旧值，找不到就接在链表尾部；插入后 size 大于 threshold（容量 × 0.75，默认 12）时扩容为 2 倍；接上前链表已有 8 个节点时，数组长度小于 64 只扩容，否则转成红黑树。
  2. JDK 1.7 用分段锁，Segment 继承 ReentrantLock，默认 16 个，并发度创建后不能改变；JDK 1.8 去掉 Segment，空桶用 CAS 放入，非空时 synchronized 锁住桶的头节点，锁粒度到桶，多个线程可以一起迁移扩容；get 不加锁，靠 volatile 读到最新值。
  3. ArrayList 基于动态数组，随机访问快，中间插入删除要移动元素，但一次复制一整块连续内存；LinkedList 基于双向链表，插入删除只改指针，但要先 O(N) 遍历到位置；实测 10 万个元素中间插入 1 万次，ArrayList 约 50 ms、LinkedList 约 0.8～1 秒，多数场景用 ArrayList。

算法（哈希表，简单）：1. 两数之和，题解见数组中两个数的和为给定值。

算法（数组，中等）：56. 合并区间，题解见合并区间。

明天：第 2 天，线程池、锁与 volatile（ThreadPoolExecutor、synchronized 与 ReentrantLock 的比较、内存模型三大特性、volatile）。

第 2 天：线程池、锁与 volatile

必学：ThreadPoolExecutor、synchronized 与 ReentrantLock 的比较、内存模型三大特性、volatile。

自测：

  1. 线程池的核心参数有哪些？提交任务后是怎样执行的？（见ThreadPoolExecutor）
  2. synchronized 和 ReentrantLock 有什么区别？（见synchronized 与 ReentrantLock 的比较）
  3. volatile 能保证什么，不能保证什么？（见volatile）
参考要点
  1. 参数有核心线程数、最大线程数、空闲线程的存活时间、任务队列、线程工厂和拒绝策略；提交时线程数小于核心数就新建线程，否则放入队列，队列满且小于最大线程数时新建线程执行当前任务，再不行就执行拒绝策略；例如核心 2、最大 4、队列 2 时第 7 个任务被拒绝；不用 Executors 的 newFixedThreadPool()、newSingleThreadExecutor()、newCachedThreadPool()，它们的队列或线程数没有上限，要直接创建 ThreadPoolExecutor 并使用有界队列。
  2. synchronized 由 JVM 实现（代码块编译为 monitorenter、monitorexit，方法用 ACC_SYNCHRONIZED 标志，异常时也会释放锁），ReentrantLock 由 JDK 基于 AQS 实现；新版本中在平台线程上两者性能大致相同，但 JDK 21 的虚拟线程在 synchronized 内阻塞会固定载体线程，这时要用 ReentrantLock；ReentrantLock 等待可中断、可以设为公平锁、能绑定多个 Condition，synchronized 都不能。
  3. 保证可见性：写入后其它线程读取时立即可见；保证有序性：volatile 写之前、volatile 读之后的读写不会被重排序越过它，可用来发布数据（如双重校验锁单例）；不保证 count++ 这类复合操作的原子性，要用锁或原子类。

算法（双指针，简单）：88. 合并两个有序数组，题解见归并两个有序数组。

算法（双指针，中等）：15. 三数之和，题解见三数之和。

明天：第 3 天，CAS、锁升级与 ThreadLocal（非阻塞同步、锁升级的过程、线程本地存储（Thread Local Storage））。

第 3 天：CAS、锁升级与 ThreadLocal

必学：非阻塞同步、锁升级的过程、线程本地存储（Thread Local Storage）。

自测：

  1. CAS 的原理是什么？ABA 问题怎么解决？（见CAS、ABA）
  2. synchronized 的锁升级过程是怎样的？（见锁升级的过程）
  3. ThreadLocal 为什么可能导致内存泄漏？（见线程本地存储（Thread Local Storage））
参考要点
  1. CAS 有内存地址 V、预期旧值 A、新值 B 三个操作数，只有 V 等于 A 时才写入 B，由处理器指令保证原子性（x86 上是带 lock 前缀的 cmpxchg）；ABA 指值从 A 变成 B 又变回 A，CAS 误以为没变，对无锁栈这类结构有害；用 AtomicStampedReference 给引用加版本号，每次修改加 1。
  2. 无锁（Mark Word 末尾 01）；轻量级锁（00）：线程用 CAS 把 Mark Word 换成指向栈中 Lock Record 的指针，重入只多放一个 Lock Record；重量级锁（10）：其它线程 CAS 失败时膨胀为 ObjectMonitor，先自适应自旋，仍抢不到再阻塞；JDK 15 起默认禁用偏向锁，空闲的 ObjectMonitor 会被回收，对象恢复为无锁。
  3. ThreadLocalMap 的 Entry 对 key（ThreadLocal）是弱引用、对 value 是强引用；ThreadLocal 没有其它强引用时 key 被回收变为 null，value 仍被线程的 Map 引用，之后这个线程的 get()、set() 在查找途中遇到它，或者新增条目、remove() 删除已有条目时才可能顺带清理，线程池中的线程一直存活又没有触发清理时，value 就一直留着；用完在 finally 中调用 remove()，也能避免线程复用时读到上一个请求的值。

算法（滑动窗口，中等）：3. 无重复字符的最长子串，题解见无重复字符的最长子串。

算法（链表，简单）：206. 反转链表，题解见链表反转。

明天：第 4 天，JVM（运行时数据区域、判断一个对象是否可被回收、垃圾收集算法、CMS 收集器、G1 收集器、内存溢出与内存泄漏）。

第 4 天：JVM

必学：运行时数据区域、判断一个对象是否可被回收、垃圾收集算法、CMS 收集器、G1 收集器、内存溢出与内存泄漏。

自测：

  1. JVM 的内存区域有哪些？（见运行时数据区域）
  2. CMS 和 G1 有什么区别？（见G1 收集器）
  3. 线上出现 OOM 怎样排查？（见内存溢出与内存泄漏）
参考要点
  1. 线程私有：程序计数器、Java 虚拟机栈（每个方法一个栈帧，-Xss 设置大小）、本地方法栈；线程共享：堆（几乎所有对象，分新生代和老年代，-Xms、-Xmx 设置）和方法区（类的元信息和运行时常量池，JDK 8 起由本地内存中的元空间实现；字符串常量池和静态变量 JDK 7 起已移到堆中，JIT 编译的代码在单独的代码缓存中）；NIO 还会使用堆外的直接内存；除程序计数器外都可能 OOM，两种栈还可能 StackOverflowError。
  2. 范围：CMS 只回收老年代，要配合 ParNew，G1 把堆分成等大的 Region，混合回收时新生代和老年代一起回收；碎片：CMS 用标记 - 清除，碎片多时只能 Full GC 整理，G1 把存活对象复制到空闲 Region，普通对象不产生碎片（Humongous 对象要连续 Region，仍可能因找不到连续空间提前触发 GC）；停顿：G1 按停顿目标（默认 200 ms）优先回收价值最大的 Region，更可预测，代价是额外内存，吞吐量通常略低于 Parallel；JDK 9 起服务器级机器默认使用 G1，JDK 14 移除了 CMS。
  3. 先看错误信息判断是哪块内存不足（Java heap space、Metaspace、direct buffer memory、unable to create native thread），Metaspace 查动态生成的类和不能卸载的类加载器，unable to create native thread 查线程数和系统限制，增大堆没有用；Java heap space 时用 -XX:+HeapDumpOnOutOfMemoryError 自动保存堆转储或用 jcmd 导出，再用 MAT 按 Retained Heap 找占用最多的对象及其到 GC Roots 的引用链；不该存活就是泄漏（静态集合、ThreadLocal 未 remove、资源未关闭），改代码，否则增大堆或减少一次加载的数据；慢泄漏可以定期用 GC.class_histogram 比较实例数。

算法（链表，简单）：21. 合并两个有序链表，题解见归并两个有序的链表。

算法（链表，简单）：141. 环形链表，题解见判断链表是否存在环。

明天：第 5 天，索引（B+ Tree 原理、MySQL 索引、索引优化、索引失效）。

四、MySQL

第 5 天：索引

必学：B+ Tree 原理、MySQL 索引、索引优化、索引失效。

自测：

  1. MySQL 为什么用 B+ 树做索引？（见B+ Tree 原理）
  2. 什么是聚簇索引、回表和覆盖索引？（见B+Tree 索引、覆盖索引）
  3. 联合索引的最左前缀是什么？哪些情况下索引会失效？（见多列索引、索引失效）
参考要点
  1. B+ 树的一个节点就是一个 16 KB 的页，有几百上千个子节点，树很矮（200 万行的主键索引 3 层，二叉树约 21 层），一次 I/O 读一个节点，读盘次数少；内部节点只存 key 和指针，比 B 树每页放的 key 更多，每次查找都走到叶子、I/O 次数稳定；叶子按顺序用指针相连，范围查询顺序扫描即可。
  2. 聚簇索引：InnoDB 主键索引的叶子节点保存整行数据，一张表只有一个；二级索引的叶子保存索引列和主键值，查其它列时先拿到主键，再到聚簇索引查出整行，这就是回表；覆盖索引指索引中已包含查询需要的全部列（含主键），不需要回表，Extra 为 Using index。
  3. 联合索引先按第一列排序、再按第二列，所以条件要从最左列开始连续使用才能定位，与 WHERE 中的书写顺序无关，范围条件之后的列一般不能再缩小扫描范围（带等号时例外）；常见的无法用索引定位的情况：缺少最左列（8.0.13 起少数情况可跳跃扫描）、对索引列用函数（可建函数索引）、字符串列与数字比较、LIKE 以 % 开头、OR 一侧没有索引；匹配的行太多时，优化器按成本选择全表扫描。

算法（链表，中等）：92. 反转链表 II。

算法（设计，中等）：146. LRU 缓存，题解见LRU。

明天：第 6 天，事务、MVCC 与锁（并发一致性问题、隔离级别、多版本并发控制、封锁类型、Next-Key Locks）。

第 6 天：事务、MVCC 与锁

必学：并发一致性问题、隔离级别、多版本并发控制、封锁类型、Next-Key Locks。

自测：

  1. 四种隔离级别分别解决了脏读、不可重复读、幻读中的哪些？（见隔离级别）
  2. MVCC 的原理是什么？（见ReadView）
  3. InnoDB 在可重复读级别下怎样避免幻读？（见Next-Key Locks）
参考要点
  1. 未提交读：三种都可能发生；提交读：解决脏读；可重复读：再解决不可重复读，按 SQL 标准仍可能幻读，InnoDB 用 MVCC 和 Next-Key Locks 在很大程度上避免；可串行化：三种都解决，并发度最低。
  2. 修改时旧版本写入 Undo Log，经回滚指针连成版本链；ReadView 记录创建时未提交的事务列表、其中最小的 TRX_ID_MIN 和下一个要分配的 TRX_ID_MAX；版本的 TRX_ID 是自己的或小于 MIN 时可见，大于等于 MAX 或仍在列表中时不可见，就沿版本链找上一个版本；提交读每次快照读都新建 ReadView，可重复读在第一次快照读时创建、整个事务复用。
  3. 快照读（普通 SELECT）用 MVCC，复用的 ReadView 看不到其它事务新插入的行；当前读（FOR UPDATE、UPDATE、DELETE）加 Next-Key Lock，即记录锁加前面的间隙锁，其它事务无法往间隙中插入；非唯一索引的等值查询还要锁到下一条记录之间的间隙，唯一索引等值命中已有记录时只锁这一条；同一个事务中快照读和当前读混用时仍可能出现幻读。

算法（栈和队列，简单）：20. 有效的括号，题解见用栈实现括号匹配。

算法（二分查找，中等）：33. 搜索旋转排序数组。

明天：第 7 天，SQL 优化、日志与分库分表（查询性能优化、MySQL 的日志、分库分表）。

第 7 天：SQL 优化、日志与分库分表

必学：查询性能优化、MySQL 的日志、分库分表。

自测：

  1. 线上出现慢 SQL，怎样排查和优化？（见慢查询的定位与优化）
  2. redo log、undo log 和 binlog 有什么区别？为什么需要两阶段提交？（见MySQL 的日志、两阶段提交）
  3. 分库分表之后会遇到哪些问题？（见Sharding 存在的问题）
参考要点
  1. 找：开启慢查询日志（long_query_time 线上常调到 1 秒左右，更小的值只短时间使用），对比 Rows_examined 与 Rows_sent，用 mysqldumpslow 或 sys.statement_analysis 按语句归类；析：用 Explain、EXPLAIN ANALYZE 看是否索引失效、回表过多、filesort、连接列无索引，Lock_time 大时查锁冲突和长事务；改：例如建覆盖索引后从 237 ms 降到 20 ms，再核对执行计划并评估对写入的影响。
  2. undo log 由 InnoDB 写，记录旧版本，用于回滚和 MVCC；redo log 由 InnoDB 写，记录对数据页的修改，循环写，用于崩溃恢复；binlog 由 Server 层写，记录行修改或语句，追加写，用于主从复制和按时间点恢复；两阶段提交先写 redo log 进入 prepare，再写 binlog，最后 commit，崩溃后 prepare 的事务在 binlog 中有 Xid 就提交、否则回滚，保证主库数据与 binlog 一致，从库才不会不一致。
  3. 跨分片的事务要用分布式事务，跨库连接拆成单表查询后在应用中合并，或用广播表、相同的分片规则避免跨库，自增主键要改用雪花算法等分布式 ID；不带分片键的查询要查所有分片，可用基因法、映射表或按另一维度再存一份；跨分片排序分页时每个分片都要返回前 N 页的数据，改用游标分页；扩容时用双写或订阅 binlog 迁移数据。

算法（排序与堆，中等）：215. 数组中的第 K 个最大元素，题解见Kth Element。

算法（排序与堆，中等）：912. 排序数组（手写快速排序），题解见快速排序。

综合题：订单表有 2000 万行，按用户查询最近的订单很慢，同时下单高峰期还出现了死锁：分别怎样分析和解决？（见使用 Explain 进行分析、索引优化、MySQL 死锁）

答题思路
  1. 定位慢查询：用慢查询日志或 sys.statement_analysis 找到语句，Explain、EXPLAIN ANALYZE 看 type、key、rows 和 Extra，例如出现 ALL、Using filesort，Rows_examined 远大于 Rows_sent。
  2. 建索引：按“等值条件列在前、排序列在后、范围列最后”建联合索引，例如 (user_id, create_time)，WHERE user_id = ? ORDER BY create_time DESC LIMIT 10 直接倒序扫描索引，不再 filesort；查询的列少时做成覆盖索引，深分页改用游标；改完再看执行计划和耗时。
  3. 定位死锁：SHOW ENGINE INNODB STATUS 的 LATEST DETECTED DEADLOCK（或开启 innodb_print_all_deadlocks）看两个事务各自持有和等待的锁，未形成死锁的等待查 performance_schema.data_locks。
  4. 常见原因：多个事务按不同顺序更新同一组行，或可重复读下“先 SELECT ... FOR UPDATE 再 INSERT”在同一个间隙上加间隙锁后插入意向锁冲突。
  5. 解决：按相同顺序加锁，去掉先查后插、直接 INSERT 依靠唯一索引判重，缩短事务，给更新条件列建索引；被回滚的事务由应用重试。

明天：第 8 天，Redis（Redis 的数据类型、Redis 的数据结构、Redis 持久化、单线程为什么快）。

五、Redis 与缓存

第 8 天：Redis

必学：Redis 的数据类型、Redis 的数据结构、Redis 持久化、单线程为什么快。

自测：

  1. Redis 有哪些数据类型？ZSET 的底层为什么用跳表？（见Redis 的数据类型、跳跃表）
  2. RDB 和 AOF 有什么区别？（见Redis 持久化）
  3. Redis 为什么快？（见单线程为什么快）
参考要点
  1. STRING、LIST、SET、HASH、ZSET 五种，另有 BITMAP、HyperLogLog、GEO、Stream；ZSET 成员多时用跳表，在有序链表上加多层索引，以 1/4 的概率升层，查找和插入删除期望 O(logN)；相比平衡树，插入删除只改前驱指针、不需要旋转，范围查询沿底层链表遍历，实现简单；数据都在内存中，不需要 B+ 树那样减少磁盘 I/O。
  2. RDB 把某个时间点的全部数据写成二进制快照，BGSAVE fork 子进程写入，文件紧凑、恢复快，但丢失最后一次快照之后的数据（可能几分钟）；AOF 追加写命令，everysec 约丢 1 秒，文件更大，需要定期重写；混合持久化让重写的基础文件用 RDB 格式；两者都开启时用 AOF 恢复。
  3. 数据在内存中，一次 GET 只查一次哈希表；单线程执行命令，不加锁、没有线程切换；I/O 多路复用让一个线程处理大量连接，数据少时用 listpack 等紧凑编码；执行命令本身很少成为瓶颈，CPU 时间大部分花在网络读写的系统调用上，实测每条命令的用户态时间约 1 微秒，流水线减少系统调用后吞吐量约为原来的 10 倍。

算法（二叉树，中等）：102. 二叉树的层序遍历，题解见剑指 Offer 32.2。

算法（二叉树，中等）：103. 二叉树的锯齿形层序遍历，题解见剑指 Offer 32.3。

明天：第 9 天，缓存问题与 Redis 集群（缓存问题、Sentinel、Redis 分片）。

第 9 天：缓存问题与 Redis 集群

必学：缓存问题、Sentinel、Redis 分片。

自测：

  1. 缓存穿透、击穿和雪崩有什么区别？分别怎样解决？（见缓存问题）
  2. 怎样保证缓存与数据库的一致性？（见缓存一致性）
  3. 哨兵和 Redis Cluster 分别解决什么问题？（见Sentinel、Redis Cluster）
参考要点
  1. 穿透查的是缓存和数据库都没有的数据，用短过期的空值缓存、布隆过滤器拦截；击穿是一个热点键过期，用互斥锁只让一个请求查库重建，或逻辑过期先返回旧值、后台重建；雪崩是大量键同时过期或缓存宕机，用随机过期时间、主从故障转移、预热、本地缓存、限流和熔断。
  2. 常用 Cache Aside：读未命中时查库并写回缓存，写时先更新数据库、事务提交后再删除缓存；删除而不更新是防止并发写乱序，先更新库是防止删缓存后读请求写回旧值；删除失败或慢读请求写回旧值时仍会不一致，补救有过期时间兜底、延迟双删、经消息队列重试删除、订阅 binlog 删除；只能最终一致，余额、库存扣减直接读写数据库。
  3. 哨兵在主从复制的基础上自动故障转移：认为主节点下线的哨兵数达到 quorum 后确认客观下线，再选出得票过半且不少于 quorum 的领头哨兵，按优先级和复制偏移量选新主并切换，但只有一个主节点写入，容量受单机内存限制；Redis Cluster 把 16384 个槽分到多个主节点，每个主节点有从节点，同时解决容量和高可用；两者都是异步复制，切换时可能丢失少量写入。

算法（二叉树，中等）：236. 二叉树的最近公共祖先，题解见二叉树的最近公共祖先。

算法（回溯与搜索，中等）：200. 岛屿数量，题解见矩阵中的连通分量数目。

明天：第 10 天，TCP 与 HTTPS（UDP 和 TCP 的特点、TCP 的三次握手、TCP 的四次挥手、TCP 可靠传输、HTTPS）。

六、网络与操作系统

第 10 天：TCP 与 HTTPS

必学：UDP 和 TCP 的特点、TCP 的三次握手、TCP 的四次挥手、TCP 可靠传输、HTTPS。

自测：

  1. 三次握手和四次挥手的过程是怎样的？为什么 TIME_WAIT 要等 2MSL？（见TCP 的三次握手、TCP 的四次挥手、TIME_WAIT）
  2. TCP 和 UDP 有什么区别？TCP 怎样保证可靠传输？（见UDP 和 TCP 的特点、TCP 可靠传输）
  3. HTTPS 的握手过程是怎样的？（见TLS 握手）
参考要点
  1. 握手：A 发 SYN（序号 x），B 回 SYN + ACK（确认号 x + 1、序号 y），A 回 ACK（确认号 y + 1），双方进入 ESTABLISHED，三次是为了让双方的初始序号都得到确认，并防止滞留的旧请求建立连接；挥手：A 发 FIN，B 确认后进入 CLOSE_WAIT 发完数据再发 FIN，A 确认后进入 TIME_WAIT；等 2MSL 一是确保最后的 ACK 能到达（丢失时 B 会重传 FIN），二是让本连接的旧报文从网络中消失。
  2. UDP 无连接、尽最大努力交付、面向报文、没有拥塞控制、首部 8 字节，延迟低，支持一对多；TCP 面向连接、可靠交付、面向字节流、有流量控制和拥塞控制，只能点对点；TCP 靠检验和、序号和累积确认（去重、排序）、超时重传和快重传（3 个重复确认，配合 SACK 只重传缺失的段），以及滑动窗口、流量控制、拥塞控制保证可靠。
  3. TLS 握手要协商算法、验证证书、协商会话密钥；TLS 1.2 的 ECDHE 握手中，双方在 Hello 中交换随机数并选定密码套件，服务器发出证书和用证书私钥签名的 ECDHE 公钥，客户端验证后发出自己的 ECDHE 公钥；双方算出预主密钥，与两个随机数一起派生会话密钥，最后用 Finished 校验握手报文，共 2 个 RTT；TLS 1.3 在 ClientHello 中直接带公钥，只需 1 个 RTT，ECDHE 每次握手生成新私钥，前向安全。

算法（回溯与搜索，中等）：46. 全排列，题解见排列。

算法（动态规划，简单）：121. 买卖股票的最佳时机，题解见买卖股票最大的收益。

明天：第 11 天，进程、死锁与 I/O 多路复用（进程与线程的区别、协程、必要条件、死锁预防、I/O 复用）。

第 11 天：进程、死锁与 I/O 多路复用

必学：进程与线程的区别、协程、必要条件、死锁预防、I/O 复用。

自测：

  1. 进程、线程和协程有什么区别？（见进程与线程的区别、协程）
  2. 死锁的必要条件是什么？怎样避免？（见必要条件、死锁预防）
  3. select、poll 和 epoll 有什么区别？（见select、poll 与 epoll 的比较、epoll）
参考要点
  1. 进程是资源分配的基本单位，线程是调度的基本单位，线程共享进程的资源，创建和切换开销小，能直接读写共享数据，进程间要用 IPC；进程互相隔离，而一个线程访问非法内存触发段错误时，整个进程都会被终止；协程是在用户态由运行时调度的轻量级线程，切换不陷入内核、内存占用小，大量协程映射到少量线程上，适合 I/O 密集任务，同一线程上的协程不能并行。
  2. 四个条件：互斥、占有和等待、不可抢占、环路等待，同时成立才会死锁；预防就是破坏其中一个，例如一次申请全部资源、申请不到就释放已占有的资源或给锁设过期时间；最常用的是给资源编号、按顺序申请来破坏环路等待，例如转账总是先锁 id 小的账户。
  3. select 只能监听编号小于 1024 的描述符，且会修改传入的集合；poll 用 pollfd 数组，没有这个限制，但两者每次调用都把整个集合复制进内核逐个检查，开销与描述符总数成正比，返回后还要遍历；epoll 用 epoll_ctl 注册一次，就绪时由回调放入就绪链表，epoll_wait 只返回就绪事件，监听 1 万个描述符、只有 1 个就绪时，poll 每次约 1.6 ms、epoll_wait 约 0.21 µs；epoll 只能在 Linux 上使用。

算法（动态规划，中等）：53. 最大子数组和，题解见子数组最大的和。

算法（动态规划，中等）：5. 最长回文子串，题解见最长回文子串。

明天：第 12 天，Spring 与设计模式（AOP、Bean 的生命周期、循环依赖、事务失效、设计模式前言、实现）。

七、框架、分布式与大模型

第 12 天：Spring 与设计模式

必学：AOP、Bean 的生命周期、循环依赖、事务失效、设计模式前言、单例。

自测：

  1. AOP 的原理是什么？JDK 动态代理和 CGLIB 有什么区别？（见动态代理）
  2. Spring 怎样解决循环依赖？（见循环依赖）
  3. 单例模式有哪几种写法？项目中还用过哪些设计模式？（见单例的实现、项目中的用法）
参考要点
  1. AOP 把日志、事务等横切逻辑从业务代码中抽离，Spring 基于动态代理实现，容器中保存代理对象，调用时先执行切面逻辑再调用原对象；JDK 动态代理要求目标实现接口，代理类继承 Proxy 并实现同样的接口，经 InvocationHandler 反射调用目标；CGLIB 在运行时生成目标的子类并重写方法，final 类和 final、static、private 方法无法代理；Spring Boot 默认用 CGLIB。
  2. 针对字段或 Setter 注入的单例 Bean，用三级缓存提前暴露未初始化完的对象：一级存初始化完成的 Bean，二级存提前暴露的 Bean，三级存生成提前引用的工厂；A 实例化后放入工厂，注入 B 时 B 从工厂拿到 A 的提前引用，A 需要 AOP 代理时工厂提前创建代理，使 B 拿到的就是最终对象；构造器注入和原型 Bean 无法解决，Spring Boot 2.6 起默认禁止循环依赖。
  3. 单例：线程不安全的懒汉式、饿汉式、方法加锁的懒汉式、双重校验锁（变量要加 volatile）、静态内部类、枚举（可防反射和反序列化）；项目中常见：下单校验用责任链，运费和支付渠道用策略加简单工厂，物流回调用模板方法，支付成功后的通知用观察者，事务和分布式锁用代理（Spring AOP）。

算法（动态规划，中等）：300. 最长递增子序列，题解见最长递增子序列。

算法（动态规划，中等）：1143. 最长公共子序列，题解见最长公共子序列。

明天：第 13 天，分布式锁、消息队列与秒杀（分布式锁、消息队列的可靠性、秒杀系统、限流、降级与熔断）。

第 13 天：分布式锁、消息队列与秒杀

必学：分布式锁、消息队列的可靠性、秒杀系统、限流、降级与熔断。

自测：

  1. 用 Redis 怎样实现分布式锁？有哪些问题？（见Redis 的 SET NX 指令）
  2. 怎样保证消息不丢失、不重复消费？（见消息队列的可靠性、接收端的可靠性）
  3. 秒杀系统怎样防止超卖？（见防止超卖的几种做法）
参考要点
  1. 用 SET lock_key unique_value NX PX 30000 一条命令加锁并设置过期时间；释放时用 Lua 脚本比较 value 是自己的才删除，避免误删别人的锁；业务超时锁会提前释放，需要续期，Redisson 的看门狗每 10 秒把过期时间重置为 30 秒，并用哈希计数支持可重入；主从是异步复制，切换时锁可能丢失；这种情况和续期失败都会让两个客户端同时持锁，正确性要求高时用栅栏令牌或数据库的唯一约束、条件更新兜底。
  2. 不丢：发送端收到确认才算成功（如 Kafka acks=all 加重试），可用与业务同事务的本地消息表；存储端持久化加多副本，消费端处理完再提交偏移量或 ack；不重复：处理完才确认意味着可能重复投递，消费要幂等，用订单号加事件类型这类业务键写去重表并与业务同事务，或用状态做条件更新；消息队列的恰好一次代替不了业务幂等。
  3. 超卖源于判断库存和扣减库存不是原子操作；数据库中可用悲观锁 SELECT ... FOR UPDATE、乐观锁版本号或条件更新 UPDATE ... SET stock = stock - 1 WHERE stock > 0；实测 1000 个用户抢 100 件，先查再扣多卖了 34～62 件，悲观锁和条件更新都恰好卖出 100 件；乐观锁不会超卖，但冲突多时会少卖，150 个用户抢、重试 3 次也只卖出 48～57 件；条件更新不需要重试、最常用；秒杀时先用 Redis 的 Lua 脚本挡住大部分请求，数据库的条件更新作为最后一道防线。

算法（双指针，困难）：42. 接雨水，题解见接雨水。

算法（链表，困难）：25. K 个一组翻转链表，题解见K 个一组翻转链表。

综合题：设计一个秒杀系统：从页面、网关、服务、缓存、消息队列到数据库，每一层分别做什么来扛住流量、防止超卖？出现故障时怎样降级？（见秒杀系统、限流、降级与熔断、消息队列的可靠性；开放题的展开顺序见系统设计题的思路）

答题思路
  1. 页面与网关：详情页静态化后放在 CDN，开售前按钮置灰、下单地址到点才下发，提交后禁止重复点击；网关按用户、IP、接口限流，拦截刷单，被限流的请求返回 429。
  2. 服务与缓存：秒杀服务独立部署；开售前把库存加载到 Redis，用 Lua 脚本原子地判断一人一单、判断库存、扣减并记录用户，没有库存直接返回已抢完。
  3. 消息队列：扣减成功的请求写入消息队列异步下单，订单服务按自己的能力消费；发送明确失败时回补 Redis，超时的消息可能已经送达，交给对账判断；消费处理完再确认，扣减数据库库存和插入订单放在同一个事务中，靠订单表（用户 ID，商品 ID）唯一索引保证幂等，重复的消息插入失败时整个事务回滚。
  4. 数据库：UPDATE goods SET stock = stock - 1 WHERE id = ? AND stock > 0 兜底防超卖；Redis 库存只是闸门，以数据库为准，活动后对账，未支付的订单超时取消并回补库存。
  5. 降级：依赖持续失败时熔断并返回默认结果（如详情页显示“有货”），大促时关闭评论、积分等非核心功能，积分通知延后写入消息队列，核心功能无法降级时快速失败提示稍后再试；限流用的 Redis 不可用时退回单机限流。

明天：第 14 天，大模型应用（RAG 的流程、Agent 是什么、工具调用、MCP）。

第 14 天：大模型应用

必学：RAG 的流程、Agent 是什么、工具调用、MCP。

自测：

  1. RAG 的流程是怎样的？（见RAG 的流程）
  2. Agent 由哪些部分组成？Function Calling 的原理是什么？（见Agent 是什么、工具调用）
  3. MCP 和 Function Calling 有什么区别？（见MCP）
参考要点
  1. 离线：解析文档、切片，用 Embedding 模型转为向量存入向量数据库，同时建立关键词索引；在线：改写问题，向量和关键词两路召回，合并后重排，把最相关的几段和问题放进提示词，生成带引用的回答；每一环都影响最终效果，解析错了或资料没被召回，后面无法弥补。
  2. 组成：模型决定下一步，工具、记忆、规划提供能力，控制循环执行工具并限制步数、校验参数和权限；Function Calling：请求附上工具的名称、用途和参数 JSON Schema，推理服务拼进提示词，模型需要时生成特定格式的文本，服务解析为 tool_calls 返回；应用校验后执行，以 tool 消息和 tool_call_id 发回结果，本质仍是生成文本，必须先校验。
  3. Function Calling 是模型侧的能力，模型根据工具描述给出函数名和参数；MCP 是应用与外部工具、数据之间的协议，统一工具的发现（tools/list）和调用（tools/call），工具实现一次服务端就能被所有支持 MCP 的应用使用；两者配合：主机把 MCP 工具转成工具定义交给模型，再通过 MCP 执行模型给出的调用。

算法（链表，困难）：23. 合并 K 个升序链表，题解见合并 K 个有序链表。

算法（动态规划，困难）：72. 编辑距离，题解见编辑距离。

在阅读器中可以用目录和搜索、切换深色模式、练习这篇笔记中的面试题：打开《学习路线 - 面试冲刺》