2020 = 1024 + 996... 對(duì)于程序員來(lái)說(shuō)，2020 年看起來(lái)可不怎么“友好”啊。

[[314898]]

但是不管外部環(huán)境如何，提升自身內(nèi)功都是每個(gè)職場(chǎng)人所必需的。在如今的環(huán)境下，想要換一份理想的工作更是需要“找準(zhǔn)時(shí)機(jī)，抓住機(jī)會(huì)”，當(dāng)然在面試前的準(zhǔn)備是必不可少的。極客大學(xué)邀請(qǐng)了算法訓(xùn)練營(yíng)的助教，請(qǐng)他們分享一下作為面試官喜歡考察候選人哪些能力、他們有哪些“ 精選算法面試題 ”。我們的助教們來(lái)自美團(tuán)、百度或海外的一線(xiàn)互聯(lián)網(wǎng)公司，希望他們分享的經(jīng)驗(yàn)可以幫助到你。

前美團(tuán)資深工程師 Windy

作為面試官，我比較看中候選人的行業(yè)背景、專(zhuān)業(yè)技能還有一些軟素質(zhì)。具體來(lái)說(shuō)：

• 行業(yè)背景就是上一份工作所在的領(lǐng)域比如電商、社交等;
• 專(zhuān)業(yè)技能的話(huà)主要是語(yǔ)言基礎(chǔ)，高并發(fā)、分布式、中間件等知識(shí)，以及排查問(wèn)題、運(yùn)維、設(shè)計(jì)的能力。這里面最重要的是編程能力，針對(duì)高級(jí)崗位還要考察架構(gòu)能力。
• 軟素質(zhì)包括候選人的溝通能力、項(xiàng)目管理能力和領(lǐng)導(dǎo)力等。

作為面試官，在面試過(guò)程我會(huì)用筆試題的形式考察候選人的思維邏輯能力，通常考察的具體知識(shí)點(diǎn)包括鏈表、樹(shù)、排序、二分查找等，需要候選人能夠分析出不同算法的時(shí)間復(fù)雜度和空間復(fù)雜度。題目我會(huì)選擇 LeetCode 上簡(jiǎn)單到中等難度的題目，?？嫉挠校?/p>

• 單鏈表翻轉(zhuǎn)(遞歸或者循環(huán))
• 樹(shù)的前中后序遍歷
• 動(dòng)態(tài)規(guī)劃(爬樓梯以及變形問(wèn)題、斐波那契數(shù)列、股票問(wèn)題)
• 二分查找(以及變形)
• 排序(快排)

通過(guò)算法面試題的考察，我希望候選人不光可以展示編程能力，還可以通過(guò)詳細(xì)了解題目，展示自己的溝通能力和推演能力(如何構(gòu)建題目的思路)。最關(guān)鍵的編程能力，候選人可以展示自己對(duì)于問(wèn)題邊界的思考，比較不同方法的性能和效率，給出解決問(wèn)題的多種方法。

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

編寫(xiě)一個(gè)高效的算法來(lái)判斷 m x n 矩陣中，是否存在一個(gè)目標(biāo)值。該矩陣具有如下特性：

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

每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)。

示例 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 

百度高級(jí)研發(fā)工程師 Kimze

針對(duì)不同層次的候選，作為面試官肯定有所側(cè)重。在算法訓(xùn)練營(yíng)中有不少是在校的學(xué)生，針對(duì)應(yīng)屆畢業(yè)生的話(huà)，我主要是考察態(tài)度、編程基礎(chǔ)，以及數(shù)據(jù)結(jié)構(gòu)和算法的基本功。對(duì)于有經(jīng)驗(yàn)的同學(xué)來(lái)說(shuō)，我會(huì)結(jié)合簡(jiǎn)歷技能，圍繞項(xiàng)目經(jīng)驗(yàn)，考察領(lǐng)域能力的廣度和深度，探知到候選人的上限，也可以互相交流學(xué)習(xí)。

高可用、高性能、高擴(kuò)展性作為后端通用的技術(shù)，針對(duì)不同技術(shù)棧，我會(huì)考察：

• 分布式分層架構(gòu)設(shè)計(jì)理解
• LB 負(fù)載均衡、前端壓縮 /CDN 緩存 /DNS 相關(guān)知識(shí)
• 多級(jí)緩存、MQ 異步解耦
• 無(wú)狀態(tài)化設(shè)計(jì) -> 快速擴(kuò)縮容
• DB Sharding 、讀寫(xiě)分離、分庫(kù)分表、SQL 和慢查詢(xún)優(yōu)化、JVM 優(yōu)化等措施
• ES 檢索、數(shù)據(jù)異構(gòu)、大數(shù)據(jù)處理
• 一致性設(shè)計(jì)：批量異步、串行改并行、同步改異步
• 數(shù)據(jù)協(xié)議、通信協(xié)議
• 容量預(yù)估規(guī)劃、全鏈路壓測(cè)、灰度發(fā)布設(shè)計(jì)、降級(jí) / 熔斷 / 限流的設(shè)計(jì)、RPC 服務(wù)治理
• 分布式配置、注冊(cè)、監(jiān)控
• CI/CD：“Docker + Kubernetes”架構(gòu)

對(duì)于數(shù)據(jù)結(jié)構(gòu)和算法的考察，比較基礎(chǔ)的如快排、歸并、二分查找的題目，候選人要能分析出時(shí)間和空間復(fù)雜度，并展示出相關(guān)推演的過(guò)程。對(duì)于高級(jí)一些的內(nèi)容，我最低的要求是有思路，知道什么情況下用什么樣的數(shù)據(jù)結(jié)構(gòu)和算法，并寫(xiě)出模板即可。比如我會(huì)問(wèn)：

Redis 底層數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，引申出跳表的原理，再擴(kuò)展到 Hash 的實(shí)現(xiàn)及擴(kuò)容實(shí)現(xiàn)，希望考察候選人是否了解跳表優(yōu)缺點(diǎn)， 以及 Redis 為什么這么設(shè)計(jì)。

MySQL B+ 樹(shù)索引結(jié)構(gòu)的時(shí)間復(fù)雜度以及選型原因，希望考察為什么使用 B+ 樹(shù)而不是紅黑樹(shù)或 Hash、跳表。

我考察的具體題目并不多，我認(rèn)為非常好的一道題目是：零錢(qián)兌換

給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒(méi)有任何一種硬幣組合能組成總金額，返回 -1。

示例 1: 

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

解釋?zhuān)?1 = 5 + 5 + 1

示例 2: 

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

說(shuō)明:

你可以認(rèn)為每種硬幣的數(shù)量是無(wú)限的。

Serko 高級(jí)軟件工程師 Xu

不同公司、不同職位、不同級(jí)別所要求能力、范圍和深度不一樣，海外公司和國(guó)內(nèi)互聯(lián)網(wǎng)公司的業(yè)務(wù)需求也有很大不同，但我認(rèn)為作為程序員一般需要具備下面能力：

• 編程能力(編碼、數(shù)據(jù)結(jié)構(gòu)和算法、數(shù)學(xué))
• 簡(jiǎn)潔代碼(Clean code)
• 好的編程實(shí)踐(Good programming practices)
• 軟件設(shè)計(jì)
• 系統(tǒng)設(shè)計(jì)
• 軟件架構(gòu)
• 系統(tǒng)架構(gòu)
• 分析和解決問(wèn)題能力
• 領(lǐng)導(dǎo)力
• 溝通表達(dá)能力
• 合作能力
• 分享能力
• 持續(xù)學(xué)習(xí)能力

對(duì)于大多數(shù)需要面試的初級(jí)和中級(jí)程序員來(lái)說(shuō)，作為技術(shù)面第一輪的白板算法題，我一般會(huì)出 LeetCode 上 easy 到 meduim 的題目，這類(lèi)題目一般可以暴力求解、能夠優(yōu)化，有多種解法和思路，同時(shí)候選人最好能夠展示一些軟件工程方面的實(shí)力。

在做題過(guò)程中，有幾點(diǎn)需要注意：

• 理解題目，在這個(gè)過(guò)程中要和面試官溝通，澄清題目的要求和相關(guān)疑問(wèn)，而不是一上來(lái)就開(kāi)始寫(xiě)程序。
• 設(shè)計(jì)算法，在這個(gè)過(guò)程中和面試官不斷互動(dòng)，一步一步探尋最優(yōu)解，而不是一聲不吭，一個(gè)人”埋頭苦干“。
• 實(shí)現(xiàn)算法，在這個(gè)過(guò)程中可以展示你對(duì)軟件開(kāi)發(fā)和測(cè)試的理解。
• 代碼完成后，酌情可以和面試官討論一些相關(guān)東西，比如 TDD、BDD、CI/CD 等。

我的精選算法面試題是：驗(yàn)證二叉搜索樹(shù)

給定一個(gè)二叉樹(shù)，判斷其是否是一個(gè)有效的二叉搜索樹(shù)。

假設(shè)一個(gè)二叉搜索樹(shù)具有如下特征：

節(jié)點(diǎn)的左子樹(shù)只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。

節(jié)點(diǎn)的右子樹(shù)只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。

所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)。

示例 1: 

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

示例 2: 

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

以上這些題目你都會(huì)做了嗎?

什么?你不會(huì)?那也不用捉急，同其他編程技能一樣，高效掌握常見(jiàn)的算法與數(shù)據(jù)結(jié)構(gòu)知識(shí)，并學(xué)會(huì)用相應(yīng)的算法來(lái)解決實(shí)際工作和面試中的算法問(wèn)題，都是 可以通過(guò)學(xué)習(xí)和訓(xùn)練不斷提高的。