题目重点：从计数基线讲到大语料外部聚合，避免未定义词边界与同频顺序导致答案不稳定。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练代码按 Unicode `\w+` 提取连续 word run，以 casefold 合并大小写；同频按词字典序升序；返回 (word,count) 列表。原题这些细节未公开。
- K≥0，空文本返回空；标点、连字符、中文词边界需要按真实语言和产品定义调整，不能将训练 tokenizer 当唯一正确解析。
解题路线
- 先确认 word 规则、归一化、停用词、标点与 tie-break。单机基线扫描文本建 hash 频次，再按 (-count,word) 排序取前 K，简单且稳定。
- 若词表 V 远大于 K，可用大小 K 的最小堆降低排序项成本到 O(V log K)，但同频字典序需要仔细反向比较；小题不必为省常数制造错误。
- 输入超出内存时按块流式分词，保留跨块词尾，分片 map 计数再 reduce 合并；若只需近似热点，可用 SpaceSaving/Count-Min Sketch，但必须说明误差与无法精确解决并列。
- 用于搜索产品时要明确是否按文档计数还是整个字符串词频；本文是单文本总词频，不能混成 TF-IDF。
手动走一遍
`Apple apple banana` 在训练契约下 apple=2、banana=1，K=1 返回 apple；`a b` 同频时先返回 a。文本为空或 K=0 返回空。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
import re
from collections import Counter
def top_k_words(text: str, k: int) -> list[tuple[str, int]]:
if k < 0:
raise ValueError("negative k")
# Training tokenizer: Unicode word runs, case-folded.
counts = Counter(word.casefold() for word in re.findall(r"\w+", text))
return sorted(counts.items(), key=lambda pair: (-pair[1], pair[0]))[:k]
复杂度
文本长度 N、不同词 V：扫描与 hash 计数期望 O(N)，排序 O(V log V)，频次表 O(V)；堆可 O(N+V log K) 时间和 O(V+K) 空间。10,000 组随机文本与独立词频参考模型一致。
易错点与追问
容易失分的边界
- 未问词边界，直接 `split(' ')` 漏标点/换行。
- 大小写是否合并不说明。
- 同频结果依赖 hash 遍历顺序。
- 分块时把跨块单词切成两个。
- 把单文本词频等同跨文档 TF-IDF。
继续深挖
- 多语言和中文分词怎么处理？
- 1 TB 文本如何精确计算？
- 只要近似 Top K 时误差如何报告？
- 停用词/词形还原应在计数前还是后？
