应该问什么问题

所以，技术面试题目不应该太难，也不应太简单，不能是脑筋急转弯，也不能直接来自网络。 前三点并不难满足：我们可以去 [算法导论](http://www.amazon.cn/gp/product/B00AK7BYJY/ref=as_li_ss_tl?ie=UTF8&camp=536&creative=3132&creativeASIN=B00AK7BYJY&linkCode=as2&tag=lucida-23)，[编程珠玑](http://www.amazon.cn/gp/product/B00SFZH0DC/ref=as_li_ss_tl?ie=UTF8&camp=536&creative=3132&creativeASIN=B00SFZH0DC&linkCode=as2&tag=lucida-23)，以及 [计算机程序设计艺术](http://www.amazon.cn/gp/product/B00478TO44/ref=as_li_ss_tl?ie=UTF8&camp=536&creative=3132&creativeASIN=B00478TO44&linkCode=as2&tag=lucida-23) 这些经典算法书籍中的课后题/练习题挑选合适的题目，也可以自己创造题目。然而，由于 [careercup](http://www.careercup.com/page) 这类网站的存在，没有什么题目可以做到绝对原创——毕竟没有人能阻止面试者把题目发到网上，所以任何编程题目都逃脱不了被公开的命运。 不过，尽管面试者会把编程题目发到网上，甚至会有一些『好心人』给出答案，但这并不代表面试官不能继续使用这道题：因为尽管题目被公开，但题目的考察点和延伸问题依然只有面试官才知道。这有点像 [公钥加密](http://zh.wikipedia.org/wiki/%E5%85%AC%E5%BC%80%E5%AF%86%E9%92%A5%E5%8A%A0%E5%AF%86)，公钥（面试题）是公开的，但私钥（解法，考察点，以及延伸问题）只有面试官才知道。这样即便面试者知道面试题，也不会妨碍面试官考察面试者的技术能力。 接下来，让我们看看什么问题适合白板编程。 ## 不止一种解法 良好的编程问题都会有不止一种解法。这样面试者可以在短时间内给出一个不那么聪明但可实现的『粗糙』算法，然后通过思考（或面试官提示）逐步得到更加优化的解法，面试官可以通过这个过程观察到面试者的思维方式，从而对面试者进行更客观的评估。 以 [数组最大子序列和](http://en.wikipedia.org/wiki/Maximum_subarray_problem) 为例，它有一个很显然的 O(n3) 解法，将 O(n3) 解法稍加改动可以得到 O(n2) 解法，利用分治思想，可以得到 O(n*logn) 解法，除此之外它还有一个 o(n) 解法。（[编程珠玑](http://www.amazon.cn/gp/product/B00SFZH0DC/ref=as_li_ss_tl?ie=UTF8&camp=536&tag=lucida-23&creativeASIN=B00SFZH0DC&linkCode=as2&creative=3132) 和 [数据结构与算法分析 C语言描述](http://www.amazon.cn/gp/product/B002WC7NGS/ref=as_li_ss_tl?ie=UTF8&camp=536&creative=3132&creativeASIN=B002WC7NGS&linkCode=as2&tag=lucida-23) 对这道题均有非常精彩的描述，有兴趣的朋友可以自行阅读） ## 考察点明确 良好的编程问题应拥有大量考察点，面试官应对这些考察点烂熟于心，从而给出更加客观量化的面试结果。这里可以参考我之前在 [从武侠小说到程序员面试](http://lucida.me/blog/from-wuxia-to-programmer-interview/) 提到的 `to_upper`。 ## 延伸问题 良好的编程问题应拥有延伸问题。延伸问题既可以应对面试者背题的情况，也可以渐进的（Incremental）考察面试者的编程能力，同时还保证了面试的延续性（Continuity）。 以 [遍历二叉树](http://zh.wikipedia.org/wiki/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86) 为例：面试官可以从非递归中序遍历二叉树开始提问，面试者有可能会很快的写（或是背）出一个使用栈的解法。这时面试官可以通过延伸问题来判别面试者是否在背题：使用常量空间中序遍历**带有父节点指针**的二叉树，或是找到二叉搜索树中第 n 小的元素。下面是中序遍历二叉树的一些延伸问题： ~~~ |--中序遍历二叉树 | |--非递归中序遍历二叉树 | |--常量空间，非递归遍历带父节点的二叉树 | | | |--在带父节点的二叉搜索树寻找第 N 小的元素 | | | |--可否进一步优化时间复杂度？ | |--常量空间，非递归遍历不带父节点的二叉树 ~~~ 上面的问题不但可以被正向使用（逐步加强难度），也可以被逆向使用（逐步降低难度）：同样从非递归中序二叉树遍历开始提问，如果面试者无法完成这个问题，那么面试官可以降低难度，要求面试者编写一个递归版本的中序遍历二叉树。