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

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

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

此外，耗子認(rèn)為是應(yīng)試教育導(dǎo)致人們會選擇O(n)的做法，而不是排序。我的感覺恰好相反，因?yàn)榕判虿攀侨巳藭佑|過的事物，應(yīng)試教育會讓人對排序有深刻的印象。但是對我來說，我看到這題的***反應(yīng)就是“不能用排序”，因?yàn)檫@顯然會產(chǎn)生不必要的開銷。好吧，我不排除是“應(yīng)試教育”讓我能立即看清題目意圖的可能性。

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

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

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

再順便談下ACM，因?yàn)槲翌A(yù)感有人會借此鄙視ACM。其實(shí)按照耗子在文章里的標(biāo)準(zhǔn)，ACM絕對屬于很工程的環(huán)境。因?yàn)槟阋谡莆账惴ǖ幕A(chǔ)上，快速理解需求，建模，根據(jù)數(shù)據(jù)量選擇合適的做法，符合題目的時間限制和空間限制快速解決問題。此時能夠快速暴力枚舉的就不用高級解法，甚至預(yù)先思考準(zhǔn)備兩種做法，一種無法通過立即換上第二種。更何況還是絕對在高壓環(huán)境下，與所謂的“工程環(huán)境”十分相符。

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

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

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

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

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