海量 QQ 号去重与找出重复号码
哪些公司问过
答案要点
- 位图:每个号码 1 位,覆盖 2^32 范围需 512MB,范围 10 亿以内约 125MB
- 位图遍历一次置位,按位输出即得去重且有序的结果
- 找重复:两位位图记录 0 次、1 次、多次,或使用两个位图
- 不用位图:按哈希取模拆分小文件,相同号码落同一文件,逐个用哈希表统计
- 也可外部排序后顺序扫描;布隆过滤器省内存但有误判
易错点
- 用 HashSet 存 25 亿个号码,内存远超限制
- 按顺序切分文件,相同号码分散在不同文件中,导致漏判重复
- 不说明号码范围就直接给出位图内存大小
面试官常见追问
- 为什么哈希分文件后结果是正确的?
- 某个小文件还是太大放不进内存怎么办?
- 多台机器怎么做?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。