Google VO 面试真题解析：列表前缀搜索 Prefix Search

Given a list, e.g. ["apple", "banana", "ant", ...], with an input prefix, find all the words starting with the prefix from the above list.

Examples:

• prefix: "a" -> apple, ant
• prefix: "ap" -> apple

process(words: str[])
query(prefix: str) -> str[]

Call process once, and query will be called many times.

这道题要求先对给定单词列表做一次预处理，然后支持多次按前缀查询所有匹配单词。典型做法是使用 Trie（前缀树）来存储词库，在查询时先沿着前缀走到对应节点，再收集该节点下的所有单词；如果更强调实现简单，也可以对单词列表排序后用二分查找定位前缀区间。题目重点在于把一次性的构建成本与多次查询效率平衡起来，适合考察前缀树、字符串匹配和时间复杂度分析。