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

[[92221]]

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

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

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

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

功能性需求分析

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

很多人會(huì)以為找第K大的需求是一種“過(guò)早擴(kuò)展”的思路，不是這樣的，我相信我們?cè)趯?shí)際編碼中寫(xiě)過(guò)太多這樣的程序了，你一定不會(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é)的話(huà)來(lái)說(shuō)，叫代數(shù)！最簡(jiǎn)單的需求分析方法就是把需求翻譯成函數(shù)名，然后看看是這個(gè)接口不是很二？！

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

非功能性需求分析

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

如果題目是——“從無(wú)序數(shù)組中找到第K個(gè)最大的數(shù)”，那么，我們一定會(huì)去思考用O(n)的線(xiàn)性算法找出第K個(gè)數(shù)。事實(shí)上，也有線(xiàn)性算法——STL中可以用nth_element求得類(lèi)似的第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ì)歡呼勝利！但是他們哪里能想得到性能的需求分析也是來(lái)源自業(yè)務(wù)的！

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

工程式的解法

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

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

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

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

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

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

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

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

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

爭(zhēng)論

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

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

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

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

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

小結(jié)

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

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

1. 會(huì)不會(huì)做需求分析？怎么理解問(wèn)題的？
2. 解決問(wèn)題的思路是什么？想法如何？
3. 會(huì)不會(huì)對(duì)基礎(chǔ)的算法和數(shù)據(jù)結(jié)構(gòu)靈活運(yùn)用？

另外，我們知道，對(duì)于軟件開(kāi)發(fā)來(lái)說(shuō)，在工程上，難是的下面是這些挑戰(zhàn)：

• 軟件的維護(hù)成本遠(yuǎn)遠(yuǎn)大于軟件的開(kāi)發(fā)成本。
• 軟件的質(zhì)量變得越來(lái)越重要，所以，測(cè)試工作也變得越來(lái)越重要。
• 軟件的需求總是在變的，軟件的需求總是一點(diǎn)一點(diǎn)往上加的。
• 程序中大量的代碼都是在處理一些錯(cuò)誤的或是不正常的流程。

所以，對(duì)于編程能力上，我們應(yīng)該主要考量程序員的如下能力：

1. 設(shè)計(jì)是否滿(mǎn)足對(duì)需求的理解，并可以應(yīng)對(duì)可能出現(xiàn)的需求變化。
2. 程序是否易讀，易維護(hù)？
3. 重構(gòu)代碼的能力如何？
4. 會(huì)不會(huì)測(cè)試自己寫(xiě)好的程序？

所以，這段時(shí)間，我越來(lái)越傾向于問(wèn)應(yīng)聘者一些有業(yè)務(wù)意義的題，而且應(yīng)增加或更改需求來(lái)看程序員的重構(gòu)代碼的能力，寫(xiě)完程序后，讓?xiě)?yīng)聘者設(shè)計(jì)測(cè)試案例。

比如：解析加減乘除表達(dá)式，字符串轉(zhuǎn)數(shù)字，洗牌程序，口令生成器，通過(guò)ip地址找地點(diǎn)，英漢詞典雙向檢索……

總之，我反對(duì)純算法面試題！

原文鏈接：http://coolshell.cn/articles/8138.html