白板編程淺談——Why, What, How
這篇文章節選自我正在撰寫的一本關于應屆生面試求職的書籍，歡迎在評論或微博（@peng_gong）上留言反饋。
面試很困難，技術面試更加困難——只用 45 ~ 60 分鐘是很難考察出面試者的水平的。所以 劉未鵬 在他的 怎樣花兩年時間去面試一個人 一文中鼓勵面試者創建 GitHub 賬號，閱讀技術書籍，建立技術影響力，從而提供給面試官真實，明確，可度量的經歷。
這種方法對面試者效果很好，但對面試官效果就很一般——面試官要面對大量的面試者，這些面試者之中可能只有很少人擁有技術博客，但這并不代表他們的 技術能力不夠強（也許他們對寫作不感興趣）；另一方面，一些人擁有技術博客，但這也不能說明他們的水平就一定會很牛（也許他們在嘴遁呢）。
總之，技術博客和 GitHub 賬號是加分項，但技術面試仍然必不可少。所以，問題又回來了，如何進行高效的技術面試？或者說，如何在 45 ~ 60 分鐘內盡可能準確的考察出面試者的技術水平？
回答這個問題之前，讓我們先看下技術面試中的常見問題都有什么：
技術面試中的常見問題
技術面試中的問題大致可以分為 5 類：
-
編碼：考察面試者的編碼能力，一般要求面試者在 20 ~ 30 分鐘之內編寫一段需求明確的小程序（例：編寫一個函數劃分一個整形數組，把負數放在左邊，零放在中間，正數放在右邊）；
-
設計：考察面試者的設計/表達能力，一般要求面試者在 30 分鐘左右內給出一個系統的大致設計（例：設計一個類似微博的系統）
-
項目：考察面試者的設計/表達能力以及其簡歷的真實度（例：描述你做過的 xxx 系統中的難點，以及你是如何克服這些難點）
-
腦筋急轉彎：考察面試者的『反應/智力』（例：如果你變成螞蟻大小然后被扔進一個攪拌機里，你將如何脫身？）
-
查漏：考察面試者對某種技術的熟練度（例：Java 的基本類型有幾種？）
這 5 類問題中，腦筋急轉彎在外企中早已絕跡（因為它無法判定面試者的真實能力），查漏類問題因為實際價值不大（畢竟我們可以用 Google）在外企中出現率也越來越低，剩下的 3 類問題里，項目類和設計類問題要求面試官擁有同類項目經驗，只有編碼類問題不需要任何前提，所以，幾乎所有的技術面試中都包含編碼類問題。
然而，最令面試者頭痛的也是這些編碼類問題——因為幾乎所有的當面（On-site）技術面試均要求面試者在白板上寫出代碼，而不是在面試者熟悉的 IDE 或是編輯器中寫出。在我的面試經歷里，不止一個被面試者向我抱怨：『如果能在計算機上編程，我早就把它搞定了！』就連我自己在面試初期也曾懷疑白板代碼的 有效性：『為什么不讓面試者在計算機上寫代碼呢？』
然而在經歷了若干輪被面試與面試之后，我驚奇的發現白板編程竟然是一種相當有效的技術考察方式。這也是我寫這篇文章的原因——我希望通過這篇文章來 闡述為什么要進行白板編程（WHY），什么是合適的白板編程題目（WHAT），以及如何進行白板編程（HOW），從而既幫助面試者更好的準備面試，也幫助 面試官更好的進行面試。
#p#
為什么要進行白板編程
很多面試者希望能夠在 IDE 中（而不是白板上）編寫代碼，因為：
-
主流 IDE 均帶有智能提示，從而大大提升了編碼速度
-
IDE 可以保證程序能夠編譯通過
-
可以通過 IDE 運行/調試代碼，找到程序的 Bug
我承認第 1 點，白板編程要比 IDE 編程慢很多，但這并不能做為否認白板編程的理由——因為白板編程往往是 API 無關（因此并不需要你去背誦 API）的一小段（一般不超過 30 行）代碼，而且面試官也會允許面試者進行適當的縮寫（比如把Iterable類型縮寫為Iter），因此它并不能成為否認白板編程的理由。
至于第 2 點和第 3 點，它們更不能成為否認白板編程的借口——如果你使用 IDE 只是為了在其幫助下寫出能過編譯的代碼，或是為了調試改 Bug，那么我不認為你是一名合格的程序員——我認為程序員可以被分為兩種：
-
先確認前條件/不變式/終止條件/邊界條件，然后寫出正確的代碼
-
先編寫代碼，然后通過各種用例/測試/調試對程序進行調整，最后得到似乎正確的代碼
我個人保守估計前者開發效率至少是后者的 10 倍，因為前者不需要浪費大量時間在 編碼-調試-編碼 這個極其耗時的循環上。通過白板編程，面試官可以有效的判定出面試者屬于前者還是后者，從而招進合適的人才，并把老油條或是嘴遁者排除在外。
除了判定面試者的開發效率，白板編程還有助于展示面試者的編程思路，并便于面試者和面試官進行交流：
白板編程的目標并不是要求面試者一下子寫出完美無缺的代碼，而是：
-
讓面試者在解題的過程中將他/他的思維過程和編碼習慣展現在面試官面前，以便面試官判定面試者是否具備清晰的邏輯思維和良好的編程素養
-
如果面試者陷入困境或是陷阱，面試官也可以為其提供適當的輔助，以免面試陷入無人發言的尷尬境地
#p#
什么是合適的白板編程題目
正如前文所述，白板編程是一種很有效的技術面試方式，但這是建立在有效的編程題目的基礎之上：如果編程題目過難，那么面試很可能會陷入『大眼瞪小眼』的境地；如果編程題目過于簡單（或者面試者背過題目），那么面試者無需思考就可以給出正確答案。這兩種情況都無法達到考察面試者思維過程的目的，從而使得面試官無法正確評估面試者的能力。
既然編程題目很重要，那么問題來了，什么才是合適（合理）的編程題目呢？
在回答這個問題之前，讓我們先看看什么編程題目不合適：
什么不該問
1.被問濫的編程問題
我在求職時發現，技術面試的編程題目往往千篇一律——拿我自己來說，反轉單鏈表被問了 5 次，數字轉字符串被問了 4 次，隨機化數組被問了 3 次，最可笑的是在面試某外企時三個面試官都問我如何反轉單鏈表，以至于我得主動要求更換題目以免誤會。
無獨有偶，我在求職時同時發現很多面試者都隨身帶一個本子或是打印好的材料，上面寫滿了常見的面試題目，一些面試者甚至會祈禱能夠被問到上面的題目。
就這個問題，我和我的同學以及后來的同事討論過，答案是很多面試官在面試前并不會提前準備面試題，而是從網絡上（例如 July 的算法博客）或 編程之美 之類的面試題集上隨機挑一道題目詢問。如果面試者做出來（或背出來）題目那么通過，如果面試者做不出來就掛掉。
這種面試方式的問題非常明顯：如果面試者準備充分，那么這些題目根本沒有區分度——面試者很可能會把答案直接背下來；如果面試者未做準備，他/她很可能被一些需要 aha! moment 的題目困住?？傊绻嬖囶}不能評估面試者水平，那么問它還有什么意義呢？
下面是一些問濫的編程問題：
-
編程之美 書里的所有題目；
-
July 的算法博客 中的絕大多數題目（包括 面試 100 題 中的所有題目）；
-
leecode 里的大部分題目；
2.涉及到庫函數或 API 調用
白板編程的目標在于考察面試者的編程基本功，而不是考察面試者使用某種語言/類庫的熟練度。所以白板編程題目應盡可能庫函數無關——例如：編寫一個 XML 讀取程序就是不合格的題目，因為面試者沒有必要把 XML 庫中的函數名背下來（不然要 Intellisense 干甚）；而原地消除字符串的重復空白（例：”ab c d e” => “abcde”）則是一道合格的題目，因為即便不使用庫函數，合格的面試者也能夠在 20 分鐘內完成這道題目。
3.過于直接（或簡單）的算法問題
這類問題類似 被問濫的編程問題，它們的特點在于過于直接，以至于面試者不需要思考就可以給出答案，從而使得面試官無法考察面試者的思維過程。快速排序，深度優先搜索，以及二分搜索都屬于這類題目。
需要注意的是，盡管過于直接的算法題目不適合面試，但是我們可以將其進行一點改動，從而使其變成合理的題目，例如穩定劃分和二分搜索計數（給出有序數組中某個元素出現的次數）就不錯，盡管它們實際是快速排序和二分搜索的變種。
4.過于復雜的題目
同 過于直接的算法問題< 相反，過于復雜的題目 屬于另一個極端：這些題目往往要求面試者擁有極強的算法背景，盡管算法問題是否過于復雜因人而異（在一些 ACM 編程競賽選手的眼里可能就沒有復雜的題目 –_-），但我個人認為如果一道題滿足了下面任何一點，那么它就太復雜，不適合面試（不過如果面試者是 ACM 編程競賽選手，那么可以無視此規則）：
-
需要 aha! moment（參考 腦筋急轉彎）
-
需要使用某些『非主流』數據結構/算法才能求解
-
耗時過長（例如實現紅黑樹的插入/刪除）
5.腦筋急轉彎
什么是腦筋急轉彎？
-
不考察編程能力
-
依賴于 aha! moment
-
All or nothin：或者做不出來，或者是最終答案
在一些書（例如 誰是谷歌想要的人才？：破解世界最頂尖公司的面試密碼）和電影的渲染下，Google 和微軟這些外企的面試被搞的無比神秘，以至于很多人以為外企真的會問諸如『井蓋為什么是圓的』或是『貨車能裝多少高爾夫球』這樣的奇詭問題。而實際上，這 些題目由于無法考察面試者的技術能力而早已在外企中絕跡。反倒是一些國內公司開始使用腦筋急轉彎 作為面試題目 –_–#
#p#
應該問什么問題
所以，技術面試題目不應該太難，也不應太簡單，不能是腦筋急轉彎，也不能直接來自網絡。
前三點并不難滿足：我們可以去 算法導論，編程珠璣，以及 計算機程序設計藝術 這些經典算法書籍中的課后題/練習題挑選合適的題目，也可以自己創造題目。然而，由于 careercup 這類網站的存在，沒有什么題目可以做到絕對原創——畢竟沒有人能阻止面試者把題目發到網上，所以任何編程題目都逃脫不了被公開的命運。
不過，盡管面試者會把編程題目發到網上，甚至會有一些『好心人』給出答案，但這并不代表面試官不能繼續使用這道題：因為盡管題目被公開，但題目的考 察點和延伸問題依然只有面試官才知道。這有點像 公鑰加密，公鑰（面試題）是公開的，但私鑰（解法，考察點，以及延伸問題）只有面試官才知道。這樣即便面試者知道面試題，也不會妨礙面試官考察面試者的技 術能力。
接下來，讓我們看看什么問題適合白板編程。
1.不止一種解法
良好的編程問題都會有不止一種解法。這樣面試者可以在短時間內給出一個不那么聰明但可實現的『粗糙』算法，然后通過思考（或面試官提示）逐步得到更加優化的解法，面試官可以通過這個過程觀察到面試者的思維方式，從而對面試者進行更客觀的評估。
以 數組最大子序列和 為例，它有一個很顯然的 O(n3) 解法，將 O(n3) 解法稍加改動可以得到 O(n2) 解法，利用分治思想，可以得到 O(n*logn) 解法，除此之外它還有一個 o(n) 解法。（編程珠璣 和 數據結構與算法分析 C語言描述 對這道題均有非常精彩的描述，有興趣的朋友可以自行閱讀）
2.考察點明確
良好的編程問題應擁有大量考察點，面試官應對這些考察點爛熟于心，從而給出更加客觀量化的面試結果。這里可以參考我之前在 從武俠小說到程序員面試 提到的 to_upper。
3.延伸問題
良好的編程問題應擁有延伸問題。延伸問題既可以應對面試者背題的情況，也可以漸進的（Incremental）考察面試者的編程能力，同時還保證了面試的延續性（Continuity）。
以 遍歷二叉樹 為例：面試官可以從非遞歸中序遍歷二叉樹開始提問，面試者有可能會很快的寫（或是背）出一個使用棧的解法。這時面試官可以通過延伸問題來判別面試者是否在 背題：使用常量空間中序遍歷帶有父節點指針的二叉樹，或是找到二叉搜索樹中第 n 小的元素。下面是中序遍歷二叉樹的一些延伸問題：
- |--中序遍歷二叉樹
- |
- |--非遞歸中序遍歷二叉樹
- |
- |--常量空間，非遞歸遍歷帶父節點的二叉樹
- | |
- | |--在帶父節點的二叉搜索樹尋找第 N 小的元素
- | |
- | |--可否進一步優化時間復雜度？
- |
- |--常量空間，非遞歸遍歷不帶父節點的二叉樹
上面的問題不但可以被正向使用（逐步加強難度），也可以被逆向使用（逐步降低難度）：同樣從非遞歸中序二叉樹遍歷開始提問，如果面試者無法完成這個問題，那么面試官可以降低難度，要求面試者編寫一個遞歸版本的中序遍歷二叉樹。
#p#
如何進行白板編程
面試官應該做什么
面試前
面試之前，面試官應至少得到以下信息：
-
面試者的簡歷
-
面試者的應聘職位
-
面試者之前被問過哪些面試題
接下來，面試官應根據面試者的簡歷/職位確認對面試者的期望值，然后準備好編程題目（而不是面試時即興選擇題目）。面試官應至少準備 4 道題目（2 道簡單題，2 道難題），以應對各種情況。
面試中
面試時，面試官應清楚的陳述題目，并通過若干組用例數據確認面試者真正的理解題目（以免面試者花很長時間去做不相關的題目，我在之前的面試就辦過這種挫事 –_–#）
在面試者解題時，面試官應全程保持安靜（或傾聽的狀態），如果面試者犯下特別嚴重的錯誤或是陷入苦思冥想，面試官應給出適當的提示，以幫助面試者走出困境完成題目，如果面試者還是不能完成題目，那么面試官應換一道略簡單的題目，要知道面試的目的是發現面試者的長處，而非為難面試者。（一些國內企業似乎正好相反）
面試后
面試之后，面試官應拍照（或謄寫）面試者寫下的代碼，然后把提問的問題發給 HR 和接下來的面試者（以確保問題不會重復）。接下來，面試官應根據面試者的代碼以及其面試表現，盡快寫出面試反饋（Interview Feedback）發給 HR，以便接下來的招聘流程。
面試者應該做什么
面試前
面試之前，面試者應至少做過以下準備：
-
擁有扎實的數據結構/算法基礎
-
知道如何利用 前條件/不變式/后條件 這些工具編寫正確的程序
-
能夠在白板（或紙上）實現基本的數據結構和算法（如果 1 和 2 做到這一步是水到渠成）
-
在 leetcode 或 careercup 上面進行過練習，了解常見的技術面試題目（我個人不鼓勵刷題，但在面試前建立起對面試題的『感覺』非常重要）
面試中
確定需求
面試者在白板編程時最重要的任務是理解題目，確認需求——確定輸入/輸出，確定數據范圍，確定時間/空間要求，確定其它限制。以最常見的排序為例：
-
輸入：來自數組？鏈表？或是不同的機器？
-
輸出：是否有重復？是否要求穩定？
-
數據范圍：排序多少個元素？100 個？ 100 萬個？ 1 億個？這些元素是否在某個范圍內？
-
時間要求：1 分鐘？1 刻鐘？一小時？
-
空間要求：是否常量空間？是否可以分配新的空間？如果可以，能分配多少空間？是否在內存中排序？
-
其它限制：是否需要盡可能少的賦值？是否需要盡可能少的比較？
有時面試官不會把題目說的特別清楚，這時就需要面試者自己去確認這些需求，不要認為這是在浪費時間，不同的需求會導致截然不同的解法，此外確認需求會留給面試官良好的印象。
#p#
白板編程
理解題目確認需求之后，面試者就可以開始在白板上編寫代碼，下面是一些我自己的白板編程經驗：
-
先寫出輪廓（大綱）
白板編程沒法復制粘貼，所以后期調整代碼結構非常困難。因此我們最好在開頭寫出程序的大致結構，從而保證之后不會有大改；
-
確定前條件/不變式/后條件
我們可以通過注釋的形式給出代碼的前條件/不變式/后條件，以劃分為例：
- 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;
- }
使用實例數據驗證自己的程序
盡管不變式足以驗證程序的正確性，但適當的使用實例數據會大大增強代碼的可信性，以上面的劃分程序為例：
- 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
- 使用縮寫
白板編程并不需要面試者在白板上寫出能夠一次通過編譯的代碼。為了節省時間，面試者可以在和面試官溝通的基礎上使用縮寫。例如使用 Iter 替代 Iterable，使用 BQ 替代 BlockingQueue。（此法尤其適合于 Java –_–#）
-
至少留一行半行寬
出于緊張或疏忽，一般面試者在白板編程時會犯下各種小錯誤，例如忘了某個判斷條件或是漏了某條語句，空余的行寬可以幫助面試者快速修改代碼，使得白板上的代碼不至于一團糟。
這就延伸出了另一個問題，如果使用大行寬，那么白板寫不下怎么辦？一些面試者聰明的解決了這個問題：他們在面試時會自帶一根細筆跡的水筆，專門用于白板編程。
不會做怎么辦
相信大多數面試者都碰到過面試題不會做的情況，這里說說我自己的對策：
-
至少先給出一個暴力（Brute force）解法
-
尋找合適的數據結構（例如棧/隊列/樹/堆/圖）和算法（例如分治/回溯/動態規劃/貪婪）
-
從小數據集開始嘗試
-
如果還是沒有頭緒，重新考慮題目的前條件，思考是否漏掉了條件（或是隱含的條件）
-
如果 3 分鐘過后還是沒有任何思路，請求面試官提示，不要覺得不好意思——經過提示給出答案遠強于沒有答案
面試后
個人不建議面試者在面試之后把題目發到網上，很多公司在面試前都會和面試者打招呼，有的會簽訂 NDA（Non Disclosure Agreement）條款以確保面試者不會泄露面試題目。盡管他們很少真的去查，但如果被查到那絕對是得不償失。
我自己在面試之后會把面試中的編程題目動手寫一遍（除非題目過于簡單不值得），這樣既能夠驗證自己寫的代碼，也可以保證自己不會在同一個地方摔倒兩次。
參考
書籍
-
Elements of Programming Interviews: The Insiders’ Guide
-
編程原本
-
程序員面試金典（第5版）
