Google经典面试题解析

作者 | Alex Golec
译者 | 弯月
责编 | 屠敏
出品 | CSDN（ID：CSDNnews）

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

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

问题

想象一下，你在操作一个流行的搜索引擎，而且你在日志中看到了两则查询，比如说“奥巴马的支持率”和“奥巴马的流行度”。（如果我没记错的话，这些是数据库面试中实际使用的例子，虽然这个问题的日期有点过时了……）这两个查询是不同的字符串，但是我认为（相信你也会同意）从根本上说它们查找的都是同一个东西，在计数查询、显示结果等方面可以将这两个查询视作等价。那么，我们如何才能知道两个查询是同义词呢？

让我们用正式语言描述一下。假设你有两个输入。第一个是一个列表，其中每个元素都是成对的两个字符串，而且它们是同义词。第二个也是一个列表，每个元素都是一组成对的字符串，代表两个查询。

为了具体起见，我通过以下示例输入来说明：

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

请注意：这里我故意没有定义words_are_synonyms

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

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

首先声明，在我看来候选人不会因为这些错误而遭遇面试失败；如果候选人做出来的实现有错，那么我会指出来，他们会调整他们的解决方案，然后面试继续。但是，面试是一个分秒必争的过程。犯错，发现错误，改正错误，这些行为都是意料之中的，但是因此而浪费掉的时间本可以用来干别的，比如找到更优的解决方案等。不犯错的候选人很少，但是犯错少的候选人就可以做得更好，因为他们花费在清理错误上的时间更少。

这就是我喜欢这道题目的原因：上一篇文章中的题目需要在灵光闪现之际找到一个算法，然后再找到一个简单的实现。这道题目与之不同，它需要在正确的方向上一步步前行。每一步都代表着一个很小的障碍，候选人可以优雅地跳过去，或者被绊倒再站起来。优秀的候选人会利用他们的经验和直觉来避免这些小陷阱，并找到更加详实和正确的解决方案，而实力比较弱的人会浪费时间和精力去处理错误，而且通常最后只会留下错误累累的代码。

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

意外的运行时杀手

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

...
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分钟的时间。幸运的是，我可以提出很多后续的问题，但是我们不太可能在那段时间内编写很多代码。尽管在一天结束后，我觉得自己没必要那么做，但我想了解候选人两方面的能力：他们能够设计算法吗？还有他们能够写代码吗？我上一篇文章中的问题首先回答了算法设计的问题，然后还可以检查代码，而本文中的这道题目得到答案的顺序正好相反。

等到候选人完成了这道题目的第一部分后，他们就解决了（这个非常有难度的）编程问题。这时，我可以很自信地说他们具备设计基本算法的能力，还可以将他们的想法转化为代码，而且他们还很熟悉自己喜欢的语言和标准库。接下来这个问题就变得更加有趣了，因为编程要求已经可以了，我们可以深入研究算法部分了。

为此，让我们回到第一部分的基本假设：单词的顺序很重要，同义词关系没有传递性，同义词不能包含多个单词。随着面试的进行，我会改变这些约束，而且在这个编程后的阶段里，我和候选人可以只讨论纯粹的算法。我会通过一些代码示例来说明我的观点，但在实际面试中，我会使用纯粹的算法术语进行讨论。

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

传递性：朴素的方法

我想讨论的第一个问题是有关传递性，也就是说如果单词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分钟的面试时间内能做的所有事情的极限了。我挑出了第一部分考查“合格”的候选人，并通过描述（不包括实现）不相交集合的解决方案挑出了“强力”的候选人，最后可以让他们向我提问了。我从来没遇到过一个候选人可以走到这一步，还有时间向我提问。

接下来还有一些后续工作要做：这道题目的一个版本是单词的顺序无关紧要，还有同义词可以是多个单词。每个问题的解决方案都富有挑战且令人期待，但是受篇幅所限，我会在后续的文章中讨论。

这个问题很实用，因为它允许候选人犯错误。日常的软件工程工作包括永无止境的分析、执行和细化。这个问题为候选人提供了机会，可以让他们展示每个阶段他们的做法。如果你想通过这个问题成为“强力”的候选人，那么需要如下的技术力：

• 分析问题的描述，找出模糊与不明确的地方，澄清必要的地方建立明确的问题描述。继续这种做法不断寻找解决方案，并遇到新问题。为了最大化效率，在该阶段尽可能早地展开这种做法，因为随着工作的进展，改正错误的代价会越来越大。

• 通过易于接近和解决问题的方式重新构建问题。在我们的这道题中，最重要的一点是观察你可以在查询中排列相应的单词。

• 实现你的解决方案。这涉及选择最佳数据结构和算法，以及设计出可读且将来易于修改的逻辑。

• 回过头来设法找到bug和错误。代码中可能会有一些实际的bug，比如上述我忘记插入“continue”语句，或者由于使用不正确的数据结构等导致的性能问题。

• 当问题定义发生变化时，请重复上述过程，并在适当的时候调整你的解决方案，如果不适用则需要弃用。无论是在面试中，还是在现实世界中，把握时机是一项关键的技能。

• 多多学习数据结构和算法知识。不相交集合的数据结构并不是一种普通的结构，但也不是非常罕见或完美无缺。确保自己了解工作中的工具的唯一方法就是尽可能地学习。

这些技术都不是能从课本上学来的（除了数据结构和算法）。获得这些技术的唯一途径是持续和广泛的实践，这与公司的希望一致：候选人掌握了他们的技术力，并且有大量的实践经验可以有效地使用这些技术。寻找这样的人才是面试的真正目的，而这道题目我使用了很长一段时间。

期待

通过本文的阅读，可能你已经看出来这道题目也被泄露了。从那以后，我还用过几个问题，根据我的心情和早期的候选人提出的问题挑一个（一直问一个问题很无聊）。其中有些问题仍在使用，所以我会保守秘密，但有些已经没人用了！所以，你可以期待在今后的文章中看到这些题目。

原文：

https://medium.com/@alexgolec/google-interview-problems-synonymous-queries-36425145387c

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

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

推荐阅读

• 为何Google将几十亿行源代码放在一个仓库？

• 熬夜写代码，不如换女装入GitHub获上千Star？

• Python告诉你绝不知道的1983-2018春晚

• 一万多条拼车数据，看春运的迁徙图

• 4个最受欢迎的大数据可视化工具！

• 直击达沃斯：区块链是好技术，比特币一文不值，为什么？

• 年薪 10 万的程序员，如何积累人生的第一个 100 万？

• 苹果开撕 Facebook、Google！

• 嫁人当嫁程序员

点击“阅读原文”，打开CSDN APP 阅读更贴心！