聊聊刷题

在之前的《谈谈面试》中我讲述了我在面试上的经历和看法，而对于软件行业的面试很多都要求被面试者解决一些编程上的问题。这类面试有很多名字：算法题(Algorithm Question)、编程题(Programming Problem)、考代码(Coding Interview)等等，但基本形式都是：给出一道问题的描述和目的，要求写出程序能够接受相应的参数然后完成目标需求最终得到结果。

大部分常见的这类面试问题都被大家总结在了网上，可以直接搜索找到，或者在一些论坛的特定板块（比如未名空间的待字闺中，一亩三分地的面经）里见到讨论，甚至形成了在线测试网站(比如LeetCode、LintCode)直接验证程序的正确性。

由于面试题目的公开性，造就了软件行业特殊的面试准备过程：刷题。很多朋友也会问我：“出去面试还刷题吗？”准确地讲，我刷过算法题目，也经常后悔没有早在还在学校里时就开始刷题，那样就能更早地进入心仪的公司。但现在出去面试前基本都还是忙着正常的工作，不会专门去练习题目。

刷题的目是理解算法和数据结构

好比读书的时候每次老师教授了新的知识后都会布置习题，完成那些作业可能会让我们在考试中碰到原题而拿到高分，但正真的作用是帮助我们理解和消化所学的知识。从简单的理解：“程序=算法+数据结构”，要写好程序就必须去熟悉算法和数据结构，刷题就应该是完成这样的作用。如果题目做不出来，就说明连最基本写程序的能力都没有，自然很难得到公司的青睐。

我常常幻想如果我高考没有失常，能进入更好的学校学习计算机知识，甚至参加ACM小组，得到老师在算法上更好的点拨指导，也因为要参加计算机竞赛，我也会练习更多的题目，现在就不需要刷题了。但现实是在我就读的大学里，算法只是一门选修课，我也没有参加过任何计算机竞赛。但联想高中数学竞赛的培训过程，老师肯定会分类进行知识传授和练习。所以刷题也一样要分类进行强化训练。

LeetCode虽然是最火的题库，但是在我刷题的时候它只是简单的罗列一百多道题目(可参看我的不完全题解列表)，所以当时我更倾向去做UVa上的题目。那上边有上千道题目，肯定是不可能做完的，但是有比较好的分类专区，可以专门的加强某一特定算法和数据结构的基础知识。

一开始我连最简单的二分查找(Binary Search)算法都写不好，但是在反复练习之后，我也能总结出二分法的实现，并汇总一些变形题目到博客里。刚毕业那会找工作，好多次面试都挂在了二叉树(Binary Tree)上，后来做遍各类遍历算法，总结了不同的实现方式，就不再担心关于树的操作。动态规划(Dynamic Programming)在我看来是面试时会碰到最难的问题，后来我发现这类问题的关键在于找到类似于数学中的“递归公式”，这样就可以找到递归的实现，之后利用空间来存放中间值来减少时间复杂度。

算法设计和分析比实现更重要

对于一道编程问题，选用不同的数据结构和算法会得到不同的实现方式，比如“最长公共子串”。所以光能写出问题的实现还不够，还需要知道怎么针对问题设计算法，然后分析算法的复杂度来比较不同实现直接的优缺点。因此刷题之外，还需要记住每种算法实现的时间复杂度和空间复杂度。最常用的是Big O notation。

本文不是介绍算法的文章，但是我想分享我是如何反过来利用“复杂度”理论来帮助我在面试中解决一些我没练到我的题目。

首先大家都知道算法主要在意时间复杂度，而优劣排序也很直接：O(1), O(log n), O(n), O(n log n), O(n2), O(nk), O(2n)。然后我们需要知道每种复杂度对应的有哪些算法和数据结构类型：O(1)是Hash，还有其他简单的运算；O(log n)是二分查找算法；O(n)是一次遍历，可以是多次循环；O(n log n)是排序算法和平衡二叉搜索树；O(n2)和O(nk)是多层嵌套循环；O(2n)就是没有优化的DP了。

做题时如果已经知道了最优解，那就直接在面试官面前来个表演时间就好。如果没见过，那就先想暴力算法怎么解，然后跟面试官讲思路，寻问是否合理。如果对方说能不能找到更好的？那就按复杂度优劣往下套，比如暴力用了O(n2)，那看看排个序会不会好点，或者建个树存储一下，可不可以落到O(n log n)。要是面试官说还能再更好，那很多时候就是考虑用Hash了。如果某个问题是关于一个有序的数组，那就可以考虑二分查找算法将复杂度降低到O(log n)。最简单的例子就是“在一组数里找出两个数，满足它们的和与指定目标相同”。

面试是一个可以互相交流的过程，所以不要闷头写答案，时而不时的向面试官寻求提示和帮助也是体现解决问题的能力和方式。有时候问题的最优解是十分讨巧的方式，那只能心理说个脏话，而那种问题面试官肯定不是在期待最优解。对于某些实在答不上来的问题，就只能想想考的是什么算法和数据结构，然后回去继续刷题了。

体现能力的不是会做什么而是做过什么

工作以后，我感觉Onsite时4-5轮面试全考算法的面试已经很少的，更多的会考察系统设计(System Design)，以及询问过往工作经历。面的算法也都比较基础，通常复杂度都在O(n)。任何考察动态规划的面试题，我个人都觉得是在耍流氓，因为通常工作中也很少用到。但因为有针对练习过，我也不会惧怕，好几次都坦诚说题目我做过，面试官就直接略过到下一题。

当题目刷得越多，越觉得题目刷不完；工作时间越长，就越感觉面试问到的算法工作中都不用实现。因为标准库都有提供类似的方法，而且这些方法经历过数代的检验和测试，远比自己写的实现要更可靠，所以在工作中，我常常被同事要求删掉自己的实现直接调用库方法。对有工作经验的候选人的能力考察，已经不是看会不会做题，而更看重有没有用过某个库或框架。对于系统设计的问题，其实也更多来自对不同框架和系统的阅读和理解，还有对设计模式的学习和分析，而不仅仅只是算法和数据结构。

在工作中写的代码除了考虑是否能解决指定问题，还要考虑可读性、维护性、扩展性、测试性等等。但是刷题时，肯本不会考虑这些方面，因为代码只有自己看，且只针对当前一个问题。如果是限时的算法比赛，为了提高书写速度，可读性就更加惨不忍睹了。至于测试，我一直是把在线测试的运行过程和结果当做测试。

在线测试题的问题总是非常明确要做什么，就好像物理课里的“理想环境”。但现实工作的问题存在更多的模糊性，需要通过分析和交流来去发现真正的需求，这些是刷题所不能提高的。另外在线算法问题的测试数据规模也远不及正式项目。只有真正参与到项目中，经历了真正的开发流程，才能在面试中对面试官类似“你觉得最具挑战性的项目是什么”娓娓道来。

提高运行效率的方法除了变更不同的算法和数据结构，其实还有终极奥义，那就是“多线程(Multithreading)”。如果线程安全就可以把操作分配到多个线程上并发运行，使得效率大大增加，但刷题练习到的问题都是基于单线程的编程。至于某个实现是否满足多线程，以及如何做好线程安全又是一门学问。

所以刷题只能表示某道题目会做，但是真正能体现胜任工作的能力还需要在正式的工作中提升。这可能也是为什么对于没有工作经验的应届生，面试只考察算法。

 

要想在软件行业获得份理想的工作，刷题还是不可缺少的过程，但是刷题并不是工作唯一的要求。只不过算法题的考察决定着是否胜任软件行业的工作，能拿到什么的Package以及Level还要看其他的能力。在工作之余做点小项目，或许比刷题更有意义。