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

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

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

图片源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 ,请勿用于任何商业用途)

好烂啊有点差凑合看看还不错很精彩 (55 人打了分,平均分: 4.44 )
Loading...

为什么我反对纯算法面试题》的相关评论

  1. 张子,你怎么看上去天天在干程序员的活儿。华为就面过这个题目。我前阵子去三星试了试,人家压根没有算法题……。闹不清现在公司的思路到底是啥。@zhiqiang

  2. 文章是好文章我很同意,只是没明白中关于STL中nth_element的描述,nth_element不是只能保证随机元素X它所在列表中的大小位置,并不能保证Sa和Sb是存在某种特定的顺序,那么不管是哪种情况也不能只用Sa或Sb中元素的位置确定是第K大数啊。确实没看懂如能赐教不胜荣幸!

  3. java QQ群:67844123
    群简介:Java开发者技术专业交流、学习、讨论中心。八位超级靓号,高级群LV3的java QQ群。

  4. 其实现在招聘最大的矛盾在于:软件公司企图用一些码字员来完成程序员该做的事情。
    当然现在确实难招人也是个问题。

  5. 观雨 :
    文章是好文章我很同意,只是没明白中关于STL中nth_element的描述,nth_element不是只能保证随机元素X它所在列表中的大小位置,并不能保证Sa和Sb是存在某种特定的顺序,那么不管是哪种情况也不能只用Sa或Sb中元素的位置确定是第K大数啊。确实没看懂如能赐教不胜荣幸!

    兩個字:遞迴

  6. 如果是面试的目的是为了招聘研究人员,纯算法面试或许也可行。
    算法往往需要长考,搞基础研究不需要Speed。

    如果目的只是招聘做项目的程序员,尤其是速战速决的,纯算法面试就没太大意义了,个人认为经验和良好的编码习惯更加重要。

  7. 真不解為何要將問題複雜化?
    寫一個投入無序array,返回排過的array的method就好,再直接從array取第幾個就行了,只要一個method就解決所有問題,舉這例子不太恰當…

  8. 纯算法有重复造轮子的意味。
    我们需要的是会造车的人才,而不是造轮子的人才

  9. 正在面试找工作,比较喜欢根据项目经验被提问,不太喜欢连简历都不看,千人一面的固定问题。

  10. 我得说,查询会执行多少次,该排序再做还是不排序直接做,以及排序的话用在线排序还是离线排序,这其实还是算法分析的范畴……
    可以理解作者的意思,但我觉得这个例子举得不好。

  11. 我面人的时候,就是按照简历上写的问,一般如果写的和说的相差不大,印象分就加上。

  12. 这个跟学历一样,刷人用的。爱面面,不面滚。像我们真的要人的时候,笔试3、40分都可以。

  13. 额……BFPRT算法泪流满面……
    其实问这题的时候就是想知道简历上写了精通算法的人,到底知不知道排序和堆,顺便问问基本的实现和复杂度。没啥问题看起来还比较聪明的一般就给过了,有点儿概念就行了,东西都能学。
    微软 bing 的搜索日志每天下来还是蛮多的,以前招过一个开发做的很好很多年的,结果4个小时的事情被弄到20多个小时,大数据处理算法稍微差一点就差很多啊……

  14. = = 你的题目没出好。面试自古均奇葩,如果你需要被面试的人考虑以后的业务扩展和需求变化,则应该给出提醒,比如,你认为这样做,扩展性如何,xxx之类的。

    其实,你哪来会出现第二大这样的需求,当人面对一个奇葩的问题的时候,第一反应其多是奇葩的解混混就过去了……而你要求一个不知情的人来回想出业务情景,然后再扩展一大堆这之上的东西(而且你又没有要求)。

    感觉你的问题其实都没有脱离学院派。学院派里面也会有这样的问题的。也就是,你把问题丢给学院派的人后,他们的解法不会差的。比如这道题,如果题目变成“我们需要查找第N大的数,可能会查找M次”,几乎100%都是给出你的解法的。

    换句话说,其实应该去考,会不会发现问题,联系业务去寻找问题,考虑以后的需求变化带来的问题。这个……据我所知学院派的是搞不了的……

  15. 同意博主的观点,不能搞纯算法面试,虽然年底找工作,但是我却认为算法真的是能体验一个人的基础、逻辑能力的,当然加上基础知识、项目修养应该是最好的了。现在还在准备算法复习,博主的题目我还真是看过哈哈~~

  16. 很赞同不能搞纯算法面试,但看到你举的例子就很无语,明显的设计过度。设想,都是你的设想而已。设想设想设想,结果5分钟的代码就会被变成2人年的算法类库。其实很简单,第一次,直接搞定;第二次,直接搞定,并把第一次的代码调整下;第三次才是把代码重构成一个通用的算法。

  17. 不会算法,就这个只是找第二大的数,能不能直接一个循环挑出第二大的数行不行?没必要把整个数组从头排到尾吧??

  18. skandhas :

    Atry :
    我赞成用纯算法题面试,而且我也赞成用数学奥赛题面试。说白了这种题就是用来测智商的。笨人没资格成为我的同事。

    呵呵~ ,这种题根本测不出智商~。你老板的算法功底有你强吗?如果没你强的话,照你的逻辑,你这么一个聪明人仍然还是在给一个笨人打工? 这…情何以堪呢。;)

    正巧我就是老板啊

  19. 相当同意陈老师的观点,”我们太习惯于标准答案了,这是我国教育最悲哀的地方”,标准答案坑人啊。这种题目在面试的时候还算可以接受,最扯淡的就是大学里面的专业课考试了。最经典的就是考C语言的时候,给你一堆转义符号,填意思。现在的大学老师太不负责了,最后导致结果是,实现了一个OS的同学操作系统考了60分,过了甲骨文认证的数据库考70分。然后那些写代码都不带空格和缩进但是背课本背PPT的考得好的同学保研了,出国了。

  20. 提到工程角度的话,讲个题外话
    我要和别的商户竞价,我想排在所有竞争对手报价的第K名,请写一个程序,我输入K,和一个商品名,系统告诉我应该订多少价?(商家的所有商品的报价在一数组中)
    上面这道题,如果在实际的工程场景中,这个(商家的所有商品的报价在一数组中)数组从哪里来的,99%以上应该都是从数据库来的,既然是从数据库来的,那整个做法就不是这样了,就变成了
    select … order by … limit 1, n
    select * from (select … order by …) where rownum <= n
    select top n … order by …

  21. 我感觉很多现成算法都可以靠背诵来获得,包括很多ACM题目都是可以靠多做题来获得好成绩的。算法玩得好,感觉就像高中数学题做得多,看到就知道怎么解一样。不过要论发明创造,估计是使不上多少力气了。

  22. 冷雨 :

    观雨 :文章是好文章我很同意,只是没明白中关于STL中nth_element的描述,nth_element不是只能保证随机元素X它所在列表中的大小位置,并不能保证Sa和Sb是存在某种特定的顺序,那么不管是哪种情况也不能只用Sa或Sb中元素的位置确定是第K大数啊。确实没看懂如能赐教不胜荣幸!

    兩個字:遞迴

    可是递归的话复杂度怎么会是O(n)呢?

  23. dohkoos :很赞同不能搞纯算法面试,但看到你举的例子就很无语,明显的设计过度。设想,都是你的设想而已。设想设想设想,结果5分钟的代码就会被变成2人年的算法类库。其实很简单,第一次,直接搞定;第二次,直接搞定,并把第一次的代码调整下;第三次才是把代码重构成一个通用的算法。

    呵呵,这是个人风格的不同。
    有些人就喜欢吃完饭把碗堆在那里,第三天才洗。有些人马上就洗。
    有些人喜欢提前做准备,有些人喜欢不得不做的时候才去做,这就是风格不同,没什么好争的。

  24. LTaoist := = 你的题目没出好。面试自古均奇葩,如果你需要被面试的人考虑以后的业务扩展和需求变化,则应该给出提醒,比如,你认为这样做,扩展性如何,xxx之类的。
    其实,你哪来会出现第二大这样的需求,当人面对一个奇葩的问题的时候,第一反应其多是奇葩的解混混就过去了……而你要求一个不知情的人来回想出业务情景,然后再扩展一大堆这之上的东西(而且你又没有要求)。
    感觉你的问题其实都没有脱离学院派。学院派里面也会有这样的问题的。也就是,你把问题丢给学院派的人后,他们的解法不会差的。比如这道题,如果题目变成“我们需要查找第N大的数,可能会查找M次”,几乎100%都是给出你的解法的。
    换句话说,其实应该去考,会不会发现问题,联系业务去寻找问题,考虑以后的需求变化带来的问题。这个……据我所知学院派的是搞不了的……

    不同意。如果为了招聘带有需求分析能力的程序员,这种方式是必要的。你做过项目就会知道,几乎所有客户提出的需求都是奇葩需求。程序员必须具有从这种奇葩需求中判断出真正需求的能力。

  25. 不同意,N多大公司(例如Google,Facebook)都有很多纯算法题面试,之所以面试纯算法题是有原因的。而且那些只用O(n)的算法的人很可能就没仔细看过《算法导论》。

    > 如果我们的FindKthMaxNum()的请求量是m次,那么你的这个每次都要O(n)复杂度的算法得到的效果就是O(n*m),这一点,是书呆子式的学院派人永远想不到的。
    就喷你这一点,《算法导论》这本书算纯学术派吧,但第二版第14章,或第三版第15章中介绍的寻找K小数的算法,就是O(N*logN + M*logN)的,引入了一种叫做 ordered statistics tree 的数据结构。还支持动态添加和删除操作。

  26. @andy

    额,一道面试题装不下太多。如果本身是想考查程序员的算法和数据结构功底,事实上考查的却是挖掘需求分析的能力?当然,二者不是割裂的,见仁见智咯~~~如果是后者,恐怕是学校教育一直都不怎么重视或者没教好的地方。

  27. 简单来说,这个例子举得不恰当。
    复杂来说,用作者的思路来看这篇文章,可以得到如此结论:作者的自我存在感、优越感偏强,有碍于正常交流和表达。

  28. 如果面的是像我这样的应届生,如果考虑需求分析什么的话,那估计面试官会郁闷死,

  29. 我觉得有几个问题,
    第一,如果面的是像我这样的应届生,如果考虑需求分析什么的话,那估计面试官会郁闷死~~毕竟有实战经验的人还是少数,
    第二,平时在学校里写程序,基本都没有软件质量的概念,软件工程这个课程也是比较边缘的课程,面试为导向的结果吧~~
    第三, 不知道实际工作中算法是个什么地位,个人感觉应该只是少数核心模块的开发人员使用的多,大部分普通码农用的比较少吧,
    第四,python真的能把代码风格变的更好,至少我比以前进步了~

回复 阿萝 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注