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

标签: 思考讨论 | 发表时间:2012-08-22 11:55 | 作者:jeffz@live.com (老赵)
分享到:
出处:http://blog.zhaojie.me/

今天早上一边出门一边在平板上读了 左耳朵耗子的新文章《 为什么我反对纯算法面试题》,略有想法。正逢外面暴雨如注,我就又回屋打开笔记本发了一些回复,特此整理一下。为了避免有人扭曲我的看法,我先声明我并不是反对这篇文章,相反我是基本同意其中的观点,只不过会加以一些补充,把其中一些我认为有些过头的地方按一按。您也可以认为我的观点是提交一些补丁,发了一些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,还有例如是不是会小于零等等。很多面试官其实也是在考察面试者对于边界条件的关注程度,问清楚这些有利于提升自己的形象,给自己争取思考的时间,几乎有百利而无一害。

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

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

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

相关 [面试 算法] 推荐:

面试失败之24点算法

- UnderSn0w - 博客园-首页原创精华区
  周一风尘仆仆(上午6点抵达成都)的去参加了凡客成都研发中心的面试,虽然经历一夜的折腾让我感觉头脑很不清醒,不过这种面试状态也不错,能让我深刻体验一下在不清醒状态下进行的思考和回答问题. 午饭过后便出了门,习惯了不堵车,突然觉得成都的交通真的很拥堵. 到达凡客成都研发中心填完表后等了大概10多分钟,面试官把我带进会议室,开始了面试.

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

- - 老赵点滴 - 追求编程之美
今天早上一边出门一边在平板上读了 左耳朵耗子的新文章《 为什么我反对纯算法面试题》,略有想法. 正逢外面暴雨如注,我就又回屋打开笔记本发了一些回复,特此整理一下. 为了避免有人扭曲我的看法,我先声明我并不是反对这篇文章,相反我是基本同意其中的观点,只不过会加以一些补充,把其中一些我认为有些过头的地方按一按.

大数据量的算法面试题

- - 编程 - 编程语言 - ITeye博客
作者:July、youwang、yanxionglu. 时间:二零一一年三月二十六日. 说明:本文分为俩部分,第一部分为10道海量数据处理的面试题,第二部分为10个海量数据处理的方法总结. 出处:http://blog.csdn.net/v_JULY_v. 第一部分、十道海量数据处理面试题. 1、海量日志数据,提取出某日访问百度次数最多的那个IP.

秒杀名企面试--150道算法面试题攻略

- - 弯曲评论

面试算法之排序算法集锦

- - CSDN博客推荐文章
排序算法在面试过程中是经常会考的,这是很基础的,面试官觉得你应该很熟悉这些东西,如果你半个小时内写不出来,那基本就给跪了,因为这真的是狠基础狠基础的东西,所以我们得对一些基本的排序算法烂熟于胸,对这些排序思想,效率了如指掌,才能让面试官觉得你还行. 基本的排序算法有:直接插入排序,冒泡排序,简单选择排序,shell排序,归并排序,快速排序,堆排序.

面试10大算法汇总+常见题目解答

- - Java - 编程语言 - ITeye博客
面试10大算法汇总+常见题目解答. 最近更新: 2013年12月15日 持续更新…. 英文版的 “面试10大算法汇总”日最高访问量已高达4,318次. 这说明总结程序员面试算法有实际意义,比读算法书更有效. 下面是中文版的10大算法汇总+有代表性的题目汇总. 这些概念是专门为面试准备的,因为日常编程中我们很少会自己去写一个链表或者做一个图,也不会经常使用没有效率的递归.

[原]程序员如何快速准备面试中的算法

- - 结构之法 算法之道
    程序员如何快速准备面试中的算法.     我决定写篇短文,即为此文. 之所以要写这篇文章,缘于微博上常有朋友询问,要毕业找工作了,如何备战算法. 尽管在 微博上简单梳理过,如下图所示:.     但因字数限制,特撰此文着重阐述下:程序员如何快速准备面试中的算法,顺便推荐一些相关的书籍或资料.

面试常见十大类算法汇总

- - ITeye博客
在Java中,String是一个包含char数组和其它字段、方法的类. 如果没有IDE自动完成代码,下面这个方法大家应该记住: . String/arrays很容易理解,但与它们有关的问题常常需要高级的算法去解决,例如动态编程、递归等. 下面列出一些需要高级算法才能解决的经典问题:. 在Java中实现链表是非常简单的,每个节点都有一个值,然后把它链接到下一个节点.

为什么最难不过二叉树的算法出现在面试题中都会被应聘者抱怨?

- - 知乎每日精选
我大二学数据结构,大作业的一部分是自己实现一个平衡二叉树,没有任何问题. 要是那个时候别人来问我各种细节,毫无压力. 然后我现在研二,自那次大作业以后再也没有实现过平衡二叉树. 需要使用各种索引的时候都是无论是自己实现还是直接调用库,都不是平衡二叉树. 然后现在要是来问我关于平衡二叉树的各种细节,当然我还记得左旋右旋左右旋右左旋,但你要我把所有的指针赋值都准确回答出来,我一定办不到.

变态面试

- Tony - 叫兽与你同在