面灵AI→

拼多多服务端二面:B+ 树、哈希冲突与 MQ 幂等,手撕字符串转数字

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

《面试题目》

  1. 手撕:字符串转数字。
  2. 堆如何实现?如何做到先进先出?
  3. 如何实现一个计算器?
  4. Kafka 相比于 RabbitMQ 有什么不同?
  5. 讲一下 MySQL 的索引。为什么用 B+ 树,为什么不用平衡二叉树、红黑树或其他树结构?
  6. 讲一下哈希。哈希解决冲突的策略有哪些?拉链法和再哈希在实际使用时有什么区别与优缺点?
  7. 在做实际后端开发时,系统维稳你会考虑哪些方面?
  8. 发货时 MQ 如果消息收发出现异常,做了什么幂等处理?

《参考解析》

字符串转数字:先处理符号、去空格,逐位 num = num * 10 + (c - '0'),每一步做溢出判断(超过 Integer.MAX_VALUE / 10 或等于且末位大于 7 就返回边界值),非法字符直接报错。写完主动说边界:""、"+"、"-2147483648"、前导零、全角字符。

堆与 FIFO:堆是完全二叉树,用数组存储,父子下标关系 2i+1 / 2i+2,插入上浮、删除堆顶下沉,O(log n)。要让「相同优先级」按入队顺序出队,就在比较器里加一个自增序号做次级键,等价于稳定优先队列;或者用 (priority, seq) 元组。注意这时堆不再严格 FIFO,只是同优先级内 FIFO。

计算器:先分词(数字、运算符、括号),再用双栈(操作数栈 + 运算符栈)按优先级归约,或转后缀表达式求值(调度场算法)。要点是运算符优先级表与括号递归,边界是负数、除零、多位数。可以补一句「支持函数与变量就要上 AST 解析器」。

Kafka vs RabbitMQ:Kafka 是分布式提交日志,分区顺序写、批量与零拷贝、消费者组拉模型,吞吐极高,消息消费后不删除(按时间/大小保留),支持回溯与多消费组各自读全量;RabbitMQ 是传统消息代理,exchange 路由灵活(direct/topic/fanout/headers)、支持优先级队列与延迟消息、单条 ack 精细,但吞吐低一到两个数量级、堆积能力弱。选型看场景:日志与流式处理用 Kafka,业务解耦与复杂路由用 RabbitMQ。

索引与哈希:B+ 树已在上一题讲过;哈希冲突的解法有拉链法(同槽挂链表/红黑树,Java HashMap)、开放寻址(线性探测、二次探测、双重哈希)、再哈希(换一个哈希函数重算)。拉链法实现简单、删除方便、装载因子高时退化但可控;开放寻址缓存友好、无指针开销,但删除要墓碑标记、装载因子高时性能陡降。工程上还要说清「哈希索引为什么不支持范围查询」与「布隆过滤器用于预判不存在」。

系统维稳:容量(压测与水位线)、依赖(超时、重试、熔断、降级)、数据(备份、对账、幂等)、可观测(日志、指标、链路追踪、告警)、变更(灰度、回滚)、故障演练。回答时挑两三条讲透,比罗列十条强。

MQ 幂等:生产端用「业务唯一键 + 本地消息表 / 事务消息」保证不丢;消费端用唯一索引或 Redis SETNX 做去重,处理成功后再 ack(至少一次语义 + 幂等 = 效果上的恰好一次)。发货场景的具体做法:以订单号 + 发货批次作为幂等键,先 INSERT 幂等表(唯一索引冲突即视为已处理),再执行发货,失败则回滚幂等记录并重试,超过次数进死信队列人工介入。