作者 | Alex Golec
译者 | 薛命灯
这是“谷歌面试题解析”系列的又一篇文章。在这一系列文章中，我介绍了谷歌面试当中经常用到的一些面试题，不过这些面试题已经被泄露，并禁止在面试中使用。不过，我的损失就是你的收获，因为它们被泄露了，我就可以把它们写下来，供你参考。上篇：
一道泄露并遭禁用的谷歌面试题，背后玄机全解析
在介绍新的面试题之前，我先宣布一个令人兴奋的消息：我已经离开谷歌了！我现在是 Reddit 的工程经理！不过，我还是会继续发表这一系列的文章，请继续关注。
免责声明：虽然面试候选人是我的工作职责之一，但这篇文章仅代表我的个人观察、个人经历和个人观点。如果有任何错误，请不要将它们归咎于谷歌、Alphabet、Reddit 或任何其他个人或组织。
问题描述
假设你在运营一个搜索引擎，在搜索引擎日志中可以看到两个搜索关键词，比如“obama approval ratings（奥巴马支持率）”和“obama popularity rate（奥巴马受欢迎程度）”。虽然这两个搜索字符串不一样，但基本上是在搜同一个东西，在计算搜索和显示结果时应该被认为是等价的。那么我们该如何判断这两个搜索词是不是同义的呢？
我们先将这个问题泛化。假设你有两个输入，一个是字符串对列表，其中每个字符串对是两个同义词。另一个也是字符串对列表，其中每个字符串对是两个搜索关键词。
下面是输入示例：
SYNONYMS = [
('rate', 'ratings'),
('approval', 'popularity'),
]
QUERIES = [
('obama approval rate', 'obama popularity ratings'),
('obama approval rates', 'obama popularity ratings'),
('obama approval rate', 'popularity ratings obama')
]
你的任务是输出一个布尔值列表，其中每个布尔值表明相应的搜索关键词对是不是同义的。
理清问题
从表面上看，这是一个很简单的问题。但是，越是细想，它就越复杂。首先，这个问题的定义不是很明确。单词可以有多个同义词吗？单词的顺序重要吗？同义词之间是否具有传递性，例如，如果 A 与 B 同义，B 与 C 同义，那么 A 是否也与 C 同义？同义词可以跨多个单词吗，例如“USA”与“United States of America”同义，还是与“United States”同义？
这种模棱两可给了优秀候选人一个脱颖而出的机会。好的候选人会先找出这些含糊不清的地方，并试图解决它们。他们的做法因人而异：有些人会走到白板前，试图手动解决一些特定的情况，而另一些人一看到问题，就会立即发现其中的“陷阱”。无论如何，关键的是要尽早发现这些问题。
我非常看重这个“理解问题”阶段。我喜欢将软件工程称为分形学科，这意味着它与分形具有相同的特性，通过放大问题来显示额外的复杂性。当你认为你理解了一个问题，仔细一看，就会发现其实忽略了一些细微之处，或者一些可以改进的实现细节，或者有其他新的方法可以用来分析这个问题并揭示出额外的见解。
工程师的能力在很大程度上取决于他们对问题理解的深度。将一个模糊的问题陈述转化为一组详细的需求是这个过程的第零步，像这样故意向候选人提出不明确问题的做法可以帮助面试官评估候选人应对意外情况的能力。
第 1 部分：简单的情况
不管候选人是如何进入到这一步的，他们都不可避免地要我回答他们提出的疑问，我总是从最简单的情况开始：单词可以有多个同义词、单词的顺序重要、同义词不具有传递性、同义词只能从一个单词映射到另一个。尽管这样的搜索引擎功能非常有限，但对于一道有趣的面试题来说，已经足够了。
解决方案大概是这样的：将搜索关键词分解为单词（按照空格进行拆分就可以了），并比较相应的单词对，看看它们是否相同或者同义。它们看起来像这样：
实现代码大概是这样的：
def synonym_queries(synonym_words, queries):
'''
synonym_words: iterable of pairs of strings representing synonymous words
queries: iterable of pairs of strings representing queries to be tested for
synonymous-ness
'''
output = []
for q1, q2 in queries:
q1, q2 = q1.split(), q2.split()
if len(q1) != len(q2):
output.append(False)
continue
result = True
for i in range(len(q1)):
w1, w2 = q1[i], q2[i]
if w1 == w2:
continue
elif words_are_synonyms(w1, w2):
continue
result = False
break
output.append(result)
return output
很简单，对吗？从算法来看，确实很简单。没有动态规划，没有递归，没有特别的数据结构，只要使用标准库操作和线性时间算法，对吧？
你可能会想，但这里的微妙之处比你第一眼看到的要多。到目前为止，这个算法最复杂的部分是同义词比较。虽然易于理解和描述，但同义词比较很有可能会出错。
需要明确的是，在我看来，这些错误都不能说明候选人是不合格的。如果候选人给出了包含错误的实现，我会直接指出来，他们会调整他们的解决方案。但是，面试首先是一场与时间赛跑的竞赛。犯错误、找出错误和纠正错误是意料之中的事，但这样会消耗原本可以花在其他地方的时间，比如提出更优的解决方案。很少有候选人不犯错误，但错误犯得少的候选人会取得更大的进步，因为他们花在纠错上的时间更少。
这也是为什么我会喜欢这个面试题：在解决骑士拨号器问题时，需要算法的灵光一现，然后给出一个简单的实现，而这个问题需要多个渐进式的小步骤，朝着正确的方向逐渐接近答案。每一步都代表了一个小障碍，候选人可以优雅地跳过，也可能会被绊倒，然后重新站起来。优秀的候选人利用他们的经验和直觉来避免这些小陷阱，他们会得到一个更加完善和正确的解决方案，而较弱的候选人则会在错误上浪费时间和精力，通常会给出包含错误的代码。
每次面试都会出现上述的状况，这里列出了我看到的更为常见的一小部分。
意外运行时杀手
首先，一些候选人通过遍历同义词列表来实现同义词检查：
...
elif (w1, w2) in synonym_words:
continue
...
从表面上看，这样似乎是合理的。但仔细一看，就会发现这是一个非常糟糕的主意。如果你不了解 Python，我可以解释一下：in 关键字是 contains 方法的语法糖，适用于所有标准的 Python 容器。这里的问题在于，synonym_words 是一个列表，通过线性搜索来实现 in 关键字。Python 用户很容易犯这个错误，因为 Python 隐藏了类型，不过 C++ 和 Java 用户偶尔也会犯类似的错误。
在我的整个职业生涯中，我只写过几次使用线性搜索的代码，而且每次都只涉及不到 24 个元素的列表，即使是这样，我也写了很长的注释，让阅读代码的人知道我为什么选择这种似乎不太理想的方法。我认为一些候选人之所以使用它，是因为他们不太了解 Python 标准库，不知道在列表上使用 in 关键字是如何实现的。这是一个很容易犯的错误，不过这也不是什么大不了事，只是你选择了自己不熟悉的语言，对你不是很有利。
实际上，这是一个很容易就可以避免的错误。首先，永远不要忘记对象的类型，即使你使用的是 Python 这种非类型化的语言！其次，请记住，在列表上使用 in 关键字是一种线性搜索。除非这个列表非常小，否则它将成为性能杀手。
提醒一下候选人，输入的数据结构是列表，这通常就足以让他们“醒悟”。好的候选人会立即想办法对同义词进行预处理，这是一个好的开始。然而，这种方法并非没有缺陷……
使用正确的数据结构
从上面的代码可以看出，为了在线性时间内实现这个算法，我们需要一种常量时间的同义词查找方法，而常量时间查找需要用到 hashmap 或 hashset。
我感兴趣的不是候选人会选择使用哪个，而是他们会把什么东西放在里面。大多数候选人会选择某种形式的 dict/hashmap。我看到的最常见的错误是候选人潜意识里认为每个单词最多只能有一个同义词:
...
synonyms = {}
for w1, w2 in synonym_words:
synonyms[w1] = w2
...
elif synonyms[w1] == w2:
continue
我不会因为候选人犯了这个错误而惩罚他们。示例中给出的输入是为了不让人想起单词可以有多个同义词，一些候选人根本没有遇到过这种情况。在我指出这个错误之后，他们迅速做出纠正。好的候选人会及早发现问题，从而避免麻烦，不过这也不会浪费太多时间。
一个稍微严重一点的问题是候选人意识不到同义词关系是双向的。然而，纠正这一点很容易出错。请看下面这个纠正方法:
...
synonyms = defaultdict(set)
for w1, w2 in synonym_words:
synonyms[w1].append(w2)
synonyms[w2].append(w1)
...
elif w2 in synonyms.get(w1, tuple()):
continue
结论是：总是问自己是否可以少做点工作！事后看来，排列查找显然是一种可以节省时间的方法，但使用次优实现说明候选人没有想要寻找优化方法。我很乐意给他们提示，但如果不需要我给提示会更好。
排序？
一些比较聪明的候选人会考虑对同义词列表进行排序，然后使用二分查找来确定两个单词是否同义。这种方法的主要优点是除了输入同义词列表之外不需要任何额外的空间（假设可以修改输入列表）。
可惜的是，时间复杂度还不够好：排序同义词列表需要 Nlog(N) 的时间复杂度，然后查找每个同义词对需要 log(N) 的时间复杂度，而前面描述的预处理是线性的，在访问时使用了常量时间。另外，候选人在白板上实现排序和二分查找在我看来是禁忌，因为排序算法已经是众所周知的东西，而且这些算法非常难搞对，通常即使是最优秀的候选人也会犯错误，而这些错误并不能告诉我他们的编程能力究竟是怎样的。
每当有候选人提供这样的解决方案，我就会问他们运行时间复杂度，以及是否可以做得更好。顺便说一句：如果面试官问你是否可以做得更好，大多数时候答案都是“是”。
最后的解决方案
到了这个时候，候选人应该已经能够给出最佳的解决方案了。下面是线性时间和线性空间的算法实现：
def synonym_queries(synonym_words, queries):
'''
synonym_words: iterable of pairs of strings representing synonymous words
queries: iterable of pairs of strings representing queries to be tested for
synonymous-ness
'''
synonyms = defaultdict(set)
for w1, w2 in synonym_words:
synonyms[w1].add(w2)
output = []
for q1, q2 in queries:
q1, q2 = q1.split(), q2.split()
if len(q1) != len(q2):
output.append(False)
continue
result = True
for i in range(len(q1)):
w1, w2 = q1[i], q2[i]
if w1 == w2:
continue
elif ((w1 in synonyms and w2 in synonyms[w1])
or (w2 in synonyms and w1 in synonyms[w2])):
continue
result = False
break
output.append(result)
return output
一些注意点：
在使用 dict.get() 时要注意。你可能是想“检查 dict 中是否存在某个键，然后获取它”，但这样有点混乱，这也表明了你对标准库的了解情况。
我个人并不喜欢在代码中大量使用 continue，一些编码指南也建议不要这么做。
第 2 部分：加大难度
遇到优秀的候选人，我通常还会剩下十到十五分钟时间。所幸的是，我可以继续问很多其他问题，但我们不太可能在这段时间内写很多代码。但不管怎样，我认为也没必要写太多代码。我想知道关于候选人的两件事是：他们可以设计算法吗？他们可以写代码吗？骑士拨号器问题需要先回答算法设计问题，然后再写代码，而这个问题恰好反过来。
当候选人完成这个问题的第一部分时，他们实际上已经解决了编码问题。从这一点上看，我可以自信地认为他们有设计基本算法并将想法转化为代码的能力，并且他们对自己喜欢的编程语言和标准库也一定的了解。既然编码方面没有问题，那么我们就可以深入研究算法了。
为此，让我们回到第一部分的基本假设：单词顺序很重要、同义词关系不具备传递性、不能有多个同义词。随着面试的进行，我改变了这些约束条件，我和候选人进行了纯粹的算法讨论。在这里，我将通过代码示例来说明我的观点，但在实际的面试中，我是通过纯粹的算法术语和候选人进行讨论的。
传递性：初级方法
我想放宽的第一个约束是关于传递性的约束，也就是说，如果单词 A 和 B 是同义的，而且单词 B 和 C 也是同义的，那么单词 A 和 C 就是同义的。敏锐的候选人很快就会意识到，他们需要调整之前的解决方案，因为约束的放宽导致之前算法的核心逻辑无效。
那么我们该怎么做呢？一种常见的方法是基于传递关系为每个单词维护一组完整的同义词。每次在同义词集合中插入一个单词时，也会将它添加到集合中所有单词的同义词集合中：
synonyms = defaultdict(set)
for w1, w2 in synonym_words:
for w in synonyms[w1]:
synonyms[w].add(w2)
synonyms[w1].add(w2)
for w in synonyms[w2]:
synonyms[w].add(w1)
synonyms[w2].add(w1)
这个方法是有效的，但并不是最好的。可以看一下这个解决方案的空间复杂度。每次我们添加同义词时，不仅要添加到初始单词的同义词集合中，还要添加到这个单词所有同义词的集合中。如果它与一个单词同义，我们必须添加一个条目。如果它与 50 个单词同义，我们必须再添加 50 个条目。如图所示，它看起来像这样：
请注意，我们已经从 3 个键和 6 个条目变成了 4 个键和 12 个条目。一个包含 50 个同义词的单词将需要 50 个键和近 2500 个条目。表示一个单词所需的空间与同义词数量的大小呈二次方式增长，这非常浪费空间。
还有其他的解决方案，但我们关注的是空间，所以我不打算深入介绍它们。最有意思的一个解决方案是使用同义词数据结构来构造有向图，然后使用广度优先搜索来查找两个单词之间是否存在路径。这是一个很好的解决方案，但查找时间复杂度是线性的。因为每次查询需要进行多次查找，所以这个解决方案不是最优的。
传递性：使用并查集
事实证明，我们可以使用一种称为并查集的数据结构，在（几乎）恒定的时间内查找同义词关系。这种数据结构是一种集合，但它提供的功能与大多数人认为的“集合”有些不一样的地方。
通常的集合（如 hashset、treeset）是一种容器对象，可以让你快速地知道一个对象是否存在集合中。而并查集解决了一个非常不一样的问题：它可以让你知道两个对象是否属于同一集合。更重要的是，它的时间复杂度是 O(a(n))，其中 a(n) 是 Ackerman 函数的逆。除非你上过高级算法课程，否则不知道这个函数也是情有可原的。对于所有合理的输入，它几乎都是常数时间。
这个算法的过程如下所述。集合通过树来表示，每个元素都有一个父元素。因为每棵树都有一个根元素（这个元素的父元素就是它自己)，所以我们可以通过跟踪两个元素的父元素来确定它们是否属于同一个集合。我们找到每个元素的根元素，如果这两个根元素是同一个元素，说明这两个元素属于相同的集合。合并两个集合也很简单：我们只需要找到根元素，并让其中一个成为另一个的根。
到目前为止，一切都很好，但在性能方面还没看到有什么特别的地方。这种结构的精妙之处在于可以进行压实。假设你有这样的一棵树：
假设你想知道“speedy”和“hurry”是否是同义词。从每个节点开始，遍历父节点关系，发现它们的根节点都是“fast”，因此它们是同义词。再假设你想知道“speedy”和“swift”是否是同义词。你将再次从每个节点开始，一直向上遍历，直到到达“fast”。但这次你可能会注意到，从“speedy”开始的遍历重复了。“你能避免重复的遍历吗?”
事实证明，可以避免重复遍历。因为这棵树中的每个元素都注定要到达“fast”，所以与其多次遍历树，不如直接更改每个元素的父元素，直到“fast”，这样可以帮我们省下很多工作。这个过程被称为压实，在一个并查集中，它发生在寻根操作过程中。例如，在我们确定“speedy”和“hurry”是同义词之后，上面的树将变成这样：
“speedy”和“fast”路径上的每个单词的父元素都被更新了，“hasty”到“fast”之间的路径也是如此。
现在，所有后续的访问都将在常量时间内完成，因为树中的每个节点都指向“fast”。分析这个结构的时间复杂度并不容易：它不是常数，因为它取决于树的深度，但也不会比常数差太多，我们姑且认为是常数时间。
下面是并查集的实现，它为我们提供了解决这个问题所需的功能：
class DisjointSet(object):
def __init__(self):
self.parents = {}
def get_root(self, w):
words_traversed = []
while self.parents[w] != w:
words_traversed.append(w)
w = self.parents[w]
for word in words_traversed:
self.parents[word] = w
return w
def add_synonyms(self, w1, w2):
if w1 not in self.parents:
self.parents[w1] = w1
if w2 not in self.parents:
self.parents[w2] = w2
w1_root = self.get_root(w1)
w2_root = self.get_root(w2)
if w1_root < w2_root:
w1_root, w2_root = w2_root, w1_root
self.parents[w2_root] = w1_root
def are_synonymous(self, w1, w2):
return self.get_root(w1) == self.get_root(w2)
通过使用这种结构，我们可以预处理同义词，并在线性时间内解决这个问题。
评估和说明
到了这个时候，我们已经达到了 40 到 45 分钟的面试极限。如果候选人能够完成算法介绍，并在描述（不是实现）并查集解决方案方面取得重大进展，我就会给他们一个“Strong Hire”评级，然后让他们问我问题。我从未见过哪位候选人到了这一步还能剩下多少时间。
这个问题还有一些待解决的地方，即单词顺序不重要、同义词可以跨多个单词。这些问题的解决方案都颇具挑战性，也很有趣，我将在后续的文章中讨论它们。
这个问题很有用，因为它允许候选人犯错误。软件工程是一个永无止境的分析、执行和改进的循环过程。这个问题为候选人提供了在每个阶段展示自己能力的机会。如果想要获得“Strong Hire”的面试评级，一个候选人需要具备如下的能力：
分析一个问题的陈述，找出模糊和不明确的地方，并在寻找解决方案和遇到新问题的过程中一直保持下去。为了提升效率，请尽可能早地完成这个阶段，因为越到后面，从纠正错误的成本就越高。
用一种容易理解和解决的方式描述问题。对于这个面试题，最重要的一点是观察到你可以在查询中排列相应的单词。
实现你的解决方案。这涉及选择最佳的数据结构和算法，设计出可读且在将来易于修改的逻辑。
回过头来尝试找出错误。这些可能是实际的错误，比如我忘记在上面插入“continue”语句，或者是性能问题，比如使用了不正确的数据结构。
当问题的定义发生变化时，重复这个过程，并在适当的时候调整你的解决方案。无论是在面试还是在现实生活中，知道什么时候做这两件事都是一项关键的技能。
随时掌握数据结构和算法知识。并查集并不是一种常见的数据结构，但也不是那么罕见。确保自己了解各种工具的唯一方法是尽可能多地学习。
这些技能都无法从教科书上学到（除了数据结构和算法之外）。获得这些技能的唯一途径是通过定期和广泛的实践，而这也正是公司所希望的：候选人不仅能够掌握技能，而且能够有效地应用它们。考察这些候选人是面试的重点，而这个面试题在很长一段时间里帮了我大忙。
期 待
既然我写了这篇文章，说明这个问题已经被泄露了。从那时起，我一直在使用其他几个问题，具体取决于我的心情（一直问一个问题很无聊）以及之前的面试官已经问了哪些问题。其中一些面试题仍然在使用当中，所以我会保密。你可以期待在未来的文章中看到更多的面试题。
英文原文：
https://medium.com/@alexgolec/google-interview-problems-synonymous-queries-36425145387c
