面灵AI→

拼多多客户端一二面:颜色分类三指针、死锁四条件与图片 LRU

轮次
一二面
时间
2026-10
来源
牛客网

《面试题目》

一面·算法(LeetCode 75 颜色分类)

  1. 手撕 LeetCode 75 颜色分类。
  2. 当前指针与右侧指针交换后,为什么当前指针不能立即向后移动?
  3. 这段算法的时间复杂度和空间复杂度分别是多少?

一面·死锁与并发

  1. 两个线程以相反顺序获取两把锁,可能发生什么?为什么?
  2. 程序直接运行一定会死锁吗?去掉中间的等待后,结论会变化吗?
  3. 死锁的四个必要条件是什么?分别如何对应到这段代码?
  4. 有哪些办法可以消除或规避死锁?
  5. 多个 goroutine 并发写同一个 map 会发生什么?
  6. 写操作和查询操作分别应该怎样加锁?为什么考虑使用读写锁?

一面·网络与 HTTPS

  1. 客户端请求一个 HTTPS 接口并把数据展示到页面,中间经历了哪些步骤?
  2. HTTPS 相比 HTTP 多了什么?主要解决哪些安全问题?
  3. TLS 如何保证数据不被篡改?数字签名的验证过程是什么?

一面·客户端缓存

  1. 客户端只允许缓存固定数量的图片,如何优先保留最近使用的数据?
  2. 为什么不能只用数组实现?不同数据结构的复杂度有什么差别?

一面·项目追问

  1. 这个项目做过哪些性能或成本优化?如何证明优化有效?
  2. 当多个系统对同一业务概念的定义不一致时,你会如何统一数据口径?
  3. 统一口径上线时,如何处理存量数据、兼容旧逻辑、校验结果和回滚?

《参考解析》

颜色分类:右指针换过来的元素还没被判过 维护三个指针,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 三层核对。