你会翻转二叉树吗？--谈程序员的招聘

字数统计: 2.4k阅读时长: 8 min

 2015/06/16 

事件回放

2015 年 6 月 10 日，Homebrew 的作者 @Max Howell 在 twitter 上发表了如下一内容：

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

事情大概是说，Max Howell 去 Google 面试，面试官说：虽然在 Google 有 90% 的工程师用你写的 Homebrew，但是你居然不能在白板上写出翻转二叉树的代码，所以滚蛋吧。

这件事情如果发生在任何一个应届生身上，那是再正常不过的了，但是偏偏面试者是有名的 Max Howell。于是乎，关于应该如何面试程序员，再一次被大家热烈的讨论。

我看了一下 Quora 和 Hacker News 上的讨论，就此话题说说我的看法。

如何做这道题

在说招聘之前，我们先谈谈这道题应该怎么做吧。LeetCode 非常与时俱进地收录了这道题，我尝试做了一下。由于 LeetCode 不支持用 Objective-C 或 Swift 写，我只好用 Java 来写，但是电脑里面没有装 Eclipse，所以我直接就在 LeetCode 编辑框里面提交了。

编译错了两次，之后运行错了一次，出现了 NullPointerException，于是想到没有检查指针为空，加上检查之后，就通过了。下图是提交记录。

除去 LeetCode 自动生成的注释和方法定义，我所写的整个代码行数为 9 行，大概花了 5 分钟时间。代码如下所示：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.left = invertTree(root.left);
        root.right = invertTree(root.right);

        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }
}

那么这道题考查了什么呢？我觉得主要是考查了递归的思想。递归是程序设计的精髓，掌握了他可以将一个大问题分解成小问题，继而求解。比如对于此题来说，反转一个二叉树其实就是：

反转二叉树的左右子树
将左右子树交换

而第 1 步又是一个反转二叉树的问题，所以就可以用递归来处理了。然后再考虑好递归的结束条件，这道题就可以解决了。

这是一道好的面试题吗？

如果面试者是一个应届生，我认为这是一道非常好的题目。因为应届生刚刚学完学校的数据结构和算法知识，二叉树和递归都是基本的知识，应该被掌握的。

如果面试者是一个有多年工作经验的人，我认为这道题的难度其实不大，一个人即使多年不使用二叉树，多年不使用递归，但是这种思考还是很容易想到的。当然，所花的时间可能会大一些。所以我并不认为这是一道难题。

但是，对于一个有工作经验的人，考查他的工作内容，或许更有价值。因为相比代码的逻辑思维能力来说，工作方式和解决问题态度，架构设计，设计模式都是更重要的考查点。

当我们面算法题的时候，我们在考查什么？

就像 Quora 上提到的那样，算法题面试被广泛应用在各大顶级互联网公司，包括 Google, Facebook, Microsoft, Amazon, Airbnb, Dropbox。在中国，这样的情况同样存在，BAT 的面试也充斥着算法题目。我当年在网易有道面试的时候，每一轮也都问了很多道算法题目。

但是，很多求职者都会问：“工作中用得到这些吗？”，说实话，用得非常少。那么当我们面算法题的时候，我们到底在考查什么？就我的经验来看，我们会从算法面试中考查到以下三点：

计算机的基础知识。一个人基础知识扎实，说明他在学校就很用功。
聪明程度。编程还是一个重智力的工作，智商高的人会在不停地知识更新中快速跟进学习。算法题其实就是计算机专业的智力测试题。这里面，动态规划的算法题目由于变化多，体现得就特别明显，考动态规划其实就是测智力。
沟通能力和思维。面试算法题的时候，一般不会直接让候选人写代码，而是会先一起讨论。通过讨论的过程，了解面试者沟通的能力和考虑问题的方式，也是考查的重点。

考查算法题会不会太片面？

是的，算法在工作中运用得比较少，一般人也不会在工作中专门积累解算法题的能力。所以通常做算法题最强的是应届生，因为他们有时间去刷题。而在实际工作中，很多能力，都比算法能力重要。比如对代码的洁癖，对设计模式的理解，对计算机底层（操作系统、网络）的理解，对待工作的态度等。

那么，为什么那么多公司不考查，或者不重点考查这些，而只是问算法题呢？

答案很简单，因为要在几个小时内了解一个人太难了。通常一场面试只有一个小时，如果要在一个小时内把上面说到的知识点都面面俱到的考查，是做不到的。但是如果花几天来考查，对于公司和求职者都是不可接受的。所以，很多大公司就用面算法题的方式来偷懒，因为这种方式虽然可能会误伤很多优秀的人才，但是不合格的人，要混进去还是相当困难的。

讲一句不好听的，很多公司在招聘的时候，首先根据学校，把非 985 的学校简历都过滤掉，也是一种不太合理，但是有效的方法。清华北大的人一定就牛逼吗？不一定，但是从概率上讲，比南翔技校的人通过面试的机会要高一些。所以，为了提高面试效率和成本，就直接把一般学校的简历过滤掉，这是一个不人道，但是从经济上合理的行为。

我自己也因为这个选拔方式深受打击，我自认为还是非常优秀的，在学校时拿到过 ACM 国际大学生程序设计竞赛的区域赛金牌，也在 IBM 实习过，学校专业课成绩也很好，但是毕业那年我连 Google 的笔试资格都没拿到。因为我不是清华北大的，Google 就在清华北大选人才，就足够了。

我们应该怎么办？

现有的面试方式，其实让公司和候选者都不是太爽，主要的原因就是考查的时间太短，能够参考的信息量太小。但是，随着互联网的发展，作为程序员，我们慢慢有了更多的方式来让公司在面试前就了解自己。

我们可以搭建自己的博客，将自己的学习心得总结下来。我们可以将自己写得好的代码开源在 Github 上。我们可以在 stackoverflow 上回答问题，用 reputation 来证明自己的能力。我们还可以给著名的开源项目提 PR，成为重要的 Contributor。我们可以给 InfoQ 网站投稿。我们可以去 QCon 上分享技术。

如果你能在网络上构建起自己的技术能力图，那么对于很多公司来说，或许面试中偏技术性的考查就不那么重要了，面试的过程就可以更轻松愉快了。

但是，不要高兴得太早，要做到上面提到的这些只会比做算法题更难。但是，至少我们可以让自己的实习得到充分展示，能够让面试不那么片面，能够让公司更加全面的了解自己。

所以说最后，机会还是给那些努力的人。如果一个人学校不好，没有做过什么大项目，在网上没有任何可以考查的信息，那么面试的时候，估计等待他的还是各种算法题。