首页 > 流程方法, 职场生涯 > 为什么我反对纯算法面试题

为什么我反对纯算法面试题

2012年8月22日 发表评论 阅读评论 66,149 人阅读    

算法面试可能是微软搞出来的面试方法,现在很多公司都在效仿,而且我们的程序员也乐于解算法题,我个人以为,这是应试教育的毒瘤!我在《再谈“我是怎么招程序员”》中比较保守地说过,“问难的算法题并没有错,错的很多面试官只是在肤浅甚至错误地理解着面试算法题的目的。”,今天,我想加强一下这个观点——我反对纯算法题面试!(注意,我说的是纯算法题)

图片源Wikipedia(点击图片查看词条)

我再次引用我以前的一个观点——

能解算法题并不意味着这个人就有能力就能在工作中解决问题,你可以想想,小学奥数题可能比这些题更难,但并不意味着那些奥数能手就能解决实际问题。

好了,让我们来看一个示例(这个示例是昨天在微博上的一个讨论),这个题是——“找出无序数组中第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,和一个商品名,系统告诉我应该订多少价?(商家的所有商品的报价在一数组中)”——业务分析,整体性能,算法,数据结构,增加需求让应聘者重构,这一个问题就全考了。
  • 你是不是在说算法不重要,不用学?千万别这样理解我,搞得好像如果面试不面,我就可以不学。算法很重要,算法题能锻炼我们的思维,而且也有很多实际用处。我这篇文章不是让大家不要去学算法,这是完全错误的,我是让大家带着业务问题去使用算法。问你业务问题,一样会问到算法题上来。

小结

看过这上面的分析,我相信你明白我为什么反对纯算法面试题了。原因就是纯算法的面试题根本不能反应一个程序的综合素质

那么,在面试中,我们应该要考量程序员的那些综合素质呢?我以为有下面这些东西:

  1. 会不会做需求分析?怎么理解问题的?
  2. 解决问题的思路是什么?想法如何?
  3. 会不会对基础的算法和数据结构灵活运用?

另外,我们知道,对于软件开发来说,在工程上,难是的下面是这些挑战:

  • 软件的维护成本远远大于软件的开发成本。
  • 软件的质量变得越来越重要,所以,测试工作也变得越来越重要。
  • 软件的需求总是在变的,软件的需求总是一点一点往上加的。
  • 程序中大量的代码都是在处理一些错误的或是不正常的流程。

所以,对于编程能力上,我们应该主要考量程序员的如下能力:

  1. 设计是否满足对需求的理解,并可以应对可能出现的需求变化。
  2. 程序是否易读,易维护?
  3. 重构代码的能力如何?
  4. 会不会测试自己写好的程序?

所以,这段时间,我越来越倾向于问应聘者一些有业务意义的题,而且应增加或更改需求来看程序员的重构代码的能力,写完程序后,让应聘者设计测试案例。

比如:解析加减乘除表达式,字符串转数字,洗牌程序,口令生成器,通过ip地址找地点,英汉词典双向检索……

总之,我反对纯算法面试题!

(全文完)

(转载本站文章请注明作者和出处 酷 壳 – CoolShell.cn ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——
好烂啊有点差凑合看看还不错很精彩 (37 人打了分,平均分: 4.81 )
Loading...Loading...
  1. coffeecn
    2012年9月17日01:04 | #1

    在工程上O(n)算法也是经常用到的,比如性能日志分析中统计m组数据99分位,如果每次都排序就太慢了。O(n*m)是最快的了

  2. 2012年9月17日03:05 | #2

    对了,指令的优化有编译器帮我们做
    算法的优化有 STL/boost 之类的库帮我们做
    唯有思想,是需要我们去创造。

  3. 星月and圣冰雨
    2012年9月19日10:49 | #3

    觉得是博主自己的眼界问题.

    算法是有特定场景的. 就好比数学建模, 你把模型抽象的有多理想化, 应用的算法也是不一样的.

    拿事实举例, 你说学院派的书呆子只会 O(N), 我告诉你. 没有哪个学院派在看到 “查询次数很多”的条件下还会用O(N)的算法.. 除非他真的是书呆子. 但书呆子并不代表所有学院派和搞算法的人。

    你的观点给我的印象就是也许你自己会在拿到题目时背出了O(N)的算法.然后交给面试官, 最后自己有感而发, 我怎么想的那么简陋呢…..

    同时, 我自己是搞数学的, 我从来都不会把背过的算法轻易套用到任何地方. 除非场景的条件是一模一样的。

    说了那么多, 以最后一个小问题来结尾, 对于01背包模型, 大家都学过有动态规划可以解答, 而且大家都能背出来动态规划的时间复杂度是 O( N * V ) , 所以是否你认为01背包问题就是多项式问题呢? (提示: 物品的体积未必是整数)

  4. fallenink
    2012年9月20日09:24 | #4

    博主说的很好。对于我们这些渐渐成长起来的程序员,有些“别人不告诉你,你又怎么会知道?”的思想(当然也可能会晚知道),它们是来之不易的。除了读文章,做点相关的思考。还比较喜欢看看评论,他们各式各样的看待角度与思维方式,很有趣。

  5. xxxxx
    2012年10月9日00:38 | #5

    @Atry

    @skandhas
    就TMD一sb

  6. 。。
    2012年10月31日13:09 | #6

    对于你这种思维层次的人多说什么也没用。。。。

  7. 。。
    2012年10月31日13:20 | #7

    @。。
    把一个ram存储模型的求第2大的问题强行扩展成在二级存储器模型下的求第k大的问题,来说别人没有利用工程思想扩展想到这一点。。。。太牵强了吧。。。。。

  8. aaa
    2012年11月1日16:12 | #8

    算法看出一个人的修为,博主还需一些历练。

  9. 水长东
    2012年11月2日22:26 | #9

    @星月and圣冰雨 是伪多项式的一个算法。

  10. 2012年11月9日16:34 | #10

    说到面试该怎么面,我这里有个实际的例子,欢迎大家来看看:
    http://blog.csdn.net/shanelooli/article/details/8155765

  11. cuiyuxuan
    2012年11月21日18:15 | #11

    同意:)

  12. htqx
    2012年12月8日16:22 | #12

    @hustzmd
    聪明的老板都会找傻子替自己打工。

  13. 程序员
    2013年1月6日19:28 | #13

    博主好奇怪 就像别人想不到一样 纯考算法没有任何问题 因为剩下的都是小儿科@星月and圣冰雨

  14. haha
    2013年2月6日16:41 | #14

    博主可能有很多经验,但是你说的max(2)到max(k)的例子实在是有欠妥当。且不说面试题出在那里,它自然有对应的解,随意乱猜需求变化不说是随意改题,也算是离题万里了。竟然还扯到应试教育?!妥妥儿的公知嘴脸呢。一个人若能知道排序,还给出了O(n)的算法,只要脑子正常的话遇到实际问题断然不会搞出博主说的那种很二的行为。博主自己在那里大战风车,当真欢乐的紧。

    博主若是有话要说,比如“设计函数接口时如何应对需求变化”,那就围绕主题来说好了。干嘛要竖个靶子自己很欢乐的打呢?这种旁敲侧击状的表达恰恰是应试教育作文的典范呢。

  15. py
    2013年2月22日23:33 | #15

    这个例子举得不太好, 有selection算法专治这类求第i大的数的问题,建立在快速排序的partition过程之上,O(n)。
    算法非常非常的重要,主要不在于算法本身,而在于学习算法的过程中,对计算机数学的能力是极大的锻炼。程序的bug,最麻烦的还是逻辑上的错误,根子在数学能力的匮乏上。我现在打算回炉,把mit公开课的数学基础课程都学一遍。

  16. dream
    2013年3月26日12:00 | #16

    这题换我做的话,就定义两个变量,遍历存储最大的两个数,搞定。
    脑子里不记那几个算法的实现,平时少用并且用的时候可以查到的东西,记着意义不大。
    退一步说,如果工作上经常用到某个算法,不必下功夫用几次就记住了。

  17. PE-NOW
    2013年7月17日06:22 | #17

    @星月and圣冰雨
    况且确实找出第k大的数有O(n)的方法,使用快速排序中的方法就可以找到第k大的数据了

  18. PE-NOW
    2013年7月17日06:24 | #18

    @星月and圣冰雨

    可以用组合的方法解决这个问题,最大需要存储的数据量是c(n,n/2),自底而上求解

  19. 才盛
    2013年8月10日01:23 | #19

    老大,看了您这篇文章,我越来越感谢上个月您电话面试我的情况。 那是一次让我倍感温暖,同时也认识到自己不足的面试。 整个过程真的让我很开心, 虽然我也很奇怪为什么您没面试我算法问题。呵呵, 我一共投了两份简历。同公司的 算法部门因为我不会KMP字符串匹配算法,直接把我刷掉了, 但是那位面试官给我的c++评价是很不错。 您问我的c++问题让我有点措手不及,但是整个过程您都在引导我,这让我很感动。 顺便说一下,KMP算法我现在写的相当熟练, 同时给我校的ACM出了一道题目。http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1482。
    谢谢您的指点。

  20. 逅舷儿
    2013年8月17日18:39 | #20

    口令生成器,通过ip地址找地点,英汉词典双向检索……
    请问这几个如何去实现呢?

  21. 小松鼠
    2013年9月16日16:11 | #21

    @星月and圣冰雨
    非常同意你的观点,lz有很多好文章,可是对算法的理解有点浅

  22. Alex
    2013年10月29日11:17 | #22

    我很喜欢博主这篇文章,因为说到我的心里去了。我一直思考算法面试题的有效性:一个刚出学校,或者做了充分应试准备的应聘者,可能会比身经百战的资深程序员在算法题面试上得到更高的分。何况现在网上已经流出大量的微软等公司的算法面试题,基本上背答案就行了。但是事实上资深程序员在实际工作上更有能力解决实际问题。

  23. wen
    2013年11月13日13:46 | #23

    “原因就是纯算法的面试题根本不能反应一个程序的综合素质!”这不是废话吗?

  24. micky
    2013年11月13日14:40 | #24

    需求需求,你又考虑过出纯算法题的面试官的需求么?出这种题的需求就是要考察算法能力而不是什么综合分析问题的能力。

  25. 2014年1月10日16:18 | #25

    看那两个算法的简单程度,浩哥可能被算法面试刷过

  26. haithink
    2014年4月30日20:40 | #26

    “公欲善其事,必先利其器”
    公—》工!

  27. RedMao
    2014年6月4日23:19 | #27

    小结那段,写得真是太到位了,受益匪浅。

  28. 2014年7月15日01:34 | #28

    国外的GOOGLE, EBAY, FACEBOOK, AMAZON, MICROSOFT等大公司都用这个面试。 我去过几个, 都很机械。里面的人也知道这个不见得帮助找到牛人, 但至少避免招个菜鸟。
    我带队照人基本上不考纯算法,但我提的问题都来自产品上而且都最终回到时间空间复杂度上的取舍。考的不是对一道题的熟悉,而是分析问题的能力,软件能力能培养,分析能力就难了。

  29. happysongs
    2015年3月1日16:27 | #29

    说的好

  30. foo
    2015年7月3日11:01 | #30

    @星月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 8138
  1. 2012年8月22日12:15 | #1
  2. 2012年8月23日13:51 | #2
  3. 2012年8月28日13:26 | #3
  4. 2012年8月30日09:02 | #4
  5. 2012年9月7日20:51 | #5
  6. 2012年9月8日13:27 | #6
  7. 2012年9月16日20:23 | #7
  8. 2012年9月28日09:08 | #8
  9. 2012年10月14日16:38 | #9
  10. 2012年10月15日15:24 | #10
  11. 2012年10月18日23:21 | #11
  12. 2012年10月30日11:51 | #12
  13. 2012年10月30日11:52 | #13
  14. 2012年12月18日20:49 | #14
  15. 2012年12月18日20:50 | #15
  16. 2012年12月28日11:30 | #16
  17. 2013年5月2日00:33 | #17
  18. 2013年5月10日09:40 | #18
  19. 2013年6月21日02:14 | #19
  20. 2013年6月21日09:46 | #20
  21. 2013年7月24日09:02 | #21
  22. 2013年10月27日15:19 | #22
  23. 2013年11月10日16:17 | #23
  24. 2013年11月11日16:04 | #24
  25. 2013年11月13日18:57 | #25
  26. 2013年11月22日17:32 | #26
  27. 2014年1月7日14:55 | #27
  28. 2014年1月22日13:48 | #28
  29. 2014年1月22日13:56 | #29
  30. 2014年3月7日14:43 | #30
  31. 2014年4月13日19:39 | #31
  32. 2014年5月27日12:46 | #32
  33. 2014年6月30日04:29 | #33
  34. 2014年10月24日02:57 | #34