2020 = 1024 + 996... 對于程序員來說，2020 年看起來可不怎么“友好”啊。

[[314898]]

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

前美團資深工程師 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: 

輸入: 
    5 
   / \ 
  1   4 
     / \ 
    3   6 
輸出: false 
解釋: 輸入為: [5,1,4,null,null,3,6]。 
     根節點的值為 5 ，但是其右子節點值為 4 。 

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

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