## 面试前
面试之前，面试者应至少做过以下准备：
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）条款以确保面试者不会泄露面试题目。尽管他们很少真的去查，但如果被查到那绝对是得不偿失。
我自己在面试之后会把面试中的编程题目动手写一遍（除非题目过于简单不值得），这样既能够验证自己写的代码，也可以保证自己不会在同一个地方摔倒两次。
