拼多多 服务端开发二面面经：最长公共子串与 trace ID 透传深挖

《面试题目》

手撕：最长公共子串长度

1. 基础要求：两个有序数组无重复数字，长度分别为 m 和 n，要求求出最长公共子串长度，时间空间复杂度均小于 O(MN)
2. 进阶要求：两数组中存在重复数字

滴滴实习与 trace ID 透传

3. 你在滴滴做了两件事，第一个是透传组件，先介绍一下之前的问题是什么？
4. trace ID 是什么含义？加上之后有什么好处？
5. 加完 trace ID 后，执行流程是什么样？这是异步任务、线程池场景，线程池怎么拿到 trace ID？
6. 能具体展开一下流程吗？比如第 65 行，你是怎么用的？
7. 你刚才提到的注入是怎么做的？线程执行时要把注入的 trace ID 拿出来使用，具体怎么处理？
8. 后面怎么用到 trace ID？是每次打日志时手动拿到 name，然后填充 trace ID 吗？
9. 你改的是线程名字吗？公用线程池改线程名有什么优缺点？
10. 我理解 trace ID 应该放在日志上下文或者 MDC 里，打日志时直接拿当前 trace ID，对吗？除此之外还有别的需求吗？
11. 为什么不把平台日志直接对应到 trace ID，而是去改线程名？改线程名有什么缺点？如果线程名频繁变更，会有什么问题吗？

并发自增代码题（现场贴代码，第 79 行）

12. 定义一个 global counter，定义 incr 函数，起 100 个线程并发调用，每个线程执行 100 万次，在其中某个线程直接打印结果，这个结果是多少？
13. 为什么结果可能在 100 万到 1 亿之间？
14. 这里的冲突怎么理解？什么叫冲突？为什么 counter++ 只有一行代码，并发之间还会有冲突？
15. 如果要优化这个逻辑，怎么做才能让最终结果一定是 1 亿？
16. 用 CountDownLatch 会不会冲突很多？
17. 加锁、synchronized 同步代码块，这些可以怎么做？

《参考解析》

1. 手撕题的关键词是「有序」和「子串」：有序数组上的公共子串一定是共同连续段，用双指针同步推进即可，时间 O(M+N)、空间 O(1)，远优于要求的 O(MN)。别往 DP 的二维表上写——那是 O(MN)，既超出复杂度要求，也浪费了「有序」这个条件。另外要分清子串和子序列：最长公共子序列（LCS）才是 O(MN) 的 DP，这题问的是连续的串，答错概念直接掉分。进阶版出现重复数字后，双指针策略依然成立，只需在相等时继续向后扩、不相等时推进较小的一方；重复值会让「共同段」变多，但不会改变算法结构。

2. trace ID 要讲清解决的是哪一个问题：日志里只有 thread-xxx，无法把一次请求散落在多个服务、多个线程池里的日志串起来，排查只能靠时间戳猜。方案是给一次请求分配唯一标识，全链路透传，日志统一带上。设计要点有四处：入口生成（或透传上游的 traceparent / 自定义 header，别重复生成），跨服务通过 HTTP header 和 MQ 消息属性传递，跨线程通过上下文传递，出口清理避免线程复用串号。

3. 线程池传 trace ID 的正确实现是「包装任务」，不是改线程名：ThreadLocal（MDC 底层就是它）不会自动跨线程，所以要在提交任务那一刻把上下文捕获下来——最朴素的做法是把 Runnable 包一层，在 run 开头 MDC.setContextMap(captured)、在 finally 里 clear；更省事的是用 TransmittableThreadLocal 配合 TtlExecutors 包装线程池，或者在提交点显式把 traceId 作为参数传进任务。无论哪种，finally 里的清理都不能少，否则线程池复用会把上一个请求的 traceId 带进下一个请求，出现串号——这类脏数据比没有 traceId 更难查。

4. 改线程名的缺点要能一条条说出来：线程池里的线程是共享且长期复用的，一次请求可能跨多个池、一个线程会串行处理很多请求，线程名和请求不是一一对应，并发改写必然互相覆盖；改名要改回去，异常路径漏一次就永久污染；线程名还是线程 dump、监控指标、排查平台的定位维度，混进业务信息会让这些工具失真。面试官给的判据其实已经写在问题里——traceId 属于请求作用域的数据，就该放在请求上下文（MDC）里，日志框架用 %X{traceId} 自动带出来，不需要动线程名。

5. counter++ 的结果为什么不是 1 亿：counter++ 是读、加一、写回三步，不原子。两个线程同时读到 5，各自算完都写 6，一次自增就丢了，这在面试里就叫冲突（丢失更新）。上界很明确：100 个线程 × 100 万次 = 1 亿，任何丢失更新都只会让结果更小；打印又发生在这个线程自己跑完 100 万次之后，此刻其它线程还在跑，所以看到的只是一个中间快照，量级落在 100 万到 1 亿之间，具体多少取决于打印时机和丢失更新的程度——这也是为什么这道题必须分清「值的上界」和「打印那一刻的值」。

6. 要保证 1 亿，得让自增原子或互斥：synchronized 或 ReentrantLock 给自增加互斥，正确但吞吐最差；AtomicLong 用 CAS 自旋，竞争激烈时空转严重；LongAdder 分段累加，高并发下吞吐最好，代价是求和得到的是弱一致的快照值；也可以每个线程本地累加、结束时汇总，彻底消除竞争。CountDownLatch 只是等待工具，它只保证「等所有线程结束再读」，不会让自增变原子——不加同步的话读到的仍然是丢更新后的结果，而且即便加了同步，若打印点仍在某个线程内部、没等其它线程跑完，看到的也不是 1 亿。