Bloomberg First Unique Words：顺序、词频与内存受限取舍

题意与假设

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

• 训练版按空白切词、大小写敏感，输出在原文中的出现顺序；标点作为词的一部分。
• ‘First Unique’ 在题目同时带‘所有’，训练版解释为所有频次恰为 1 的词，而非仅第一个；应在现场澄清。

解题路线

1. 第一遍切词并计每词频次，第二遍按原顺序输出 count==1 的词。
2. Python split 会同时分配词列表与字符串对象；C++ 可以在原字符串上记录 string_view 或起止偏移，并只对不同词建频次表，注意原缓冲区生命周期。
3. 若内存极紧且允许极慢，可逐词对整段文本重新扫描计数，输出前再排除重复出现；额外空间可降到少量下标/当前词视图，时间最坏 O(n²) 或更高。
4. 如需 Unicode 词边界或不区分大小写，先选规范化/分词规则，不能直接把 byte 子串当词。

手动走一遍

训练输入 ‘a b a C c’ 的频次为 a:2，b/C/c 各 1，因此输出 [b,C,c]；如果忽略大小写则 C/c 都不唯一，答案变成 [b]。

Python 参考实现

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

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

from collections import Counter


def unique_words_in_order(text):
    """Whitespace-delimited, case-sensitive words occurring exactly once."""
    words = text.split()
    frequency = Counter(words)
    return [word for word in words if frequency[word] == 1]

复杂度

两遍哈希计数期望 O(n) 时间、O(n) 单词列表加 O(U) 频次空间；多遍极低内存策略可到 O(n²) 时间，具体还受切词表示影响。

易错点与追问

容易失分的边界

• 只返回首个 unique 而未问清‘所有’。
• 用 set 失去出现顺序。
• 声称 Python split 没有复制/对象开销。
• string_view 指向已释放缓冲区。

继续深挖

• 只允许 O(1) 额外内存怎么办？
• 输入是文件流且不能回放？
• 大小写与标点如何处理？