共计 3404 个字符，预计需要花费 9 分钟才能阅读完成。
本文翻译自 Google 工程师 / 面试官 Alex Golec 的文章：Google Interview Questions Deconstructed: The Knight’s Dialer；起源：实验楼，翻译：实验楼扫地阿姨，原文：https://medium.com/@alexgolec…
作为一名 Google 的工程师和面试官，明天是我第二次发文分享科技公司面试倡议了。 这里先申明：本文仅代表我集体的察看、意见和倡议。请勿当作来自 Google 或 Alphabet 的官网倡议或申明 。
上面这个问题，是我面试生涯中第一个问题；也是第一个被透露进去，以及第一个被禁掉的问题 。我喜爱这个问题，因为它有以下长处：
- 问题很容易表述分明，也容易了解。
- 这个问题有多个解。每个解都须要不同水平的算法和数据结构常识。而且，还须要一点点远见。
- 每个解都能够简略几行代码实现，非常适合有工夫限度的面试。
如果你是学生，或者求职者，我心愿你通过本文可能理解到，面试问题个别会是怎么样的。如果你也是面试官，我很乐意分享本人在面试中的格调和想法，如何更好地传播信息、征求意见。
留神，我将应用 Python 写代码；我喜爱 Python 因为它易学，简洁，而且有海量的规范库。我遇到的很多面试者也很喜爱，只管咱们推广“不限定语言”的政策，我面试 90% 的人都用 Python。而且，我用的 Python 3 因为，托付，这都 2018 年了。
问题
把你的手机拨号页设想成一个棋盘。棋子走只能走“L”形态，横着两步，竖着一步；或者竖着两步，横着一步。
当初，假如你拨号只能像棋子一样走“L”形态。每走完一个“L”形拨一次号，起始地位也算拨号一次。问题：从某点开始，在 N 步内，你能够拨到多少不同的数字？
探讨
每次面试，我根本都会分成两个局部：首先咱们找出算法计划，而后让面试者在代码中实现。我说“咱们找出算法计划”，因为这个过程我不是缄默的独裁者。在这样低压下，设计并实现一种算法，45 分钟工夫并不算短缺。
我通常会让面试者主导探讨，让他们去产生想法，我嘛，就在旁边，时不时地透露一点点“天机”。面试者们能力越强，我须要透露的“天机”就越少；然而目前为止，我还没遇到一点都不须要我提醒的面试者。
有一点我想强调一下，重要的很 ：作为面试官，我的职责可不是坐那看着大家失败搞砸。我想要给大家侧面的反馈，给大家机会去展示大家最善于的点。给他们提醒，就像是在说：呐，这一步路我给你铺上，但这只是为了让你展现给我，你在前面的路上能走的更远。
当听完面试官的问题，你应该做什么？ 切记不要立即就去写代码，而是在黑板上试着一步一步去合成问题。合成问题可能帮忙你寻找到法则，特例等等，逐步在大脑中造成解决方案。比方，你当初从数字 6 开始走，能走 2 步，会有如下组合：
6–1–8
6–1–6
6–7–2
6–7–6
6–0–4
6–0–6
一共有 6 种组合。你能够试着用铅笔在纸上画，置信我，有时候入手去解决问题会产生意想不到的事，比你盯着在脑袋里想更神奇。
怎么样？你脑海里有计划了吗？
第 0 阶：达到下一步
应用这个问题面试，最让我诧异的是，太多人都卡在了计算从某个特定点跳出时，一共有多少种可能，即邻 Neighbors。我的倡议是：当你不确定时，先写个占位符，而后申请面试官是否晚点实现这一部分。
这个问题的复杂性并不在 Neighbors 的计算；我在意的是你如何计算出总数。所有破费在计算 Neighbors 上的工夫其实都是节约。
我会承受“让咱们假如有一个函数能给出我 Neighbors”。当然，我也可能会让你前面有工夫再去实现这一步，你只须要这样写，而后持续。
而且，如果一个问题的复杂性不在这里，你也能够问我能不能先略过，个别我都是容许的。我倒是不介意面试者不晓得问题的复杂性在哪里，尤其刚开始他们还没有全面理解问题的时候。
至于 Neighbors 函数，因为数字永远不变，你能够间接写一个 Map 而后返回合乎的值。
第 1 阶：递归
聪慧的你可能留神到了，这个问题能够通过枚举出所有符合条件的数字，而后计算。这里能够应用递归产生这些值：
这个办法能够，而且是在面试中最广泛的办法。然而请留神，咱们产生了这么多数字却并没有应用他们，咱们计算完他们的个数后，就再也不去碰了。所以我倡议大家遇到这种状况，尽量去想一下看有没有更好的计划。
第 2 阶：数不数数
怎么在不产生这些数字的状况下计算出个数？能够做到，但须要一点点机智。留神从特定点跳出 N 次可能拨到的数字个数，等于从它所有邻近的点跳出 N - 1 次可能拨到的数字个数的总和。咱们能够表白为这样的递归关系：
如果你这样想，就会很直观了，跳一次时：6 有 3 个 neighbors（1，7 和 0），当跳 0 次时每个数字自身算一次，因而每次你只能拨到 3 个数字。
怎么会产生这样机智的想法？其实，如果你学了递归，并且在黑板上好好钻研，这一点就会变得不言而喻。这样你就能持续去解决这个问题，实际上就这一点就有多种实现办法，上面这个便是面试中最常见的：
就是这样，联合这个函数计算出 neighbors 就能够了。这时候，你就能够捏捏肩膀劳动下了，因为到这里，你曾经刷掉很多人了。
接下来这个问题我常常问：这个计划的算法实践速度如何？在这个实现中，每次调用 count_sequences() 都会递归地调用 count_sequences() 至多 2 次，因为每个数字至多有 2 个 neighbors。这样会导致 runtime 成指数增长。
对于跳 1 次到 20 次这样的次数还能够，然而到更大的数字，咱们就要碰壁。500 次可能就须要整个宇宙的热量来实现运算。
第 3 阶：记忆
那么，咱们能做的更好么？应用下面的办法，并不能。我喜爱这个问题，也是因为他能一层一层带出大家的智慧，找到更高效的办法。为了找到更好的办法，让咱们看下这个函数是怎么调用的，以 count_sequences(6, 4) 为例。留神这里用 C 作为函数名简化。
你可能留神到了，C(6, 2) 运行了 3 次，每次都是同样的运算并返回同样的值。这里最要害的点在于这些反复的运算，每次你应用过他们的值之后，就没有必要再次计算。
怎么解决这个问题？记忆。咱们那些雷同的函数调用和后果，而不是让他们反复。这样，在前面咱们就能够间接给出之前的后果。实现办法如下：
第 4 阶：动静设计
如果你再看看后面的递归关系，就会发现递归记忆的计划也有一点局限性：
留神跳 N 次的后果仅仅取决于跳 N - 1 次后调用的后果。同时，缓存中蕴含着每个次数的所有后果。我之所以说这是个小局限，因为的确不会造成真的问题，当跳的次数增长时，缓存也只是线性增长。然而，毕竟，这还是不够高效。
怎么办？让咱们再来看一看计划和代码。留神，代码中是从最大的次数开始，而后间接递归到最小的次数：
如果你把整个的函数调用图设想成某种虚构的树，你就会发现咱们在执行深度优先策略 。这并没有什么问题，然而它没有利用到浅依赖这个属性。
如何实现广度优先策略？ 这里就是一种实现办法：
这个版本比后面递归版好在哪里？其实并没有好很多，然而这个不是递归的，因而即便解决超大数据也很难解体。其次，它应用的是常量内存；最初，它仍旧是线性增长，即使解决 200000 次跳也只用不到 20 秒。
评估
到这里，根本就算完了。设计并实现一个线性时的、产量内存的计划，在面试中是十分好的后果。在我的面试中，如果有面试者写出动静编程设计，我通常会给他一个极高的评估：excellent！
当评估算法和数据结构的时候，我常常会说 ：面试者对问题意识清晰，并且思考到各方面的可能，当指出有余时他也能迅速改良并进步；最终，实现了一个不错的解决方案。
当评估代码的时候，我最现实的说法是 ：面试者迅速并准确地把想法转化为了代码；代码构造谨严，容易浏览。所有非凡状况都有概括，并且认真查看测试了代码，确保了没有 Bug。
总结
我晓得，这个面试问题看上去仿佛有点吓人，尤其整个解释下来十分繁琐。但本文的目标和面试中齐全不一样。 最初，一点面试相干的技巧，以及一些好的习惯，分享给大家 ：
- 肯定要手动来，从最小的问题开始解决。
- 当你的程序在做无用的运算时，肯定要留神去优化。缩小不必要的运算可能让你的解决方案更加简洁，说不定能因而发现更高效的计划。
- 理解你的递归函数。在理论生产中，递归经常很容易出问题，但它仍旧是十分弱小的算法设计和策略。递归计划也总是有优化和进步的余地。
- 要经常去寻找记忆的机会。如果你的函数是目的性的，并且会屡次调用雷同的值，那么就试着去存储起来。
