有限内存下对海量电话号码排序(位图)
哪些公司问过
阿里智能信息1
答案要点
- 号码去掉区号后是 8 位整数,范围有限且不重复,适合位图
- 1 亿个号码需要 1 亿位,约 12.5MB
- 读文件置位后从小到大扫描位图,顺序输出即有序
- 内存不足时按号码范围分段多遍读入,输出仍顺序写一次
- 有重复号码时改用计数数组而不是位图
易错点
- 把号码当字符串排序,内存和时间都浪费
- 位图大小算错,把 1 亿位当成 1 亿字节
- 分段处理时打乱输出顺序,或者需要多次写输出文件
面试官常见追问
- 如果号码会重复出现怎么办?
- 不用位图还有什么做法?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场