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

openkk 12年前
   <p> 文/赵劼</p>    <p> 今天早上一边出门一边在平板上读了<a href="/misc/goto?guid=4958185590815146876">左耳朵耗子</a>的新文章《<a href="http://www.open-open.com/news/view/148461b">为什么我反对纯算法面试题</a>》,略有想法。正逢外面暴雨如注,我就又回屋打开笔记本发了一些回复,特此整理一下。为了避免有人扭曲我的看法,我先声明我并不是反对这篇文章,相反我是基本同意其中的观点,只不过会加以一些补充,把其中一些我认为有些过头的地方按一按。您也可以认为我的观点是提交一些补丁,发了一些 Pull Request(当然不是<a href="/misc/goto?guid=4958522703578103762">这种 Pull Request</a>)就行了。我当时吐的第一个槽,是说文章太鄙视搞学术研究的人,说他们是书呆子,不关心业务需求,认为那是应试教育不会思考的产物。这个么其实不是重点,只不过触到了我的学术研究情结罢了,接下来的才是我真正想说的。</p>    <p> 耗子的文章以前两天的一个讨论引出话题,那是一道面试题:“找出无序数组的第 2 大的数”,而在当时的面试中,“排序”后再取数被判为不合格的答案。耗子认为其实在工程中“排序”才是更合适的做法,因为需求往往会变化,经过“需求分析”后更合理的决策应该是寻找“第K大的数”。我当时看到这题面试时就提出“寻找第K大的数”是一种过早优化,但耗子在新文章里的观点是,<code>FindKthMax (array, k)</code>才是更常见的接口,而不会是<code>Find2ndMax</code>。</p>    <p> 不过,即便是从“工程”角度来说,我还是认为“排序”是种不合适的做法,同时<code>FindKthMax (array, k)</code>依然是种过早优化。既然提出了需求是取第 2 个数,其实我不太建议去考虑提前去实现取第K个数的需求,因为这太复杂了。例如,难道排序一次之后真可以反复取数?排序后反复取的前提是数组不变化,且这么做往往接口往往不是<code>FindKthMax (array, k)</code>,而是<code>new ArrayFinder (array) .Find (k)</code>。还有,排序往往会改变数组本身元素顺序,那么是否允许?是否要做一份拷贝?要考虑这些实在太复杂了,其实既然目前的需求只是取第 2 个,这是个很有用的限制,两个变量一个循环可以让我们在 3 分钟里完成这个工作,那何必要做成通用的呢?</p>    <p> 此外,耗子认为是应试教育导致人们会选择O(n)的做法,而不是排序。我的感觉恰好相反,因为排序才是人人会接触过的事物,应试教育会让人对排序有深刻的印象。但是对我来说,我看到这题的第一反应就是“不能用排序”,因为这显然会产生不必要的开销。好吧,我不排除是“应试教育”让我能立即看清题目意图的可能性。</p>    <p> 换个角度来说,其实<code>Find2ndMax</code>这种接口也并没有什么问题,尽管只解决了特例,但针对这个特例高效地完成任务,且没有副作用。大伙可以去看看 .NET 框架里的<code>String.Concat</code>方法,它为2~4个字符串的连接操作各实现了一份重载,还提供了一个接受一个字符串数组的接口。由于大部分字符串的连接操作都在 4 个以内,因此单独为这些特例实现有针对性的实现,这在实际工程中并不罕见。</p>    <p> 我不反对纯面试算法,尤其是我认为一个简单的算法“你不会我就不能接受”的情况,这是个门槛。当然我也反对纯用很变态的面试算法来刷人,例如 <a href="/misc/goto?guid=4958522703655848833">winter</a> 被面试过的“Winner 树”以及传说中的“大草原”。此外,谁说纯算法不符合实际需求的啊?算法根据输入参数的大小变化选取不同策略这个太多了,纯算法没说在割离工程。更进一步地说,算法题也不代表只有标准答案才是正确的,算法题只是表现形式,考得也是解题思路,并非只有“最优解”才算过关,次优解以及沟通的过程都是在考察面试者。就如 winter 当年并不知道“Winner 树”,但通过发现题目中缺少的一个限制条件,使用取哈希值的方法给出了满足要求的解决方案,这也体现出了强大的应变能力,这对于“工程”来说也至关重要。</p>    <p> 有问题的不是算法题,只不过是面试官或是面试方式而已。</p>    <p> 再顺便谈下 ACM,因为我预感有人会借此鄙视 ACM。其实按照耗子在文章里的标准,ACM 绝对属于很工程的环境。因为你要在掌握算法的基础上,快速理解需求,建模,根据数据量选择合适的做法,符合题目的时间限制和空间限制快速解决问题。此时能够快速暴力枚举的就不用高级解法,甚至预先思考准备两种做法,一种无法通过立即换上第二种。更何况还是绝对在高压环境下,与所谓的“工程环境”十分相符。</p>    <p> 当然,ACM 也并非没有与工程中相违背的地方,例如不重视代码的可维护性,还有输入数据的边界条件等等。这顺便可以引出一个可以写入“面试宝典”的面试经验:拿到问题后确认每一个输入的细节,例如现在这题是 2 呢还是k,还有例如是不是会小于零等等。很多面试官其实也是在考察面试者对于边界条件的关注程度,问清楚这些有利于提升自己的形象,给自己争取思考的时间,几乎有百利而无一害。</p>    <p> 除非你遇到了极品面试官,这就是另外一回事情了。</p>    <p> 再除非你是美女,这就又是另外一回事情了。</p>    <p> 话说男人真是没出息的动物,看到美女就围着团团转流口水。</p>    <div id="come_from">    来自:     <a id="link_source2" href="/misc/goto?guid=4958522703751180372" target="_blank">blog.zhaojie.me</a>    </div>