如何在面试生涯中使用的第一个面试题？

如果您是学生或正在申请技术工作，我希望您在阅读本文时希望能更好地理解面试问题。 如果您是面试官，我想分享我的思维过程和面试方法并寻求反馈。

我将使用 编写代码。 我喜欢它，因为它易于学习、紧凑，并且拥有庞大的标准库。 应聘者也喜欢它：我们并没有真正限制它的语言，但我面试的 90% 的应聘者都使用它。 我也会用3，毕竟是2018年了。

面试问题

想象一下您将骑士放在电话拨号盘上。 骑士的移动方式为大写“L”：两横步，然后一纵步，或一横步，然后两纵步：

假设你只是按照骑士的步骤按下键盘上的按键。 每当骑士落在按钮上时，我们就按下该按钮并继续进行下一个跳跃。 起始位置标记为按下。

从特定位置出发的 N 跳内可以拨打多少个不同的号码？

讨论

我的面试基本上分为两个部分：首先，我们找到一个算法解决方案，然后由候选人使用代码来实现。 我之所以说“我们”找到了解决方案，是因为我不是一个闭嘴的旁观者：在最好的情况下，45 分钟设计和实现算法并没有那么长； 考虑面试的压力。 我让候选人主导我们的讨论，产生想法，解决问题，我也很乐意为他们提供建议。 候选人越好，我提供的提示就越少，但我还没有遇到一个根本不需要我提供任何提示的候选人。

我需要强调这一点，因为它很重要：作为面试官，我不会坐视候选人失败。 我想向候选人提供尽可能多的积极反馈，就好像在说：“我要给你一点提示，这样你就可以继续向我展示你对问题其他部分的理解”。

听完面试问题后，你的第一直觉是走到白板前，开始解决小规模的问题。 先别急着写代码！ 通过解决小规模问题，您可以找到模式和边缘情况，并帮助您在头脑中制定解决方案。 例如，假设您从 6 开始，需要跳两次。 你的数字序列将是...

总共六个序列。 您可以尝试使用铅笔和纸写出这些序列。 也许文章中不能很好地表达，但是相信我，通过手动解决问题，你可以获得更多的见解，而不是仅仅盯着它或默默思考。

无论如何，您可能已经想到了解决方案。 但在那之前……

0级：下一跳

当我开始使用这个面试问题时，我很惊讶应聘者经常陷入如何计算从给定位置跳转到的键（又称邻居）的困境。 我的建议：如果有疑问，请留一个空的占位符，然后询问面试官是否可以稍后再回来讨论。 这个问题的复杂性不在于计算邻居，我关心的是候选人如何计算所有数字。 数邻居是浪费时间。

我同意“假设有一个返回所有邻居的函数”。 当然，我可能会要求你稍后回来实施它，但前提是我们有时间。 您可以简单地编写一个像这样的空函数并继续：

如果你要求函数存根也没关系，它不会花费你太多的分数：如果问题的复杂性在于其他地方，我会允许它。 否则，我会要求你实施它。 我不介意候选人是否没有意识到问题的复杂性在哪里，因为他们在刚开始时可能没有充分探索问题。

至于返回所有邻居的函数，假设它永远不会改变，您可以简单地创建一个映射并返回适当的值：

第 1 级：递归生成数字

现在回到解决方案。 您可能已经注意到，这个问题可以通过枚举所有可能的数字并计算它们来解决。 您可以使用递归来生成这些值：

这样做是可以的，候选人在面试时经常这样做。 但请注意，我们生成了这些数字，但并未使用它们。 这个问题问的是数字的数量，而不是数字本身。 数完之后，我们就再也不会使用它们了。 根据经验，我建议您注意您的解决方案是否计算了您不需要的东西。 通常您可以使用更好的解决方案。

第2级：获取数字的个数而不计算数字

我们如何在不生成电话号码的情况下统计电话号码的数量？ 我们可以做到，但是需要额外的算法。 请注意，计算从给定起始位置开始的 N 跳内生成的数字数量等于其每个邻居在 N-1 跳内生成的跳数之和。 从数学上来说，这种递归关系如下所示：

如果只考虑一跳，很直观：6 有 3 个邻居（1、7 和 0），而在零跳时，每个邻居只能到达一位数字，因此您只能拨打三个号码。

你可能会问，你是怎么想到这个的？ 如果学过递归的话，在白板上画一下就知道了。 许多了解递归的考生立即知道问题可以分解为更小的子问题。 如果我面试你而你想不到这一点，我通常会给你提示，直到候选人真的想不到为止，然后完全放弃。

想到这个解决方案后，就可以继续解决问题了。 基于这个想法的代码实现有很多，但我想从我在面试中最常看到的一种开始——最基本的递归方法：

将此代码与计算邻居的函数结合起来，您就得到了一个可行的解决方案！ 这个时候，你应该给自己竖起大拇指。 如果你继续深入挖掘，你会发现我们还有很多问题需要解决，但现在我们可以说我们已经达到了一个里程碑。 找到这个解决方案已经可以让您脱颖而出。

下一个问题是：这个解决方案的 Big-O 复杂度是多少？ 如果有人不知道 Big-O 是什么，它是（非正式地）算法所需的计算量随输入大小变化的速率的简单表示。 对于这个面试问题，输入的大小就是跳数。

对于上面的实现，每次调用 () 都会递归调用 () 至少两次，因为每个键至少有两个邻居。 由于我们递归的次数等于所需的跳数，并且每次 call() 的次数至少是两倍，因此运行时复杂度至少是指数级的。

这表现太糟糕了。 每增加一跳计数至少会使操作复杂性增加一倍。 对于较小的跳数，例如 1 到 20，这是可以接受的，但对于较大的跳数则不行。 比如跳数是500，不知道要到猴年马年才能完成计算。

3级：

我们可以做得更好吗？ 仅使用上述数学关系可能行不通。 然而，我喜欢这个面试问题的地方在于它可以用越来越多有效的解决方案来解决。 为了找到下一步的解决方案，我们首先画出函数调用结构。 让我们首先考虑情况(6,4)。 请注意，我使用 C 作为函数名称：

您可能会注意到一些奇怪的事情：C(6,2) 被调用了三次，每次都执行相同的计算并返回相同的值。 因此，这些函数调用会重复进行，并且每次都返回相同的值。 计算出结果后，应该不需要再次重新计算。

如果您想知道如何解决这个问题，最简单的方法是使用白板：仅仅盯着问题就可以了，但我总是鼓励考生在白板上画出示例解决方案。 像上面画出树结构，你会发现里面有多个C(6,2)。 你一定会注意到它。 有时，这足以让候选人完全绕过解决方案 1 和 2 并直接跳到此处。 在45分钟的面试中，这无疑会为你节省大量宝贵的时间。

那么，接下来我们如何解决这个问题呢？ 我们可以使用(not)，这意味着我们需要记录我们之前见过的函数调用的结果并重用它们，而不是重新计算结果。 当我们在调用图中遇到不需要重新计算整个子树的位置时，立即返回之前计算的结果。 这是一个实现：

那么现在的运行时复杂度（Big-O）是多少？ 这很难回答。 对于之前的实现，计算运行时复杂度就像计算递归函数被调用的次数一样简单，每次调用总是两到三次。 现在计算次数就比较复杂了，因为递归调用是有条件的。 从表面上看，没有明确的方法来统计函数调用的次数。

我们可以通过检查缓存来解开这个谜团。 每个函数调用的结果都保存在缓存中，并且只插入一次。 因此，问题可以变成“缓存的大小如何随着输入的大小而增长？” 由于缓存由关键位置和跳数组成，并且恰好有十个关键位置，因此我们可以将缓存增长视为请求的跳数的函数。 成比例的。 这遵循鸽子洞原则：如果缓存中对于关键位置和跳数的每个组合都有一个条目，那么所有调用都将使用缓存而不是重新调用该函数。

这是线性时间！ 好的。 添加一个简单的缓存将算法的运行复杂度从指数变为线性，这实际上是很棒的。 在我的旧 Air 上，递归实现大约需要 45 秒才能运行 20 跳，而新实现可以在大约 50 毫秒内处理 500 跳。 一点也不差。

那么我们是否正在尽力而为呢？ 还没有。 该解决方案有两个缺点。 一是它是递归的。 大多数语言都会限制调用堆栈的大小，这意味着每个实现可以支持的最大跳数都有上限。 在我的机器上，大约 1000 跳后失败。 然而，任何递归都可以实现为迭代，但比较麻烦。 至于另一个缺点，那就引出了下一个解决方案……

第 4 级：动态规划

如果你看一下前面的递归关系，你会发现递归内存解决方案的缺点很明显：

请注意，N 跳的结果仅取决于 N-1 跳呼叫的数量。 此外，每个（非零）跳数都包含在缓存中。 我认为这是一个小问题，因为它不会真正引起任何实际问题，因为缓存只会随着跃点数量线性增长。 然而，使用线性空间虽然不是世界末日，但仍然不是最有效的。

当你在白板上画出函数调用结构时，结果就一目了然了。 请注意，跳数从最大到最小递归减少：

如果你把整个函数调用图想象成一棵虚拟树，你会发现我们正在进行深度优先遍历。 这也是一个合适的解决方案，但它没有利用上面指出的浅层依赖关系。

是否可以采用广度优先遍历，从顶部开始，调用N跳函数后才调用N跳函数？ 很不幸的是，不行。 非零跳数函数返回的值取决于较小跳数的值，因此在到达零跳数层之前您不会得到任何结果。

但是，您可以颠倒顺序：仅在调用 N-1 跳函数后才调用 N-hops 函数。 学过或正在学习离散数学的人应该知道归纳法：我们知道零跳函数的值始终为 1。我们还知道如何使用一个函数将 N-1 个跳值组合成 N 个跳值。递归关系（归纳步骤）。 我们可以从零跳数开始并推广到所有大于零的值。 这是一个实现：

那么这个版本比递归深度优先解决方案更好吗？ 不会好很多，但肯定会更好。 首先，它不是递归的，这意味着它可以运行非常大的跳数而不会崩溃。 其次，它使用固定内存，因为它只需要两个固定大小的数组，而不是像那样增长缓存。 最后，它仍然是线性的：我可以在不到 20 秒的时间内计算出 200,000 跳。

评价

所以是时候结束这一切了，对吧？ 几乎。 设计并实现一个线性时间、恒定空间的解决方案，是面试中非常好的结果。 对于能够提供动态规划解决方案的候选人，我永远都会竖起大拇指。

您可能会问，还有其他解决方案吗？ 我只能说，我不能对候选人进行抽象评论。 面试并不总是如你所期望的那样。 候选人可能会迟到，他们可能会感到紧张，而且他们往往很晚才想出解决方案，导致他们几乎没有时间编写代码。 我还关注候选人如何传达他们的想法并将想法与反馈相结合。 在建议是否通过候选人之前，我会考虑这些因素。

在评估算法和数据结构时，我会说：“候选人探索了问题并提出了解决所有边缘情况的解决方案，并在发现缺点时改进了解决方案。最后，他们提出了最佳解决方案”。 我还要说：“候选人为解决方案选择了适当的数据结构，并正确解释了运行时复杂性和空间复杂性”。

在评估候选人的编码能力时，我理想的说法是：“候选人快速、简洁地将自己的想法转化为代码。代码使用标准语言结构，可读性强。所有边缘情况都被考虑在内，候选人仔细检查代码以确保其正确性。” 对于入门级职位，如果应聘者提供了测试用例，我会给他们额外的加分，但对于需要更多经验的职位，我会对没有列出相关测试用例的应聘者进行惩罚。

关于面试进行的速度，我想说的是：“候选人推动解决问题的过程：他们提出自己的解决方案，找出缺点并改进它们，而无需我帮助指出它们。候选人只需要很少的提示可以让解决问题朝着正确的方向发展。”

总结

以下是此面试问题涵盖的技能以及您应该养成的习惯的列表：

但是等等，事情还没有结束！

事情似乎就这样结束了，但事实证明还有另一种解决方案。 在我所有的采访中，我从未见过有人提出这个解决方案。 我什至不知道它的存在，直到我的一位同事回到办公桌前，脸上露出惊讶的表情，告诉我们他刚刚面试了他认为是有史以来最好的候选人。

但我想先把解的对数复杂度留给读者想象……