作者| Alex Golec
译者|说明灯
写在前面
免责条款：作为Google的工程师和面试官，面试候选人是我的职责之一。
这篇文章仅代表我个人的经验和观点。请不要错误地将它与谷歌、Alphabet 或其他人或组织的任何形式的官方声明联系在一起。这是我在面试生涯中使用的第一个面试题，也是第一个被泄露和禁用的面试题。我很喜欢这个面试题，因为它有很多有趣的地方：
- 它很容易表述和理解。
- 它有很多解决方案，每个解决方案都要求不同程度的算法和数据结构知识。
- 每个解决方案都可以通过相对较少的代码行来实现，非常适合用在时间紧凑的面试场景中。
如果你是学生或正在申请技术工作，我希望你能够怀着更好地了解面试题的期望来阅读本文。如果你是面试官，我想分享我的思考过程和面试方法，并征求反馈建议。
我将用 Python 编写代码。我喜欢 Python，因为它易学、紧凑，拥有庞大的标准库。候选人也喜欢它：我们其实没有在语言方面做出限制，但在我面试的候选人当中有 90％使用 Python。我也使用 Python 3 吧，毕竟是 2018 年了。
面试题
试想一下，你将骑士放在电话拨号盘上。骑士按照大写“L”的形状移动：水平两步，然后是垂直一步，或者水平一步，然后垂直两步：
假设你只按照骑士的步法来按键盘上的按键。每当骑士落在一个按键上，我们就按那个按键，然后继续下一跳。起始位置被标记为已按过。
从某个特定的位置开始，在 N 跳内可以拨打多少个不同的号码？
讨 论
我的面试基本上分为两部分：首先，我们会找到一个算法解决方案，然后由候选人使用代码实现。我之所以说是“我们”找到了一个解决方案，那是因为我不是一个闭着嘴巴的旁观者：在最好的情况下，用 45 分钟设计和实现一个算法并不算长，这还没有把面试的压力考虑在内。我让候选人来主导我们的讨论，产生想法，解决问题，我也很乐意为他们提供一些提示。候选人越好，我提供的提示就越少，但我还没有见过哪个候选人完全不需要我的提示。
有一点我需要强调，因为这很重要：作为一名面试官，我不会干坐着看着候选人失败。我想尽可能多地为候选人提供积极反馈，就好像在说：“我会给你一点提示，这样你才能继续向我展示你对问题其他部分的理解”。
在听完面试题后，你的第一个反应是走到白板前面开始解决小规模问题。先不要急着写代码！通过解决小规模问题，你可以找到模式和边界情况，而且有助你在脑子里形成解决方案。例如，假设你从 6 开始，并且需要跳两次。你的数字序列将是……
- 6–1–8
- 6–1–6
- 6–7–2
- 6–7–6
- 6–0–4
- 6–0–6
总共六个序列。你可以尝试使用铅笔和纸张写出这些序列。可能在文章里不能很好地表达出来，但相信我，手动解决问题可以获得更多的见解，而不只是盯着它看或静静地思考。
不管怎样，你可能已经在脑海中形成了一个解决方案。但在那之前......
第 0 级：下一跳
当我开始使用这个面试题时，让我感到吃惊的是候选人经常卡在如何计算从给定位置可以跳到的按键（也就是邻居）这个问题上。我的建议是：如果有疑问，可以先放一个空的占位符，并问面试官是否可以后面再回过头来解决。这个问题的复杂性不在于计算邻居，我在意的是候选人是如何计算出所有的号码的。计算邻居其实是在浪费时间。
我可以接受“让我们假设有一个可以返回所有邻居的函数”这样的做法。当然，我可能会要求你稍后回来实现它，但前提是我们要有时间。你可以简单地像这样写一个空函数，然后继续：
def neighbors(position): ...如果你要求使用函数桩也没问题，这样并不会让你失分太多：如果问题的复杂性在于其他地方，我会允许这样做。否则的话，我会要求你实现它。我不介意候选人意识不到问题的复杂性在哪里，因为在刚开始时，他们可能还没有充分探究过问题。
至于返回所有邻居的函数，我们假设它永远不会发生改变，你可以简单地创建一个 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): return NEIGHBORS_MAP[position]第 1 级：递归生成号码
现在回到解决方案上来。也许你已经注意到，这个问题可以通过枚举所有可能的号码并计算它们的个数来解决。你可以使用递归来生成这些值：
def yield_sequences(starting_position, num_hops, sequence=None): if sequence is None: sequence = [starting_position] if num_hops == 0: yield sequence return for neighbor in neighbors(starting_position): yield from yield_sequences( neighbor, num_hops - 1, sequence + [neighbor]) def count_sequences(starting_position, num_hops): num_sequences = 0 for sequence in yield_sequences(starting_position, num_hops): num_sequences += 1 return num_sequences这么做是可以的，候选人在面试中经常会这么做。但请注意，我们生成了号码，但并没有使用它们。这个问题问的是号码的个数，而不是号码本身。在计算了号码的个数后，我们就再也不会用到这些号码。根据经验，我建议你注意一下你的解决方案是否会计算用不到的东西。通常你可以使用更好的解决方案。
第 2 级：不通过计算个数得到号码个数
我们如何在不生成电话号码的情况下计算电话号码的个数？我们可以做到，但需要额外的算法。请注意，计算从给定起始位置在 N 跳之内生成号码的个数等于它的每个邻居在 N-1 跳内生成跳数的总和。通过数学的方式来表示这种递归关系看起来像这样：
如果只考虑一跳，那么就很直观：6 有 3 个邻居（1、7 和 0），在零跳时，每个邻居只能达到一个数字，因此你只能拨打三个号码。
你可能会问，这是怎么想到的？如果你学过递归，那么在白板上画一画你就会知道了。很多了解递归的候选人马上就知道这个问题可以被分解为较小的子问题。如果我是在面试你，而你想不到这点，我通常会给出提示，直到候选人实在想不出来才彻底放弃。
在想到这个办法之后，就可以继续解决问题。有很多代码实现都是基于这个想法，但我想从我在面试中最常见的那个开始——最初级的递归方法：
from neighbors import neighbors def count_sequences(start_position, num_hops): if num_hops == 0: return 1 num_sequences = 0 for position in neighbors(start_position): num_sequences += count_sequences(position, num_hops - 1) return num_sequences if __name__ == '__main__': print(count_sequences(6, 2))将这段代码与计算邻居的函数相结合，你就得到了可行的解决方案！这个时候，你应该给自己点个赞。如果你继续深入进去，你会发现，我们仍然有很多需要解决的问题，但现在可以说是达到了一个里程碑。找到这个解决方案已经可以让你脱颖而出了。
接下来的问题是：这个解决方案的 Big-O 复杂性是什么？如果有人不知道 Big-O 是什么，它是（非正式地说）算法所需计算量随输入大小变化的速率的一种简单的表示方式。对于这个面试题，输入的大小就是跳数。
对于上面的实现，每次调用 count_sequences() 都会递归调用 count_sequences() 至少两次，因为每个键至少有两个邻居。由于我们递归的次数等于所需的跳数，并且每次调用 count_sequences() 的次数至少翻倍，因此运行时复杂度至少是指数级的。
这样的性能很糟糕。每增加一个跳数，运行复杂度至少会加倍。对于较少的跳数，比如从 1 到 20，尚可接受，但对于比较大的跳数就不行了。例如，如果跳数是 500，不知道要等到猴年马月才能算完。
第 3 级：memoization
我们可以做得更好吗？只使用上面的数学关系估计不行。不过，我之所以喜欢这个面试题，是因为它可以使用更多更有效的解决方案来解决。为了找到下一个解决方案，我们先把函数的调用结构画出来。我们先考虑 count_sequences(6,4) 的情况。注意，我使用 C 表示函数名：
你可能会注意到一些奇怪的事情：C(6,2) 被调用了三次，每次执行的是相同的计算，并返回相同的值。所以这些函数调用是重复的，而且每次返回相同的值。在计算完一个结果后，应该是不需要重新再算一次的。
如果你想知道怎样才会想到这一点，最简单的办法就是使用白板：光盯着问题看也是可以的，但我总是鼓励候选人在白板上画出样本解决方案。像上面那样画出树结构，你就会发现里面有多个 C(6,2)，你肯定会注意到的。有时候，这足以让候选人完全绕过解决方案 1 和 2，直接跳到这里。在一个只有 45 分钟的面试中，这无疑为你节省了大量的宝贵时间。
那么，接下来我们该如何解决这个问题？我们可以使用 memoization（不是 memorization），这意味着我们需要记录之前见过的函数调用结果，并重用它们，而不是重新计算结果。当我们在调用图中遇到一个没有必要重新计算整个子树的位置时，立即返回之前已经计算过的结果。这是一种实现：
def count_sequences(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: return 1 else: num_sequences = 0 for neighbor in neighbors(position): num_sequences += helper(neighbor, num_hops - 1) cache[ (position, num_hops) ] = num_sequences return num_sequences res = helper(start_position, num_hops) return res那么现在的运行时复杂性（Big-O）是多少？这很难回答。对于之前的实现，计算运行时复杂度与计算递归函数被调用的次数一样简单，每个调用总是两到三次。现在要计算次数比较复杂，因为递归调用受条件限制。从表面上看，没有明确的方法可用于计算函数调用次数。
我们可以通过检查缓存来解开这个谜团。每个函数调用的结果都保存在缓存中，并且它只被插入一次。于是，问题可以变成“缓存的大小如何随输入的大小增长？”因为缓存是由按键位置和跳数组成的，并且正好有十个按键位置，所以我们可以认为缓存增长与请求的跳数成正比。这遵循的是鸽子洞原理：对于每个按键位置和跳数的组合，如果在缓存中都有一个对应条目，那么所有调用都会使用缓存而不是重新调用函数。
这是线性时间！不错。添加一个简单的缓存将算法的运行复杂度从指数级变为线性的，这其实是非常棒的。在我的老款 MacBook Air 上，递归实现大约需要 45 秒才能运行 20 个跳数，而新的实现可以在大约 50 毫秒内处理 500 个跳数。一点也不差。
所以我们已经做到最好了吗？还不是。这个解决方案有两个缺点。一个是它是递归的。大多数语言都限制了调用栈的大小，这意味着每种实现可以支持的最大跳数都会有一个上限。在我的机器上，在执行大约 1000 个跳数时就失败了。不过，任何递归都可以实现成迭代，但很麻烦。至于另一个缺点，它将导致下一个解决方案的出现……
第 4 级：动态规划
如果你看一下之前的递归关系，你会发现递归记忆解决方案的缺点很明显：
请注意，N 跳的结果只取决于 N-1 跳的调用次数。同时，缓存中包含了每种（非零）跳数。我认为这是一个小问题，因为它实际上不会导致任何实际问题，因为缓存只会随跳数线性增长。不过，使用线性空间虽然不是导致世界末日，但仍然不是最高效的。
当你在白板上画出函数调用结构时，结果就很清楚了。请注意，跳数从最大递归减到最小：
如果你将整个函数调用图想象为一棵虚拟树，你会发现，我们正在进行深度优先遍历。这也是一个合适的解决方案，但它没有利用上面指出的浅依赖。
是否可以使用广度优先遍历，从顶部开始，并只在调用过 N 跳数的函数之后才能调 N-1 跳数的函数？可惜的是，不行。非零跳数函数返回的值依赖较小跳数的值，因此，在到达零跳数层之前，将不会得到任何结果。
但是，你可以将顺序颠倒过来：只在调用了 N-1 跳数的函数之后，才能调用 N 跳数的函数。那些学过或正在学习离散数学的人应该知道归纳法：我们知道，零跳数函数的值总是 1。我们还知道如何使用递归关系（归纳步骤）将 N-1 跳的值组合成 N 跳的值。我们可以从零跳数开始，并归纳所有大于零的值。这是一种实现：
def count_sequences(start_position, num_hops): prior_case = [1] * 10 current_case = [0] * 10 current_num_hops = 1 while current_num_hops <= num_hops: current_case = [0] * 10 current_num_hops += 1 for position in range(0, 10): for neighbor in neighbors(position): current_case[position] += prior_case[neighbor] prior_case = current_case return current_case[start_position]那么这个版本比递归深度优先解决方案更好吗？不会好很多，但肯定会好一些。首先，它不是递归的，这意味着它可以运行非常大跳数而不会崩溃。其次，它使用固定的内存，因为它只需要两个固定大小的数组，而不是像 memoization 那样缓存会不断增长。最后，它仍然是线性的：我可以在不到 20 秒的时间内计算 200,000 跳数。
评 价
所以该结束了，对吧？差不多。在面试中设计和实现线性时间、恒定空间的解决方案是一个非常好的结果。我总是会给那些能够提供动态规划解决方案的候选人一个很好的评价。
你可能会问，那么其他解决方案呢？我只能说，我无法对抽象的候选人做出评价。面试不会按照你预想的那样一成不变，候选人可能来晚了，他们可能会感到紧张，他们经常到了后面才想到解决方案，留给他们编写代码的时间就不多了。我还会关注候选人如何沟通他们的想法，并将想法和反馈结合起来。在建议是否让候选人通过之前，我会考虑这些因素。
在评价算法和数据结构时，我会说：“候选人探究了这个问题，并提出了可以解决所有边界情况的解决方案，并在发现缺点时改进了解决方案。最后，他们得出了最佳的解决方案”。我还会说：”候选人为解决方案选择了合适的数据结构，并正确解释了运行时复杂度和空间复杂度”。
在评价候选人的编码能力时，我的理想陈述应该是：“候选人快速而简洁地将他们的想法转化为代码。代码使用了标准的语言结构，可读性强。所有边界情况都考虑到了，候选人仔细检查代码，确保它的正确性”。对于入门级岗位，如果候选人提供了测试用例，我会给他们额外的奖励分，但对于需要更多经验的岗位，我会惩罚那些没有列出相关测试用例的候选人。
关于面试进展的速度，我喜欢说：“候选人推动了解决问题的过程：他们给出了自己的解决方案，并且在我没有帮忙指出的情况下识别出缺点，并加以改进。候选人只需要很少的提示就可以让解决问题朝着正确的方向前进”。
总 结
这里列出了这个面试题涵盖的技能和你应该要去养成的习惯：
- 先手动解决小规模问题。对于这个面试题，当你手动画出函数调用结构时，递归关系和重复的函数调用就变得更加明显。
- 注意不要计算不需要用到的东西，例如那个初级解决方案生成号码，但实际上用不到它们。减少不必要的计算通常可以提供更简单的解决方案。
- 了解递归。递归在大多数生产代码中几乎是没有用的，因为它可能会爆栈，但却是一种非常强大的算法设计策略。递归解决方案通常可以进行调整和改进：指数级复杂度解决方案与线性最优 memoization 解决方案之间的差异其实是最小的。
- 了解 Big-O！在面试过程中，你很有可能会在某个时间点被问到这个问题。
- 总是想方设法找到 memoization 解决方案。如果你的函数是确定性的，并且会使用相同的输入多次调用它，那么可能可以从 memoization 解决方案中受益。
- 查找并写出递归关系。对于这个面试题，把递归关系写出来，就可以发现 N 跳的计数只取决于 N-1 跳的计数。
但等等，事情还没有结束！
事情似乎就这么结束了，但事实证明，这个问题还有另外一个解决方案。在我所有的面试中，我从未见过有人提出这个解决方案。我甚至都不知道它的存在，直到我的一位同事面带惊讶地回到他的办公桌前，然后告诉我们，他刚刚面试了一个他认为是有史以来最好的候选人。
但我想先把这个对数级复杂度的解决方案留给读者去想……
英文原文
