很多公司技术岗面试都会考编程题来了解面试者的代码编写能力。毕竟如果只是单纯的口述,很难判断一个人的真实水平。编程题不可避免的会涉及到一些算法。
算法作为一项偏基础和理论的技能,对于程序员而言很重要。如果想要在技术方向深入发展,算法能力往往决定了你能走多远。但是前文已经提到,国内很多企业缺乏基础技术的研发能力,往往都是在做应用层,初阶程序员在工作过程中常常只是调用API,接触算法较少(尤其是前端开发),有点“面试造火箭,入职拧螺丝”的意思。
举个例子,编程语言的常规使用并不难,但是编程语言的实现需要很多算法支撑,如果你想自己改造或发明新的编程语言,就必须有好的算法功底。
算法和软件工程的关系,有点像数学和物理的关系,前者是理论基础,后者是实际应用。据说历史上一些物理学家就是因为数学功力不够强吃了亏,影响了物理学的深入研究。
面试刷题是一个有点类似应试教育的学习方式,虽然有不少问题,但确实是一个可以快速掌握新技能的方法。我刚开始刷题很头疼,但是刷了一阵子之后,发现一直自认为不太擅长的算法能力,在短期内有了不小的进步。刷之前:冒泡排序都写不好。刷之后:腰不酸了,腿不痛了,走路也有劲了(划掉) 看到一些相对容易的题,瞬间就能想到思路。
关于如何看待刷题的讨论,还可以看知乎
如何看待中国学生为了进 Google、微软等外企疯狂地刷题?北美学生想进这些名企也要刷题吗? - 知乎
https://www.zhihu.com/question/35133069
如何刷题
1、刷题目的
刷题的目的,不应该是为了追求面试遇到原题,投机取巧通过面试。而应该是加强对数据结构的理解,掌握常用的算法、思想、技巧,训练思维,提升算法能力等。
2、刷题网站
LeetCode , 牛客网 ,LintCode, PAT 等,推荐优先使用体验最好的LeetCode。
3、刷哪些题
LeetCode有几千道题,没有精力都刷一遍,因此需要找到一些典型的题库。除了算法岗位的面试题会比较难,大部分开发岗位刷简单和中等难度的题就足够了。
我主要刷了GitHub的资源 CS Notes 和 剑指Offer ,顺便再推荐一下 探索字节跳动,看起来题目都比较典型。
图论部分内容很多,难度稍大,开发岗位要求不高,可以了解一点常用的,例如参考我的博客 图论基础 ,如果想了解更完整的图论算法,可以参考 OI Wiki(我在第一轮电话面试的时候,面试官问我对图论有没有了解,当时还没来得及看图论部分,说不太了解,所以面试官也没问)。
4、刷题流程
刷题建议按不同的分类集中刷,例如链表、树、搜索、字符串、动态规划、背包问题等。每种类型的题刷完了可以自己写点总结,整理一下常见的思路,有需要的时候拿出来再看看。也可以看我在博客中做的一些 总结 。
5、解题思路与优化
想不出来解法的题,尝试分析几个实际的例子,往往会有一些意外发现。
如果一时想不出来性能好的方法,可以先用最简单的暴力法做一遍,至少保证能解决问题(编程基础好并且暴力法太容易的话,为了节省时间可以想一下不用写)。有时候可能还没人想到更好的方法,暴力法就是最好的办法。另外,很多优化思路也是在暴力法的基础上实现的,考虑暴力解法的时候可能就发现优化思路了。
如果一道题想了十分钟还是没有思路,没太大必要继续想了,多半想不出来,直接去看题解,看懂别人的思路,然后可以给这道题做个标记,过几天再来把代码写出来。特别是有些题会用到技巧性较强的算法,如果没看过,自己不太可能直接想出来,毕竟发明这些算法的人也是花了很多时间去研究,发明一个这样的算法就足以成为名人了。
代码提交通过不代表这道题就结束了,还需要思考有没有更好的解法。例如一个典型的例子,很多题目既可以用DFS解决,又可以在此基础上使用动态规划思路进行优化。
6、算法复杂度分析
要会分析自己所写代码的算法复杂度,当然有些算法的复杂度需要用到比较深入的数学知识才能计算出来,这种可以不考虑。
7、边界情况处理与代码测试
边界情况处理是写代码的时候需要特别重视的问题。无论是算法题,还是实际写代码,有时候常常是问题解决思路并不复杂,但是会有各种边界情况,例如字符串处理,可能会传入各种格式的字符串,还可能是空字符串。
这里要重点强调一下了,和国内多数公司不一样,微软等外企是没有测试(或称为QA)岗位的,程序员写完代码后需要自己写单元测试,确保代码正确性。因此边界情况的考虑就更加重要了,面试过程中也很重视这种能力。
有两种写代码的思路,可以根据实际情况按需选择,或两者结合。一种思路比较快速直接,先解决主要矛盾,再解决次要问题,也就是先写关键代码,之后再考虑各种边界问题并完善代码。另一种思路更加系统化,先思考测试用例,把能想到的所有情况都列举出来,之后再写代码,好处是不容易漏掉不同分支的处理和边界情况的判断,对于拿到题一时没有思路的情况也能帮助分析。
在LeetCode刷题时,测试用例都是题库已经给出来了的。在实际场景中,测试用例除了直接人工思考,也有一点技巧。例如可以借助随机函数生成输入值;实现一个能确保可靠性但不追求性能的算法版本(可能是暴力法,可能是复杂度更高的办法,也可能是调用现成的代码库),生成每个输入值对应的输出值。