Hello World
Spiga

我看面试时出(纯)算法题

2012-08-22 19:55 by 老赵, 13366 visits

今天早上一边出门一边在平板上读了左耳朵耗子的新文章《为什么我反对纯算法面试题》,略有想法。正逢外面暴雨如注,我就又回屋打开笔记本发了一些回复,特此整理一下。为了避免有人扭曲我的看法,我先声明我并不是反对这篇文章,相反我是基本同意其中的观点,只不过会加以一些补充,把其中一些我认为有些过头的地方按一按。您也可以认为我的观点是提交一些补丁,发了一些Pull Request(当然不是这种Pull Request)就行了。我当时吐的第一个槽,是说文章太鄙视搞学术研究的人,说他们是书呆子,不关心业务需求,认为那是应试教育不会思考的产物。这个么其实不是重点,只不过触到了我的学术研究情结罢了,接下来的才是我真正想说的。

耗子的文章以前两天的一个讨论引出话题,那是一道面试题:“找出无序数组的第2大的数”,而在当时的面试中,“排序”后再取数被判为不合格的答案。耗子认为其实在工程中“排序”才是更合适的做法,因为需求往往会变化,经过“需求分析”后更合理的决策应该是寻找“第K大的数”。我当时看到这题面试时就提出“寻找第K大的数”是一种过早优化,但耗子在新文章里的观点是,FindKthMax(array, k)才是更常见的接口,而不会是Find2ndMax

不过,即便是从“工程”角度来说,我还是认为“排序”是种不合适的做法,同时FindKthMax(array, k)依然是种过早优化。既然提出了需求是取第2个数,其实我不太建议去考虑提前去实现取第K个数的需求,因为这太复杂了。例如,难道排序一次之后真可以反复取数?排序后反复取的前提是数组不变化,且这么做往往接口往往不是FindKthMax(array, k),而是new ArrayFinder(array).Find(k)。还有,排序往往会改变数组本身元素顺序,那么是否允许?是否要做一份拷贝?要考虑这些实在太复杂了,其实既然目前的需求只是取第2个,这是个很有用的限制,两个变量一个循环可以让我们在3分钟里完成这个工作,那何必要做成通用的呢?

此外,耗子认为是应试教育导致人们会选择O(n)的做法,而不是排序。我的感觉恰好相反,因为排序才是人人会接触过的事物,应试教育会让人对排序有深刻的印象。但是对我来说,我看到这题的第一反应就是“不能用排序”,因为这显然会产生不必要的开销。好吧,我不排除是“应试教育”让我能立即看清题目意图的可能性。

换个角度来说,其实Find2ndMax这种接口也并没有什么问题,尽管只解决了特例,但针对这个特例高效地完成任务,且没有副作用。大伙可以去看看.NET框架里的String.Concat方法,它为2~4个字符串的连接操作各实现了一份重载,还提供了一个接受一个字符串数组的接口。由于大部分字符串的连接操作都在4个以内,因此单独为这些特例实现有针对性的实现,这在实际工程中并不罕见。

我不反对纯面试算法,尤其是我认为一个简单的算法“你不会我就不能接受”的情况,这是个门槛。当然我也反对纯用很变态的面试算法来刷人,例如winter被面试过的“Winner树”以及传说中的“大草原”。此外,谁说纯算法不符合实际需求的啊?算法根据输入参数的大小变化选取不同策略这个太多了,纯算法没说在割离工程。更进一步地说,算法题也不代表只有标准答案才是正确的,算法题只是表现形式,考得也是解题思路,并非只有“最优解”才算过关,次优解以及沟通的过程都是在考察面试者。就如winter当年并不知道“Winner树”,但通过发现题目中缺少的一个限制条件,使用取哈希值的方法给出了满足要求的解决方案,这也体现出了强大的应变能力,这对于“工程”来说也至关重要。

有问题的不是算法题,只不过是面试官或是面试方式而已。

再顺便谈下ACM,因为我预感有人会借此鄙视ACM。其实按照耗子在文章里的标准,ACM绝对属于很工程的环境。因为你要在掌握算法的基础上,快速理解需求,建模,根据数据量选择合适的做法,符合题目的时间限制和空间限制快速解决问题。此时能够快速暴力枚举的就不用高级解法,甚至预先思考准备两种做法,一种无法通过立即换上第二种。更何况还是绝对在高压环境下,与所谓的“工程环境”十分相符。

当然,ACM也并非没有与工程中相违背的地方,例如不重视代码的可维护性,还有输入数据的边界条件等等。这顺便可以引出一个可以写入“面试宝典”的面试经验:拿到问题后确认每一个输入的细节,例如现在这题是2呢还是k,还有例如是不是会小于零等等。很多面试官其实也是在考察面试者对于边界条件的关注程度,问清楚这些有利于提升自己的形象,给自己争取思考的时间,几乎有百利而无一害。

除非你遇到了极品面试官,这就是另外一回事情了。

再除非你是美女,这就又是另外一回事情了。

话说男人真是没出息的动物,看到美女就围着团团转流口水。

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

25 条回复

  1. myyers
    183.15.44.*
    链接

    myyers 2012-08-22 20:35:19

    再除非你是美女,这就又是另外一回事情了。

    总是表现的这么明显啊.

  2. E.T
    74.207.250.*
    链接

    E.T 2012-08-22 21:21:38

    我是来赞最后一句话的 XD

  3. 链接

    anders06 2012-08-22 21:55:21

    什么是“Winner树”,可否给个链接。 k大问题,最佳应该是用最小堆吧? 快排改进的算法也可以达到O(n),但快排并不适用于外部排序。

  4. Cat Chen
    216.157.85.*
    链接

    Cat Chen 2012-08-22 22:09:43

    ACM 训练会让人追求时间复杂度尽可能低,如果是个人都想得出 n log n 的排序能解决问题,这显然不是题目要求的解。

  5. Cat Chen
    216.157.85.*
    链接

    Cat Chen 2012-08-22 22:16:43

    一个有序数组如果要增删同时保持有序,就该用 binary heap,这是原文提到过的,做 ACM 的人肯定也懂这样做。

  6. jels108710
    144.212.3.*
    链接

    jels108710 2012-08-22 23:35:10

    我看完了全部,前面的看了觉得有理。综合老赵的和耗子的意见,可能会跟好一点。 但是,看到最后一句,我决定一定要上来留言赞一个!哈哈

  7. depeng
    218.4.149.*
    链接

    depeng 2012-08-23 08:33:14

    写作文最后一段一般上是“拔高主题 升华情操”用的,看来我是漏了什么信息,我完全看不懂最后2句话的外延。

  8. ghyghoo8
    122.224.129.*
    链接

    ghyghoo8 2012-08-23 10:10:47

    传说中的“大草原”?!~

  9. 链接

    Paul 2012-08-23 10:36:52

    同赞最后一句

  10. willerce
    125.77.202.*
    链接

    willerce 2012-08-23 10:39:52

    老赵最后的两句,明显是HTML5大会上的感受啊!

  11. 图灵谢工
    118.26.185.*
    链接

    图灵谢工 2012-08-24 16:43:04

    老赵心善啊中,对美女有贼心没贼胆。

  12. 老赵
    admin
    链接

    老赵 2012-08-24 16:51:34

    @图灵谢工

    有贼胆啊,只是心肠太好了,不舍得让女人伤心难过,哈哈。

  13. Joe  Wulf
    219.128.255.*
    链接

    Joe Wulf 2012-08-25 16:01:47

    关于ACM我想说一个题外话

    我参加过一次比赛,里面有一道题,大意是给出一个N x M的数组,检测是否能用L形积木填充。

    经过几分钟的讨论,我用一行代码就把这个题目PASS了。

  14. 老赵
    admin
    链接

    老赵 2012-08-25 23:39:57

    @Joe Wulf

    直接证明给出个O(1)的算法什么的最好玩了。

  15. 我的温柔
    77.13.182.*
    链接

    我的温柔 2012-08-28 05:06:55

    这次有理有据了。赞。

  16. 砖家
    106.187.50.*
    链接

    砖家 2012-08-29 01:11:54

    我是来顶最后一句话的......

  17. tongxl
    64.104.124.*
    链接

    tongxl 2012-08-29 09:27:36

    有问题的不是算法题,只不过是面试官或是面试方式而已

    一语道破天机。

  18. shell
    222.68.177.*
    链接

    shell 2012-09-03 15:34:47

    我是来顶最后一句话的

  19. PunCha
    125.98.160.*
    链接

    PunCha 2012-09-04 17:16:09

    我反而觉得Find2ndMax()更好,本来需求就是找第二大的,你写那么多多余的代码干什么!你凭什么保证你的那些多余的代码没有bug呢?测试员也只会根据需求来做测试,试想某一天,有人用了你未加测试过的代码(当然取第二大的是经过测试了的),花了大把时间,最终找到是你代码的BUG引起的,这会浪费多少时间!我反而比较喜欢当今的TDD与敏捷开发,迭代式开发!

  20. 链接

    martin zhang 2012-09-12 10:12:57

    很想知道大牛是怎样炼成的,怎么老能看到老赵的身影,大牛InfoQ上也榜上有名,虽然很讨厌你,但是确实打不过膜拜你啊。

  21. seaslee
    211.87.234.*
    链接

    seaslee 2012-09-13 15:12:42

    老赵说的不错,这种特例的需求是有的。像Scheme里面的vector,就有vector-first,vector-second,...这样的特殊过程。我觉得,算法在计算机中还是处于核心地位呀!

  22. 链接

    gole 2012-09-17 17:42:37

    有听说过对面试题的复杂度不满的,也听说过对面试官水平嗤之以鼻的(我对IBM面试官),头一次听说过有人对算法不满的。 其实我也怕算法,因为我么系统练过,只是理论学习了些表面,更没在ACM上锻炼过自己。 也许太想进那家公司,但结局让人痛苦,理解。 建议大家面试时,不要怕自己不会,没学过,关键要自己主动与面试官沟通,阐述自己能想到的东西,有条理的表达出来。 重在表达,沟通是合作的基础,你的语言表达能力基本能体现出你的智商。

  23. 融资
    115.236.164.*
    链接

    融资 2012-10-30 09:34:23

    像Scheme里面的vector,就有vector-first,vector-second,...这样的特殊过程。

  24. 剪板机刀片
    115.236.164.*
    链接

    剪板机刀片 2012-10-30 09:37:24

    花了大把时间,最终找到是你代码的BUG引起的,这会浪费多少时间!我反而比较喜欢当今的TDD与敏捷开发,迭代式开发!

  25. on_the_way
    119.161.188.*
    链接

    on_the_way 2014-06-27 10:05:44

    求第任意区间的第K大 有很多高效算法,只要搞过ACM时间长一点,应该都知道; 分块hash 线段树 划分树 查询一次大概 log(N)

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我