我看面试时出（纯）算法题
2012-08-22 19:55 by 老赵, 14332 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，还有例如是不是会小于零等等。很多面试官其实也是在考察面试者对于边界条件的关注程度，问清楚这些有利于提升自己的形象，给自己争取思考的时间，几乎有百利而无一害。
除非你遇到了极品面试官，这就是另外一回事情了。
再除非你是美女，这就又是另外一回事情了。
话说男人真是没出息的动物，看到美女就围着团团转流口水。
总是表现的这么明显啊.