## 面試前
面試之前，面試者應至少做過以下準備：
1. 擁有扎實的數據結構/算法基礎
2. 知道如何利用 前條件/不變式/后條件 這些工具編寫正確的程序
3. 能夠在白板（或紙上）實現基本的數據結構和算法（如果 1 和 2 做到這一步是水到渠成）
4. 在?[leetcode](https://leetcode.com/)?或?[careercup](http://www.careercup.com/page)?上面進行過練習，了解常見的技術面試題目（我個人不鼓勵刷題，但在面試前建立起對面試題的**『感覺』**非常重要）
## 面試中
**確定需求**
面試者在白板編程時最重要的任務是**理解題目，確認需求**——確定輸入/輸出，確定數據范圍，確定時間/空間要求，確定其它限制。以最常見的**排序**為例：
* 輸入：來自數組？鏈表？或是不同的機器？
* 輸出：是否有重復？是否要求穩定？
* 數據范圍：排序多少個元素？100 個？ 100 萬個？ 1 億個？這些元素是否在某個范圍內？
* 時間要求：1 分鐘？1 刻鐘？一小時？
* 空間要求：是否常量空間？是否可以分配新的空間？如果可以，能分配多少空間？是否在內存中排序？
* 其它限制：是否需要盡可能少的賦值？是否需要盡可能少的比較？
有時面試官不會把題目說的特別清楚，這時就需要面試者自己去確認這些需求，不要認為這是在浪費時間，不同的需求會導致截然不同的解法，此外確認需求會留給面試官良好的印象。
**白板編程**
理解題目確認需求之后，面試者就可以開始在白板上編寫代碼，下面是一些我自己的白板編程經驗：
* 先寫出輪廓（大綱）
白板編程沒法復制粘貼，所以后期調整代碼結構非常困難。因此我們最好在開頭寫出程序的大致結構，從而保證之后不會有大改；
* 確定前條件/不變式/后條件
我們可以通過注釋的形式給出代碼的前條件/不變式/后條件，以劃分為例：
~~~
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 –_–#）
* 至少留一行半行寬
出于緊張或疏忽，一般面試者在白板編程時會犯下各種小錯誤，例如忘了某個判斷條件或是漏了某條語句，空余的行寬可以幫助面試者快速修改代碼，使得白板上的代碼不至于一團糟。
這就延伸出了另一個問題，如果使用大行寬，那么白板寫不下怎么辦？一些面試者聰明的解決了這個問題：**他們在面試時會自帶一根細筆跡的水筆，專門用于白板編程。**
**不會做怎么辦**
相信大多數面試者都碰到過面試題不會做的情況，這里說說我自己的對策：
1. 至少先給出一個暴力（Brute force）解法
2. 尋找合適的數據結構（例如棧/隊列/樹/堆/圖）和算法（例如分治/回溯/動態規劃/貪婪）
3. 從小數據集開始嘗試
4. 如果還是沒有頭緒，重新考慮題目的前條件，思考是否漏掉了條件（或是隱含的條件）
5. 如果 3 分鐘過后還是沒有任何思路，請求面試官提示，不要覺得不好意思——經過提示給出答案遠強于沒有答案
## 面試后
個人不建議面試者在面試之后把題目發到網上，很多公司在面試前都會和面試者打招呼，有的會簽訂 NDA（Non Disclosure Agreement）條款以確保面試者不會泄露面試題目。盡管他們很少真的去查，但如果被查到那絕對是得不償失。
我自己在面試之后會把面試中的編程題目動手寫一遍（除非題目過于簡單不值得），這樣既能夠驗證自己寫的代碼，也可以保證自己不會在同一個地方摔倒兩次。
