应该问什么问题

所以,技术面试题目不应该太难,也不应太简单,不能是脑筋急转弯,也不能直接来自网络。

前三点并不难满足:我们可以去 算法导论编程珠玑,以及 计算机程序设计艺术 这些经典算法书籍中的课后题/练习题挑选合适的题目,也可以自己创造题目。然而,由于 careercup 这类网站的存在,没有什么题目可以做到绝对原创——毕竟没有人能阻止面试者把题目发到网上,所以任何编程题目都逃脱不了被公开的命运。

不过,尽管面试者会把编程题目发到网上,甚至会有一些『好心人』给出答案,但这并不代表面试官不能继续使用这道题:因为尽管题目被公开,但题目的考察点和延伸问题依然只有面试官才知道。这有点像 公钥加密,公钥(面试题)是公开的,但私钥(解法,考察点,以及延伸问题)只有面试官才知道。这样即便面试者知道面试题,也不会妨碍面试官考察面试者的技术能力。

接下来,让我们看看什么问题适合白板编程。

不止一种解法

良好的编程问题都会有不止一种解法。这样面试者可以在短时间内给出一个不那么聪明但可实现的『粗糙』算法,然后通过思考(或面试官提示)逐步得到更加优化的解法,面试官可以通过这个过程观察到面试者的思维方式,从而对面试者进行更客观的评估。

以 数组最大子序列和 为例,它有一个很显然的 O(n3) 解法,将 O(n3) 解法稍加改动可以得到 O(n2) 解法,利用分治思想,可以得到 O(n*logn) 解法,除此之外它还有一个 o(n) 解法。(编程珠玑 和 数据结构与算法分析 C语言描述 对这道题均有非常精彩的描述,有兴趣的朋友可以自行阅读)

考察点明确

良好的编程问题应拥有大量考察点,面试官应对这些考察点烂熟于心,从而给出更加客观量化的面试结果。这里可以参考我之前在 从武侠小说到程序员面试 提到的 to_upper

延伸问题

良好的编程问题应拥有延伸问题。延伸问题既可以应对面试者背题的情况,也可以渐进的(Incremental)考察面试者的编程能力,同时还保证了面试的延续性(Continuity)。

以 遍历二叉树 为例:面试官可以从非递归中序遍历二叉树开始提问,面试者有可能会很快的写(或是背)出一个使用栈的解法。这时面试官可以通过延伸问题来判别面试者是否在背题:使用常量空间中序遍历带有父节点指针的二叉树,或是找到二叉搜索树中第 n 小的元素。下面是中序遍历二叉树的一些延伸问题:

|--中序遍历二叉树
    |
    |--非递归中序遍历二叉树
        |
        |--常量空间,非递归遍历带父节点的二叉树
        |   |
        |   |--在带父节点的二叉搜索树寻找第 N 小的元素
        |       |
        |       |--可否进一步优化时间复杂度?
        |
        |--常量空间,非递归遍历不带父节点的二叉树

上面的问题不但可以被正向使用(逐步加强难度),也可以被逆向使用(逐步降低难度):同样从非递归中序二叉树遍历开始提问,如果面试者无法完成这个问题,那么面试官可以降低难度,要求面试者编写一个递归版本的中序遍历二叉树。

文章导航