今天早上出门在平板上看了LeftEarMouse的新文《为什么我反对纯算法面试题》，有了一些想法。外面下着大雨，所以我回到屋子里打开笔记本发一些回信，想整理一下。为了避免有人歪曲我的观点，我先声明，我不反对这篇文章。相反，我基本同意里面的观点，但是我会补充一些，点一下我觉得有点过分的。你也可以认为我的观点是提交一些补丁，发送一些PullRequests（当然不是这种PullRequest）。我当时吐槽的第一件事就是文章太鄙视搞学术研究的人，说他们是书呆子，不关心业务需求，认为他们是不能思考的应试教育产物。这其实不是重点，只是触动了我的学术研究情结，接下来才是我真正想说的。前两天喵子文章里的一个讨论引出了一个话题。那是一道面试题：“找出无序数组中第二大的数”。在当时的采访中，经过“排序”后被判定为无效。合格的答案。Mouse认为在工程上“排序”是更合适的做法，因为需求经常变化，“需求分析”后更合理的决策应该是找到“第K大数”。面试看到这道题的时候，我提出“求第K大数”是一个过早的优化，但是鼠标在新文中的观点是FindKthMax(array,k)是一个比较通用的接口，不会成为Find2ndMax。然而，即使从“工程”的角度来看，我仍然认为“排序”是一种不合适的做法，FindKthMax(array,k)仍然是一种过早的优化。由于需求是取第2个数，其实我不建议考虑提前实现取第K个数的需求，因为太复杂了。比如排序一次后是否可以重复取数？排序后重复取数的前提是数组不变，往往接口不是FindKthMax(array,k)，而是newArrayFinder(array).Find(k)。另外，排序经常会改变数组本身元素的顺序，那么允许吗？你想复印吗？考虑这些太复杂了。事实上，由于现在的要求只是取第二个，所以这是一个非常有用的限制。两个变量一个循环就可以让我们在3分钟内完成这个工作，那为什么还要通用呢？？另外，Mice认为是应试教育导致人们选择O(n)而不是排序。我的感觉恰恰相反，因为排序是每个人都会接触到的东西，而应试教育会给排序留下很深的印象。但对我来说，看到这个问题的第一反应是“不要使用排序”，因为它显然会产生不必要的开销。嗯，不排除是“应试教育”让我一眼看出题目的意图。换个角度看，Find2ndMax接口其实没有问题。虽然它只解决了一个特例，但它可以高效地完成针对这个特例的任务，而且没有副作用。你可以看看.NET框架中的String.Concat方法。它为2~4个字符串的连接操作实现了一个重载，同时也提供了一个接受字符串数组的接口。由于大多数字符串拼接操作都在4以内，因此单独针对这些特殊情况进行针对性的实现在实际工程中并不少见。我不反对纯面试算法，尤其是我觉得一个简单的算法“你不知道，我接受不了”，这就是门槛。当然，我也反对纯粹用很变态的面试算法来招人，比如冬天面试的“优胜者树”和传说中的“草原”。另外，谁说纯算法不能满足实际需求？该算法根据输入参数的大小选择不同的策略。这就过分了，纯算法不说就是把项目分开了。此外，算法题并不意味着只有标准答案是正确的。算法题只是一种表达形式，考试也是解决问题的一种方式。不仅仅是“最佳方案”被认为是通过。次优解和沟通过程都在看受访者。就像winter当年不认识“胜者树”，而是通过找到题中缺失的一个约束条件，用hash值的方法给出了满足要求的解，也体现了很强的适应能力，这就是对“工程”也很重要。问题不是算法题，而是面试官或者面试方式。顺便说一下ACM，因为我有一种预感，有人会以此来鄙视ACM。其实按照文中鼠标的标准，ACM绝对是一个非常工程化的环境。因为在掌握算法的基础上，需要快速了解需求，建模，根据数据量选择合适的方法，快速解决符合题目时间和空间限制的问题。这时候能快速暴力枚举的就不需要高级解法了，甚至想着提前准备两种方法，一种过不去马上换成第二种。更何况，这里绝对是处于高压环境中，这与所谓的“工程环境”是非常相符的。当然，ACM也不是没有违背工程的，比如不注意代码的可维护性，不注意输入数据的边界条件等等。顺便说一句，这可以导致一个可以写的面试经验入《面试书》：拿到问题后，确认每一个输入的细节，比如这个问题现在是2还是k，会不会小于0等。很多面试官其实是在考察面试官的注意力边界条件。问这些问题，有助于提升自己的形象，给自己思考的时间，几乎是有益无害的。除非你遇到了***面试官，这个另当别论。除非你是一个漂亮的女人，否则这是另一回事。都说男人真是没用的动物，看到美女就流口水。原文链接：http://blog.zhaojie.me/2012/08/my-opinion-of-algorithm-interview.html
