為什么我反對(duì)純算法面試題

作者：陳皓 2012-08-22 09:32:54

算法面試可能是微軟搞出來的面試方法，現(xiàn)在很多公司都在效仿，而且我們的程序員也樂于解算法題，我個(gè)人以為，這是應(yīng)試教育的毒瘤！我在《再談“我是怎么招程序員”》中比較保守地說過，“問難的算法題并沒有錯(cuò)，錯(cuò)的很多面試官只是在膚淺甚至錯(cuò)誤地理解著面試算法題的目的。”

算法面試可能是微軟搞出來的面試方法，現(xiàn)在很多公司都在效仿，而且我們的程序員也樂于解算法題，我個(gè)人以為，這是應(yīng)試教育的毒瘤！我在《再談“我是怎么招程序員”》中比較保守地說過，“問難的算法題并沒有錯(cuò)，錯(cuò)的很多面試官只是在膚淺甚至錯(cuò)誤地理解著面試算法題的目的。”，今天，我想加強(qiáng)一下這個(gè)觀點(diǎn)——我反對(duì)純算法題面試！（注意，我說的是純算法題）

[[92221]]

圖片源Wikipedia（點(diǎn)擊圖片查看詞條）

我再次引用我以前的一個(gè)觀點(diǎn)——

能解算法題并不意味著這個(gè)人就有能力就能在工作中解決問題，你可以想想，小學(xué)奧數(shù)題可能比這些題更難，但并不意味著那些奧數(shù)能手就能解決實(shí)際問題。

好了，讓我們來看一個(gè)示例（這個(gè)示例是昨天在微博上的一個(gè)討論），這個(gè)題是——“找出無序數(shù)組中第2大的數(shù)”，幾乎所有的人都用了O(n)的算法，我相信對(duì)于我們這些應(yīng)試教育出來的人來說，不用排序用O(n)算法是很正常的事，連我都不由自主地認(rèn)為O(n)算法是這個(gè)題的標(biāo)準(zhǔn)答案。我們太習(xí)慣于標(biāo)準(zhǔn)答案了，這是我國(guó)教育最悲哀的地方。（廣義的洗腦就是讓你的意識(shí)依賴于某個(gè)標(biāo)準(zhǔn)答案，然后通過給你標(biāo)準(zhǔn)答案讓你不會(huì)思考而控制你）

功能性需求分析

試想，如果我們?cè)趯?shí)際工作中得到這樣一個(gè)題我們會(huì)怎么做？我一定會(huì)分析這個(gè)需求，因?yàn)槲液ε滦枨笪磥頃?huì)改變，今天你叫我找一個(gè)第2大的數(shù)，明天你找我找一個(gè)第4大的數(shù)，后天叫我找一個(gè)第100大的數(shù)，我不搞死了。需求變化是很正常的事。分析完這個(gè)需求后，我會(huì)很自然地去寫找第K大數(shù)的算法——難度一下子就增大了。

很多人會(huì)以為找第K大的需求是一種“過早擴(kuò)展”的思路，不是這樣的，我相信我們?cè)趯?shí)際編碼中寫過太多這樣的程序了，你一定不會(huì)設(shè)計(jì)出這樣的函數(shù)接口 —— Find2ndMaxNum(int* array, int len)，就好像你不會(huì)設(shè)計(jì)出 DestroyBaghdad(); 這樣的接口，而是設(shè)計(jì)一個(gè)DestoryCity( City& ); 的接口，而把Baghdad當(dāng)成參數(shù)傳進(jìn)去！所以，你應(yīng)該是聲明一個(gè)叫FindKthMaxNum(int* array, int len, int kth)，把2當(dāng)成參數(shù)傳進(jìn)去。這是最基本的編程方法，用數(shù)學(xué)的話來說，叫代數(shù)！最簡(jiǎn)單的需求分析方法就是把需求翻譯成函數(shù)名，然后看看是這個(gè)接口不是很二？！

（注：不要糾結(jié)于FindMaxNum()或FindMinNum()，因?yàn)檫@兩個(gè)函數(shù)名的業(yè)務(wù)意義很清楚了，不像Find2ndMaxNum()那么二）

非功能性需求分析

性能之類的東西從來都是非功能性需求，對(duì)于算法題，我們太喜歡研究算法題的空間和時(shí)間復(fù)雜度了。我們希望做到空間和時(shí)間雙豐收，這是算法學(xué)術(shù)界的風(fēng)格。所以，習(xí)慣于標(biāo)準(zhǔn)答案的我們已經(jīng)失去思考的能力，只會(huì)機(jī)械地思考算法之內(nèi)的性能，而忽略了算法之外的性能。

如果題目是——“從無序數(shù)組中找到第K個(gè)最大的數(shù)”，那么，我們一定會(huì)去思考用O(n)的線性算法找出第K個(gè)數(shù)。事實(shí)上，也有線性算法——STL中可以用nth_element求得類似的第n大的數(shù)，其利用快速排序的思想，從數(shù)組S中隨機(jī)找出一個(gè)元素X，把數(shù)組分為兩部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。這時(shí)有兩種情況：1）Sa中元素的個(gè)數(shù)小于k，則Sb中的第k-|Sa|個(gè)元素即為第k大數(shù)；2） Sa中元素的個(gè)數(shù)大于等于k，則返回Sa中的第k大數(shù)。時(shí)間復(fù)雜度近似為O(n)。

搞學(xué)術(shù)的nuts們到了這一步一定會(huì)歡呼勝利！但是他們哪里能想得到性能的需求分析也是來源自業(yè)務(wù)的！

我們一說性能，基本上是個(gè)人都會(huì)問，請(qǐng)求量有多大？如果我們的FindKthMaxNum()的請(qǐng)求量是m次，那么你的這個(gè)每次都要O(n)復(fù)雜度的算法得到的效果就是O(n*m)，這一點(diǎn)，是書呆子式的學(xué)院派人永遠(yuǎn)想不到的。因?yàn)閼?yīng)試教育讓我們不會(huì)從實(shí)際思考了。

工程式的解法

根據(jù)上面的需求分析，有軟件工程經(jīng)驗(yàn)的人的解法通常會(huì)這樣：

1）把數(shù)組排序，從大到小。

2）于是你要第k大的數(shù)，就直接訪問 array[k]。

排序只需要一次，O(n*log(n))，然后，接下來的m次對(duì)FindKthMaxNum()的調(diào)用全是O(1)的，整體復(fù)雜度反而成了線性的。

其實(shí)，上述的還不是工程式的最好的解法，因?yàn)椋跇I(yè)務(wù)中，那數(shù)組中的數(shù)據(jù)可能會(huì)是會(huì)變化的，所以，如果是用數(shù)組排序的話，有數(shù)據(jù)的改動(dòng)會(huì)讓我重新排序，這個(gè)太耗性能了，如果實(shí)際情況中會(huì)有很多的插入或刪除操作，那么可以考慮使用B+樹。

工程式的解法有以下特點(diǎn)：

1）很方便擴(kuò)展，因?yàn)閿?shù)據(jù)排好序了，你還可以方便地支持各種需求，如從第k1大到k2大的數(shù)據(jù)（那些學(xué)院派寫出來的代碼在拿到這個(gè)需求時(shí)又開始撓頭苦想了）

2）規(guī)整的數(shù)據(jù)會(huì)簡(jiǎn)化整體的算法復(fù)雜度，從而整體性能會(huì)更好。（公欲善其事，必先利其器）

3）代碼變得清晰，易懂，易維護(hù)！（學(xué)院派的和STL一樣的近似O(n)復(fù)雜度的算法沒人敢動(dòng)）

爭(zhēng)論

你可能會(huì)和我有以下爭(zhēng)論，

如果程序員做這個(gè)算法題用排序的方式，他一定不會(huì)像你想那么多。是的，你說得對(duì)。但是我想說，很多時(shí)候，我們直覺地思考，恰恰是正確的路。因?yàn)?ldquo;排序”這個(gè)思路符合人類大腦處理問題的方式，而使用學(xué)院派的方式是反大腦直覺的。反大腦直覺的，通常意味著晦澀難懂，維護(hù)成本上升。

就是一道面試題，我就是想測(cè)試一下你的算法技能，這也扯太多了。沒問題，不過，我們要清楚我們是在招什么人？是一個(gè)只會(huì)寫算法的人，還是一個(gè)會(huì)做軟件的人？這個(gè)只有你自己最清楚。

這個(gè)算法題太容易誘導(dǎo)到學(xué)院派的思路了。是的這道“找出第K大的數(shù)”，其實(shí)可以變換為更為業(yè)務(wù)一點(diǎn)的題目——“我要和別的商戶競(jìng)價(jià)，我想排在所有競(jìng)爭(zhēng)對(duì)手報(bào)價(jià)的第K名，請(qǐng)寫一個(gè)程序，我輸入K，和一個(gè)商品名，系統(tǒng)告訴我應(yīng)該訂多少價(jià)？（商家的所有商品的報(bào)價(jià)在一數(shù)組中）”——業(yè)務(wù)分析，整體性能，算法，數(shù)據(jù)結(jié)構(gòu)，增加需求讓應(yīng)聘者重構(gòu)，這一個(gè)問題就全考了。

你是不是在說算法不重要，不用學(xué)？千萬別這樣理解我，搞得好像如果面試不面，我就可以不學(xué)。算法很重要，算法題能鍛煉我們的思維，而且也有很多實(shí)際用處。我這篇文章不是讓大家不要去學(xué)算法，這是完全錯(cuò)誤的，我是讓大家?guī)е鴺I(yè)務(wù)問題去使用算法。問你業(yè)務(wù)問題，一樣會(huì)問到算法題上來。

小結(jié)

看過這上面的分析，我相信你明白我為什么反對(duì)純算法面試題了。原因就是純算法的面試題根本不能反應(yīng)一個(gè)程序的綜合素質(zhì)！

那么，在面試中，我們應(yīng)該要考量程序員的那些綜合素質(zhì)呢？我以為有下面這些東西：