如何进行算法设计面试

https://www.hiredintech.com/courses/algorithm-design

算法理论和练习肯定是必备的，此外面试算法设计需要在编写代码和设计测试上花点心思。

Some of the key things to keep in mind when coding outside your IDE:

考虑清楚然后编码 Think before you code. Especially if you’re coding on a sheet of paper (where there’s no “undo”), if you’re not careful everything could become very messy very quickly
良好编码风格 Coding outside of an IDE does not give you permission to stop abiding by good code style. Make sure you name your variables properly, indent nicely, write clean code, etc. etc.
函数和模块化 It’s even more important to decompose your code into small logical pieces and NOT copy-paste
Read your code multiple times before you claim it’s ready. You don’t have the luxury to compile, see if it compiles, run, see if it runs, and then debug for 4 hours. Your code needs to work off the bat.

Extensive testing 扩展测试，通常来说必须考虑好前面三种case.

Edge cases: Remember that "Constraints" section that we filled in? It's going to come in very handy. Design cases that make sure the code works when the min and/or max values of the constraints are hit. This includes negative numbers, empty arrays, empty strings, etc.
Cases where there's no solution: To make sure the code does the right thing (hopefully you know what it is)
Non-trivial functional tests: these depend very much on the problem. They would test the internal logic of the solution to make sure the algorithm works correctly.
Randomized tests: this makes sure your code works well in the "average" case, as opposed to only working well on human-generated tests (where there's inherent bias).
Load testing: Test your code with as much data as allowed by the constraints. These test your code against being very slow or taking up too much memory.

A good "test set" is a well-balanced combination of the above types. It will include tests that cover most edge cases, a few non-trivial functional tests, and then a series of random tests. These will make sure the code is solid and functionally correct. Finally, some load tests make sure the algorithm works well on the largest and most resource-demanding tests.

Summary

Sign up for an automated online judge like TopCoder.
Always follow the Canvas, even on simpler problems.
Not use your IDE so that you can train your interview coding skills.
Read and review your code before compiling and running the automated tests on TopCoder.

谈谈面试官在面试coding题目时的考察终点与心理活动，求大米【一亩三分地论坛刷题版】 -

本人简介：曾经微软dev, 35+， 10年经验，有FLG offer. 去年加入一个start up 公司，最近前景不明，在犹豫要不要去个稳定点的大公司。我从sde开始面试其他人，到现在估计面试过100+人次的面试和debrief。我面过coding, problem solving, design, behavior. 本帖子只谈论纯粹coding, 视情况讨论要不要再开帖子讨论其他方面。

本文涉及下面几个问题：

我刷过这个题目，还要不要伪装
我觉得这题很简单，但是不知道为什么就挂了
我觉得面试官不是很友好，没提示
我一定要bug free才能被录取吗
leet code的hard问题真的会被问到吗？考起来有什么意义？

我们从一个非常经典的，大家可能都刷过的题目开始。序列化／反序列化二叉树。先说个背景，能面到我这里的，基本需要面试者有3-5年的面试经验。做为应聘任何微软或者flg的高级dev (63 and above, T4/E4 and above), 面试官其实都是假设你刷过不少题目的。我假设你刷过这个题目，所以我并不关心你写的到底有多快，写的是不是完全bug free，我更关心的是你做事的方式和沟通问题的能力。具体请看下面。

提出问题，请序列化／反序列化二叉树。什么？面试者不知道什么是序列化，反序列化？那我就问个多线程爬虫， timing LRU 一类的。如果多线程, 锁也不会，那说明这个面试者的项目经验很不足。为了和其他有经验的人相match, 往往我会给一个很open的问题，或者一个很难的hard coding (取决于他已经被考察了哪个方面). 我个人觉得很少有面试官上来会考你 very hard coding question, 只是当某个面试者与其他面试人比显得相当缺少项目经验，那他除非能在聪明敏捷或者下苦功方面有突出表现，否则很难击败其他候选人。
交流阶段。如果面试者马上开始写程序，或者马上给出他的想法，我会觉得面试者太过于着急了。在实际项目中，你很熟悉的地方可能成为项目中的滑铁卢，因为你熟悉的地方可能有变化，可能有个big change你不知道，可能很快你熟悉的api就不工作了。你总是要有很好的沟通能力，确保大家知道你在做什么，及早的发现你的错误。在code review甚至是test 阶段被人发现问题对项目来说就是个灾难。我期望面试者能够在这个阶段提出一些问题，例如，有什么限制条件吗？二叉树的value是什么类型？这个api谁来使用，内部的还是public的？这个api更注重speed还是space? 我需要多线程吗？如果面试者没问任何问题马上开始照着leetcode的signature开始coding, 甚至class 名字也叫solution(很多人)，我会觉得面试者做事的方式不够成熟。可能以后工作中会很毛躁，需要人来指导。
无论你提出的建议是什么，例如你说你觉得speed更重要，我可能会说我更期待space. 这样做是避免陷入你最熟悉的套路。假设我说，我更需要序列化之后的空间占用最小。这时候一般的候选人不会刷到这么深，开始思考。如果候选人根本没有办法优化空间，那我会认为他give up too early. 我希望候选人能安静的思考，提出几种方案，哪怕方案不成立。如果候选人提出过多的方案，没有问help, 这些方案也不工作，我就认为候选人沟通有问题，无法把握好度。举个leetcode的例子来说明问题的深入， leetcode的序列化格式中， ','是必要的吗？ ‘[’是必要的吗？有没有办法用byte直接序列化？ byte还能变长吗？ base64是什么？ zip会有帮助吗？
候选人选定方案后，我希望他能和我沟通，看看是不是在有限时间内能够写完。项目中，很多时候谁都知道什么design是正确的，什么是bad smell, 最聪明的人不是能做出最好design的，而是在有限时间内能给出大家都能接受的solution的人。如果空间优化非常好，但是代码将超级复杂，无法写完，那么面试者应该及时和我交流。我也会偶尔提醒一下这样能不能在40分钟内写完。如果面试者坚持，我不会坚持，我会看他是不是能写完。这就是either strong hire or fail.
候选人可能这时候说太复杂了，我们简化一下，简化到他熟悉的，刷过的coding.
coding 开始。到这一步，如果你做了2，3，4，5中的大部分，并且code看起来似乎是work的，没有什么致命的问题，我不会纠结于比如正负数， nullpointer, int.min, coding是不是整洁一类的无聊问题。一般就开始7. 如果你2，3，4，5都skip, 那么一般我就希望你bug free, 否则你没办法和其他候选者做比较。往往bug free又要求你code组织很好，否则谁都很难一眼看出你有没有问题。
follow up。还有什么能改进的吗？这是考察面试者的知识面，也看你是不是耐心。很多时候，很多面试者做出题目高兴的得意忘形，到这里就开始语无伦次的乱说，这不会影响到是不是hire，但是可能会影响是不是strong hire, 也可能影响到你的level.

举例子：我觉得还需要写点java doc啊，unit test, regression test, performance tuning, benchmarking, A/B testing, 等等。

总结：如果你能想到1-7中的所有点，谁会在乎你是不是刷过这个题目？即使你刷过这个题目，我也十分确定你刷的比别人好很多，你就是我心中想要的那个同事。反之，如果你只做到了6#，但是别人做了1，2，3，4，5，6，7，那你又怎么能面试成功呢？

有感而发，组织的不是很严密，大家去粗取精，也说说你们的想法。

谈谈coding面试的种类与基本应对策略，欢迎其他有面试经验的人一起讨论【一亩三分地论坛刷题版】 -

在上一篇帖子中提到了coding的一般步骤与考察点，在开贴讨论design，behavior， culture fit前，继续深入的讨论一下coding的考察范围，也以此做为对一些同学，特别是new grad的问题的统一回复。我就不排版和检查拼写了，大家继续凑合读。

>>>> coding 种类与应对策略

大致上，面试官在开始面试前，会收到一封email, 里面回大致说明每个人需要侧重于考察面试者的哪个方面。对于coding来说，一般有三类问题，每个面试官会被分配到一类问题。

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面试题。限于篇幅，我就不展开来说了。

>>>> 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, 至少我没在面试中遇到过，因为很难临时造出一道这样的题目，面试官一般也没这个能力和时间来思考题目是不是严谨。贪心准备下加油站，迪杰斯特拉，最小生成树就足够了。

>>>>> bar raiser

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