美团后端开发岗面经（03）

《面试题目》

1. 频繁插入删除正整数并查询第 k 大值，应该选择什么数据结构？
2. 四个连接请求需要拼接且要求高并发时，应该如何设计？
3. 如何实现大整数相乘，数字很长时还能采用哪些方法？
4. 熔断和降级有什么区别？
5. 秒杀平台通常会遇到哪些问题，应该如何解决？
6. 网站扫码登录如何实现，后端如何主动通知前端？
7. 消息队列堆积时如何处理，怎样提升消费者消费能力？
8. Redis Big Key 如何治理？
9. 分布式 ID 除了雪花算法还有哪些实现方式？
10. 分布式锁除了 Redis 还能如何实现？
11. 两个 10GB 文件只有 1GB 内存时，如何找出相似 URL？
12. 如何设计一个短链接服务并处理低频数据淘汰？

《参考解析》

1. 需要同时支持动态顺序统计时，可用平衡树、树状数组或线段树。值域已知且有限时线段树能用计数维护第 k 大，值域离散化后空间更可控。
2. 可用事件循环或线程池接收连接，把分片放入按请求 ID 聚合的状态机；状态更新要原子化，并设置超时清理不完整请求，避免连接长期占用内存。
3. 普通长度可用竖式乘法，超长输入可采用分块乘法、Karatsuba 或 FFT。实现时要明确进位、符号和输出前导零处理。
4. 熔断是在依赖持续失败时暂时阻断调用，保护调用方；降级是在功能不可用或资源不足时提供简化结果。两者可以同时使用，但触发条件和用户提示应可观测。
5. 秒杀要处理超卖、重复下单、热点缓存、流量突增和异步一致性。库存扣减需原子校验，订单写入需幂等，热点数据可预热并通过队列削峰。
6. 扫码登录可让二维码绑定短期随机票据，手机确认后服务端改变票据状态；前端通过短轮询、SSE 或 WebSocket 获取结果。票据必须过期且只能消费一次。
7. 先确认堆积来自生产过快、消费变慢还是下游阻塞，再通过扩容分区、增加消费者、批量处理或修复慢依赖缓解。盲目加线程会放大数据库和锁竞争。
8. 大 Key 应先按访问和内存指标定位，再拆分集合、分页读取或按业务维度分片。删除超大集合要采用渐进式删除，避免阻塞 Redis 主线程。
9. 可按号段批量分配、数据库自增、UUID、时间排序 ID 或中心化发号器实现。选择时要权衡趋势递增、位数、时钟回拨、可用性和跨机唯一性。
10. 可使用数据库行锁、ZooKeeper/etcd 临时节点或基于共识的租约。无论哪种实现，都要有持有者校验、超时释放和故障恢复策略。
11. 先对 URL 做分片哈希或外部排序，按桶落盘后逐桶比较；也可用 Bloom Filter 先过滤明显不相交的数据，再对候选集合做精确比对。
12. 短链服务需要唯一键、缓存、跳转统计和过期策略。低频数据可用 LRU 或 TTL 淘汰，但淘汰不能破坏仍有效的数据库记录。