谷歌面试问题被解构：骑士拨号器

这是我在一系列帖子中分享的第二个帖子，在这些帖子中，我借鉴了我在谷歌担任工程师和面试官的经验，分享了我对科技公司面试候选人的建议。如果您还没有，请看一下本系列的简介。

在我开始之前，先声明一下：虽然面试候选人是我的职业职责之一，但这个博客代表了我的个人观察、我的个人轶事和我的个人观点。请不要把这误认为是谷歌、Alphabet或任何其他人或组织发表的或关于谷歌、Alphabet或任何其他人或组织的任何形式的官方声明。

这是我在采访生涯中使用的第一个问题，也是第一个泄露并被禁止的问题。我喜欢它，因为它击中了许多甜蜜点：

它有许多解决方案，每个解决方案都需要不同程度的算法和数据结构知识。此外，一点点的洞察力也会有很大的帮助。

每种解决方案都可以在相对较少的行中实现，这使得它非常适合于时间有限的环境。

如果你是一名学生或以其他方式申请技术工作，我希望你读完这篇文章后会更好地理解面试问题会带来什么。如果你是一名面试官，我想分享一下我的思维过程和面试风格，这样可以更好地告知其他人并征求意见。

注我将用Python编写代码。我喜欢Python，因为它易学、紧凑，并且有一个绝对庞大的标准库。应聘者也喜欢它：即使我们没有语言限制，我面试的90%的人都使用Python。另外，我使用Python3是因为现在是2018年。

想象一下，你把一个骑士棋子放在电话拨号盘上。该棋子以大写的“L”字形移动：先水平走两步，然后垂直走一步，或者水平走一步，然后垂直走两步：

假设你只用骑士能做的跳数来拨打键盘上的按键。每次骑士落在一个键上，我们就拨那个键，然后再跳一跳。起始位置视为已拨打。

您可以从特定的起始位置在N跳中拨打多少个不同的数字？

我进行的每一次面试基本上都分为两个部分：首先我们找到一个算法解决方案，然后候选人用代码实现它。我说“我们”找到一个解决方案是因为我不是一个沉默的旁观者：45分钟不是在最好的情况下设计和实现任何事情的大量时间，更不用说在压力下了。我让应聘者在讨论、产生想法、解决问题实例等方面发挥带头作用，但我非常乐意推动正确的方向。候选人越好，我给出的暗示就越少，但我还没有见过根本不需要我提供意见的候选人。

我应该强调这一点，因为这很重要：作为一名面试官，我不会袖手旁观，眼睁睁地看着人们失败。我想写尽可能多的正面反馈，我会尽量给你机会，让我写一些关于你的好东西。暗示是我表达“好的，我要把这个部分给你，但只有这样，你才能继续前进，向我展示你在问题的其他部分有什么。”

话虽如此，您听到问题后的第一个行动应该是走到白板前，手动解决问题的小实例。永远不要一头扎进代码里！解决小实例可以让您发现模式、观察到的情况和边缘情况，还有助于在您的头脑中明确解决方案。例如，假设您从6开始，需要进行两跳。您的序列将是…。

…。总共有六个序列。如果你正在跟随，试着拿出一支铅笔和一张纸，然后推导出这些。这不能很好地转化为博客文章，但相信我，当我说手工解决问题有一种神奇的东西时，它会带来更多的洞察力，而不仅仅是盯着它静静地思考。

说了这么多，你的脑海里可能已经形成了一个解决方案。但是在我们到达那里之前，…。

当我开始使用这个问题时，我感到惊讶的是，考生经常被困在计算我们可以从给定位置(也称为邻居)跳到的钥匙上。我的建议是：当有疑问的时候，写一个空的占位符，然后问面试官你是否可以稍后实施它。这个问题的复杂性不在于邻居计算；我关注的是您如何计算完整的数字。花在邻居计算上的任何时间实际上都是浪费的。

我会接受“让我们假设有一个函数可以给我提供邻居”以及下面的存根。当然，我可能会要求您稍后加倍执行，但前提是我们有时间。您可以简单地像这样编写一个存根，然后继续：

此外，要求使用存根并不会造成太大损失：如果问题的复杂性在其他地方，我会允许这样做。如果没有，我会要求您实际实现它。我不介意考生没有意识到问题的复杂性在哪里，特别是在他们可能没有充分探索问题的早期阶段。

对于此处的Neighbors函数，假设它不会更改，您只需创建一个Map并返回适当的值即可：

Neighbors_MAP={1：(6，8)，2：(7，9)，3：(4，8)，4：(3，9，0)，5：tuple()，#5没有邻居6：(1，7，0)，7：(2，6)，8：(1，3)，9：(2，4)，0：(4，6)，}def Neighbors(Position)：返回Neighbors_map[位置]。

不管怎样，继续解决问题。也许您已经注意到，这个问题可以通过枚举所有可能的数字并计数来解决。您可以使用递归生成以下值：

定义YIELD_SEQUENES(STARTING_POSITION，NUM_HOPS，SEQUENCE=NONE)：如果SEQUENCE为NONE：SEQUENCE=[STARGING_POSITION]如果num_hops==0：邻居(STARTING_POSITION)中的屈服序列返回(STARTING_POSITION)：YIELD_SEQUENES+=1返回Num_SEQUENES)定义COUNT_SEQUENES(STARTING_POSITION，NUM_HOPS)：对于YILILE_SEQUENCE(STARTING_POSITION，NUM_HOPS)中的SEQUENCE：

这很管用，这是我在采访中看到的一个常见起点。然而，请注意，我们生成的数字从未实际使用过。这个问题要求计算数字，而不是数字本身。一旦我们数了一个数字，我们就再也不会去看它了。作为一般经验法则，我建议注意您的解决方案何时计算出它不使用的内容。通常你可以把它剪掉，然后得到一个更好的解决方案。我们现在就开始吧。

我们怎么能不生成电话号码就计算它们呢？这是可以做到的，但不能没有额外的洞察力。请注意，N跳中给定起始位置可生成的数字计数如何等于N-1跳中每个邻居可生成的跳数之和。从数学上讲，它是一个递归关系，看起来是这样的：

当您考虑一跳发生的情况时，这一点显而易见：6有3个邻居(1、7和0)，在零跳中，每个邻居都可以接通一个号码，因此您只能拨打三个号码。

你可能会问，一个人是如何获得这种洞察力的？如果您已经学习过递归，那么在白板上进行一些探索之后，这一点应该会变得很明显。许多练习过递归的考生立即注意到这个问题被分解成更小的子问题，这是一个完全暴露的问题。如果你正在接受我的采访，而你似乎不能达到这个洞察力，我通常会给出一些提示来帮助你做到这一点，包括如果督促失败，我会直接把它送出去。

一旦你有了这个洞察力，你就可以继续前进，再次解决这个问题。有许多实现使用了这一事实，但让我们从我在采访中最常看到的一种开始：朴素的递归方法：

从邻居导入邻居def count_equence(start_position，num_hops)：如果num_hops==0：为邻居中的位置(Start_Position)返回1 num_equence=0：num_equence+=count_equence(position，num_hops-1)如果__name__=='；__main__'；：print(count_equence(6，2))。

就这样!。将其与计算邻居的函数相结合，您就产生了一个有效的解决方案！在这一点上，你应该拍拍自己的背。如果你向下滚动，你会注意到我们还有很多地方要覆盖，但这一点是一个里程碑。提出任何可行的解决方案都会让你从数量惊人的候选人中脱颖而出。

下一个问题是您将经常从我这里听到的问题：此解决方案的Big-O复杂性是多少？对于那些不知道的人来说，Big-O复杂性(非正式地)是解决方案所需的计算量作为输入大小的函数增长的速率的一种简写。对于此问题，输入的大小是跳数。如果你对正确的数学定义感兴趣，你可以在这里阅读更多。

对于此实现，每个对count_equence()的调用至少递归调用Count_Sequence()两次，因为每个键至少有两个邻居。由于我们递归的次数等于所需的跳数，并且每次调用Count_Sequence()的次数至少翻了一番，因此我们的运行时复杂性至少是指数时间。

这太糟糕了。请求额外的跳数将使运行时间加倍(如果不是三倍的话)。对于像1到20这样的小数字，这是可以接受的，但是当我们要求越来越多的跳数时，我们就碰壁了。例如，500次跳跃需要在宇宙热死亡之后很久才能完成。

我们能做得更好吗？只用上面的数学关系，不用其他的，不是真的。不过，我喜欢这个问题的原因之一是，它具有层次分明的洞察力，可以产生越来越有效的解决方案。要找到下一个函数，让我们绘制出该函数进行的函数调用。让我们考虑COUNT_SEQUENCE(6，4)的情况。注为简洁起见，我使用C作为函数名：

您可能会注意到一些奇怪的事情：C(6，2)调用执行了三次，每次都执行相同的计算，并返回相同的值。这里的关键观点是这些函数调用重复，每次都返回相同的值。一旦计算了它们的结果，就不需要重新计算它们了。

如果你想知道如何才能做到这一点，最简单的方法是通过好的老式白板：抽象地盯着这个问题陈述是很好的，但我总是鼓励应聘者在黑板上抛出一个样本解决方案。解决这样的问题并像我上面所做的那样绘制树将看到您多次为C(6，2)编写子树，您一定会注意到这一点。这有时足以让候选人完全绕过解决方案1和2，直接跳到这个阶段。不用说，在你只有45分钟来解决问题的面试中，这是一大笔节省的时间。

有了这样的洞察力，我们该如何解决这个问题呢？我们可以使用Memoization(而不是Memoriization)，这基本上意味着我们记录我们以前看到的函数调用的结果，并使用这些结果而不是重做工作。这样，当我们在调用图中遇到不必要地重新计算整个子树的位置时，我们会立即返回已经计算的结果。下面是一个实现：

Def count_equence(start_position，num_hops)：cache={}def helper(position，num_hops)：if(position，num_hops)in cache：return cache[(position，num_hops)]if num_hops==0：返回1 Else：num_equence=0表示邻居(位置)中的邻居：num_equence+=helper(neighbor，num_hops-1)cache[(position，num_hops)]=num_Sequence返回Num_Sequence res=helper(start_position，num_hops)RETURN。

好的，现在的运行时复杂度(Big-O)是多少？这就更难回答了。对于以前的实现，计算运行时非常简单，只需计算递归函数被调用的次数，每次调用的次数总是两到三次。此时间计数更为复杂，因为递归调用由条件保护。从表面上看，没有明显的方法来计算函数调用。

我们可以通过查看缓存来解开这个谜团。每个函数调用的结果都存储在缓存中，并且只插入一次。这允许我们将问题重新表述为“缓存的大小如何随输入的大小增长？”假设缓存按位置和跳数设置关键字，并且恰好有10个位置，我们可以得出结论，缓存的增长与请求的跳数成正比。这遵循鸽子洞原理：一旦我们在缓存中有了位置和跳转计数的每个组合的条目，所有调用都将命中缓存，而不是导致新的函数调用。

线性时间！那还不错。事实上，这是值得注意的：添加一个简单的缓存将算法的运行时间从指数更改为线性。在我那台受人尊敬的老MacBook Air上，递归实现大约需要45秒才能运行20跳。该实现可以在大约50毫秒内处理500跳。一点也不差。

那我们就完事了，对吧？嗯，不完全是。这个解决方案有两个缺点，一个是主要的(ISH)，另一个是次要的。它的主要缺点是它是递归的。大多数语言对其调用堆栈的最大大小进行了限制，这意味着实现始终可以支持最大跳数。在我的机器上，它在大约1000跳之后失败。这是一个主要的限制，而不是一个主要的限制，因为任何递归函数都可以以迭代的方式重新实现，但这仍然是一个麻烦。至于次要限制，这实际上将我们引向下一个解决方案…。

当您从上面查看递归关系时，递归记忆解决方案的次要限制是显而易见的：

请注意，N跳的结果仅取决于具有N-1跳的呼叫的结果。同时，缓存包含每(非零)跳数的条目。我称这是一个小问题，因为它实际上不会造成任何真正的问题，因为缓存只随跳数线性增长。需要线性空间并不是世界末日，但效率仍然很低。

什么给予？同样，当您查看写出的解决方案和代码时，结果是显而易见的。请注意，代码从最大跳数开始，直接递归到最小跳数：

如果您将整个函数调用图想象为一种虚拟树，您很快就会看到我们正在执行深度优先遍历。这很好，它给出了一个适当的解决方案，但是它没有利用我上面指出的浅层依赖属性。

您是否可以改为执行广度优先遍历，即从顶部开始，仅在访问了N跳的函数调用后才“访问”N-1跳的函数调用？遗憾的是，没有。具有非零跳的函数调用的值绝对需要来自较小跳数的值，因此在到达零跳层并开始返回数字而不是其他函数调用之前，您不会得到任何结果(请注意，这里没有描述零跳层)。

但是，您可以颠倒顺序：只有在访问了N-1跳的层之后，才能访问N跳的层。你们中学习或正在学习离散数学的人将认识到归纳的所有必要成分：我们知道零跳函数调用的值始终为1(基本情况)。我们还知道如何使用递归关系(归纳步骤)组合N-1个跳值以获得N个跳值。我们可以从零跳的基本情况开始，归纳出所有大于零的值。下面是一个实现：

定义COUNT_SEQUENCES(start_position，num_hops)：PIRE_CASE=[1]*10 CURRENT_CASE=[0]*10 CURRENT_Num_Hops=1而CURRENT_Num_Hops<；=Num_Hops：CURRENT_CASE=[0]*10 CURRENT_NUM_HOPS+=1对于范围(0，10)中的位置：对于邻居(位置)：CURRENT_CASE[位置]+=PERVICE_CASE[邻居]PERVICE_CASE=CURRENT_CASE[START_POSITION]

那么，这个版本还有什么比递归、深度优先解决方案更好的呢？不是很多，但也有一些好处。首先，它不是递归的，这意味着它可以在不崩溃的情况下运行极大的值。其次，它使用常量内存，因为它只需要两个固定大小的数组，而不需要内存解决方案不断增长的缓存。最后，它仍然是线性时间：我可以在不到20秒的时间内计算20万跳。

所以我们说完了，对吧？差不多吧。在求职面试中设计并实施线性时间、恒定空间的解决方案是一个非常好的结果。当我使用这个问题时，我给提供了动态编程解决方案的应聘者一个极好的评分。

你可能会问，其他的解决方案呢？不幸的是，不可能给抽象的候选人打分。面试是一件混乱的事情；他们可能开始得很晚，人们可能会紧张，而且他们经常在会议后期得出见解和解决方案，让他们几乎没有时间对任何事情进行编码。还有一场对话正在进行：我关注应聘者如何很好地沟通他们的想法，并将想法和反馈整合在一起。我总是在做出录用/不录用建议之前考虑这些因素，你不能抽象地这么做。

我将把重点放在我想要说的事情上，而不是潜在的推荐。在评估算法和数据结构时，我想这样说：“TC(候选)探索了问题并产生了解决所有边缘情况的解决方案，并在发现其缺点时改进了解决方案。最终，他们得出了一个最优解决方案。“。我还想说，“TC为解决方案选择了适当的数据结构，并正确回答了有关其解决方案的运行时和空间需求的大问题。”

在评估编码时，我的理想陈述是“TC快速而简明地将他们的想法转换成代码。该代码使用标准语言结构，并且易于阅读。所有的边缘情况都得到了解决，TC检查了他们的代码以进行调试并验证其正确性。“。对于入门级职位，如果有某种测试，我会给他们加分，但更有经验的职位，我会惩罚那些至少没有列出相关测试用例的应聘者。

至于进展速度，我很乐意说：“TC推动了问题的解决过程：他们开发了大部分自己的解决方案，并且能够识别和解决不足之处，而不需要我指出它们。TC只需要最少的提示就能让他们朝着正确的方向前进。

在我的书中，任何我能说出这些话的人都会得到“强有力的聘用”。然而，“雇佣”和“学习雇佣”也是积极的代言。如果你在某一方面表现欠佳，但在另一方面大放异彩，那么我可能仍然可以证明一个积极的推荐是合理的。

这个问题可能看起来令人望而生畏，特别是考虑到这个帖子已经变得如此之久。不过，请记住，这篇帖子故意比任何面试都要彻底得多。我不是把我期望看到的一切都罗列出来，我只是把问题分解成最细微的细节，不留任何遗漏。

为此，这里列出了这个问题涵盖的技能和你应该养成的习惯：

总是从手工解决问题的一个小实例开始。在这个问题中，当您手动解决问题时，函数调用的递归关系和重复变得更加明显。

当您的解决方案正在计算您不需要的东西时要注意，比如朴素的计数解决方案如何生成序列，但实际上并没有使用它们。减少不必要的计算通常可以提供更简单的解决方案，如果不能为更有效的解决方案打开大门的话。

了解您的递归。它在大多数产品中几乎毫无用处。

.