我看面試時出（純）算法題

文/趙劼

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

耗子的文章以前兩天的一個討論引出話題，那是一道面試題：“找出無序數組的第 2 大的數”，而在當時的面試中，“排序”后再取數被判為不合格的答案。耗子認為其實在工程中“排序”才是更合適的做法，因為需求往往會變化，經過“需求分析”后更合理的決策應該是尋找“第K大的數”。我當時看到這題面試時就提出“尋找第K大的數”是一種過早優化，但耗子在新文章里的觀點是，FindKthMax (array， k)才是更常見的接口，而不會是Find2ndMax。

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

此外，耗子認為是應試教育導致人們會選擇O(n)的做法，而不是排序。我的感覺恰好相反，因為排序才是人人會接觸過的事物，應試教育會讓人對排序有深刻的印象。但是對我來說，我看到這題的第一反應就是“不能用排序”，因為這顯然會產生不必要的開銷。好吧，我不排除是“應試教育”讓我能立即看清題目意圖的可能性。

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

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

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

再順便談下 ACM，因為我預感有人會借此鄙視 ACM。其實按照耗子在文章里的標準，ACM 絕對屬于很工程的環境。因為你要在掌握算法的基礎上，快速理解需求，建模，根據數據量選擇合適的做法，符合題目的時間限制和空間限制快速解決問題。此時能夠快速暴力枚舉的就不用高級解法，甚至預先思考準備兩種做法，一種無法通過立即換上第二種。更何況還是絕對在高壓環境下，與所謂的“工程環境”十分相符。

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

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

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

話說男人真是沒出息的動物，看到美女就圍著團團轉流口水。