為什麼我反對純演演算法面試題

　　來自：酷 殼 - CoolShell.cn

　　作者：陳皓

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

　　演演算法面試可能是微軟搞出來的面試方法，現在很多公司都在效仿，而且我們的程序員也樂於解演演算法題，我個人以為，這是應試教育的毒瘤！我在《再談「我是怎麼招程序員」》中比較保守地說過，「問難的演演算法題並沒有錯，錯的很多面試官只是在膚淺甚至錯誤地理解著面試演演算法題的目的。」，今天，我想加強一下這個觀點——我反對純演演算法題面試！（注意，我說的是純演演算法題）

　　我再次引用我以前的一個觀點——

　　「能解演演算法題並不意味著這個人就有能力就能在工作中解決問題，你可以想想，小學奧數題可能比這些題更難，但並不意味著那些奧數能手就能解決實際問題。

　　好了，讓我們來看一個示例（這個示例是昨天在微博上的一個討論），這個題是——「找出無序數組中第2大的數」，幾乎所有的人都用了O(n)的演演算法，我相信對於我們這些應試教育出來的人來說，不用排序用O(n)演演算法是很正常的事，連我都不由自主地認為O(n)演演算法是這個題的標準答案。我們太習慣於標準答案了，這是我國教育最悲哀的地方。（廣義的洗腦就是讓你的意識依賴於某個標準答案，然後通過給你標準答案讓你不會思考而控制你）

　　功能性需求分析

　　試想，如果我們在實際工作中得到這樣一個題 我們會怎麼做？我一定會分析這個需求，因為我害怕需求未來會改變，今天你叫我找一個第2大的數，明天你找我找一個第4大的數，後天叫我找一個第100大的數，我不搞死了。需求變化是很正常的事。分析完這個需求后，我會很自然地去寫找第K大數的演演算法——難度一下子就增大了。

　　很多人會以為找第K大的需求是一種「過早擴展」的思路，不是這樣的，我相信我們在實際編碼中寫過太多這樣的程序了，你一定不會設計出這樣的函數介面—— Find2ndMaxNum(int* array, int len)，就好像你不會設計出 DestroyBaghdad(); 這樣的介面，而是設計一個DestoryCity( City& ); 的介面，而把Baghdad當成參數傳進去！所以，你應該是聲明一個叫FindKthMaxNum(int* array, int len, int kth)，把2當成參數傳進去。這是最基本的編程方法，用數學的話來說，叫代數！最簡單的需求分析方法就是把需求翻譯成函數名，然後看看是這個介面不是很二？！

　　（註：不要糾結於FindMaxNum()或FindMinNum()，因為這兩個函數名的業務意義很清楚了，不像Find2ndMaxNum()那麼二）

　　非功能性需求分析

　　性能之類的東西從來都是非功能性需求，對於演演算法題，我們太喜歡研究演演算法題的空間和時間複雜度了。我們希望做到空間和時間雙豐收，這是演演算法學術界的風格。所以，習慣於標準答案的我們已經失去思考的能力，只會機械地思考演演算法之內的性能，而忽略了演演算法之外的性能。

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

　　搞學術的nuts們到了這一步一定會歡呼勝利！但是他們哪裡能想得到性能的需求分析也是來源自業務的！

　　我們一說性能，基本上是個人都會問，請求量有多大？如果我們的FindKthMaxNum()的請求量是m次，那麼你的這個每次都要O(n)複雜度的演演算法得到的效果就是O(n*m)，這一點，是書獃子式的學院派人永遠想不到的。因為應試教育讓我們不會從實際思考了。

　　工程式的解法

　　根據上面的需求分析，有軟體工程經驗的人的解法通常會這樣：

　　1）把數組排序，從大到小。

　　2）於是你要第k大的數，就直接訪問 array[k]。

　　排序只需要一次，O(n*log(n))，然後，接下來的m次對FindKthMaxNum()的調用全是O(1)的，整體複雜度反而成了線性的。

　　其實，上述的還不是工程式的最好的解法，因為，在業務中，那數組中的數據可能會是會變化的，所以，如果是用數組排序的話，有數據的改動會讓我重新排序，這個太耗性能了，如果實際情況中會有很多的插入或刪除操作，那麼可以考慮使用B+樹。

　　工程式的解法有以下特點：

　　1）很方便擴展，因為數據排好序了，你還可以方便地支持各種需求，如從第k1大到k2大的數據（那些學院派寫出來的代碼在拿到這個需求時又開始撓頭苦想了）

　　2）規整的數據會簡化整體的演演算法複雜度，從而整體性能會更好。（公欲善其事，必先利其器）

　　3）代碼變得清晰，易懂，易維護！（學院派的和STL一樣的近似O(n)複雜度的演演算法沒人敢動）

　　爭論

　　你可能會和我有以下爭論，

　　如果程序員做這個演演算法題用排序的方式，他一定不會像你想那麼多。是的，你說得對。但是我想說，很多時候，我們直覺地思考，恰恰是正確的路。因為「排序」這個思路符合人類大腦處理問題的方式，而使用學院派的方式是反大腦直覺的。反大腦直覺的，通常意味著晦澀難懂，維護成本上升。

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

　　這個演演算法題太容易誘導到學院派的思路了。是的這道「找出第K大的數」，其實可以變換為更為業務一點的題目——「我要和別的商戶競價，我想排在所有競爭對手報價的第K名，請寫一個程序，我輸入K，和一個商品名，系統告訴我應該訂多少價？（商家的所有商品的報價在一數組中）」——業務分析，整體性能，演演算法，數據結構，增加需求讓應聘者重構，這一個問題就全考了。

　　你是不是在說演演算法不重要，不用學？千萬別這樣理解我，搞得好像如果面試不面，我就可以不學。演演算法很重要，演演算法題能鍛煉我們的思維，而且也有很多實際用處。我這篇文章不是讓大家不要去學演演算法，這是完全錯誤的，我是讓大家帶著業務問題去使用演演算法。問你業務問題，一樣會問到演演算法題上來。

　　小結

　　看過這上面的分析，我相信你明白我為什麼反對純演演算法面試題了。原因就是純演演算法的面試題根本不能反應一個程序的綜合素質！

　　那麼，在面試中，我們應該要考量程序員的那些綜合素質呢？我以為有下面這些東西：

　　1、會不會做需求分析？怎麼理解問題的？

　　2、解決問題的思路是什麼？想法如何？

　　3、會不會對基礎的演演算法和數據結構靈活運用？

　　另外，我們知道，對於軟體開發來說，在工程上，難是的下面是這些挑戰：

　　4、軟體的維護成本遠遠大於軟體的開發成本。

　　5、軟體的質量變得越來越重要，所以，測試工作也變得越來越重要。

　　6、軟體的需求總是在變的，軟體的需求總是一點一點往上加的。

　　7、程序中大量的代碼都是在處理一些錯誤的或是不正常的流程。

　　所以，對於編程能力上，我們應該主要考量程序員的如下能力：

　　1、設計是否滿足對需求的理解，並可以應對可能出現的需求變化。

　　2、程序是否易讀，易維護？

　　3、重構代碼的能力如何？

　　4、會不會測試自己寫好的程序？

　　所以，這段時間，我越來越傾向於問應聘者一些有業務意義的題，而且應增加或更改需求來看程序員的重構代碼的能力，寫完程序后，讓應聘者設計測試案例。

　　比如：解析加減乘除表達式，字元串轉數字，洗牌程序，口令生成器，通過ip地址找地點，英漢詞典雙向檢索……

　　總之，我反對純演演算法面試題！