面試很困難，技術(shù)面試更加困難——只用 45 ~ 60 分鐘是很難考察出面試者的水平的。所以 劉未鵬 在他的 怎樣花兩年時間去面試一個人 一文中鼓勵面試者創(chuàng)建 GitHub 賬號，閱讀技術(shù)書籍，建立技術(shù)影響力，從而提供給面試官真實，明確，可度量的經(jīng)歷。

這種方法對面試者效果很好，但對面試官效果就很一般——面試官要面對大量的面試者，這些面試者之中可能只有很少人擁有技術(shù)博客，但這并不代表他們的技術(shù)能力不夠強（也許他們對寫作不感興趣）；另一方面，一些人擁有技術(shù)博客，但這也不能說明他們的水平就一定會很牛（也許他們在嘴遁呢）。

總之，技術(shù)博客和 GitHub 賬號是加分項，但技術(shù)面試仍然必不可少。所以，問題又回來了，如何進(jìn)行高效的技術(shù)面試？或者說，如何在 45 ~ 60 分鐘內(nèi)盡可能準(zhǔn)確的考察出面試者的技術(shù)水平？

回答這個問題之前，讓我們先看下技術(shù)面試中的常見問題都有什么：

技術(shù)面試中的常見問題

技術(shù)面試中的問題大致可以分為 5 類：

編碼：考察面試者的編碼能力，一般要求面試者在 20 ~ 30 分鐘之內(nèi)編寫一段需求明確的小程序（例：編寫一個函數(shù)劃分一個整形數(shù)組，把負(fù)數(shù)放在左邊，零放在中間，正數(shù)放在右邊）；

設(shè)計：考察面試者的設(shè)計/表達(dá)能力，一般要求面試者在 30 分鐘左右內(nèi)給出一個系統(tǒng)的大致設(shè)計（例：設(shè)計一個類似微博的系統(tǒng)）

項目：考察面試者的設(shè)計/表達(dá)能力以及其簡歷的真實度（例：描述你做過的 xxx 系統(tǒng)中的難點，以及你是如何克服這些難點）

腦筋急轉(zhuǎn)彎：考察面試者的『反應(yīng)/智力』（例：如果你變成螞蟻大小然后被扔進(jìn)一個攪拌機里，你將如何脫身？）

查漏：考察面試者對某種技術(shù)的熟練度（例：Java 的基本類型有幾種？）

這 5 類問題中，腦筋急轉(zhuǎn)彎在外企中早已絕跡（因為它無法判定面試者的真實能力），查漏類問題因為實際價值不大（畢竟我們可以用 Google）在外企中出現(xiàn)率也越來越低，剩下的 3 類問題里，項目類和設(shè)計類問題要求面試官擁有同類項目經(jīng)驗，只有編碼類問題不需要任何前提，所以，幾乎所有的技術(shù)面試中都包含編碼類問題。

然而，最令面試者頭痛的也是這些編碼類問題——因為幾乎所有的當(dāng)面（On-site）技術(shù)面試均要求面試者在白板上寫出代碼，而不是在面試者熟悉的 IDE 或是編輯器中寫出。在我的面試經(jīng)歷里，不止一個被面試者向我抱怨：『如果能在計算機上編程，我早就把它搞定了！』就連我自己在面試初期也曾懷疑白板代碼的有效性：『為什么不讓面試者在計算機上寫代碼呢？』

然而在經(jīng)歷了若干輪被面試與面試之后，我驚奇的發(fā)現(xiàn)白板編程竟然是一種相當(dāng)有效的技術(shù)考察方式。這也是我寫這篇文章的原因——我希望通過這篇文章來闡述為什么要進(jìn)行白板編程（WHY），什么是合適的白板編程題目（WHAT），以及如何進(jìn)行白板編程（HOW），從而既幫助面試者更好的準(zhǔn)備面試，也幫助面試官更好的進(jìn)行面試。

為什么要進(jìn)行白板編程

很多面試者希望能夠在 IDE 中（而不是白板上）編寫代碼，因為：

主流 IDE 均帶有智能提示，從而大大提升了編碼速度

IDE 可以保證程序能夠編譯通過

可以通過 IDE 運行/調(diào)試代碼，找到程序的 Bug

我承認(rèn)第 1 點，白板編程要比 IDE 編程慢很多，但這并不能做為否認(rèn)白板編程的理由——因為白板編程往往是 API 無關(guān)（因此并不需要你去背誦 API）的一小段（一般不超過 30 行）代碼，而且面試官也會允許面試者進(jìn)行適當(dāng)?shù)目s寫（比如把Iterable類型縮寫為Iter），因此它并不能成為否認(rèn)白板編程的理由。

至于第 2 點和第 3 點，它們更不能成為否認(rèn)白板編程的借口——如果你使用 IDE 只是為了在其幫助下寫出能過編譯的代碼，或是為了調(diào)試改 Bug，那么我不認(rèn)為你是一名合格的程序員——我認(rèn)為程序員可以被分為兩種：

先確認(rèn)前條件/不變式/終止條件/邊界條件，然后寫出正確的代碼

先編寫代碼，然后通過各種用例/測試/調(diào)試對程序進(jìn)行調(diào)整，最后得到似乎正確的代碼

我個人保守估計前者開發(fā)效率至少是后者的 10 倍，因為前者不需要浪費大量時間在 編碼-調(diào)試-編碼 這個極其耗時的循環(huán)上。通過白板編程，面試官可以有效的判定出面試者屬于前者還是后者，從而招進(jìn)合適的人才，并把老油條或是嘴遁者排除在外。

除了判定面試者的開發(fā)效率，白板編程還有助于展示面試者的編程思路，并便于面試者和面試官進(jìn)行交流：

[[135632]]

白板編程的目標(biāo)并不是要求面試者一下子寫出完美無缺的代碼，而是：

讓面試者在解題的過程中將他/他的思維過程和編碼習(xí)慣展現(xiàn)在面試官面前，以便面試官判定面試者是否具備清晰的邏輯思維和良好的編程素養(yǎng)

如果面試者陷入困境或是陷阱，面試官也可以為其提供適當(dāng)?shù)妮o助，以免面試陷入無人發(fā)言的尷尬境地

什么是合適的白板編程題目

正如前文所述，白板編程是一種很有效的技術(shù)面試方式，但這是建立在有效的編程題目的基礎(chǔ)之上：如果編程題目過難，那么面試很可能會陷入『大眼瞪小眼』的境地；如果編程題目過于簡單（或者面試者背過題目），那么面試者無需思考就可以給出正確答案。這兩種情況都無法達(dá)到考察面試者思維過程的目的，從而使得面試官無法正確評估面試者的能力。

既然編程題目很重要，那么問題來了，什么才是合適（合理）的編程題目呢？

在回答這個問題之前，讓我們先看看什么編程題目不合適：

什么不該問

被問濫的編程問題

我在求職時發(fā)現(xiàn)，技術(shù)面試的編程題目往往千篇一律——拿我自己來說，反轉(zhuǎn)單鏈表被問了 5 次，數(shù)字轉(zhuǎn)字符串被問了 4 次，隨機化數(shù)組被問了 3 次，最可笑的是在面試某外企時三個面試官都問我如何反轉(zhuǎn)單鏈表，以至于我得主動要求更換題目以免誤會。

無獨有偶，我在求職時同時發(fā)現(xiàn)很多面試者都隨身帶一個本子或是打印好的材料，上面寫滿了常見的面試題目，一些面試者甚至?xí)矶\能夠被問到上面的題目。

就這個問題，我和我的同學(xué)以及后來的同事討論過，答案是很多面試官在面試前并不會提前準(zhǔn)備面試題，而是從網(wǎng)絡(luò)上（例如 July 的算法博客）或 編程之美 之類的面試題集上隨機挑一道題目詢問。如果面試者做出來（或背出來）題目那么通過，如果面試者做不出來就掛掉。

這種面試方式的問題非常明顯：如果面試者準(zhǔn)備充分，那么這些題目根本沒有區(qū)分度——面試者很可能會把答案直接背下來；如果面試者未做準(zhǔn)備，他/她很可能被一些需要 aha! moment 的題目困住?？傊绻嬖囶}不能評估面試者水平，那么問它還有什么意義呢？

下面是一些問濫的編程問題：

編程之美 書里的所有題目；

July 的算法博客 中的絕大多數(shù)題目（包括 面試 100 題 中的所有題目）；

leecode 里的大部分題目；

涉及到庫函數(shù)或 API 調(diào)用

白板編程的目標(biāo)在于考察面試者的編程基本功，而不是考察面試者使用某種語言/類庫的熟練度。所以白板編程題目應(yīng)盡可能庫函數(shù)無關(guān)——例如：編寫一個 XML 讀取程序就是不合格的題目，因為面試者沒有必要把 XML 庫中的函數(shù)名背下來（不然要 Intellisense 干甚）；而原地消除字符串的重復(fù)空白（例："ab c d e" => "ab c d e"）則是一道合格的題目，因為即便不使用庫函數(shù)，合格的面試者也能夠在 20 分鐘內(nèi)完成這道題目。

過于直接（或簡單）的算法問題

這類問題類似 被問濫的編程問題，它們的特點在于過于直接，以至于面試者不需要思考就可以給出答案，從而使得面試官無法考察面試者的思維過程。快速排序，深度優(yōu)先搜索，以及二分搜索都屬于這類題目。

需要注意的是，盡管過于直接的算法題目不適合面試，但是我們可以將其進(jìn)行一點改動，從而使其變成合理的題目，例如穩(wěn)定劃分和二分搜索計數(shù)（給出有序數(shù)組中某個元素出現(xiàn)的次數(shù)）就不錯，盡管它們實際是快速排序和二分搜索的變種。

過于復(fù)雜的題目

同 過于直接的算法問題< 相反，過于復(fù)雜的題目 屬于另一個極端：這些題目往往要求面試者擁有極強的算法背景，盡管算法問題是否過于復(fù)雜因人而異（在一些 ACM 編程競賽選手的眼里可能就沒有復(fù)雜的題目 –_-），但我個人認(rèn)為如果一道題滿足了下面任何一點，那么它就太復(fù)雜，不適合面試（不過如果面試者是 ACM 編程競賽選手，那么可以無視此規(guī)則）：

需要 aha! moment（參考 腦筋急轉(zhuǎn)彎）

需要使用某些『非主流』數(shù)據(jù)結(jié)構(gòu)/算法才能求解

耗時過長（例如實現(xiàn)紅黑樹的插入/刪除）

腦筋急轉(zhuǎn)彎

什么是腦筋急轉(zhuǎn)彎？

不考察編程能力

依賴于 aha! moment

All or nothin：或者做不出來，或者是最終答案

在一些書（例如 誰是谷歌想要的人才？：破解世界最頂尖公司的面試密碼）和電影的渲染下，Google 和微軟這些外企的面試被搞的無比神秘，以至于很多人以為外企真的會問諸如『井蓋為什么是圓的』或是『貨車能裝多少高爾夫球』這樣的奇詭問題。而實際上，這些題目由于無法考察面試者的技術(shù)能力而早已在外企中絕跡。反倒是一些國內(nèi)公司開始使用腦筋急轉(zhuǎn)彎 作為面試題目 –_–#

應(yīng)該問什么問題

所以，技術(shù)面試題目不應(yīng)該太難，也不應(yīng)太簡單，不能是腦筋急轉(zhuǎn)彎，也不能直接來自網(wǎng)絡(luò)。

前三點并不難滿足：我們可以去 算法導(dǎo)論，編程珠璣，以及 計算機程序設(shè)計藝術(shù) 這些經(jīng)典算法書籍中的課后題/練習(xí)題挑選合適的題目，也可以自己創(chuàng)造題目。然而，由于 careercup 這類網(wǎng)站的存在，沒有什么題目可以做到絕對原創(chuàng)——畢竟沒有人能阻止面試者把題目發(fā)到網(wǎng)上，所以任何編程題目都逃脫不了被公開的命運。

不過，盡管面試者會把編程題目發(fā)到網(wǎng)上，甚至?xí)幸恍汉眯娜恕唤o出答案，但這并不代表面試官不能繼續(xù)使用這道題：因為盡管題目被公開，但題目的考察點和延伸問題依然只有面試官才知道。這有點像 公鑰加密，公鑰（面試題）是公開的，但私鑰（解法，考察點，以及延伸問題）只有面試官才知道。這樣即便面試者知道面試題，也不會妨礙面試官考察面試者的技術(shù)能力。

接下來，讓我們看看什么問題適合白板編程。

不止一種解法

良好的編程問題都會有不止一種解法。這樣面試者可以在短時間內(nèi)給出一個不那么聰明但可實現(xiàn)的『粗糙』算法，然后通過思考（或面試官提示）逐步得到更加優(yōu)化的解法，面試官可以通過這個過程觀察到面試者的思維方式，從而對面試者進(jìn)行更客觀的評估。

以 數(shù)組最大子序列和 為例，它有一個很顯然的 O(n3) 解法，將 O(n3) 解法稍加改動可以得到 O(n2) 解法，利用分治思想，可以得到 O(n*logn) 解法，除此之外它還有一個 o(n) 解法。（編程珠璣 和 數(shù)據(jù)結(jié)構(gòu)與算法分析 C語言描述 對這道題均有非常精彩的描述，有興趣的朋友可以自行閱讀）

考察點明確

良好的編程問題應(yīng)擁有大量考察點，面試官應(yīng)對這些考察點爛熟于心，從而給出更加客觀量化的面試結(jié)果。這里可以參考我之前在 從武俠小說到程序員面試 提到的 to_upper。

延伸問題

良好的編程問題應(yīng)擁有延伸問題。延伸問題既可以應(yīng)對面試者背題的情況，也可以漸進(jìn)的（Incremental）考察面試者的編程能力，同時還保證了面試的延續(xù)性（Continuity）。

以 遍歷二叉樹 為例：面試官可以從非遞歸中序遍歷二叉樹開始提問，面試者有可能會很快的寫（或是背）出一個使用棧的解法。這時面試官可以通過延伸問題來判別面試者是否在背題：使用常量空間中序遍歷帶有父節(jié)點指針的二叉樹，或是找到二叉搜索樹中第 n 小的元素。下面是中序遍歷二叉樹的一些延伸問題：

|--中序遍歷二叉樹 
| 
|--非遞歸中序遍歷二叉樹 
| 
|--常量空間，非遞歸遍歷帶父節(jié)點的二叉樹 
| | 
| |--在帶父節(jié)點的二叉搜索樹尋找第 N 小的元素 
| | 
| |--可否進(jìn)一步優(yōu)化時間復(fù)雜度？ 
| 
|--常量空間，非遞歸遍歷不帶父節(jié)點的二叉樹 

上面的問題不但可以被正向使用（逐步加強難度），也可以被逆向使用（逐步降低難度）：同樣從非遞歸中序二叉樹遍歷開始提問，如果面試者無法完成這個問題，那么面試官可以降低難度，要求面試者編寫一個遞歸版本的中序遍歷二叉樹。

如何進(jìn)行白板編程

面試官應(yīng)該做什么

面試前

面試之前，面試官應(yīng)至少得到以下信息：

面試者的簡歷

面試者的應(yīng)聘職位

面試者之前被問過哪些面試題

接下來，面試官應(yīng)根據(jù)面試者的簡歷/職位確認(rèn)對面試者的期望值，然后準(zhǔn)備好編程題目（而不是面試時即興選擇題目）。面試官應(yīng)至少準(zhǔn)備 4 道題目（2 道簡單題，2 道難題），以應(yīng)對各種情況。

面試中

面試時，面試官應(yīng)清楚的陳述題目，并通過若干組用例數(shù)據(jù)確認(rèn)面試者真正的理解題目（以免面試者花很長時間去做不相關(guān)的題目，我在之前的面試就辦過這種挫事 –_–#）

在面試者解題時，面試官應(yīng)全程保持安靜（或傾聽的狀態(tài)），如果面試者犯下特別嚴(yán)重的錯誤或是陷入苦思冥想，面試官應(yīng)給出適當(dāng)?shù)奶崾?，以幫助面試者走出困境完成題目，如果面試者還是不能完成題目，那么面試官應(yīng)換一道略簡單的題目，要知道面試的目的是發(fā)現(xiàn)面試者的長處，而非為難面試者。（一些國內(nèi)企業(yè)似乎正好相反）

面試后

面試之后，面試官應(yīng)拍照（或謄寫）面試者寫下的代碼，然后把提問的問題發(fā)給 HR 和接下來的面試者（以確保問題不會重復(fù)）。接下來，面試官應(yīng)根據(jù)面試者的代碼以及其面試表現(xiàn)，盡快寫出面試反饋（Interview Feedback）發(fā)給 HR，以便接下來的招聘流程。

面試者應(yīng)該做什么

面試前

面試之前，面試者應(yīng)至少做過以下準(zhǔn)備：

擁有扎實的數(shù)據(jù)結(jié)構(gòu)/算法基礎(chǔ)

知道如何利用 前條件/不變式/后條件 這些工具編寫正確的程序

能夠在白板（或紙上）實現(xiàn)基本的數(shù)據(jù)結(jié)構(gòu)和算法（如果 1 和 2 做到這一步是水到渠成）

在 leetcode 或 careercup 上面進(jìn)行過練習(xí)，了解常見的技術(shù)面試題目（我個人不鼓勵刷題，但在面試前建立起對面試題的『感覺』非常重要）

面試中

確定需求

面試者在白板編程時最重要的任務(wù)是理解題目，確認(rèn)需求——確定輸入/輸出，確定數(shù)據(jù)范圍，確定時間/空間要求，確定其它限制。以最常見的排序為例：

輸入：來自數(shù)組？鏈表？或是不同的機器？

輸出：是否有重復(fù)？是否要求穩(wěn)定？

數(shù)據(jù)范圍：排序多少個元素？100 個？ 100 萬個？ 1 億個？這些元素是否在某個范圍內(nèi)？

時間要求：1 分鐘？1 刻鐘？一小時？

空間要求：是否常量空間？是否可以分配新的空間？如果可以，能分配多少空間？是否在內(nèi)存中排序？

其它限制：是否需要盡可能少的賦值？是否需要盡可能少的比較？

有時面試官不會把題目說的特別清楚，這時就需要面試者自己去確認(rèn)這些需求，不要認(rèn)為這是在浪費時間，不同的需求會導(dǎo)致截然不同的解法，此外確認(rèn)需求會留給面試官良好的印象。

白板編程

理解題目確認(rèn)需求之后，面試者就可以開始在白板上編寫代碼，下面是一些我自己的白板編程經(jīng)驗：

先寫出輪廓（大綱）

白板編程沒法復(fù)制粘貼，所以后期調(diào)整代碼結(jié)構(gòu)非常困難。因此我們最好在開頭寫出程序的大致結(jié)構(gòu)，從而保證之后不會有大改；

確定前條件/不變式/后條件

我們可以通過注釋的形式給出代碼的前條件/不變式/后條件，以劃分為例：

int* partition(int *begin, int *end, int pivot) { 
int *par = begin; 
for ( ; begin < end; begin++) { 
if (*begin < pivot) { 
swap(begin, par++) 
} 
} 
return par; 
} 

就不如

int* partition(int *begin, int *end, int pivot) { 
// [begin, end) should be a valid range 
int *par = begin; 
// Invariant: All [0, par) < pivot && All [par, begin) >= pivot 
for ( ; begin < end; begin++) { 
if (*begin < pivot) { 
swap(begin, par++) 
} 
} 
// Now All [0, par) < pivot && All [par, end) >= pivot 
return par; 
} 

使用實例數(shù)據(jù)驗證自己的程序

盡管不變式足以驗證程序的正確性，但適當(dāng)?shù)氖褂脤嵗龜?shù)據(jù)會大大增強代碼的可信性，以上面的劃分程序為例：

Given range [2, 3, 4, 5, 1] and pivot 3 
[ 2, 3, 4, 5, 1 ] 
^ ^ 
p,b e 
[ 2, 3, 4, 5, 1 ] 
^ ^ 
p,b e 
[ 2, 3, 4, 5, 1 ] 
^ ^ ^ 
p b e 
[ 2, 3, 4, 5, 1 ] 
^ ^ ^ 
p b e 
[ 2, 1, 4, 5, 3 ] 
^ ^ ^ 
p b e 
[ 2, 1, 4, 5, 3 ] 
^ ^ 
p b,e 
Now we have all [0, p) < 3 and all [p, e) >= 3 

使用縮寫

白板編程并不需要面試者在白板上寫出能夠一次通過編譯的代碼。為了節(jié)省時間，面試者可以在和面試官溝通的基礎(chǔ)上使用縮寫。例如使用 Iter 替代 Iterable，使用 BQ 替代 BlockingQueue。（此法尤其適合于 Java –_–#）

至少留一行半行寬

出于緊張或疏忽，一般面試者在白板編程時會犯下各種小錯誤，例如忘了某個判斷條件或是漏了某條語句，空余的行寬可以幫助面試者快速修改代碼，使得白板上的代碼不至于一團(tuán)糟。

這就延伸出了另一個問題，如果使用大行寬，那么白板寫不下怎么辦？一些面試者聰明的解決了這個問題：他們在面試時會自帶一根細(xì)筆跡的水筆，專門用于白板編程。

不會做怎么辦

相信大多數(shù)面試者都碰到過面試題不會做的情況，這里說說我自己的對策：

至少先給出一個暴力（Brute force）解法

尋找合適的數(shù)據(jù)結(jié)構(gòu)（例如棧/隊列/樹/堆/圖）和算法（例如分治/回溯/動態(tài)規(guī)劃/貪婪）

從小數(shù)據(jù)集開始嘗試

如果還是沒有頭緒，重新考慮題目的前條件，思考是否漏掉了條件（或是隱含的條件）

如果 3 分鐘過后還是沒有任何思路，請求面試官提示，不要覺得不好意思——經(jīng)過提示給出答案遠(yuǎn)強于沒有答案

面試后

個人不建議面試者在面試之后把題目發(fā)到網(wǎng)上，很多公司在面試前都會和面試者打招呼，有的會簽訂 NDA（Non Disclosure Agreement）條款以確保面試者不會泄露面試題目。盡管他們很少真的去查，但如果被查到那絕對是得不償失。

我自己在面試之后會把面試中的編程題目動手寫一遍（除非題目過于簡單不值得），這樣既能夠驗證自己寫的代碼，也可以保證自己不會在同一個地方摔倒兩次。