海量数据中找出现频次最高的 TopK
哪些公司问过
答案要点
- 按哈希取模把数据分到多个小文件,保证相同元素落在同一文件且单个文件能装入内存
- 对每个小文件用哈希表统计频次,得到局部计数
- 维护大小为 K 的小顶堆合并各文件结果,复杂度约 O(N log K)
- IP 转为 32 位整数存储;数据倾斜时对过大的文件换哈希函数再拆分
- 允许近似时可用 Count-Min Sketch 加堆单遍处理,分布式场景可用 MapReduce
易错点
- 直接把整个大文件读进内存建哈希表,忽略内存限制
- 按文件顺序随机切块而不是按哈希分桶,导致同一元素分散在多个文件,局部 TopK 合并出错
- 用大顶堆保存全部元素,内存和时间都不划算
面试官常见追问
- 为什么用小顶堆而不是大顶堆?
- 如果某个小文件还是放不下怎么办?
- 如果只有 K 比较大或要求精确排序呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。