1亿个短单词统计每个单词出现次数
哪些公司问过
答案要点
- 词长 1 到 2 字节,可能的词不到 7 万种,可直接用计数数组
- 1 字节词下标为字节值,2 字节词下标为 256 加 16 位编码
- 总数 1 亿小于 2^32,32 位计数器足够,数组约 260KB
- 顺序读一遍 O(n),多份数据的计数数组可逐位相加合并
- 通用情况:哈希分片到小文件,分别用哈希表计数
易错点
- 忽视词长很短的条件,上来就拆文件做分治
- 1 字节词和 2 字节词编码冲突,比如都映射到同一个下标
- 计数器用 16 位导致溢出
面试官常见追问
- 如何求出现频率最高的 N 个词?
- 如果单词很长、种类很多呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。