题目重点：根据题目的 prefix+dictionary 题、OOD 拆分与热门词追问，给出可复用 Trie 和频次排序训练实现。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版 dictionary 构造时去重，匹配为区分大小写的前缀匹配；输出默认字典序，热门优先时按被选次数降序、词典序打破并列。
- 题目只建议 node counter，未定义“常用”来源；本文把显式 select(word) 次数作为训练口径，不冒称原题要求。
解题路线
- 构造 Autocomplete 时一次插入所有单词，Trie 节点保存子字符映射和是否为完整词；查询只沿 prefix 走到节点，不重建整个字典。
- 从该节点 DFS 收集所有终止词；一个前缀本身若在字典中，必须包含。最后按稳定规则排序。
- 热门追问有两种路线：小规模匹配后按计数排序，简单且频次更新 O(1)；高 QPS 且只取 Top K 时可在 Trie 节点缓存候选，但每次频次变化要更新沿词路径的缓存。
- 封装边界：Trie 负责插入和前缀定位，查询服务负责排名、计数口径和 API；数据加载阶段与请求路径分离。
手动走一遍
字典 [app,apple,ape,bat]，prefix ap 得 [ape,app,apple]；select(apple) 两次后热门排序变为 [apple,ape,app]。prefix xyz 返回空列表，空前缀返回全部词。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Build a dictionary Trie once; query matches and optional selection-frequency rank."""
class TrieNode:
def __init__(self):
self.children: dict[str, TrieNode] = {}
self.terminal = False
class Autocomplete:
def __init__(self, words: list[str]):
self.root = TrieNode()
self.frequency: dict[str, int] = {}
for word in set(words):
self.frequency[word] = 0
node = self.root
for char in word:
node = node.children.setdefault(char, TrieNode())
node.terminal = True
def select(self, word: str) -> None:
if word not in self.frequency:
raise KeyError(word)
self.frequency[word] += 1
def matches(self, prefix: str, rank_by_frequency: bool = False) -> list[str]:
node = self.root
for char in prefix:
if char not in node.children:
return []
node = node.children[char]
result: list[str] = []
stack = [(node, prefix)]
while stack:
current, word = stack.pop()
if current.terminal:
result.append(word)
for char, child in current.children.items():
stack.append((child, word + char))
if rank_by_frequency:
return sorted(result, key=lambda word: (-self.frequency[word], word))
return sorted(result)
复杂度
总词字符数 M 的建树时间与空间 O(M)；前缀长度 P、匹配词总输出字符量 R、匹配数 S，查询约 O(P+R+S log S)；select 在哈希表平均 O(1)。若只要前 K 名并预缓存，更新成本和额外空间会上升。
易错点与追问
容易失分的边界
- 每次查询重建 Trie，浪费与整个词典大小成正比的时间。
- 只返回严格更长的词，漏掉 prefix 本身就是完整词。
- 仅加计数器却没有定义何时增量、并列排序和缓存失效。
- 误把按频次排序的 O(S log S) 称为 O(P) 查询。
继续深挖
- 如何支持词典增删和高并发下的一致快照？
- 若要求 prefix Top 10 在 10ms 内返回，节点缓存怎样更新与分片？
- 热门词是否需要按用户、地区、时间衰减分组？
