为什么我反对纯算法面试题
openkk 12年前
<p> 文/<a href="/misc/goto?guid=4958185560036269721" target="_blank">陈皓</a> </p> <p> 算法面试可能是微软搞出来的面试方法，现在很多公司都在效仿，而且我们的程序员也乐于解算法题，我个人以为，这是应试教育的毒瘤！我在《<a title="再谈“我是怎么招聘程序员的”（上）" href="/misc/goto?guid=4958337036877492589">再谈“我是怎么招程序员”</a>》中比较保守地说过，“问难的算法题并没有错，错的很多面试官只是在肤浅甚至错误地理解着面试算法题的目的。”，今天，我想加强一下这个观点——我反对纯算法题面试！（注意，我说的是纯算法题）</p> <p style="text-align:center;"><a href="/misc/goto?guid=4958522589158548028"><img title="Sheldon_Cooper" alt="为什么我反对纯算法面试题" src="https://simg.open-open.com/show/424296f7968e5cef24ede5031d1df09c.jpg" width="250" height="333" /></a></p> <p style="text-align:center;">图片源 Wikipedia（点击图片查看词条）</p> <p> <strong>我再次引用我以前的一个观点——</strong></p> <blockquote> <p>能解算法题并不意味着这个人就有能力就能在工作中解决问题，你可以想想，小学奥数题可能比这些题更难，但并不意味着那些奥数能手就能解决实际问题。</p> </blockquote> <p> 好了，让我们来看一个示例（这个示例是昨天在<a href="/misc/goto?guid=4958522589259181358" target="_blank">微博上的一个讨论</a>），这个题是——“<strong>找出无序数组中第 2 大的数</strong>”，几乎所有的人都用了O(n)的算法，我相信对于我们这些应试教育出来的人来说，不用排序用O(n)算法是很正常的事，连我都不由自主地认为O(n)算法是这个题的标准答案。<strong>我们太习惯于标准答案了，这是我国教育最悲哀的地方</strong>。（广义的洗脑就是让你的意识依赖于某个标准答案，然后通过给你标准答案让你不会思考而控制你）</p> <p> <strong>功能性需求分析</strong></p> <p> 试想，如果我们在实际工作中得到这样一个题我们会怎么做？我一定会分析这个需求，因为我害怕需求未来会改变，今天你叫我找一个第 2 大的数，明天你找我找一个第 4 大的数，后天叫我找一个第 100 大的数，我不搞死了。需求变化是很正常的事。分析完这个需求后，我会很自然地去写找第K大数的算法——难度一下子就增大了。</p> <p> 很多人会以为找第K大的需求是一种“过早扩展”的思路，不是这样的，我相信我们在实际编码中写过太多这样的程序了，你一定不会设计出这样的函数 接口—— Find2ndMaxNum (int* array， int len)，就好像你不会设计出 DestroyBaghdad (); 这样的接口，而是设计一个 DestoryCity ( City& ); 的接口，而把 Baghdad 当成参数传进去！所以，你应该是声明一个叫 FindKthMaxNum (int* array， int len, int kth)，把 2 当成参数传进去。<strong>这是最基本的编程方法，用数学的话来说，叫代数</strong>！最简单的需求分析方法就是把需求翻译成函数名，然后看看是这个接口不是很二？！</p> <p> （注：不要纠结于 FindMaxNum ()或 FindMinNum ()，因为这两个函数名的业务意义很清楚了，不像 Find2ndMaxNum ()那么二）</p> <p> <strong>非功能性需求分析</strong></p> <p> 性能之类的东西从来都是非功能性需求，对于算法题，我们太喜欢研究算法题的空间和时间复杂度了。我们希望做到空间和时间双丰收，这是算法学术界的风格。所以，<strong>习惯于标准答案的我们已经失去思考的能力，只会机械地思考算法之内的性能，而忽略了算法之外的性能</strong>。</p> <p> 如果题目是——“从无序数组中找到第K个最大的数”，那么，我们一定会去思考用O(n)的线性算法找出第K个数。事实上，也有线性算法—— STL 中可以用 nth_element 求得类似的第n大的数，其利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分 Sa 和 Sb。Sa 中的元素大于等于X，Sb 中元素小于X。这时有两种情况：1）Sa 中元素的个数小于k，则 Sb 中的第k-Sa 个元素即为第k大数；2） Sa 中元素的个数大于等于k，则返回 Sa 中的第k大数。时间复杂度近似为O(n)。</p> <p> 搞学术的 nuts 们到了这一步一定会欢呼胜利！但是他们哪里能想得到性能的需求分析也是来源自业务的！</p> <p> <strong>我们一说性能，基本上是个人都会问，请求量有多大？如果我们的 FindKthMaxNum ()的请求量是m次，那么你的这个每次都要O(n)复杂度的算法得到的效果就是O(n*m)，这一点，是书呆子式的学院派人永远想不到的。</strong>因为应试教育让我们不会从实际思考了。</p> <p> <strong>工程式的解法</strong></p> <p> 根据上面的需求分析，有软件工程经验的人的解法通常会这样：</p> <p> 1）把数组排序，从大到小。</p> <p> 2）于是你要第k大的数，就直接访问 array[k]。</p> <p> 排序只需要一次，O(n*log (n))，然后，接下来的m次对 FindKthMaxNum ()的调用全是O(1)的，整体复杂度反而成了线性的。</p> <p> 其实，上述的还不是工程式的最好的解法，因为，在业务中，那数组中的数据可能会是会变化的，所以，如果是用数组排序的话，有数据的改动会让我重新排序，这个太耗性能了，如果实际情况中会有很多的插入或删除操作，那么可以考虑使用B+ 树。</p> <p> 工程式的解法有以下特点：</p> <p> 1）很方便扩展，因为数据排好序了，你还可以方便地支持各种需求，如从第 k1 大到 k2 大的数据（那些学院派写出来的代码在拿到这个需求时又开始挠头苦想了）</p> <p> 2）规整的数据会简化整体的算法复杂度，从而整体性能会更好。（公欲善其事，必先利其器）</p> <p> 3）代码变得清晰，易懂，易维护！（学院派的和 STL 一样的近似O(n)复杂度的算法没人敢动）</p> <p> <strong>争论</strong></p> <p> 你可能会和我有以下争论，</p> <ul> <li><strong>如果程序员做这个算法题用排序的方式，他一定不会像你想那么多</strong>。是的，你说得对。但是我想说，很多时候，我们直觉地思考，恰恰是正确的路。因为“排序”这个思路符合人类大脑处理问题的方式，而使用学院派的方式是反大脑直觉的。反大脑直觉的，通常意味着晦涩难懂，维护成本上升。</li> </ul> <ul> <li><strong>就是一道面试题，我就是想测试一下你的算法技能，这也扯太多了</strong>。没问题，不过，我们要清楚我们是在招什么人？是一个只会写算法的人，还是一个会做软件的人？这个只有你自己最清楚。</li> </ul> <ul> <li><strong>这个算法题太容易诱导到学院派的思路了</strong>。是的这道“找出第K大的数”，其实可以变换为更为业务一点的题目——“<strong>我要和别的商户竞价，我想排在所有竞争对手报价的第K名，请写一个程序，我输入K，和一个商品名，系统告诉我应该订多少价？</strong>（商家的所有商品的报价在一数组中）”——业务分析，整体性能，算法，数据结构，增加需求让应聘者重构，这一个问题就全考了。</li> </ul> <ul> <li><strong>你是不是在说算法不重要，不用学？</strong>千万别这样理解我，搞得好像如果面试不面，我就可以不学。<strong>算法很重要，算法题能锻炼我们的思维，而且也有很多实际用处</strong>。我这篇文章不是让大家不要去学算法，这是完全错误的，我是让大家带着业务问题去使用算法。问你业务问题，一样会问到算法题上来。</li> </ul> <p> <strong>小结</strong></p> <p> 看过这上面的分析，我相信你明白我为什么反对纯算法面试题了。原因就是<strong>纯算法的面试题根本不能反应一个程序的综合素质</strong>！</p> <p> 那么，在面试中，我们应该要考量程序员的那些综合素质呢？我以为有下面这些东西：</p> <ol> <li>会不会做需求分析？怎么理解问题的？</li> <li>解决问题的思路是什么？想法如何？</li> <li>会不会对基础的算法和数据结构灵活运用？</li> </ol> <p> 另外，我们知道，对于软件开发来说，在工程上，难是的下面是这些挑战：</p> <ul> <li>软件的维护成本远远大于软件的开发成本。</li> <li>软件的质量变得越来越重要，所以，测试工作也变得越来越重要。</li> <li>软件的需求总是在变的，软件的需求总是一点一点往上加的。</li> <li>程序中大量的代码都是在处理一些错误的或是不正常的流程。</li> </ul> <p> 所以，对于编程能力上，我们应该主要考量程序员的如下能力：</p> <ol> <li>设计是否满足对需求的理解，并可以应对可能出现的需求变化。</li> <li>程序是否易读，易维护？</li> <li>重构代码的能力如何？</li> <li>会不会测试自己写好的程序？</li> </ol> <p> 所以，这段时间，我越来越倾向于问应聘者一些有业务意义的题，而且应增加或更改需求来看程序员的重构代码的能力，写完程序后，让应聘者设计测试案例。</p> <p> 比如：解析加减乘除表达式，字符串转数字，洗牌程序，口令生成器，通过 ip 地址找地点，英汉词典双向检索……</p> <p> <strong>总之，我反对纯算法面试题！</strong></p> <div id="come_from"> 来自: <a id="link_source2" href="/misc/goto?guid=4958522589355378986" target="_blank">coolshell.cn</a> </div>