有一个 1G 大小的文件，里面每一行是一个词，词大小不超过 16 字节，内存限制 1M，要求返回出现频数最高的 100 个词。

Given a 1GB file where each line is a word (each word <= 16 bytes) and memory is limited to 1MB, how do you return the top 100 most frequent words?

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: hard

分类: 大数据处理, TopK, 外部存储算法

标签: hash partition, top-k, min-heap, external merge

参考答案摘要

核心答案 由于内存仅 1MB，无法直接对 1GB 文件做全量统计，需要采用 哈希分桶 + 小文件统计 + 归并 的方式获取 Top 100。 Step 1：分桶拆分大文件 顺序读取文件，对每个词 x 计算 hash(x) % 5000 ，写入 5000 个小文件： f0, f1, ..., f4999 。每个文件约 200KB。 如果某个小文件仍超过 1MB，可继续递归分桶，直到所有小文件都不超过...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。