CWYAlpha

Just another WordPress.com site

Thought this was cool: 我看面试时出(纯)算法题

leave a comment »


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

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

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

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


0

   

0

IT 牛人博客聚合网站(udpwork.com) 聚合
|
评论: 0
|
10000+ 本编程/Linux PDF/CHM 电子书下载

from IT牛人博客聚合网站: http://www.udpwork.com/item/7992.html

Written by cwyalpha

八月 22, 2012 在 1:35 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: