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

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

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

图片源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. 陈老师这样的非纯算法面试题考察范围更大难度也显然更大了,算法变成了有血有肉的有机体。

  2. 找出无序数组中第2大的数这种题谈不上是算法题,这在考一种直觉,或者说考智商。与作者最后给的例子是两个不同的层面。喜欢自己培养员工的公司喜欢搞前面这种,让员工一上来就要实际干活的要用后面这种。

  3. 纯算法题做面试题最大的问题是,大部分算法,比如说找第k大数的线性算法,作为人类智慧的结晶,面试者在面试的短时间内根本做不出来。最后基本上变成在考面试者有没有见过类似的题目。这样的话作用非常有限。

  4. 我前段时间也去面了一些,试了试水,现在不少公司都是这样的,有时候有些无奈。

  5. 算法是对现有各种业务的抽象和归纳,绝不单单是算法,如果算法只是算法,那就是学院派了。算法一定是为了解决实际问题服务的

  6. 海纳百川 :

    基础知识和项目经验哪个重要?知识是基础,做项目能总结出经验,纯算法并不可取,但能考察基础知识。

    都重要,可以一起考,参看我文中把该算法题转成相关的业务题。

  7. 顶,我一直觉得出纯算法题那些公司都不是技术人员出的题,都是hr上网瞎找的。如果是技术人员出的,只能说明这个公司的技术人员水平太差。这样的公司都没有去的兴趣。
    我认为除了对上个月刚毕业的学生来说可能有点用,对有工作经验的人来说都不能靠这种纯算法题看出真实水平来。

  8. zhiqiang :
    纯算法题做面试题最大的问题是,大部分算法,比如说找第k大数的线性算法,作为人类智慧的结晶,面试者在面试的短时间内根本做不出来。最后基本上变成在考面试者有没有见过类似的题目。这样的话作用非常有限。

    有道理!

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

  10. 哦你当然是无敌的, 因为你站在工程角度说学院派不好, 这和站在工程角度说工程好一样无敌:) 但是站在中立的角度, 我觉得只是二者的思路和目的不同罢了…并无好坏之分. 当然对于面试来说确实有啦… // 说到最后还是看要招什么人?

    1. 我以为我一直有个假设——招聘的是程序员。而且,我一直以为这样的学术派的面试题对工程派程序员很不公平。呵呵。

  11. DestroyBaghdad,哈哈。
    说实在的,作为没正规受过编程训练的人,我完全不知道O(n)是啥意思,但是排序就很容易理解了。
    英国一些公司招聘程序员的时候是不要求面试者懂代码的,笔试的题目都是出一个问题,让面试者写伪代码,比如最短路程的解法,一个酒店里电梯的程序设计,等等……

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

    嗯,楼主的配图是为你定制的。

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

    你牛逼完了!

  14. 除非要设计文件存储,否则会用二叉平衡树比如rbtree而不是b+树什么的

    另外搞笑的是没有人用纯算法的面试题面试别的能力,算法题是面试算法能力的…… 你们觉得难的照样有牛人能搞定,人家都变成应试的了- –

  15. 以前刚毕业的时候,面试腾讯的校招,就是楼主讲的那种很恶心的情况。第一次,面试官找了一堆算法、脑筋急转弯的题目,我大部分都不会,除了那些之前在网络上看过的。然后我回来一查,这些题目网络上都有。这就是,我有做题,我就能过,我没做题,我就不过,对于那些玩ACM的来说,很容易,因为他们整天就玩这个,但对于只懂基础数据结构,只学基础知识的应届生来说,一点都不容易。第二次,面试官就一句话,写个hash、快排,写完之后也没任何延伸,接着就随便扯两句,然后就让你走了,非常不尊重面试者。面试官水平差,有工作经验的人肯定能感觉到。

  16. 同意博主的看法,除非是专门设计算法的工作,否则工程学思想比算法重要得多。

  17. 作为找工作的人,有怎么能这么要求公司呢?文中那个第2大数的复杂度如果在面试里还好说.要是在笔试里,就一个填空..那也没法折腾这么多啊..

  18. 如果是招刚毕业的应届生尤其是要去搞研究方面的,算法和数学很重要,这样做没啥不可。如果是招来做业务,做项目的,或者是招聘非应届的有工作经验的,当然这样很不合理,因为不是每个人都是去做纯理论,做研究的。都去搞算法,做研究当计算机科学家,软件工程这门专业也没有存在的必要了。很多人压根没有翻过《算法导论》这本书,但照样可以参与很多项目。所以,我觉得微软,google这些企业搞算法有他们的目的和需求,但大量的公司都去效仿,就好比这几天新闻上说的火热的奥数和应试挂钩的问题,这就真出现问题了。

  19. 试想,如果我们在实际工作中得到这样一个题 我们会怎么做?我一定会分析这个需求,因为我害怕需求未来会改变,今天你叫我找一个第K大的数,明天你找我写一个网络流,后天叫我写一个动态树,我不搞死了。需求变化是很正常的事。分析完这个需求后,我会很自然地去写网络流和动态树——难度一下子就增大了。

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

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

  21. 在3年前我写过一些关于财务计算的代码,被人训得很惨,因为扩展性不好, 所有的数都是编在程序里的,如果会计计算方法变了就整个都得重写.可是因为太麻烦,所以也没有人去修改它. 然后3年过去了, 这段代码除了改了1个数以外什么也没变过.

    股市有句老话:”跟随市场,不要预测市场”,我觉得用在需求变化上也挺合适,”拥抱变化,可是不要预测变化”. 找第2大的数你声明一个叫FindKthMaxNum(int* array, int len, int kth),然后明天需求如你所愿变化了: 找第2小的数, 找离中位数第2近的数. 你觉得如何?

  22. dfewfe :
    在3年前我写过一些关于财务计算的代码,被人训得很惨,因为扩展性不好, 所有的数都是编在程序里的,如果会计计算方法变了就整个都得重写.可是因为太麻烦,所以也没有人去修改它. 然后3年过去了, 这段代码除了改了1个数以外什么也没变过.
    股市有句老话:”跟随市场,不要预测市场”,我觉得用在需求变化上也挺合适,”拥抱变化,可是不要预测变化”. 找第2大的数你声明一个叫FindKthMaxNum(int* array, int len, int kth),然后明天需求如你所愿变化了: 找第2小的数, 找离中位数第2近的数. 你觉得如何?

    找第二小的数是FindKthMaxNum(a, len, len – 3)(k从0开始), 离中位数第二近的数是:

    如果len为奇数, 结果为FindKthMaxNum(a, len, len / 2 – 1)和FindKthMaxNum(a, len, len / 2 + 1)离中位数更远的那个;
    如果len为偶数, 结果为FindKthMaxNum(a, len, len / 2 – 1)和FindKthMaxNum(a, len, len / 2)离中位数更远的那个;
    当然, 如果Find二者距离相等, 还需要再明确需求.

    我想说的是, 机制要和策略分离. 策略多变, 自然不应纳入库代码; 但是机制一定要灵活, 不然无法让众多策略以”薄封装”的形式出现, 上面两个就是比较薄的例子. 用”策略供不应求”来推出”机制不必有预见性”是不恰当的.

  23. 我认为纯算法题面试无所谓的,
    你说的那些东西只不过是在纯算法上面强加了很多条件,而且是隐含式的。
    这就很不好了,你隐含的假设这个查找是竞价排名,可能面试者隐含的认为这是从500T的磁带阵列里找一个数据。
    当然需要算法就不一样了。

    当你把所有的隐含条件都显式的给出之后——它还是一道纯算法题:
    “找出无序数组n中第K大的数,请求量是m次,K每次不同”
    甚至还可以针对不同算法给出所需的期望时间和最坏时间。

    我的意思是,当面试的人把那些虚无飘渺的隐含假设条件明确化之后,这显然还是一道纯算法题。

  24. 如果题目中说明会多次调用,应试者自然就会用排序并缓存了。条件不充分的题目更像是个脑筋急转弯。

    写程序的不知道这个kth-max算法,说明了基本功不扎实,知识量不够。

    我并不是考他的智商,所以不会要求应试者花时间实现它,只要知道它是O(n)的并能利用即可。

    单纯的算法题不能找到合适的人,但能反映出一个人这方面的素质,定位他的薪水。

    出什么样的题,选什么样的答案,取决于你想要什么样的人。这是你自己的算法题。

  25. 顶,鄙视那种只看算法和写代码能力的面试。 可以像博主说的那样,全方位的考察,最后发掘出最合适的职位。

  26. @Tim Shen
    好吧, 你可以用FindKthMaxNum来表示找第2小的数. 可是很明显我的重点不在怎么实现找第2小的数上,而且也不在于”策略供不应求”上. 关键在于,需求虽然会变化, 但是它不一定会在什么地方变化, 变化的方向也不一定如你预期. 所以你当然需要利用一些设计模式来保证系统具有扩展性, 但是你不应该同时假设需求会如何变化,让系统同时适应这种假设的需求,这样应该说就叫做过度设计.

  27. 我反而觉得在没有其他条件的情况下, O(n)算法才是直觉的算法, 反而受过训练的程序员才会想到排序. 比如不是在计算机上, 让一个人从一堆扑克中挑出最小的一张, 一般人是不可能靠脑子去排序的, O(n)是来源于生活经验的直觉算法. 排序才是训练的结果. 我面试就遇到过这个问题, 当时我给出的就是O(n)算法, 然后补充了一句: 也可以先排序. 在题干的条件下, 我给出了最优的算法, 有什么问题么? 如果真的想考察程序员的能力, 可以在题干的基础上, 加上: 请给出两种算法, 比较优劣.

  28. 1、算法面试始终是一个考察软件开发人员的一个非常合适的手段,只要不是为了算法而算法
    2、很多公司做的事情确实不需要面试算法,不要为了装B而面算法。如果确实用得到算法,那就大胆的面好了
    3、博主说的软件工程方面的东西,和算法并不矛盾。。。

  29. “2)规整的数据会简化整体的算法复杂度,从而整体性能会更好。(公欲善其事,必先利其器)”

    我来挑错字的,后面括号里是”工欲善其事”

  30. Nano :
    我反而觉得在没有其他条件的情况下, O(n)算法才是直觉的算法, 反而受过训练的程序员才会想到排序. 比如不是在计算机上, 让一个人从一堆扑克中挑出最小的一张, 一般人是不可能靠脑子去排序的, O(n)是来源于生活经验的直觉算法. 排序才是训练的结果. 我面试就遇到过这个问题, 当时我给出的就是O(n)算法, 然后补充了一句: 也可以先排序. 在题干的条件下, 我给出了最优的算法, 有什么问题么? 如果真的想考察程序员的能力, 可以在题干的基础上, 加上: 请给出两种算法, 比较优劣.

    确实是。比如求无序数组中前n大的。不需要全部排序。
    一些应试教育受害者会开始背书上的哪个排序算法复杂度最好。
    其实面试算法,有时候不是为了看你会不会算法,而是看这个人的思维方式,说白了就是够不够聪明。

发表回复

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