为什么我反对纯算法面试题
算法面试可能是微软搞出来的面试方法,现在很多公司都在效仿,而且我们的程序员也乐于解算法题,我个人以为,这是应试教育的毒瘤!我在《再谈“我是怎么招程序员”》中比较保守地说过,“问难的算法题并没有错,错的很多面试官只是在肤浅甚至错误地理解着面试算法题的目的。”,今天,我想加强一下这个观点——我反对纯算法题面试!(注意,我说的是纯算法题)
我再次引用我以前的一个观点——
能解算法题并不意味着这个人就有能力就能在工作中解决问题,你可以想想,小学奥数题可能比这些题更难,但并不意味着那些奥数能手就能解决实际问题。
好了,让我们来看一个示例(这个示例是昨天在微博上的一个讨论),这个题是——“找出无序数组中第2大的数”,几乎所有的人都用了O(n)的算法,我相信对于我们这些应试教育出来的人来说,不用排序用O(n)算法是很正常的事,连我都不由自主地认为O(n)算法是这个题的标准答案。我们太习惯于标准答案了,这是我国教育最悲哀的地方。(广义的洗脑就是让你的意识依赖于某个标准答案,然后通过给你标准答案让你不会思考而控制你)
目录
功能性需求分析
试想,如果我们在实际工作中得到这样一个题 我们会怎么做?我一定会分析这个需求,因为我害怕需求未来会改变,今天你叫我找一个第2大的数,明天你找我找一个第4大的数,后天叫我找一个第100大的数,我不搞死了。需求变化是很正常的事。分析完这个需求后,我会很自然地去写找第K大数的算法——难度一下子就增大了。
很多人会以为找第K大的需求是一种“过早扩展”的思路,不是这样的,我相信我们在实际编码中写过太多这样的程序了,你一定不会设计出这样的函数接口—— Find2ndMaxNum(int* array, int len),就好像你不会设计出 DestroyBaghdad(); 这样的接口,而是设计一个DestoryCity( City& ); 的接口,而把Baghdad当成参数传进去!所以,你应该是声明一个叫FindKthMaxNum(int* array, int len, int kth),把2当成参数传进去。这是最基本的编程方法,用数学的话来说,叫代数!最简单的需求分析方法就是把需求翻译成函数名,然后看看是这个接口不是很二?!
(注:不要纠结于FindMaxNum()或FindMinNum(),因为这两个函数名的业务意义很清楚了,不像Find2ndMaxNum()那么二)
非功能性需求分析
性能之类的东西从来都是非功能性需求,对于算法题,我们太喜欢研究算法题的空间和时间复杂度了。我们希望做到空间和时间双丰收,这是算法学术界的风格。所以,习惯于标准答案的我们已经失去思考的能力,只会机械地思考算法之内的性能,而忽略了算法之外的性能。
如果题目是——“从无序数组中找到第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)。
搞学术的nuts们到了这一步一定会欢呼胜利!但是他们哪里能想得到性能的需求分析也是来源自业务的!
我们一说性能,基本上是个人都会问,请求量有多大?如果我们的FindKthMaxNum()的请求量是m次,那么你的这个每次都要O(n)复杂度的算法得到的效果就是O(n*m),这一点,是书呆子式的学院派人永远想不到的。因为应试教育让我们不会从实际思考了。
工程式的解法
根据上面的需求分析,有软件工程经验的人的解法通常会这样:
1)把数组排序,从大到小。
2)于是你要第k大的数,就直接访问 array[k]。
排序只需要一次,O(n*log(n)),然后,接下来的m次对FindKthMaxNum()的调用全是O(1)的,整体复杂度反而成了线性的。
其实,上述的还不是工程式的最好的解法,因为,在业务中,那数组中的数据可能会是会变化的,所以,如果是用数组排序的话,有数据的改动会让我重新排序,这个太耗性能了,如果实际情况中会有很多的插入或删除操作,那么可以考虑使用B+树。
工程式的解法有以下特点:
1)很方便扩展,因为数据排好序了,你还可以方便地支持各种需求,如从第k1大到k2大的数据(那些学院派写出来的代码在拿到这个需求时又开始挠头苦想了)
2)规整的数据会简化整体的算法复杂度,从而整体性能会更好。(公欲善其事,必先利其器)
3)代码变得清晰,易懂,易维护!(学院派的和STL一样的近似O(n)复杂度的算法没人敢动)
争论
你可能会和我有以下争论,
- 如果程序员做这个算法题用排序的方式,他一定不会像你想那么多。是的,你说得对。但是我想说,很多时候,我们直觉地思考,恰恰是正确的路。因为“排序”这个思路符合人类大脑处理问题的方式,而使用学院派的方式是反大脑直觉的。反大脑直觉的,通常意味着晦涩难懂,维护成本上升。
- 就是一道面试题,我就是想测试一下你的算法技能,这也扯太多了。没问题,不过,我们要清楚我们是在招什么人?是一个只会写算法的人,还是一个会做软件的人?这个只有你自己最清楚。
- 这个算法题太容易诱导到学院派的思路了。是的这道“找出第K大的数”,其实可以变换为更为业务一点的题目——“我要和别的商户竞价,我想排在所有竞争对手报价的第K名,请写一个程序,我输入K,和一个商品名,系统告诉我应该订多少价?(商家的所有商品的报价在一数组中)”——业务分析,整体性能,算法,数据结构,增加需求让应聘者重构,这一个问题就全考了。
- 你是不是在说算法不重要,不用学?千万别这样理解我,搞得好像如果面试不面,我就可以不学。算法很重要,算法题能锻炼我们的思维,而且也有很多实际用处。我这篇文章不是让大家不要去学算法,这是完全错误的,我是让大家带着业务问题去使用算法。问你业务问题,一样会问到算法题上来。
小结
看过这上面的分析,我相信你明白我为什么反对纯算法面试题了。原因就是纯算法的面试题根本不能反应一个程序的综合素质!
那么,在面试中,我们应该要考量程序员的那些综合素质呢?我以为有下面这些东西:
- 会不会做需求分析?怎么理解问题的?
- 解决问题的思路是什么?想法如何?
- 会不会对基础的算法和数据结构灵活运用?
另外,我们知道,对于软件开发来说,在工程上,难是的下面是这些挑战:
- 软件的维护成本远远大于软件的开发成本。
- 软件的质量变得越来越重要,所以,测试工作也变得越来越重要。
- 软件的需求总是在变的,软件的需求总是一点一点往上加的。
- 程序中大量的代码都是在处理一些错误的或是不正常的流程。
所以,对于编程能力上,我们应该主要考量程序员的如下能力:
- 设计是否满足对需求的理解,并可以应对可能出现的需求变化。
- 程序是否易读,易维护?
- 重构代码的能力如何?
- 会不会测试自己写好的程序?
所以,这段时间,我越来越倾向于问应聘者一些有业务意义的题,而且应增加或更改需求来看程序员的重构代码的能力,写完程序后,让应聘者设计测试案例。
比如:解析加减乘除表达式,字符串转数字,洗牌程序,口令生成器,通过ip地址找地点,英汉词典双向检索……
总之,我反对纯算法面试题!
(全文完)
(转载本站文章请注明作者和出处 宝酷 – sou-ip ,请勿用于任何商业用途)
《为什么我反对纯算法面试题》的相关评论
看那两个算法的简单程度,浩哥可能被算法面试刷过
“公欲善其事,必先利其器”
公—》工!
小结那段,写得真是太到位了,受益匪浅。
国外的GOOGLE, EBAY, FACEBOOK, AMAZON, MICROSOFT等大公司都用这个面试。 我去过几个, 都很机械。里面的人也知道这个不见得帮助找到牛人, 但至少避免招个菜鸟。
我带队照人基本上不考纯算法,但我提的问题都来自产品上而且都最终回到时间空间复杂度上的取舍。考的不是对一道题的熟悉,而是分析问题的能力,软件能力能培养,分析能力就难了。
说的好
@星月and圣冰雨
我个人觉得在这个问题上可能是例子有一些问题,书呆子自然可以通过多做题来解决这些问题。但是有更多的问题了,复杂度分析可是理论上的!不知道这位同仁有没有试过跑时间对比,我记得我有一次课的作业用C写了两个算法,O(n^2)和O(nlogn), 可能现在大家都觉得后者好了吧。偏偏不是。前者在数据量不是天文级的时候远比后者快。为什么呢?在算法复杂度的分析里我们总是假设所有的操作是等价的,并且忽略常数考虑增长。那么这个在实际卡时间的时候要不要紧呢?自然是有关系的,一个n一个2n一样O(n)他就是一倍的差距。 操作本身也不等价, 从内存里读数和直接找Cache,再和直接在register里面,和从硬盘里读取这个速度之间能差几万倍。写过一个lightsout游戏算法,有一个O(n^6)算法和一个O(n!)算法。最后跑出来都是0.05秒。。。猜猜0.05秒是什么时间?读取那个棋盘的时间。那么这么一搞就让大多数在理论领域搞算法研究的和真正实现有了本质区别(比如不到天文数字不用高端算法之类,明明有确定性多项式素数验证算法大家却还在用随机算法等等)。
书呆子之所以为书呆子,并不是因为他会做题,现实问题也是题目啊,而是因为他只会做书本上的题。书本上的题目自带的一些假设,一些理想化他都不知道,被他当做现实的情况,而不会随机应变,这才是书呆子的问题。真正研究算法的高手,比如本人理论计算机教授,上能写论文战unique games conjecture,下能进微软研究Markov Chain,脑子里面理论那套和实际那套,什么是本质,什么要考虑,分得清楚着呢。想必博主没有说这种人也是“书呆子”。
浩哥的这篇文章,让我不自觉得想起了《编程珠玑》这本书;如同这本书整体反应的逻辑是:
1. 好好问问需求
2. 分析需求的可变程度
3. 选择算法
4. 性能优化
学究派的固有思维是:什么算法的性能最好呢?但是这种方式,永远是片面的。
这篇文章是写于2012年。差不多6年过去了,这篇文章读起来还是那么有味道。
想消化掉这篇文章,真需要很多基础知识和经验的积累。至少我看到了以下知识点和经验:
1. 算法复杂度如何计算
2. 快速排序算法
3. 函数的命名方式
4. STL 是什么?
5. 理解功能性需求和非功能性需求
6. 服务端开发基本思维方式:接口访问量级的变化
7. 对软件工程中的健壮性、可变性、扩展性等了解
8. ……
在软件这个领域不深耕多年、思考多年,真心无法写出上面的文章。
说句话,我真心佩服笔者
这两天思考下来,又有新的心得:
“算法化思考方式” 和 “工程化思考方式”,这两种思维方式,我觉得都是必须的,重要的。 而且他们都是被刻意训练出来的。 但是难点在于,什么时候需要“算法化思考方式” ,什么时候需要“工程化思考方式”,这需要思考者去选择,最后可能还需要将这两种思考方式综合在一起,才能有一个好的产出!
注: “算法化思考方式” 是我随便杜撰的一个词,大家理解就好!
最近在狂补算法这一块的知识,正好看到“随机从一个数列中选择第K大的数,才知道,这个问题竟然是一个经典的算法问题。 详情见:“快速选择”算法的维基百科:https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E9%80%89%E6%8B%A9
上述评论错误纠正: “随机从一个数列中选择第K大的数 ” 纠正为 “从一个无序数列中选择第K大的数”。
算法题难道不是用来筛人的?
楼主的文章虽然写得不错,但是,你的观点其实有点绝对了,老实说吧,你高考的时候,里面的考题,有多少题是跟你实际生活、或者你未来的专业有直接关联或者挂钩的?但是高考就是用来区分你是读清华还是大专的。
这个世界就是这样,有些题目就是为了考验面试者的反应能力。你说只是做软件的,不需要纯算法,甚至不需要算法,那么两个做软件实力接近的候选人,你怎么决定要谁,这个算法,哪怕是纯算法,也是能让他们区分出实力的一种表现罢了,没必要这么愤世嫉俗,真的。
这不是愤世嫉俗,而且,作者也没有说不需要算法,作者反对的是面试时候纯粹用算法题来刷人的方式,以及追求标准答案的思维。作者最后也给出了一个可行的解决方案,比如说将真实的业务需求跟题目结合起来,很多东西放在真实需求下,每种算法的优劣评判可能就不一样了,以及需要考虑的问题就不仅仅是实现功能这么简单了,没有什么是绝对的。这其实也是为什么同样的排序任务,排序算法还分冒泡排序、插入排序、快速排序和堆排序等。
我想说的是,今天偶然搜到这篇7年前的文章,虽然过去的时间很久了,但是看完之后,我收获很大,同时也让我理清了算法跟应用开发的关系,知道了如何利用算法更好地解决实际问题,而不是做一个只会刷OJ的书呆子。
确实
对于 destroyCity 或 destroyBaghdad 的讨论,更我偏向于拥抱YAGNI原则,用尽少代码完成需求。
诚然,从software elegance角度说destroyBaghdad的确轧眼。然而资源时间有限的情况下,我认为应当尽可能地排斥过早优化。