这是一篇有关Google采访中的任务讨论的新文章。 当我在那里工作时，我向应聘者提供了此类任务。 然后有一个泄漏，他们被禁止了。 但是硬币有另一面：现在我可以自由地解释解决方案了。

要开始的好消息：我退出了Google！ 很高兴地通知您，我现在担任纽约Reddit的技术经理！ 但是，这一系列文章仍将继续。

免责声明：尽管采访候选人是我的专业职责之一，但在此博客上，我分享个人观察，故事和个人见解。 请不要将此视为Google，Alphabet，Reddit，任何其他个人或组织的正式声明。

问题

在最后 两篇有关马匹拨打电话的过程的文章发表之后，我受到批评，这不是一个现实的问题。 学习候选人的思维能力有多么有用，但我必须承认：这项任务确实有点不现实。 尽管我对面试问题和现实之间的相关性有一些想法，但我现在将它们留给我。 可以肯定的是，我到处都读到评论，还有一些要回答的问题，但现在不是。

但是，几年前禁止传递马匹的任务时，我引起了批评，并试图用一个与Google范围更相关的问题来代替它。 还有什么比搜索查询机制更适合Google？ 因此，我发现了这个问题并使用了很长时间，然后这个问题才被公开并被禁止。 和以前一样，我将提出问题，深入研究其解释，然后讲述在面试中如何使用它以及为什么喜欢它。

问题是。

想象一下，您管理一个流行的搜索引擎，并在日志中看到两个请求：说“奥巴马的支持率”和“奥巴马的受欢迎程度”（如果我没记错的话，这些是问题库中的真实示例，尽管它们现在已经有些过时了……） 。 我们看到的查询是不同的，但是每个人都会同意：用户正在寻找基本相同的信息，因此在计算查询数量，显示结果等时，应将查询视为等效的。 如何确定两个查询是否同义？

让我们形式化任务。 假设有两组字符串对：同义词对和查询对。

具体来说，这是一个示例输入来说明：

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的同义词吗？ 同义词可以覆盖几个词吗？“美国”是短语“美利坚合众国”还是“美国”的同义词？

这样的模棱两可立即使您有能力向好的候选人证明自己。 他要做的第一件事是找出这种歧义并设法解决它们。 每个人都以不同的方式进行操作：有些人与董事会接触并尝试手动解决特定情况，而另一些人则着眼于问题并立即发现差距。 无论如何，及早发现这些问题至关重要。

“了解问题”的阶段非常重要。 我喜欢将软件工程称为分形学科。 像分形一样，逼近揭示了额外的复杂性。 您以为自己理解了问题，然后仔细看了一下，发现错过了可以改进的一些细微之处或细节。 或以其他方式解决问题。


曼德布罗集

工程师的才能很大程度上取决于他对问题的理解程度。 将模糊的问题陈述转化为详细的要求集是此过程的第一步，而故意低估陈述可以使您评估候选人对新情况的适应程度。

我们忽略了一些琐碎的问题，例如“大写字母重要吗？”，这些问题不会影响主算法。 对于这些问题，我总是给出最简单的答案（在这种情况下，“假定所有字母都已经过预处理并转换为小写字母”）

第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用户对这种错误特别敏感，因为该语言隐藏了类型，但是C ++和Java用户有时也会犯类似的错误。

在我的职业生涯中，我只写过几次线性搜索代码，每次搜索都包含不超过二十个元素。 即使在这种情况下，他也写了一篇很长的评论，解释了为什么他选择了这种看似次优的方法。 我怀疑有些候选人只是因为不知道in关键字如何在Python标准库的列表中工作而使用它。 这是一个简单的错误，不是致命的，但是与您喜欢的语言的相识不是很好。

实际上，很容易避免该错误。 首先，即使使用诸如Python之类的非类型化语言，也不要忘记对象类型！ 其次，请记住，当您在列表中使用in关键字时，将开始线性搜索。 如果不能保证此列表将始终保持很小，则会降低性能。

对于候选人来说，通常足以提醒他输入结构是一个列表。 观察候选人对提示的反应非常重要。 最好的候选人立即尝试以某种方式对同义词进行预处理，这是一个好的开始。 但是，这种方法并非没有缺陷。

使用正确的数据结构

从上面的代码中，很明显，为了在线性时间内实现此算法，必须快速找到同义词。 当我们谈论快速搜索时，它总是一张地图或一组哈希。

对我来说，候选人选择地图还是散列数组都没有关系。 重要的是他会把它放在那里（顺便说一句，在过渡到True或False ，切勿使用dict / hashmap）。 大多数候选人选择某种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 

为什么要两次插入并使用两倍的内存？

 ... synonyms = defaultdict(set) for w1, w2 in synonym_words: synonyms[w1].append(w2) ... elif (w2 in synonyms.get(w1, tuple()) or w1 in synonyms.get(w2, tuple())): continue 

结论： 总是想着如何优化代码 ！ 回想起来，搜索功能的排列是一个明显的优化，否则我们可以得出结论，候选人没有考虑优化选项。 再次，我很高兴给出一个提示，但最好自己猜一下。

排序？

一些聪明的候选人希望对同义词列表进行排序，然后使用二进制搜索。 实际上，此方法具有一个重要的优势：除了同义词列表（前提是允许更改列表）之外，它不需要其他空间。

不幸的是，时间复杂度会干扰：对同义词列表进行排序需要Nlog(N)时间，然后需要另一个log(N)来搜索每一对同义词，而所描述的预处理解决方案则是线性发生的，然后是恒定的时间。 另外，我坚决反对强迫候选人在板上执行排序和二进制搜索，因为：1）排序算法是众所周知的，因此，据我所知，候选人可以不加考虑地发布它； 2）这些算法很难正确实现，而且即使是最好的候选人，也会犯一些错误，而这些错误并不能说明他们的编程技能。

每当有候选人提出这样的解决方案时，我都会对程序的执行时间感兴趣，并询问是否有更好的选择。 有关信息：如果面试官问您是否有更好的选择，答案几乎总是是。 如果我问过你这个问题，答案肯定是那样。

最后解决

最后，候选人提供了正确且合理的最佳选择。 这是在给定条件下线性时间和线性空间的实现：

 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()的使用。 您可以实施检查以查看密钥是否在字典中，然后再获取它，但这是一种复杂的方法，尽管通过这种方式您将展示出对标准库的了解。
• 我个人不喜欢频繁地continue编写代码，并且某些样式指南禁止或不推荐它们 。 我自己在这段代码的第一版中，在检查了请求的长度之后，忘记了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个条目。 在图中，它看起来像这样：



注意，我们从三个键和六个记录变为四个键和十二个记录。 具有50个同义词的单词将需要50个键和近2500个条目。 代表一个单词的必要空间随着同义词集的增加而平方增加，这是相当浪费的。

还有其他解决方案，但是为了不给文章充气，我不会做得太深。 其中最有趣的是使用同义词数据结构构造有向图，然后进行广度优先搜索以找到两个单词之间的路径。 这是一个很好的解决方案，但是搜索的单词的同义词集的大小变成线性的。 由于我们针对每个请求执行了几次搜索，因此这种方法不是最佳的。

可及性：使用不交集

事实证明，归功于称为不交集的数据结构，几乎（恒定）时间内可以搜索同义词。 与常规数据集相比，此结构提供的可能性略有不同。

通常的集合结构（哈希集，树集）是一个容器，可让您快速确定对象是在对象内部还是外部。 不相交集解决了一个完全不同的问题：无需定义特定元素，而是使您可以确定两个元素是否属于同一集合 。 此外，该结构在令人难以置信的快速时间O(a(n)) ，其中a(n)是逆阿克曼函数。 如果您尚未研究高级算法，则可能不知道此功能，对于所有合理的输入，该功能实际上都是在恒定时间内执行的。

在较高级别，该算法的工作原理如下。 集用树表示，每个元素都有父级。 由于每棵树都有一个根（一个元素是其自己的父元素），因此我们可以通过将两个元素的父元素追踪到根来确定两个元素是否属于同一集合。 如果两个元素具有一个根，则它们属于一组。 组合集合也很容易：只需找到根元素并将其中一个作为另一个的根。

到目前为止，还不错，但是到目前为止，还没有看到令人眼花speed乱的速度。 这种结构的精髓在于称为压缩的过程。 假设您有以下树：



假设您想知道speedy和草率是否是同义词。 通过每个父母-找到相同的快速根。 现在，假设我们对speedy和swift单词执行类似的检查。 再一次，我们走到了根源，然后迅速地走同样的路。 可以避免重复工作吗？

事实证明您可以。 从某种意义上说，这棵树中的每一个元素注定要快速发展 。 为什么不更改所有快速后代的父级以缩短到根的路径，而不是每次都遍历整个树？ 此过程称为压缩，并且在不相交的集中将其嵌入到根搜索操作中。 例如，在比较快速和匆忙的第一个操作之后，结构将理解它们是同义词，并将压缩树，如下所示：


对于快速和快速之间的所有单词，父级都进行了更新，仓促发生了同一件事

现在，所有后续调用将在固定时间内发生，因为此树中的每个节点都指向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分钟的面试中所能展现的极限。对于应对入门部分并在描述（不实施）不相关的集合方面取得重大进展的所有候选人，我将其评级为“极力推荐”，并允许他们提出任何问题。我从未见过候选人能走这么远，还有很多时间。

原则上，传递性问题仍然存在变体：例如，删除对单词顺序或单词的多个同义词的限制。每个决定都将是困难而令人愉快的，但我将其留待以后再谈。

这项任务的优点是它可以使求职者犯错误。日常软件开发包括无休止的分析，执行和完善周期。这个问题使候选人有可能在每个阶段展示自己的能力。考虑在此问题上获得最高分的必要技能：

• 分析问题的陈述并确定未明确表述的地方，制定明确的表述。解决并继续出现新问题时，请继续执行此操作。为了获得最大的效率，请尽早执行这些操作，因为工作进行得越远，修复错误所花费的时间就越多。
  
• , . , .
  
• . , , .
  
• , . , continue , , .
  
• , : , , , . , , , .
  
• . — , . — .

这些技能无法从教科书中学习到（数据结构和算法可能除外）。获得这些证书的唯一方法是通过定期和广泛的实践，这与雇主的需求非常一致：有经验的候选人能够有效地运用其知识。访谈的重点是找到这样的人，这篇文章的任务在很长一段时间内对我都很有帮助。

未来计划

如您所知，这项任务最终为公众所熟知。从那以后，我使用了其他几个问题，具体取决于以前的访问者的要求和我的心情（问一个问题一直很无聊）。我仍然会使用一些问题，所以我将为您保密，但有些则不是！您可以在以下文章中找到它们。

我计划在不久的将来写两篇文章。首先，如上所述，我将解释该任务剩下的两个问题的解决方案。我从未在面试中问过他们，但它们本身很有趣。此外，我将分享我在IT部门寻找员工的过程的想法和个人见解，这对我来说现在尤其有趣，因为我正在Reddit寻找我的团队的工程师。

与往常一样，如果您想了解新文章的发布，请在Twitter或Medium 上关注我。如果您喜欢这篇文章，请不要忘记投票或发表评论。

感谢您的阅读！

PS：您可以检查所有物品的代码库GitHub的或和他们住在一起玩感谢从我的好朋友repl.it。