抓住「金九银十」的尾巴！技术面试如何准备，谷歌面试官亲授

有位外国小哥在自己的博客上通过解答一道面试题，发布了自己在谷歌担任工程师和面试官的经验，分享了对于科技公司面试者的一些建议。

「金九银十」的求职季也只剩下了一个尾巴，不知道正在求职的你结果如何呢？

如果你是一名学生或者正在申请技术类的工作，希望你在读完这篇文章之后能够更好地应对即将到来的面试。

面试「脑筋急转弯」，你怎么答？

想象一个电话拨号盘，从某个位置开始只能以大写字母 「L」的形状移动: 水平移动两步，垂直移动一步，或水平移动一步，垂直移动两步:

假设您在键盘上只能使用这种方式来拨号，拨下一个键并进行下一跳。起始位置计算为正在拨号的键。

那么，从一个特定的起始位置开始，能以 N 跳的方式拨多少个不同的号码？

回答的套路：由浅至深的讨论

面试基本上分为两部分: 首先找到一个该问题的算法解决方案，然后面试者用代码来实现它。

在面试的整个过程中，面试官通常不是一个沉默的旁观者: 在松弛的环境中花45分钟设计和实现任何东西时间都不充足，更不用说在有压力的情况下了。

面试官通常会让面试者在讨论中发挥带头作用，产生想法，提出解决问题的实例等，但作者有时也非常乐意在正确的方向上给予对方推动。

面试者的水平越高，他倾向于给出的暗示就越少，但是作者还没有看到过一个候选人完全不需要他的参与。

作为一个面试官，通常不会坐视别人失败，「我想写尽可能多的积极的反馈，我会尽量给你机会让我写关于你的好东西，提示是我说：好吧，我给你一点提示」，只有这样才能让一些面试者继续前进，看看他们对问题的其他部分有什么看法。

话虽如此，作者希望面试者听到这个问题后的第一个行动应该是走到白板前，手工解决这个问题的一些小实例。

「永远不要一头扎进代码里！解决小的实例可以让你发现模式，观察和边缘情况，也有助于在你的头脑中明确解决方案」。

举个例子，假设起始位置从6开始，你有两跳的机会。则序列将会是：

以上总共有六个序列。如果试着用铅笔和纸来推导这些，总比只是盯着它静静地思考，会带来更好的结果。

黄铜答案：初级面试者通常给出的方案

Level 1：到达下一跳

作者作为面试官经常会感到惊讶的是，求职者经常会陷入计算键值的困境，其实恰恰可以从一个给定的位置跳到这个键值，也就是我们所说的邻居（neighbors）。

作者的建议是: 当有疑问的时候，可以写一个空的占位符，然后问面试官是否可以稍后实现它。

这个问题的复杂性不在于邻居的计算，而是如何很好地计算完整的数字，任何花费在邻居计算上的时间都被浪费掉了。

通常可以假设有一个函数会传给邻居值，如下图所示：

当然，这个空函数功能最终也是需要被实现的，但前提是面试剩余的时间还足够。

而且，如果问题的复杂性在其他地方的话，面试者通常不会因为要求使用空函数而被留下坏印象，面试官通常都会同意这种做法。

如果没有别的复杂问题，面试官还会要求面试者实际执行它。

至于这里的邻居函数，考虑到它从不改变，可以简单地创建一个 map 并返回相应的值:

Level 2：递归生成数字

不管怎样，我们来看看解决方案。也许你已经注意到这个问题可以通过列举所有可能的数字并计算它们来解决，可以使用递归来生成这些值:

这是一种非常普遍的想法。然而，生成的数字并没有真正的使用它们。这个问题要求的是数字计数，而不是数字本身。

一旦计算了一个数字，就再也不会重访它了。作为一般的经验法则，作者建议注意当解决方案计算一些不使用的东西时，在通常情况下可以把它删除，然后得到一个更好的解决方案。

钻石方案：高级一些的想法

Level 3：「不计数的计数」

怎样才能在不产生电话号码的情况下计算电话号码呢？请注意，从 n 跳中给定的起始位置生成的数字计数等于从 n 跳中的每个相邻位置生成的数字计数之和。

从数学角度来说，它是一个递推关系式，看起来像这样:

有很多实现使用了这个公式的思想，但是让我们从我在面试中最常见的一个开始: 「朴素的递归方法」:

接下来这个问题会经常从面试中听到: 「这个解决方案的复杂度是多少」。对于那些不知道的人来说，O(N)复杂度是一种速率，一个解决方案所需的计算量随着函数输入大小的变化而增长。对于这个问题，输入的大小是跳数。

对于这种实现，每次递归调用 count _ sequences ( ) 至少两次，因为每个键至少有两个邻居。由于我们递归的次数等于所需的跳数，并且每次调用时计算 _ sequences ()的调用数量至少翻了一番，因此运行时的复杂度至少为指数级。

接下来通常的做法就是解决时间复杂度太高的问题。

Level 4：降低复杂度

为了找到下一个函数，让我们把这个函数调用的函数映射出来。让我们考虑 count _ sequences (6,4)的情况。注意: 为了简洁起见，使用 c 作为函数名:

注意这里 c (6,2)调用执行了三次，每次执行相同的计算并返回相同的值。这里关键的一点是，这些函数调用会重复调用，每次都返回相同的值。一旦你计算了他们的结果，就不需要重新计算了。

使用制表法可以解决这个问题 ，这基本上意味着我们可以记录之前看到的函数调用的结果，并使用这些结果来代替重复工作。

这样，当我们在调用图中遇到不必要地重新计算整个子树的位置时，可以立即返回已经计算的结果。下面是一个实现:

经过这样的处理，复杂度就已经降到了线性的结果。

这个解决方案依旧有一些不足之处，主要的缺点是它是递归的。大多数语言都对其调用堆栈的最大大小进行限制，这意味着总是需要考虑可以支持最大的跳数。

Level 5：动态规划

请注意，n 跳的结果仅依赖于 n-1 跳调用的结果。同时，缓存包含每个(非零)跳数的条目。

学过归纳法的人都知道，可以使用递推关系式归纳步骤，可以从零跳数的基本情况开始，并归纳推导出所有大于零的值。下面是它的一个实现:

还有没有比递归的深度优先解决方案更好的版本呢？不是很多，但也有一些。

首先，不是递归的意味着可以运行非常大的值而不会崩溃。

其次，使用常量内存，因为只需要两个固定大小的数组，而不需要不断增长的制表解决方案的缓存。

最后，仍然是线性时间复杂度: 可以在20秒内计算200,000跳。

在求职面试中设计和实现一个线性时间、常数空间的解决方案通常都会得到一个很好的结果。当作者使用这个问题进行面试时，经常给那些使用动态规划方案的面试者一个很好的反馈。

最后，作者还列出了为了准备面试和今后的工作你应该养成的习惯:

1.始终从手推一个小实例开始。

2.注意你的解决方案做的哪些计算是不必要的。

3.清楚地使用递归。

4.知道你解决方案的O（N）。