今天早上一邊出門一邊在平板上讀了左耳朵耗子的新文章《為什么我反對純算法面試題》，略有想法。正逢外面暴雨如注，我就又回屋打開筆記本發(fā)了一些回復，特此整理一下。為了避免有人扭曲我的看法，我先聲明我并不是反對這篇文章，相反我是基本同意其中的觀點，只不過會加以一些補充，把其中一些我認為有些過頭的地方按一按。您也可以認為我的觀點是提交一些補丁，發(fā)了一些Pull Request（當然不是這種Pull Request）就行了。我當時吐的***個槽，是說文章太鄙視搞學術研究的人，說他們是書***，不關心業(yè)務需求，認為那是應試教育不會思考的產(chǎn)物。這個么其實不是重點，只不過觸到了我的學術研究情結(jié)罷了，接下來的才是我真正想說的。

耗子的文章以前兩天的一個討論引出話題，那是一道面試題：“找出無序數(shù)組的第2大的數(shù)”，而在當時的面試中，“排序”后再取數(shù)被判為不合格的答案。耗子認為其實在工程中“排序”才是更合適的做法，因為需求往往會變化，經(jīng)過“需求分析”后更合理的決策應該是尋找“第K大的數(shù)”。我當時看到這題面試時就提出“尋找第K大的數(shù)”是一種過早優(yōu)化，但耗子在新文章里的觀點是，F(xiàn)indKthMax(array, k)才是更常見的接口，而不會是Find2ndMax。

不過，即便是從“工程”角度來說，我還是認為“排序”是種不合適的做法，同時FindKthMax(array, k)依然是種過早優(yōu)化。既然提出了需求是取第2個數(shù)，其實我不太建議去考慮提前去實現(xiàn)取第K個數(shù)的需求，因為這太復雜了。例如，難道排序一次之后真可以反復取數(shù)？排序后反復取的前提是數(shù)組不變化，且這么做往往接口往往不是FindKthMax(array, k)，而是new ArrayFinder(array).Find(k)。還有，排序往往會改變數(shù)組本身元素順序，那么是否允許？是否要做一份拷貝？要考慮這些實在太復雜了，其實既然目前的需求只是取第2個，這是個很有用的限制，兩個變量一個循環(huán)可以讓我們在3分鐘里完成這個工作，那何必要做成通用的呢？

此外，耗子認為是應試教育導致人們會選擇O(n)的做法，而不是排序。我的感覺恰好相反，因為排序才是人人會接觸過的事物，應試教育會讓人對排序有深刻的印象。但是對我來說，我看到這題的***反應就是“不能用排序”，因為這顯然會產(chǎn)生不必要的開銷。好吧，我不排除是“應試教育”讓我能立即看清題目意圖的可能性。

換個角度來說，其實Find2ndMax這種接口也并沒有什么問題，盡管只解決了特例，但針對這個特例高效地完成任務，且沒有副作用。大伙可以去看看.NET框架里的String.Concat方法，它為2~4個字符串的連接操作各實現(xiàn)了一份重載，還提供了一個接受一個字符串數(shù)組的接口。由于大部分字符串的連接操作都在4個以內(nèi)，因此單獨為這些特例實現(xiàn)有針對性的實現(xiàn)，這在實際工程中并不罕見。

我不反對純面試算法，尤其是我認為一個簡單的算法“你不會我就不能接受”的情況，這是個門檻。當然我也反對純用很變態(tài)的面試算法來刷人，例如winter被面試過的“Winner樹”以及傳說中的“大草原”。此外，誰說純算法不符合實際需求的啊？算法根據(jù)輸入?yún)?shù)的大小變化選取不同策略這個太多了，純算法沒說在割離工程。更進一步地說，算法題也不代表只有標準答案才是正確的，算法題只是表現(xiàn)形式，考得也是解題思路，并非只有“***解”才算過關，次優(yōu)解以及溝通的過程都是在考察面試者。就如winter當年并不知道“Winner樹”，但通過發(fā)現(xiàn)題目中缺少的一個限制條件，使用取哈希值的方法給出了滿足要求的解決方案，這也體現(xiàn)出了強大的應變能力，這對于“工程”來說也至關重要。

有問題的不是算法題，只不過是面試官或是面試方式而已。

再順便談下ACM，因為我預感有人會借此鄙視ACM。其實按照耗子在文章里的標準，ACM絕對屬于很工程的環(huán)境。因為你要在掌握算法的基礎上，快速理解需求，建模，根據(jù)數(shù)據(jù)量選擇合適的做法，符合題目的時間限制和空間限制快速解決問題。此時能夠快速暴力枚舉的就不用高級解法，甚至預先思考準備兩種做法，一種無法通過立即換上第二種。更何況還是絕對在高壓環(huán)境下，與所謂的“工程環(huán)境”十分相符。

當然，ACM也并非沒有與工程中相違背的地方，例如不重視代碼的可維護性，還有輸入數(shù)據(jù)的邊界條件等等。這順便可以引出一個可以寫入“面試寶典”的面試經(jīng)驗：拿到問題后確認每一個輸入的細節(jié)，例如現(xiàn)在這題是2呢還是k，還有例如是不是會小于零等等。很多面試官其實也是在考察面試者對于邊界條件的關注程度，問清楚這些有利于提升自己的形象，給自己爭取思考的時間，幾乎有百利而無一害。

除非你遇到了***面試官，這就是另外一回事情了。

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

話說男人真是沒出息的動物，看到美女就圍著團團轉(zhuǎn)流口水。

原文鏈接：http://blog.zhaojie.me/2012/08/my-opinion-of-algorithm-interview.html