谈谈coding面试的种类与基本应对策略， 欢迎其他有面试经验的人一起讨论

前言

前几天写了个关于面试官心理活动和侧重点的帖子， 见 谈谈面试官在面试coding题目时的考察终点与心理活动， 求大米, 首先感谢大家的捧场与大米， 也请大家原谅我的一些错别字与语无伦次（为了快速求大米写的粗糙了一点）， 反应超出我的预期。  也让我有了动力接着写这一篇帖子。
在上一篇帖子中提到了coding的一般步骤与考察点， 在开贴讨论design，behavior， culture fit前， 继续深入的讨论一下coding的考察范围， 也以此做为对一些同学， 特别是new grad的问题的统一回复。我就不排版和检查拼写了， 大家继续凑合读。

coding 种类与应对策略
大致上， 面试官在开始面试前， 会收到一封email, 里面回大致说明每个人需要侧重于考察面试者的哪个方面。 对于coding来说， 一般有三类问题， 每个面试官会被分配到一类问题。
1. solid coding
这类问题说白了， 谁都知道怎么做， 纯粹就是考察coding是不是扎实， 平时自己写code多不多， 能不能快速的把自己的idea转化为code。 对于面试者来说属于必考种类， new grad 一般会有两轮甚至三轮这样的题目, 有很多工作经验的人可能就只有1轮了。  这类题目不过关， 很可能电面死掉或者前几轮突然死亡。
solid coding又一般可以分成两个小类：
1.1  考察你对算法的基本理解以及边界条件的运用， 比如findkth largest integer, search in rotate array, bit manipulation 等等。
1.2 考察你对基本数据结构以及复杂度的理解。 比如binary search tree, linkedlist vs array, stack, tree dfs, tree bfs 等等。

按难度来分， easy的比如3 sum, tree level order iterator.  medium 难度的比如 reverse linked list from index m to index n, course schedule，string multiplication, hard 难度的比如valid number, 复杂的calculator等。

应对策略：
1.1 类型， 如果是简单和medium的没得说了， 就是希望你又快又好， 除了勤奋和熟练， 没有什么好策略。 对于像merge sort, partition这类的算法， 如果7-8分钟还写不出bug free我估计就没戏了。easy问题请多多注意边界条件， int 溢出， nullpointer, 负数， 非法输入等。  
hard 1.1的请参考1.3
1.2 类型， 简单和medium请在写代码前多阐明复杂度， 这类数据结构的问题往往也可以在coding前画图来表示运行状态， 图画的清楚也是个重要的加分项。 hard请参考1.3
1.3 hard类型的coding题目. 这往往是考察你的solid coding的能力， 即我在前文中提到的， 你做事的方式和你思考问题的方法。 即给你一个coding任务， 你如何从白板开始， 一步步的做出bug free的程序。 这类问题的过程重于结果。 比如valid number, 你能确保每实现一个模块， 都没有regressgion, 都没有bug, 比你一下子实现所有的feature但是有很多bug 要好很多。  一般来说面试官看你是否能够一步步的分隔出小的coding模块（method）, 你如何设计test case, 你如何能够确保这些test case能cover所有的scenario, 你是不是和面试官提前做了足够的沟通并且限定了coding范围。   从这个角度来说， valid number其实是个很不错的solid coding面试题。  限于篇幅， 我就不展开来说了。

2. problem resolving
这类问题对于new grad是关键， 也是能帮你differentiate的关键。 说白了， 计算机并不是只有算法，我们还需要数据库， 操作系统， 网络， 安全等方面的知识。  new grad这些方面要弱一些， 所以面试者希望new grad能展现出思维敏捷， 多思考， 快速反应的能力。 problem resolving就为了考察这个能力而诞生的。
problem resolving也可以分成四个小类型。
2.1  API design.  这类问题是为了更深入的考察你对数据结构的理解与运用。 例如LRU cache,  insert delete getRandom ALL O(1) ， design twitter等等。
2.2  Abstraction.  这类问题是考察你能不能把一个相对抽象的问题规约到你熟悉的问题上面。 比如skyline problem, int stream find median， cleaning robot等等。
2.3 计算机小程序， 例如thread pool, 爬虫，日志merge等， random generator等。
2.4 dynamic programming问题。 这类问题有点像solid problem resolving.  主要考察你是不是有systemmatic的方法来降低一个brute force程序的复杂度

这类问题一般都不是很easy的问题， 根据面试官心情， 可能走的很深很难。 也可能最后演变成bar raiser.

应对策略:
2.1  主要考察你对数据结构的深层次认识。  首先请同时确保你理解了题目的意思， 最好能问清点条件 例如immutable array max subarray sum, 那数组将来会变吗？问清这类的问题有助于你写代码前做好重构和测试的准备。 其次， 如果你能证明你选择的算法的复杂度， 甚至证明这就是最佳复杂度， 那是一个大大的加分项， 如果不能， 至少你也问问面试官是不是已经满意了再开始写代码。
2.2  这个我自己也头疼， 说实话如果第一次遇见了skyline, 我也不知道能不能搞定。  大家有好办法请回复有什么好办法能系统化的解决这类的问题， 我个人觉得很多时候靠灵光一闪。
2.3  这类问题主要看你平时积累， 也是一大类不能通过leetcode练习的问题。临时抱佛脚的话， 我个人推荐java concurrency in practice这本书。
2.4  动态规划， 我不知道为什么很多人害怕动态规划。 面试中的动态规划大致分为单向递归（首或者尾）， O（n2）或者O(n3) 距离递归,  O(mn)递归，有限定条件的NP (背包）。 每种类型听几节课， 懂了基本原理即可。 至于贪心和带状态的dp(走道铺砖）一类的dp, 至少我没在面试中遇到过， 因为很难临时造出一道这样的题目， 面试官一般也没这个能力和时间来思考题目是不是严谨。 贪心准备下加油站， 迪杰斯特拉， 最小生成树就足够了。

3. bar raiser
这类的问题只有当onsite应聘者的数量远远大于head count的时候， 或者你前几轮明显超出了电面时对你的定位才会发生。 其目的是帮助公司选择最优秀的人。 对应聘者来说， 坏消息是要度过痛苦一小时， 好消息是你能充分了解这公司厉害的人有多厉害， 能充分展示你的能力， 甚至被越级录取也不是不可能。
bar raiser也是三小类。  

23：25， 喊我去睡觉了， 留下这类问题下次有空再说。 大家赏大米啊。

wzyath 发表于 2018-7-28 07:55
同问碰到skyline这种题该怎么办。如果直接说出最优解，一看就知道是背过的。。。

较难的hard题，最好在彻底理解答案的基础上背题。面试官比较看重的是得到这个解法的过程。
我们来以skyline的表演为例，抛砖引玉一下～

题目要求的是建筑的剪影，可以抽象为每个固定横坐标上的最高点（划重点：提取问题核心）。因此这个解法可以分成两部分：
（1）如何把input转换为线性，从而抽象成扫描线问题（甩名词：sweep line）
（2）扫描线的具体实现

第一部分，如果想要简单扫一遍，数据必须是按x轴排序的。假设我们 start_x 来对 building 排序，则end_x仍然是无序的，这样不好。（此时演技爆棚一拍脑袋想到）我们只需要知道skyline的线段是在哪里开始的，因此在building高度发生变化的X位置进行处理即可。building的开始和结束都算是高度变化，因此可以把 start 和 end 拆开处理，只需要标记 X 位置上的高度数据以及这个高度是开始还是结束。

至于每个X位置数据的具体结构，可以用一个tuple（int h 高度，bool start 表示是开始还是结束），也可以像高票解法一样用正数代表开始、负数代表结束。可以和面试官阐明。

第二部分，主要是如何维持一个高度的queue。
阐明在扫描过程中需要三个操作，插入（遇到start），删除（遇到end），获取最大值（高度更新），因此可能有：
1. 因为要取最大值嘛，所以很明显我们试试heap，插入O(logn)，max O(1)，但是删除是O(n)，不太好，我们试试别的；
2. balanced bst (c++ ordered map以及java treemap），全场O(logn)，通通O(logn)；
3. 有没有可能优化方法1呢？可以用 hashmap + heap的方式来实现，O(logn) insert, O(logn) remove, O(1) get_max。

第一部分稍微举例说明了一下如何展示思路。
第二部分我认为是装逼重点。能写方法3，就先列出1和2，指出他们的不足，然后提出3。如果懒得实现3，先提出1，再提出2，指出红黑树的时间优于heap，在面试官看来也是对数据结构足够熟练的应用了。

最后记得提出edge case，比如两个building高度相同怎么办（假装思考一下）如果先push start，再pop end，就不会有高度变化的问题了嘛，所以我们重写compare函数的时候注意一下就行了。

以上整个过程，在表演不崩的情况下用5-8分钟来解释，我认为都是可以的。


两年没刷题了，具体细节可能记得不太清楚。最近刚开始当面试官，在演技方面给大家举个栗子🌰。对于这种candidate，即使对方可能是在表演，如果能够把问题肢解得这么清楚、把多种实现细节的trade-off分析得这么明白，我也会给一个pass的。
（皮完就跑 #滑稽#

补充内容 (2018-7-29 05:14):
解释思路的时间扩展到10+分钟应该也可以吧，诸位要不要试试mock一下计个时？我们统计一下（笑）
总之只要思路连贯，有理有据令人信服，就不会演崩。但一定要有develop思路的过程，这也能体现对解法的充分理解

wzyath 发表于 2018-7-28 07:55
同问碰到skyline这种题该怎么办。如果直接说出最优解，一看就知道是背过的。。。

我觉得复杂度意义上的“最优解”其实只是真正面试时面试官所期望的“最优解答”的一个组成部分。也就是说不管你有没有背过，“复杂度”这一考察点上肯定是过关了。

然而，“直接说出最优解”或者大家所喜欢的“秒题”这一做法，会对其它考察点造成负面影响，例如你对问题的抽象能力，如何以小见大进行归纳，对语言细节和底层机制的把控与讨论，等等。

如果你看大公司例如Facebook给的Interview Guide，他们所期望的解题过程基本上符合算法研究的方法论——如何通过对问题的观察、通过举例简化的输入进行归纳而抓住各种性质。一般的问题，核心的不变性（invariant）也就一两个，列出来后代码基本上也就是搬砖了。

但问题是大多数人并不懂算法研究的方法论而一大类工作也用不上（我感觉大多数高中理化老师也并不懂自然科学研究的方法论...）。但是面试又考算法题，就自成了一套背题秒题的民俗方法论。而面试官见的世面（面试者）多一点应该是知道什么是好的解题过程，但是他们想看到的东西其实自己也不一定能做到。

回到skyline这类问题上，背题其实是知识体系不全面又受时间精力所迫的无奈之举，短期方案我也不知道.. 但是真想提升自己内力的话，可以有意识积累一些“一锤定音”的东西：想象一下有一个对skyline这题完全没有头绪的人向你请教，能不能给出三到四点关键性质（定理），让他恍然大悟并且可以自己写出代码？面试时列举出这样的关键定理甚至能让面试官自身对一个问题学习到新的理解。

我不得不说你这要求也太奇特了。我在FLAG，UPA做hm多年，从来没有说什么 7-8分钟不能bug free就挂了的事情。
相反，大家其实很反感背答案的情况。最好花时间和面试官确认好你的确理解题意，交流大致思路之后再写。

再次感谢楼主分享 明天起来再加米。
有两个小问题:
1.
2. 我感兴趣的是 以上的总结是基于楼主自己的经验还是 you

Zetecx 发表于 2018-7-26 15:46
再次感谢楼主分享 明天起来再加米。
有两个小问题:
1.

手抖直接发出去了 赶紧补充一下。
我感兴趣的是两个问题:
1. lz在前一篇帖子中提到"对于bug free是没有那么高要求的"在这个帖子中提到 "希望对于easy和medium的题目是越快约好", 我想知道对于medium（easy我相信大家都能handle)难度的题目 如果面试者已经have a nice try 和良好的沟通(如上篇帖子提到的前几项）但没有做出来。有没有仍然可能通过的可能性?

2.lz分享的经验大多是基于自己的经历呢还是 有和他人探讨过？ 我无意质疑lz 只是想知道 lz分享的看法是否有很强的普适性 或者 是很强的个人偏好

再次感谢分享

我也想提问一下，就是我们面试的时候需要在有限的时间内，比如45分钟两道题的情况下，提出从暴力到最优解吗（有可能两到三种解法）？
谢谢

1点50分 发表于 2018-7-26 19:50
我也想提问一下，就是我们面试的时候需要在有限的时间内，比如45分钟两道题的情况下，提出从暴力到最优解吗 ...

只有 FB 和谷歌才会这样的要求吧？

Zetecx 发表于 2018-7-26 15:57
手抖直接发出去了 赶紧补充一下。
我感兴趣的是两个问题:
1. lz在前一篇帖子中提到"对于bug free是没有 ...

我只能说我看的大部分是这样的， 什么特殊类型的都有， 具体要和面试人和team的情况有关系。  

1点50分 发表于 2018-7-26 19:50
我也想提问一下，就是我们面试的时候需要在有限的时间内，比如45分钟两道题的情况下，提出从暴力到最优解吗 ...

看难度和面试官想考coding还是Problem resolving。 word ladder 2这种能暴力写好就不错。  

本文被选为07/27/2018的全站置顶帖子之一。
大米奖励作者，非常感谢您的分享。

mark。。。。紫薯紫薯紫薯紫薯