注册一亩三分地论坛，查看更多干货！
您需要 登录 才可以下载或查看附件。没有帐号？注册账号
x
坐标硅谷，已经工作3年了的程序媛一枚。最近硅谷很多公司都裁员了，很多小伙伴在找工作，需要刷题。
我本科毕业的时候面了10家美国公司，全都拿到了Offer。包括Google，Facebook，Microsoft之类的大厂，Airbnb，Snap，Asana之类的初创公司，也有Citadel，Bloomberg之类的金融公司。我在当时面试的时候刷的leetcode题不超过100道。我想和小伙伴们交流讨论一下我自己的一些经验和方法。拒绝题海战术，力求100道题内帮助你拿到你想要的offer。希望能对找工作的小伙伴有一些帮助。
算法面试考察什么？
工作三年，身边很多同事和朋友包括我自己都是面试官。在聊怎么刷题之前，想先聊一聊算法面试考察的是什么？面试官在面试结束后会怎么评价你的表现，怎么做反馈？根据我的面试经验和从面试官朋友那里了解的信息，有几种公司：
1. 着重考察做题正确性：看了地里很多同学理解的面试顺利一般是这样的体验。「这道题我刷过，所以轻松秒了」。这里的秒了一般指
- 把题快速做出来
- 经过现场测试（testing），验证了做的是对的（有些面试不要求这一点）
- 题的解法是最优解
我遇到过很多公司，尤其是规模偏小一些的公司，和不少中国公司很看重面试者的解题能力。想要轻松应对这类面试，其实多多刷题是很有帮助的。因为刷过题更容易轻松地做出一道题，并且不怎么犯错，做到bug free。遇到这种面试style，其实夸夸把题做出来外加沟通清楚就行了。后面会讲到大家会遇到不同的bar，以及一些技巧。但是基本上遇到这种style的面试，多刷题，把题快速做出来就很稳了。
2. 着重考察思维能力：很多硅谷的大厂，比如FANG，很看重面试者的思维能力。这里的思维能力有多种：
- 优化算法的能力（Algorithm Optimization）：面试者能够不断地优化算法。比如把O(n!)的解法优化到O(n^3)，再优化到O(n^2logn)。和第一种公司不同的是，面试官在这里并不期待你一定要做到最优。如果遇到两个面试者，第一个对算法做了两次优化，最后没有做到最优，第二个上来直接做出最优解。第一个面试者会有更大的优势。因为可以看出面试者勤于思考，并且可以不断优化现有解法。
我一般听到题之后，第一步会想暴力解法是什么，把解法和面试官解释清楚，然后说出它的时间复杂度（Time Complexity）和空间复杂度（Space Complexity）。然后再看能不能一步一步地优化。尽可能地优化两次以上，每次都把算法解释清楚，并讲出复杂度。如果看到有可能的tradeoff，比如一个算法比较快，另一个比较省空间，也可以清楚地讲出来。之后再和面试官沟通哪种解法比较适合，之后再开始写代码。
这里之所以要花时间做算法上的讨论是因为如果你不做，很多面试官之后也会问你follow up questions如何优化。除非你上来就说最优解，把她的follow up questions堵死了。那面试官肯定内心很不开心，认为你都是靠刷题的。但是她如果看到你一步一个脚印地优化到最优，就会觉得确实看到了你的思考，也不会觉得你都是靠刷题背答案才做出这题。 - 测试能力（Testing）：有不少面试，不论是白板面试还是online compile的，会要求你测试（test）你的算法。除了代码的正确性，面试官也在考察你的测试（test）能力。有经验的小伙伴一定知道testing在实际工作中有多重要。通过面试来观察test的习惯其实可以比较好地反应面试者是否有code quality的基本功。
我一般会从两个角度来test：先着重于logic correctness，再试图抓corner cases。
（1）Logic correctness我一般就会看for loop，while loop是不是和想的一样，variable变化对不对，语言（syntax）是否正确之类。我一般会用面试官给我的例子来test。这个例子一般会比较简单，但是仍旧能够test主要的逻辑。
（2）之后我会再看看corner cases。比如如果input是空的，或者input特别大会有什么问题。while loop，for loop会不会在input特别小的时候出错。 - 调试能力（Debugging）：在工作中，大部分时候写代码都不是一帆风顺的。苦逼的程序员儿就得一点一点地在代码中抓bug在哪里。正是因为debug占比时间之多，debug的能力也十分重要。有些同学认为在面试中一遍写出bugless代码会很讨喜。实际上，我觉得这样面试官就会再次怀疑你是刷题选手而质疑你的真正实力了。在真正面试中，写出bug不可避免，稳住心情debug就好。
我自己在面试的时候debug喜欢通过自己手动一步一步test一个错误的例子，来找到问题在哪里。有的时候，我比较急，一遍一遍地跑代码来看问题在哪里反而耗时更多。这个时候，静下心来，手动跑例子其实容易更快发现问题，而且面试官也可以跟着你的思维走，理解你的是在怎么debug的。 - 表达能力（Communication）：在面试中清晰地表达自己的想法也是很重要的。这点是刷题很难练习的。因为刷题的时候可以一个人静静地写代码，没有人干扰。但是面试的时候却要和面试官同步思考。
我的方法是，每次刷题都当作面试的练习。我会通过comment来表达我的想法。有时也会自言自语地一步一步讲我的思路。事实证明，经过一段时间的练习，我习惯了一步一步讲清楚我的思路的时候，我做题的正确率变高了。不容易范一些小错误。
给大家分享一道我自己做的Leetcode原题。我回顾了之前做的基本上每一道题都会有一段comment来模拟面试时候的交流。我会在comment里尽可能地把题的每一种解法，以及优化的过程讲清楚。这样我即使三年后重新来看这些题，还能快速想起当时是这么做的：
- 合作能力（Collaboration）：基本上所有算法面试也在考察，你是不是一个面试官愿意合作的好队友。尊重面试官其实挺重要的。我有一位朋友，特别大神，但是面试的结果总是不太理想。后来我和他一聊发现他常常会内心悄悄觉得面试官太弱。其实面试官可以感受的到你内心觉得她弱的心声，觉得你不太好合作。
- 好奇心（Curiosity）：有些公司还会比较看中你对公司所在领域是否有热情有好奇心。一般体现在最后留下的5分钟问问题时间。对于应该问面试官什么问题我想要之后再专门讲一讲，要是感兴趣的小伙伴点赞或者留言告诉我哦。
总结一下，这类面试尽可能不要一上来就给面试官最优解。于是问题来了，作为面试者，我们怎么知道面试官到底是看我的答案正确性还是在考察我的思维能力呢？我们其实很难知道。所以我建议不论是什么面试，除非很确定这个公司不考察优化能力，尽可能地一步一步地做题，从暴力解开始讲起，最后达到你能到的最优解。
面试的Bar在哪里？
Bar通俗地说就是面试是否通过的线划在哪里。我遇到的公司有几种不同的bar：
- 代码能跑 + Test cases：要求代码可以在网上直接运行（online compile + run）。这类公司会提前写好一些test cases，让你直接网上submit，看是否能跑过所有test cases。这类公司更看重你的代码正确性。
建议做题的时候尽可能稳一点，把每一步的想法都和面试官交流清楚，自己也可以用一些小的例子给面试官解释这段代码在做什么，比如用一个example input来跑一跑你的while loop，来解释一下什么时候每个variable都是什么值。解释的时候其实也是很好的机会帮助自己做一些简单的testing，来保证代码的正确率。 - 代码能跑 + 自己写test：要求代码可以在网上直接运行（online compile + run），外加面试官希望你能够自己写test cases。这里面试官不仅考察你的正确性，还考察你的test能力。
- 代码不需要跑：不要求跑代码，基本上会要求你白板测试代码正确性。这类面试一般更注重你的能力，比如优化能力和测试能力等等。
- 最优解：有一些面试官对解法的优化程度有一定的要求。有时候，你的代码完全正确，test也没问题，但是解法不是最优。这种情况不用慌，面试官不会默默地把你拒了。她要是对代码优化有更高的要求，一般会问follow up questions。
问的一般是，你还能怎么优化？或者你能不能做到时间复杂度O(n),空间复杂度O(1)。一般你即使不能完全达到面试官的要求，但是有优化也是很好的signal。如果你能够想出来解法，但是没有时间把代码写出来也没有关系。
哪些知识点重要？
这个文章是原创内容一个字一个字地辛苦打出来，如果要转载请和我联系。
补充内容 (2020-6-20 16:41):
这个帖子针对两个问题：
1. 面试中把题秒了，可是面试官怀疑我刷题怎么办？
2. 如果来不及刷很多题，面试又迫在眉睫，怎么样尽可能地提高刷题效率。
之前拿到10个offer有很大一部分是运气，希望有一些总结有些帮助。
补充内容 (2020-6-23 07:04):
这两个月我拿了一些offer。现在确实觉得bar变高了，面的很多是hard题。
我自己刷了150题。拿到了FANG里面的2个offer和一些别的offer，也拿了两个拒信。 | 
狗仔卡
收藏
淘帖
好苗
杂草
提升卡
置顶卡
关贴卡
开贴卡
变色卡
千斤顶
楼主
