唐巧的博客

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

字数统计: 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。于是乎,关于应该如何面试程序员,再一次被大家热烈的讨论。

我看了一下 QuoraHacker 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. 反转二叉树的左右子树
  2. 将左右子树交换

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

这是一道好的面试题吗?

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

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

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

当我们面算法题的时候,我们在考查什么?

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

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

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

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

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

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

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

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

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

我们应该怎么办?

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

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

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

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

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

猿题库是如何招聘的?

或许你会失望,我们其实就是和 Google 一样,会问大量的算法题。即使你来自名校名企,但是不会翻转二叉树,我们肯定会把你拒掉。

对于有经验的开发者,我们会适当降低算法题的难度,同时考查一些工作经历,但是翻转二叉树这种难度的题目,是必须做出来的。

所以,如果你没有各种社交网络的资料证明自己的实力,那还是老老实实把基础知识准备扎实吧。算法知识虽然用得少,但是在关键时候还是有用的,以后我会另外撰文举例。

愿大家都能找到自己的伯乐~


PS: 我所负责的小猿搜题项目,在半年时间内做到了市场第一的位置,现在想招更多 Java 服务器端和 Android 端开发,待遇和期权高于 BAT,面试要求也会高于 BAT。欢迎大家将简历发到 tangqiao(AT)fenbi.com 。这里有职位说明


扫码关注我的「iOS 开发」微信公共帐号,及时获得我精选的各种 iOS 文章:

CATALOG
  1. 1. 事件回放
  2. 2. 如何做这道题
  3. 3. 这是一道好的面试题吗?
  4. 4. 当我们面算法题的时候,我们在考查什么?
  5. 5. 考查算法题会不会太片面?
  6. 6. 我们应该怎么办?
  7. 7. 猿题库是如何招聘的?