Google 经典面试题解析

6hz7vif

在这篇文案中，作者将介绍其过去在Google面试时采用的面试题，不外因为题目泄漏此刻已然禁止在面试中运用了。然而，失之东隅收之桑榆，由于这些题目已被泄漏，因此笔者期盼透过问题看本质，分享Google面试值得重视的细节，期盼对大众有所裨益。

作者 | Alex Golec

译者 | 弯月

责编 | 屠敏

出品 | CSDN（ID：CSDNnews）

在深入问题之前，有一个令人振奋的信息：我离开了Google！我激动地宣布，我已然加入了Reddit，并在纽约市担任项目经理！

声明：虽然面试候选人是我的职责，但这篇文案仅表率我个人的观察、轶事和观点。请不要把本文当成Google、Alphabet、Reddit，或其他个人或组织的官方声明。

问题

想象一下，你在操作一个流行的搜索引擎，况且你在日志中看到了两则查找，例如说“奥巴马的支持率”和“奥巴马的流行度”。（倘若我没记错的话，这些是数据库面试中实质运用的例子，虽然这个问题的日期有点过时了……）这两个查找是区别的字符串，然则我认为（相信你亦会同意）从基本上说它们查询的都是同一个东西，在计数查找、表示结果等方面能够将这两个查找视作等价。那样，咱们怎样才可晓得两个查找是同义词呢？

让咱们用正式语言描述一下。假设你有两个输入。第1个是一个列表，其中每一个元素都是成对的两个字符串，况且它们是同义词。第二个亦是一个列表，每一个元素都是一构成对的字符串，表率两个查找。

为了详细起见，我经过以下示例输入来讲明：

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件事便是找出这类的歧义，并设法处理它们。怎样做到这一点因人而异：有些人会到白板前设法手动处理详细的问题；有些人则看一眼立即就能看出其中的猫腻。不管怎么样，尽早发掘这些问题至关重要。

我非常注重这个问题的“问题理解”周期。我爱好将软件工程叫作为分形学科，这寓意着它与分形学有类似之处，即放大问题就能够显现出额外的繁杂性。就在你以为你理解了某个问题的时候，走近一看才发掘你忽略了一个微妙之处，或能够改进的实施细节，或找到一种新的看待这个问题的办法从而洞悉更加多细节。

工程师的能力在很大程度上取决于她们对问题的理解程度。将一个模糊的问题描述转换成一组仔细的需要是这个过程的第1步，有目的地定义问题是我评定候选人处理新状况能力的依据。

顺便说一句，还有一些不重要的问题，例如“是不是需要思虑体积写”，这些问题即使候选人不晓得亦不会影响核心算法问题。针对这些问题，通常状况下我会给出最简单的答案（就这个例子而言，我会说“假设所有内容都已预处理为小写了”）。

第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

请重视：这儿我故意无定义words_are_synonyms

很简单，对不对？从算法上讲，这非常简单。无动态规划，无递归，无棘手的数据结构等等。只是非常简单的标准库操作，以及线性时间算法，对吧？

你可能会这么想，然则这儿面比你第1眼看到的更微妙。到日前为止，这个简单的算法中最棘手的部分是同义词比较。虽然易于理解和描述，但同义词比较这部分有可能会出非常多错。下面我来介绍一下我看到的有些平常的问题。

首要声明，在我看来候选人不会由于这些错误而遭遇面试失败；倘若候选人做出来的实现有错，那样我会指出来，她们会调节她们的处理方法，而后面试继续。然则，面试是一个分秒必争的过程。犯错，发掘错误，改正错误，这些行径都是意料之中的，然则因此呢而浪费掉的时间本能够用来干别的，例如找到更优的处理方法等。不犯错的候选人很少，然则犯错少的候选人就能够做得更好，由于她们花费在清理错误上的时间更少。

这便是我爱好这道题目的原由：上一篇文案中的题目需要在灵光闪现之际找到一个算法，而后再找到一个简单的实现。这道题目与之区别，它需要在正确的方向上一步步前行。每一步都表率着一个很小的阻碍，候选人能够优雅地跳过去，或被绊倒再站起来。优秀的候选人会利用她们的经验和直觉来避免这些小陷阱，并找到更加详实和正确的处理方法，而实力比较弱的人会浪费时间和精力去处理错误，况且一般最后只会留下错误累累的代码。

每次面试我都会看到有人优雅地跳过去了，而有人却摔得鼻青脸肿，但这里我只想举几个例子说明平常的几个小错误。

意外的运行时杀手

首要，有些候选人会经过简单地遍历同义词列表来实现同义词的检测：

... elif (w1, w2) in synonym_words: continue ...

从表面上看，这似乎很恰当。但仔细观察，你就会发掘这是一个非常非常糟糕的主意。我想跟哪些不认识Python的人解释一下：关键字in是contains办法的语法糖，适用于所有标准的Python容器。这儿的问题在于synonym_words是一个列表，它经过线性搜索实现了关键字in。Python用户尤其容易受到这种错误的影响，由于这种语言会隐匿类型，但C ++和Java用户偶尔亦会犯一样的错误。

在我的全部职业生涯中，编写这类线性搜索代码的次数屈指可数，况且每次触及的列表都不会超过二十多个元素，即便如此，我还是会写一大篇注释告诉读者为何我选取了这种看似不太理想的办法。我可疑有些候选人在这儿运用线性搜索的原由是由于她们对Python标准库的认识不足，她们不晓得怎样在列表上实现关键字in。这是很容易犯的一个错误，虽然这并不致命，然则你对选取的语言不足熟悉似乎亦不太好看。

至于实质的意见吗，其实很容易避免这种错误。首要，在你运用python这种无类型的语言时，永远不要忘记对象的类型！其次，请记住，倘若你对列表运用关键字in，那样就会形成线性搜索。除非你能够保准这个列表始终非常小，否则它就会作为性能杀手。

一般，提醒候选人这个输入结构是一个列表就能够让她们反应过来。在我给出提示后就有好戏看了。优秀的候选人会立即想到以某种方式预处理同义词，这是一个不错的开端。然而，这种办法亦并非无陷阱......

运用正确的数据结构

从上面的代码能够看出，为了在线性时间内实现这个算法，咱们需要一个常数时间的同义词查询。况且在每次常数时间的查询后面都应该有一个hashmap或hashset。

我感兴趣的不是候选人会从这两个中选取哪一个，而是她们会在里面存什么。（顺便说一句，永远不要运用返回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()的运用。你能够采用“先检测key是不是在dict中再获取”的实现，但那样你就失去了展示你对标准库的认识的机会。我个人并不太爱好用了非常多continue的代码，况且有些编程风格指南禁止或不意见这么运用。其实，我最初的代码中有一个bug——查找长度检测后面省略了continue。这个bug不是很糟糕，然则要晓得它很容易出错。

第2部分：加大难度！

在面试优秀的候选人时，我常常发掘最后还剩下10-15分钟的时间。幸运的是，我能够提出非常多后续的问题，然则咱们不太可能在那段时间内编写非常多代码。尽管在一天结束后，我觉得自己不必那样做，但我想认识候选人两方面的能力：她们能够设计算法吗？还有她们能够写代码吗？我上一篇文案中的问题首要回答了算法设计的问题，而后还能够检测代码，而本文中的这道题目得到答案的次序正好相反。

等到候选人完成为了这道题目的第1部分后，她们就处理了（这个非常有难度的）编程问题。此时，我能够很自信地说她们具备设计基本算法的能力，还能够将她们的想法转化为代码，况且她们还很熟练自己爱好的语言和标准库。接下来这个问题就变得更加有趣了，由于编程需求已然能够了，咱们能够深入科研算法部分了。

为此，让咱们回到第1部分的基本假设：单词的次序很重要，同义词关系无传递性，同义词不可包括多个单词。随着面试的进行，我会改变这些约束，况且在这个编程后的周期里，我和候选人能够只讨论纯粹的算法。我会经过有些代码示例来讲明我的观点，但在实质面试中，我会运用纯粹的算法术语进行讨论。

在深入说明之前，我想说从我的期望值来看后面的面试基本上都属于“加分项”。我个人对这个问题的处理办法是，挑选第1部分考察完全“合格”的候选人，而后经过下一个环节的考察从“合格”的候选人挑选“强力”的候选人。“合格”的候选人已然很厉害了，表率了“我相信这个人能够很好地胜任工作”，而“强力”的候选人则暗示“我相信这个人非常优秀，聘用她们能够为机构带来巨大的利益。”

传递性：朴素的办法

我想讨论的第1个问题是相关传递性，亦便是说倘若单词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）是一个容器，准许你快速查询集合中是不是包括某个对象。不相交集（disjoint set）处理的是另一个区别的问题：它并不关注某个集合本身是不是包括某个特定项，而是准许你检测两项是不是属于同一个集合。更重要的是，它完成这项操作所花费的时间非常短，只需O(a(n))，其中a(n)是Ackerman函数的相反数。除非你曾经上过高级算法的课程，否则即便你不晓得这个功能亦无需自责，针对所有恰当的输入来讲，这实质上能够在常数时间内完成。

该算法的操作大体如下。树表率集合，其中每一项都有父项。因为每一个树都有一个根（寓意着有一项目的父项是它本身），那样咱们能够经过查看父项来确定两个项目是不是属于同一个集合，直到找到每一个项目的根元素。倘若两个元素持有同一个根元素，则它们必然属于同一个集合。连接这些集合亦很容易：咱们只需找到根元素并将其中一个做为另一个元素的根。

到这儿为止，一切都很顺利，但在性能方面依然无突破性的发展。这种结构的天才之处在于一种名为“压缩”的过程。假设你有以下树：

假设你想晓得“speedy”和“hasty”是不是是同义词。从每一个节点起始遍历父关系，直到你发掘它们持有同一个根节点“fast”，因此呢它们肯定是同义词。此刻假设你想晓得“speedy”和“swift”是不是是同义词。你会在一次从每一个节点起始遍历，直到你找到“fast”，然则这一次你重视到你重复了“speedy”的遍历。你能够避免这种重复工作吗？

事实证明，你能够。在某种程度上，这棵树中的每一个元素都注定会找到“fast”节点。与其多次遍历这棵树，为何不简单地将每一个元素的父元素改为“fast”呢，如此一来不是就能够减轻工作量了吗？这个过程被叫作作“压缩”，而在不相交的集合中，“压缩”的构建便是查询根的操作。例如，在咱们确定“speedy”和“hasty”是同义词之后，上面的树就变成为了下面这般：

“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分钟的面试时间内能做的所有事情的极限了。我挑出了第1部分考查“合格”的候选人，并经过描述（不包含实现）不相交集合的处理方法挑出了“强力”的候选人，最后能够让她们向我提问了。我从来没遇到过一个候选人能够步行到这一步，还有时间向我提问。

接下来还有有些后续工作要做：这道题目的一个版本是单词的次序无关紧要，还有同义词能够是多个单词。每一个问题的处理方法都富有挑战且令人期待，然则受篇幅所限，我会在后续的文案中讨论。

这个问题很实用，由于它准许候选人犯错误。平常的软件工程工作包含永无止境的分析、执行和细化。这个问题为候选人供给了机会，能够让她们展示每一个周期她们的做法。倘若你想经过这个问题作为“强力”的候选人，那样需要如下的技术力：

分析问题的描述，找出模糊与不知道的地区，澄清必要的地区创立知道的问题描述。继续这种做法持续寻找处理方法，并遇到新问题。为了最大化效率，在该周期尽可能早地展开这种做法，由于随着工作的发展，改正错误的代价会越来越大。经过易于接近和处理问题的方式重新构建问题。在咱们的这道题中，最重要的一点是观察你能够在查找中摆列相应的单词。实现你的处理方法。这触及选取最佳数据结构和算法，以及设计出可读且将来易于修改的规律。回过头来设法找到bug和错误。代码中可能会有有些实质的bug，例如以上我忘记插进“continue”语句，或因为运用不正确的数据结构等引起的性能问题。当问题定义出现变化时，请重复以上过程，并在适当的时候调节你的处理方法，倘若不适用则需要弃用。无论是在面试中，还是在现实世界中，把握机会是一项关键的技能。多多学习数据结构和算法知识。不相交集合的数据结构并不是一种普通的结构，但亦不是非常罕见或完美无缺。保证自己认识工作中的工具的独一办法便是尽可能地学习。

这些技术都不是能从课本上学来的（除了数据结构和算法）。得到这些技术的独一途径是连续和广泛的实践，这与机构的期盼一致：候选人把握了她们的技术力，并且有海量的实践经验可以有效地运用这些技术。寻找这般的人才是面试的真正目的，而这道题目我运用了很长一段时间。

期待

经过本文的阅读，可能你已然看出来这道题目亦被泄密了。从那以后，我还用过几个问题，按照我的心情和初期的候选人提出的问题挑一个（始终问一个问题很无聊）。其中有些问题仍在运用，因此我会保守奥密，但有些已然没人用了！所以，你能够期待在今后的文案中看到这些题目。

原文：https://medium.com/@

alexgolec/google-interview-problems-synonymous-queries-36425145387c

作者：Alex Golec，工程经理@ Reddit NYC，前 Google 员工。

本文为 CSDN 翻译，如需转载，请注明源自出处。

j8typz

认真阅读了楼主的帖子，非常有益。