為什么我反對純算法面試題
算法面試可能是微軟搞出來的面試方法，現(xiàn)在很多公司都在效仿，而且我們的程序員也樂于解算法題，我個人以為，這是應(yīng)試教育的毒瘤！我在《再談“我是怎么招程序員”》中比較保守地說過，“問難的算法題并沒有錯，錯的很多面試官只是在膚淺甚至錯誤地理解著面試算法題的目的。”，今天，我想加強(qiáng)一下這個觀點——我反對純算法題面試！（注意，我說的是純算法題）
圖片源Wikipedia（點擊圖片查看詞條）
我再次引用我以前的一個觀點——
能解算法題并不意味著這個人就有能力就能在工作中解決問題，你可以想想，小學(xué)奧數(shù)題可能比這些題更難，但并不意味著那些奧數(shù)能手就能解決實際問題。
好了，讓我們來看一個示例（這個示例是昨天在微博上的一個討論），這個題是——“找出無序數(shù)組中第2大的數(shù)”，幾乎所有的人都用了O(n)的算法，我相信對于我們這些應(yīng)試教育出來的人來說，不用排序用O(n)算法是很正常的事，連我都不由自主地認(rèn)為O(n)算法是這個題的標(biāo)準(zhǔn)答案。我們太習(xí)慣于標(biāo)準(zhǔn)答案了，這是我國教育最悲哀的地方。（廣義的洗腦就是讓你的意識依賴于某個標(biāo)準(zhǔn)答案，然后通過給你標(biāo)準(zhǔn)答案讓你不會思考而控制你）
功能性需求分析
試想，如果我們在實際工作中得到這樣一個題 我們會怎么做？我一定會分析這個需求，因為我害怕需求未來會改變，今天你叫我找一個第2大的數(shù)，明天你找我找一個第4大的數(shù)，后天叫我找一個第100大的數(shù)，我不搞死了。需求變化是很正常的事。分析完這個需求后，我會很自然地去寫找第K大數(shù)的算法——難度一下子就增大了。
很多人會以為找第K大的需求是一種“過早擴(kuò)展”的思路，不是這樣的，我相信我們在實際編碼中寫過太多這樣的程序了，你一定不會設(shè)計出這樣的函數(shù)接口 —— Find2ndMaxNum(int* array, int len)，就好像你不會設(shè)計出 DestroyBaghdad(); 這樣的接口，而是設(shè)計一個DestoryCity( City& ); 的接口，而把Baghdad當(dāng)成參數(shù)傳進(jìn)去！所以，你應(yīng)該是聲明一個叫FindKthMaxNum(int* array, int len, int kth)，把2當(dāng)成參數(shù)傳進(jìn)去。這是最基本的編程方法，用數(shù)學(xué)的話來說，叫代數(shù)！最簡單的需求分析方法就是把需求翻譯成函數(shù)名，然后看看是這個接口不是很二？！
（注：不要糾結(jié)于FindMaxNum()或FindMinNum()，因為這兩個函數(shù)名的業(yè)務(wù)意義很清楚了，不像Find2ndMaxNum()那么二）
非功能性需求分析
性能之類的東西從來都是非功能性需求，對于算法題，我們太喜歡研究算法題的空間和時間復(fù)雜度了。我們希望做到空間和時間雙豐收，這是算法學(xué)術(shù)界的風(fēng)格。所以，習(xí)慣于標(biāo)準(zhǔn)答案的我們已經(jīng)失去思考的能力，只會機(jī)械地思考算法之內(nèi)的性能，而忽略了算法之外的性能。
如果題目是——“從無序數(shù)組中找到第K個最大的數(shù)”，那么，我們一定會去思考用O(n)的線性算法找出第K個數(shù)。事實上，也有線性算法——STL中可以用nth_element求得類似的第n大的數(shù)，其利用快速排序的思想，從數(shù)組S中隨機(jī)找出一個元素X，把數(shù)組分為兩部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。這時有兩種情況：1）Sa中元素的個數(shù)小于k，則Sb中的第k-|Sa|個元素即為第k大數(shù)；2） Sa中元素的個數(shù)大于等于k，則返回Sa中的第k大數(shù)。時間復(fù)雜度近似為O(n)。
搞學(xué)術(shù)的nuts們到了這一步一定會歡呼勝利！但是他們哪里能想得到性能的需求分析也是來源自業(yè)務(wù)的！
我們一說性能，基本上是個人都會問，請求量有多大？如果我們的FindKthMaxNum()的請求量是m次，那么你的這個每次都要O(n)復(fù)雜度的算法得到的效果就是O(n*m)，這一點，是書呆子式的學(xué)院派人永遠(yuǎn)想不到的。因為應(yīng)試教育讓我們不會從實際思考了。
工程式的解法
根據(jù)上面的需求分析，有軟件工程經(jīng)驗的人的解法通常會這樣：
1）把數(shù)組排序，從大到小。
2）于是你要第k大的數(shù)，就直接訪問 array[k]。
排序只需要一次，O(n*log(n))，然后，接下來的m次對FindKthMaxNum()的調(diào)用全是O(1)的，整體復(fù)雜度反而成了線性的。
其實，上述的還不是工程式的最好的解法，因為，在業(yè)務(wù)中，那數(shù)組中的數(shù)據(jù)可能會是會變化的，所以，如果是用數(shù)組排序的話，有數(shù)據(jù)的改動會讓我重新排序，這個太耗性能了，如果實際情況中會有很多的插入或刪除操作，那么可以考慮使用B+樹。
工程式的解法有以下特點：
1）很方便擴(kuò)展，因為數(shù)據(jù)排好序了，你還可以方便地支持各種需求，如從第k1大到k2大的數(shù)據(jù)（那些學(xué)院派寫出來的代碼在拿到這個需求時又開始撓頭苦想了）
2）規(guī)整的數(shù)據(jù)會簡化整體的算法復(fù)雜度，從而整體性能會更好。（公欲善其事，必先利其器）
3）代碼變得清晰，易懂，易維護(hù)！（學(xué)院派的和STL一樣的近似O(n)復(fù)雜度的算法沒人敢動）
爭論
你可能會和我有以下爭論，
- 如果程序員做這個算法題用排序的方式，他一定不會像你想那么多。是的，你說得對。但是我想說，很多時候，我們直覺地思考，恰恰是正確的路。因為“排序”這個思路符合人類大腦處理問題的方式，而使用學(xué)院派的方式是反大腦直覺的。反大腦直覺的，通常意味著晦澀難懂，維護(hù)成本上升。
- 就是一道面試題，我就是想測試一下你的算法技能，這也扯太多了。沒問題，不過，我們要清楚我們是在招什么人？是一個只會寫算法的人，還是一個會做軟件的人？這個只有你自己最清楚。
- 這個算法題太容易誘導(dǎo)到學(xué)院派的思路了。是的這道“找出第K大的數(shù)”，其實可以變換為更為業(yè)務(wù)一點的題目——“我要和別的商戶競價，我想排在所有競爭對手報價的第K名，請寫一個程序，我輸入K，和一個商品名，系統(tǒng)告訴我應(yīng)該訂多少價？（商家的所有商品的報價在一數(shù)組中）”——業(yè)務(wù)分析，整體性能，算法，數(shù)據(jù)結(jié)構(gòu)，增加需求讓應(yīng)聘者重構(gòu)，這一個問題就全考了。
- 你是不是在說算法不重要，不用學(xué)？千萬別這樣理解我，搞得好像如果面試不面，我就可以不學(xué)。算法很重要，算法題能鍛煉我們的思維，而且也有很多實際用處。我這篇文章不是讓大家不要去學(xué)算法，這是完全錯誤的，我是讓大家?guī)е鴺I(yè)務(wù)問題去使用算法。問你業(yè)務(wù)問題，一樣會問到算法題上來。
小結(jié)
看過這上面的分析，我相信你明白我為什么反對純算法面試題了。原因就是純算法的面試題根本不能反應(yīng)一個程序的綜合素質(zhì)！
那么，在面試中，我們應(yīng)該要考量程序員的那些綜合素質(zhì)呢？我以為有下面這些東西：
- 會不會做需求分析？怎么理解問題的？
- 解決問題的思路是什么？想法如何？
- 會不會對基礎(chǔ)的算法和數(shù)據(jù)結(jié)構(gòu)靈活運用？
另外，我們知道，對于軟件開發(fā)來說，在工程上，難是的下面是這些挑戰(zhàn)：
- 軟件的維護(hù)成本遠(yuǎn)遠(yuǎn)大于軟件的開發(fā)成本。
- 軟件的質(zhì)量變得越來越重要，所以，測試工作也變得越來越重要。
- 軟件的需求總是在變的，軟件的需求總是一點一點往上加的。
- 程序中大量的代碼都是在處理一些錯誤的或是不正常的流程。
所以，對于編程能力上，我們應(yīng)該主要考量程序員的如下能力：
- 設(shè)計是否滿足對需求的理解，并可以應(yīng)對可能出現(xiàn)的需求變化。
- 程序是否易讀，易維護(hù)？
- 重構(gòu)代碼的能力如何？
- 會不會測試自己寫好的程序？
所以，這段時間，我越來越傾向于問應(yīng)聘者一些有業(yè)務(wù)意義的題，而且應(yīng)增加或更改需求來看程序員的重構(gòu)代碼的能力，寫完程序后，讓應(yīng)聘者設(shè)計測試案例。
比如：解析加減乘除表達(dá)式，字符串轉(zhuǎn)數(shù)字，洗牌程序，口令生成器，通過ip地址找地點，英漢詞典雙向檢索……
總之，我反對純算法面試題！
