1.1 现场一：词频统计与字典功力

1.1 现场一：词频统计与字典功力

本节摘要：面试官给一段英文文本，要求统计词频并取出前 k 个高频词。这道题是热身现场的第一道门槛：Counter 一行就能写对，但追问链会一路压到堆、排序稳定性与边遍历边改的经典崩溃。本节还原完整的白板现场，并给出可复算的代码与输出。

承接本章开篇的热身线，这是候选人落笔的第一道题。它看起来只考字典，实际上考的是"你在最熟悉的领地里，代码习惯是否干净"。

面试官提问

面试官在共享屏幕上贴出一段话，题目只有两句：

"统计这段文本里每个单词出现的次数；然后告诉我出现频率最高的前三个词。文本可能有大小写和标点，你需要自己处理。"

注意两个细节：面试官没有说"用 Counter"，也没有说数据量。这两处留白就是追问的伏笔——你选择什么工具、按什么规模假设，都会成为下一层追问的入口。

现场推演

候选人先口述思路："先把文本统一小写、去掉标点、按空白切分；然后用字典累加计数；最后按计数排序取前三。"面试官点头，他开始落笔。

第一版用了标准库的 Counter，这是对的起点——面试不惩罚你熟悉标准库，惩罚的是你只会标准库。

from collections import Counter
import re

text = ("The quick brown fox jumps over the lazy dog. "
        "The dog barks, and the fox runs away. The dog sleeps.")

words = re.findall(r"[a-z]+", text.lower())   # 转小写后只留字母串，天然去掉标点
counter = Counter(words)
top3 = counter.most_common(3)
print(counter["the"])      # 单词 the 的出现次数
print(top3)
​

输出（逐位可复算）：

4
[('the', 4), ('dog', 3), ('fox', 2)]
​

核对一下："the" 出现在第 1、3、4 句，共 4 次；"dog" 出现 3 次；"fox" 与 "quick"、"over" 等都是 2 次或 1 次——"fox" 是 2 次（第 1 句和第 3 句），其余候选如 "jumps" 只有 1 次，所以前三名成立。

追问链

第一问：不用 Counter 呢？ 候选人擦掉一行，改手工累加。这一版展示的是字典的基础功力，也是后面所有计数类代码的地基。

freq = {}
for w in words:
    if w in freq:
        freq[w] += 1      # 已存在则累加
    else:
        freq[w] = 1       # 首次出现
print(freq["the"], freq["dog"], freq["fox"])
​

4 3 2
​

更地道的写法是 freq[w] = freq.get(w, 0) + 1，一行替代四行分支。候选人补了这句，面试官在笔记本上画了个勾——细节分。

第二问：如果词汇表有几十万个词，你只要前三个，还排序吗？ 这是最关键的一层。全排序是 O(n log n)（n 为词种数），而只需要前 k 个时，用小顶堆可以把复杂度压到 O(n log k)。候选人先答"排序也够快"，被追问"k 等于一时呢"，随即反应过来：k 很小时堆的优势明显。

import heapq

# heapq.nsmallest 内部维护规模为 k 的堆，等价取"计数最小的前 k 个"再反转
top3_by_heap = heapq.nsmallest(3, freq.items(), key=lambda kv: -kv[1])
print(top3_by_heap)
​

[('the', 4), ('dog', 3), ('fox', 2)]
​

这里用负计数配合 nsmallest，绕开了"堆取最大"的手感问题。面试官追问"为什么不用 nlargest"，候选人答："效果等价，nlargest 内部对负号取反，语义上 nsmallest 配负计数更直白；两者复杂度同阶。"这种"两个都行但我选这个，理由是语义"的回答，正是面试官想听的。

第三问：两个词计数相同，谁排前面？ 这问的是排序稳定性。Python 的排序是稳定排序，Counter.most_common 在计数相同时按首次插入顺序输出。候选人现场验证：

pairs = [("b", 2), ("a", 2), ("c", 1)]
print(sorted(pairs, key=lambda kv: -kv[1]))   # 稳定排序：b 仍在 a 前
​

[('b', 2), ('a', 2), ('c', 1)]
​

第四问：数据是流式来的，内存放不下全量呢？ 候选人把场景接住："计数本身不需要全量——字典增量更新天然流式安全；要 top-k 就用固定规模的堆在线维护，新词计数超过堆顶才进堆。"他顺手把字典的两种惯用法并排写了一遍：

from collections import defaultdict
import heapq

freq = defaultdict(int)              # 缺失的键自动补零，省掉存在性分支
for w in ['a', 'b', 'a']:
    freq[w] += 1
print(dict(freq))

cnt = defaultdict(int)
for w in ['x', 'y', 'x', 'z', 'x', 'y']:
    cnt[w] += 1
print('流式 top-2:', heapq.nsmallest(2, cnt.items(), key=lambda kv: -kv[1]))
​

{'a': 2, 'b': 1}
流式 top-2: [('x', 3), ('y', 2)]
​

defaultdict 把"在不在"的分支吃进了类型里，与 get 写法等价，选哪个纯属口味；有信息量的是后半段——流式 top-k 的内存从词种数压到 k，规模假设变了，数据结构跟着换，这正是本节开头那句"留白是追问伏笔"的收尾。

失误复盘

这一场最常见的翻车点有三个。其一是边遍历字典边修改：有人会在 for w in freq 的循环里做 del freq[w]，运行时直接抛 RuntimeError，正确做法是先收集待删键再统一删，或遍历副本。其二是正则处理想当然：直接 text.split(" ") 会把 "dog." 当成一个词，统计结果悄悄出错——不报错的 bug 比报错的更危险。其三是抢答：面试官话音未落就开写，漏掉"处理大小写与标点"这个明确要求，写完才补，印象分已经掉了。

复盘那位主线候选人：他第一版干净利落，第二层追问先是答了全排序，靠面试官提示才改口到堆。面试官的事后评语是"基础扎实，优化的第一反应偏慢"。这说明热身环节的分数，一半在追问链上。

举一反三

词频统计是 NLP 的最小完整闭环：清洗 → 切分 → 计数 → 取要点。第 5 章的现场十三会把这套流程接到中文分词与词向量上，届时追问会升级为"切分本身怎么做"。而在数据工程面试里，同一道题会换皮成"实时流里怎么维护 top-k"，答案是计数最小堆加哈希，结构本章已经练过。

关键直觉：面试官问"只要前 k 个"时，几乎一定在提示你放弃全排序——听懂题目里的规模暗示，比背十个 API 值钱。