當(dāng)一個(gè)程序員真正掌握算法之后，會(huì)變得有多強(qiáng)？
2020 = 1024 + 996... 對(duì)于程序員來(lái)說(shuō)，2020 年看起來(lái)可不怎么“友好”啊。
但是不管外部環(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)、百度或海外的一線互聯(lián)網(wǎng)公司，希望他們分享的經(jīng)驗(yàn)可以幫助到你。
前美團(tuán)資深工程師 Windy
作為面試官，我比較看中候選人的行業(yè)背景、專業(yè)技能還有一些軟素質(zhì)。具體來(lái)說(shuō)：
- 行業(yè)背景就是上一份工作所在的領(lǐng)域比如電商、社交等;
- 專業(yè)技能的話主要是語(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)單到中等難度的題目，常考的有：
- 單鏈表翻轉(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è)生的話，我主要是考察態(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 和慢查詢優(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
解釋：11 = 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)練不斷提高的。
