拼多多客户端一二面:颜色分类三指针、死锁四条件与图片 LRU
- 轮次
- 一二面
- 时间
- 2026-10
- 来源
- 牛客网
《面试题目》
一面·算法(LeetCode 75 颜色分类)
- 手撕 LeetCode 75 颜色分类。
- 当前指针与右侧指针交换后,为什么当前指针不能立即向后移动?
- 这段算法的时间复杂度和空间复杂度分别是多少?
一面·死锁与并发
- 两个线程以相反顺序获取两把锁,可能发生什么?为什么?
- 程序直接运行一定会死锁吗?去掉中间的等待后,结论会变化吗?
- 死锁的四个必要条件是什么?分别如何对应到这段代码?
- 有哪些办法可以消除或规避死锁?
- 多个 goroutine 并发写同一个 map 会发生什么?
- 写操作和查询操作分别应该怎样加锁?为什么考虑使用读写锁?
一面·网络与 HTTPS
- 客户端请求一个 HTTPS 接口并把数据展示到页面,中间经历了哪些步骤?
- HTTPS 相比 HTTP 多了什么?主要解决哪些安全问题?
- TLS 如何保证数据不被篡改?数字签名的验证过程是什么?
一面·客户端缓存
- 客户端只允许缓存固定数量的图片,如何优先保留最近使用的数据?
- 为什么不能只用数组实现?不同数据结构的复杂度有什么差别?
一面·项目追问
- 这个项目做过哪些性能或成本优化?如何证明优化有效?
- 当多个系统对同一业务概念的定义不一致时,你会如何统一数据口径?
- 统一口径上线时,如何处理存量数据、兼容旧逻辑、校验结果和回滚?
《参考解析》
颜色分类:右指针换过来的元素还没被判过 维护三个指针,left 左侧全是 0、right 右侧全是 2、cur 在中间扫描。遇到 0 与 left 交换后 cur 可以前进,因为 left 位置原本只可能是 0 或 1、换过来的一定是 1,已经归位;遇到 2 与 right 交换后 cur 必须停在原地,因为 right 位置是从未检查区换来的,值可能是 0、1 或 2,得再判一次,而 right 本身要左移一格。这个不对称是这题唯一的坑,写成对称的两支就会漏排。时间复杂度 O(n) 每个元素至多被处理两次,空间 O(1)。它本质上是荷兰国旗问题,也是快排三路划分的同一段代码。
死锁:四个条件缺一不可,工程上最常破的是循环等待 互斥、持有并等待、不可剥夺、循环等待四条同时成立才会死锁。反序加锁的代码里,互斥对应两把锁本身,持有并等待对应拿到第一把后不释放就去要第二把,不可剥夺对应锁只能由持有者释放,循环等待就是 A 等 B、B 又等 A。程序直接跑不一定会死锁——线程到达顺序是竞争性的,可能总是一前一后错开,所以是概率性故障,测试难复现、线上偶发卡死,去掉中间的 sleep 只改变概率不改变可能性。工程手段按代价排:统一全局加锁顺序或按地址排序加锁、带超时的 tryLock 让失败方回退、多锁合并成一把或改无锁结构。
HTTPS 一趟请求:DNS、TCP、TLS、HTTP 四段 先解析域名,与服务器三次握手建 TCP,再做 TLS 握手:客户端发 ClientHello 带上版本、套件与随机数,服务端回 ServerHello 与证书链,客户端验证书链与域名,再用 ECDHE 协商出共享密钥,之后应用数据用对称密钥加密。数字签名保证「来源可信且未被篡改」:服务端用私钥对握手消息摘要签名,客户端用证书里 CA 签过的公钥验签,改任何一段都对不上。非对称只用于密钥交换与身份认证,因为它慢。
固定容量图片缓存:LRU 必须是哈希表加双向链表 要 O(1) 的 get 与 put,就得同时具备「按 key 定位」和「按访问顺序移动」两种能力。哈希表负责定位节点,双向链表负责维护顺序:命中就把节点摘下挂到表头,插入超出容量就删表尾。只用数组的话,命中后把元素挪到最前是 O(n) 的搬移,列表一滚就卡;用单链表则摘除节点还得从头找前驱,同样是 O(n)。所以标准实现是哈希表存节点指针加双向链表,且节点自己带 key,淘汰表尾时才能反查哈希表删掉对应项。
统一数据口径:先定唯一源头,再谈迁移 冲突来自三处:同名不同义、同义不同名、计算口径不同(是否含退款、时区、去重键)。做法是选定一处作权威定义(指标字典或数仓 DWS 层),把口径写成可执行的 SQL,其他系统只消费、不各自加工。上线分四步:新旧并行双算并归因差异;存量按业务时间回刷并留版本号;旧逻辑用适配层兼容、灰度切读;备好回滚开关,切换后用总量、分布、TopN 三层核对。