拼多多服务端二面:B+ 树、哈希冲突与 MQ 幂等,手撕字符串转数字
- 轮次
- 二面
- 时间
- 2026-10
- 来源
- 牛客网
《面试题目》
- 手撕:字符串转数字。
- 堆如何实现?如何做到先进先出?
- 如何实现一个计算器?
- Kafka 相比于 RabbitMQ 有什么不同?
- 讲一下 MySQL 的索引。为什么用 B+ 树,为什么不用平衡二叉树、红黑树或其他树结构?
- 讲一下哈希。哈希解决冲突的策略有哪些?拉链法和再哈希在实际使用时有什么区别与优缺点?
- 在做实际后端开发时,系统维稳你会考虑哪些方面?
- 发货时 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 幂等表(唯一索引冲突即视为已处理),再执行发货,失败则回滚幂等记录并重试,超过次数进死信队列人工介入。