一位老外在博客上通过回答面试问题的方式，晒出了自己在谷歌做工程师兼面试官的经历，分享了自己对科技公司面试官的一些建议。“金九银十”的求职季只剩下一条尾巴。不知道找工作的你会怎么样呢？如果您是学生或正在申请技术工作，希望您在阅读本文后能为即将到来的面试做好更好的准备。面试“脑筋急转弯”，你怎么回答？想象一个电话拨号盘，从某个位置只能以大写“L”的形状移动：水平两步垂直一步，或者水平一步垂直两步：假设你只有这种拨号方式，拨号下一个密钥并进行下一跳。起始位置被计为被拨的键。那么，从一个特定的起始位置经过N跳可以拨出多少个不同的号码？答题套路：由浅入深讨论面试基本上分为两部分：先找到问题的算法解决方案，然后面试官用代码实现。在整个面试过程中，面试官通常不是一个沉默的旁观者：45分钟来设计和实现任何东西在松散的环境中是不够的，更不用说在压力大的情况下了。面试官通常会要求面试官带头讨论、产生想法、举出解决问题的例子等，但作者有时也很乐意给对方一个正确方向的推动。面试官的水平越高，他越不会给出暗示，但笔者还没见过完全不需要他介入的候选人。作为面试官，你通常不会坐视别人失败，“我想写尽可能多的积极反馈，我会尽量给你机会写一些关于你的好话，提示是我说：好吧，我给你一点提示”是让一些受访者继续前进并了解他们对问题其他部分的看法的唯一方法。话虽如此，作者希望第一个动作是面试官听完这个问题应该是走到白板前，动手解决这个问题的一些小例子。“永远不要一头扎进代码里！解决小例子可以让你发现模式、观察和边缘情况，也有助于在你的头脑中理清解决方案。例如，假设起始位置从6开始，你有两次跳跃的机会。那么序列将是：上面一共六个sequences尝试用纸笔来推导会比盯着看默默想的效果更好BrassAnswer:初级面试官通常给出的解决方案Level1:ReachingthenexthopTheauthorasan面试官常常会惊讶，求职者经常会卡在计算键值上，其实可以从给定的位置跳转到这个键值，也就是我们所说的邻居。作者建议：有疑问时，写一个空的占位符，问问面试官你以后能不能实现。这个问题的复杂性不在于邻居的计算，而在于完整数的计算有多好，任何花在计算邻居上的时间都是浪费的。通常可以假设有一个函数会传递给neighborvalues，如下图所示：当然这个空函数function最终还是要实现的，但是前提是有足够的时间剩余面试。另外，如果问题的复杂性在别处，要求使用空函数通常不会给面试官留下不好的印象，而且面试官通常会同意这种做法。如果没有其他复杂的问题，面试官也会要求面试者实际执行。至于这里的neighbor函数，考虑到它永远不会变，可以简单的创建一个map，返回对应的值：关卡2：递归生成数字不管怎样，我们来看解决方案。也许你已经注意到，这个问题可以通过枚举所有可能的数字并计算它们来解决，使用递归来生成这些值：这是一个非常普遍的想法。但是，生成的数字并没有真正使用它们。该问题要求计算数字，而不是数字本身。一旦计算出一个数字，就永远不会重新访问它。作为一般经验法则，作者建议注意，当解决方案计算未使用的内容时，通常可以将其删除并获得更好的解决方案。金刚解：进阶思路第3关：“数而不数”如何统计电话号码而不生成电话号码？请注意，从给定的起始位置在n跳中生成的数字计数等于在n跳中从每个相邻位置生成的数字计数的总和。从数学上讲，它是一个看起来像这样的递归关系：有很多实现都使用了这个公式的思想，但让我们从我在面试中最常得到的一个开始：“朴素递归方法”：下一个问题通常是在采访中听到：“这个解决方案的复杂性是什么”。对于那些不知道的人，O(N)复杂度是解决方案所需的计算量随着函数输入的大小而增长的速率。对于这个问题，输入的大小就是跳数。对于此实现，每次递归至少调用count_sequences()两次，因为每个键至少有两个邻居。由于我们递归的次数与所需的跃点数一样多，并且每次调用的compute_sequences()调用次数至少加倍，因此运行时复杂度至少是指数级的。接下来常见的做法是解决时间复杂度过高的问题。第4级：降低复杂性为了找到下一个函数，让我们绘制出该函数调用的函数。让我们考虑count_sequences(6,4)的情况。注意：为简洁起见，使用c作为函数名：注意这里c(6,2)调用执行了三次，每次执行相同的计算并返回相同的值。这里的关键点是这些函数调用被重复调用，每次都返回相同的值。一旦计算出它们的结果，就无需重新计算。这个问题可以使用制表来解决，这基本上意味着我们可以记录我们之前看到的函数调用的结果，并使用这些结果而不是重复工作。这样，当我们在调用图中遇到不需要重新计算整个子树的位置时，我们可以立即返回已经计算的结果。这是一个实现：在这样做之后，复杂性已降低为线性结果。这个解决方案仍然有一些缺点，主要的缺点是它是递归的。大多数语言都对其调用堆栈的最大大小施加了限制，这意味着始终需要考虑可以支持的最大跳数。Level5：动态规划注意n跳的结果只依赖于n-1跳调用的结果。同时，缓存包含每个（非零）跳数的条目。学过归纳法的都知道，递归关系归纳步骤可以从零跳的基本情况出发，归纳推导出所有大于零的值。这是它的一个实现：有没有比递归深度优先解决方案更好的版本？不多，但也有一些。首先，不递归意味着可以运行非常大的值而不会崩溃。其次，使用常量内存，因为只需要两个固定大小的数组，不需要不断增长的制表方案缓存。最后，还是线性时间复杂度：20秒内可以计算出200,000跳。设计和实施线性时间、恒定空间的解决方案通常在求职面试中表现出色。笔者在用这道题进行面试时，往往给使用动态规划方案的面试者很好的反馈。最后，作者还列出了你应该养成的习惯，以便为面试和未来的工作做准备：1.总是从一个小例子开始。2.了解您的解决方案进行的哪些计算是不必要的。3.明确使用递归。4.知道你的解决方案的O(N)。5、总是找机会回忆，比如：写一个空函数。现在是“金九银十”和校招季，希望大家都能找到自己喜欢的工作！
