當一個程式設計師真正掌握演算法之後，會變得有多強？

2020 = 1024 + 996... 對於程式設計師來說，2020 年看起來可不怎麼「友好」啊。

当一个程序员真正掌握算法之后，会变得有多强？

但是不管外部環境如何，提升自身內功都是每個職場人所必需的。在如今的環境下，想要換一份理想的工作更是需要「找準時機，抓住機會」，當然在面試前的準備是必不可少的。極客大學邀請了演算法訓練營的助教，請他們分享一下作爲面試官喜歡考察候選人哪些能力、他們有哪些「精選演算法面試題」。我們的助教們來自美團、百度或海外的一線網際網路公司，希望他們分享的經驗可以幫助到你。

当一个程序员真正掌握算法之后，会变得有多强？

前美團資深工程師 Windy

作爲面試官，我比較看中候選人的行業背景、專業技能還有一些軟素質。具體來說：

行業背景就是上一份工作所在的領域比如電商、社交等;
專業技能的話主要是語言基礎，高併發、分佈式、中介軟體等知識，以及排查問題、運維、設計的能力。這裏面最重要的是程式設計能力，針對高階崗位還要考察架構能力。
軟素質包括候選人的溝通能力、專案管理能力和領導力等。

作爲面試官，在面試過程我會用筆試題的形式考察候選人的思維邏輯能力，通常考察的具體知識點包括鏈表、樹、排序、二分查詢等，需要候選人能夠分析出不同演算法的時間複雜度和空間複雜度。題目我會選擇 LeetCode 上簡單到中等難度的題目，常考的有：

單鏈表翻轉(遞回或者回圈)
樹的前中後序遍歷
動態規劃(爬樓梯以及變形問題、斐波那契數列、股票問題)
二分查詢(以及變形)
排序(快排)

通過演算法面試題的考察，我希望候選人不光可以展示程式設計能力，還可以通過詳細瞭解題目，展示自己的溝通能力和推演能力(如何構建題目的思路)。最關鍵的程式設計能力，候選人可以展示自己對於問題邊界的思考，比較不同方法的效能和效率，給出解決問題的多種方法。

我的精選演算法面試題是：搜尋二維矩陣

編寫一個高效的演算法來判斷 m x n 矩陣中，是否存在一個目標值。該矩陣具有如下特性：

每行中的整數從左到右按升序排列。

每行的第一個整數大於前一行的最後一個整數。

範例 1:

輸入: 
matrix = [ 
  [1, 3, 5, 7], 
  [10, 11, 16, 20], 
  [23, 30, 34, 50] 
] 
target = 3 
輸出: true

範例 2:

輸入: 
matrix = [ 
  [1, 3, 5, 7], 
  [10, 11, 16, 20], 
  [23, 30, 34, 50] 
] 
target = 13 
輸出: false

当一个程序员真正掌握算法之后，会变得有多强？

百度高階研發工程師 Kimze

針對不同層次的候選，作爲面試官肯定有所側重。在演算法訓練營中有不少是在校的學生，針對應屆畢業生的話，我主要是考察態度、程式設計基礎，以及數據結構和演算法的基本功。對於有經驗的同學來說，我會結合簡歷技能，圍繞專案經驗，考察領域能力的廣度和深度，探知到候選人的上限，也可以互相交流學習。

高可用、高效能、高擴充套件性作爲後端通用的技術，針對不同技術棧，我會考察：

分佈式分層架構設計理解
LB 負載均衡、前端壓縮 /CDN 快取 /DNS 相關知識
多級快取、MQ 非同步解耦
無狀態化設計 -> 快速擴縮容
DB Sharding 、讀寫分離、分庫分表、SQL 和慢查詢優化、JVM 優化等措施
ES 檢索、數據異構、大數據處理
一致性設計：批次非同步、序列改並行、同步改非同步
數據協定、通訊協定
容量預估規劃、全鏈路壓測、灰度發佈設計、降級 / 熔斷 / 限流的設計、RPC 服務治理
分佈式設定、註冊、監控
CI/CD：「Docker + Kubernetes」架構

對於數據結構和演算法的考察，比較基礎的如快排、歸併、二分查詢的題目，候選人要能分析出時間和空間複雜度，並展示出相關推演的過程。對於高階一些的內容，我最低的要求是有思路，知道什麼情況下用什麼樣的數據結構和演算法，並寫出模板即可。比如我會問：

Redis 底層數據結構設計，引申出跳錶的原理，再擴充套件到 Hash 的實現及擴容實現，希望考察候選人是否瞭解跳錶優缺點，以及 Redis 爲什麼這麼設計。

MySQL B+ 樹索引結構的時間複雜度以及選型原因，希望考察爲什麼使用 B+ 樹而不是紅黑樹或 Hash、跳錶。

我考察的具體題目並不多，我認爲非常好的一道題目是：零錢兌換

給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1。

範例 1:

輸入: coins = [1, 2, 5], amount = 11 
輸出: 3

解釋：11 = 5 + 5 + 1

範例 2:

輸入: coins = [2], amount = 3 
輸出: -1

說明:

你可以認爲每種硬幣的數量是無限的。

Serko 高階軟體工程師 Xu

不同公司、不同職位、不同級別所要求能力、範圍和深度不一樣，海外公司和國內網際網路公司的業務需求也有很大不同，但我認爲作爲程式設計師一般需要具備下面下麪能力：

程式設計能力(編碼、數據結構和演算法、數學)
簡潔程式碼(Clean code)
好的程式設計實踐(Good programming practices)
軟體設計
系統設計
軟體架構
系統架構
分析和解決問題能力
領導力
溝通表達能力
合作能力
分享能力
持續學習能力

對於大多數需要面試的初級和中級程式設計師來說，作爲技術面第一輪的白板演算法題，我一般會出 LeetCode 上 easy 到 meduim 的題目，這類題目一般可以暴力求解、能夠優化，有多種解法和思路，同時候選人最好能夠展示一些軟體工程方面的實力。

在做題過程中，有幾點需要注意：

理解題目，在這個過程中要和麪試官溝通，澄清題目的要求和相關疑問，而不是一上來就開始寫程式。
設計演算法，在這個過程中和麪試官不斷互動，一步一步探尋最優解，而不是一聲不吭，一個人」埋頭苦幹「。
實現演算法，在這個過程中可以展示你對軟件開發和測試的理解。
程式碼完成後，酌情可以和麪試官討論一些相關東西，比如 TDD、BDD、CI/CD 等。

我的精選演算法面試題是：驗證二元搜尋樹

給定一個二元樹，判斷其是否是一個有效的二元搜尋樹。

假設一個二元搜尋樹具有如下特徵：

節點的左子樹只包含小於當前節點的數。

節點的右子樹只包含大於當前節點的數。

所有左子樹和右子樹自身必須也是二元搜尋樹。

範例 1:

輸入: 
 
    2 
   / \ 
  1   3 
 
輸出: true

範例 2:

輸入: 
 
    2 
   / \ 
  1   3 
 
輸出: true

以上這些題目你都會做了嗎?

什麼？你不會？那也不用捉急，同其他程式設計技能一樣，高效掌握常見的演算法與數據結構知識，並學會用相應的演算法來解決實際工作和麪試中的演算法問題，都是可以通過學習和訓練不斷提高的。