Bloomberg 下一词预测：Bigram 频次、并列与整句补全

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版‘最可能’=相邻词出现频率最高；并列按训练语料首次出现先后，题目未明确概率平滑或 tie-break。
• 句子边界不能跨越训练为 bigram；查询无后继返回 None，整句补全设最大 token 数防循环。

解题路线

1. 逐句遍历相邻 pair，维护 followerCount[前词][后词]；同时记录 pair 首次出现序号以稳定并列。
2. query 查 followerCount[word] 最大频次；高 QPS 可训练后预先缓存每个词的最佳后继，读 O(1)。
3. 对整句补全从起始词迭代取下词，遇无后继或达到上限结束；若要识别自然句末需显式 EOS token。
4. 回答 O(N) 空间追问：准确保存任意语料的后继频次，最坏有 O(N) 个不同 pair，无法无条件压成 O(1)；可近似 sketch、截断低频或外部存储换准确性。

手动走一遍

训练两句 I→am→sam、am→sam：I 的唯一后继 am；am→sam 计 2，query am 得 sam。若语料中 A→B 与 A→C 同频，训练版取首次出现的后继。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import Counter, defaultdict


class NextWord:
    def __init__(self, sentences):
        self.followers = defaultdict(Counter)
        self.first_seen = {}
        order = 0
        for tokens in sentences:
            for word, following in zip(tokens, tokens[1:]):
                self.followers[word][following] += 1
                self.first_seen.setdefault((word, following), order)
                order += 1

    def next_word(self, word):
        choices = self.followers.get(word)
        if not choices:
            return None
        return min(
            choices,
            key=lambda following: (-choices[following], self.first_seen[(word, following)]),
        )

    def complete(self, first, max_tokens=20):
        output = [first]
        for _ in range(max_tokens - 1):
            following = self.next_word(output[-1])
            if following is None:
                break
            output.append(following)
        return output

复杂度

N 个训练 token、E 个不同 bigram：训练 O(N)，存储 O(E+词数)，查询扫描后继种类 O(deg(word))；预计算 top1 可降单次查询 O(1)。

易错点与追问

容易失分的边界

• 跨句尾和下一句首生成不存在的 bigram。
• 把一次出现就当真正概率模型。
• 并列结果不稳定。
• 整句补全在词循环中无限生成。

继续深挖

• 能否少于 O(N) 空间仍准确？
• 如何回答 Query 的 top K 下一个词？
• EOS 与未知词如何处理？
• 若训练数据流不断更新怎么办？