吴军
我一直在强调人要少做事情，因为提高效率的根本在于少做事情，事实上对计算机来讲也是如此。今天我们再讲解一道Google面试题，你会从中进一步理解为什么效率的来源在于少做无用功了。
这道题是我最爱考面试人的一道题，因为它说起来简单，但一大半的面试者做不对，而且对那一小半答对了的人，我还可以不断追问下去，把9成的面试者难在某个地方。说起来难吧，没有计算机背景知识的人也能一听就懂。这道题是这么说的：
假如有一个巨大的数组（你可以理解成一串数字），如何用最有效的方法找到它的中值？
题目本身就这么简单的一句话。由于它看上去太简单了，以至于我每次出这道题之前总要说几句话做铺垫，“我们今天从一道简单的题开始，算是热热身，你看好不好？”这样，面试者不会觉得被一道简单的题目羞辱了。不过请注意这里有好几处坑。我常讲，很多时候做不出题是因为根本没有读懂题，理解题，匆匆忙忙就做了，这比不会做给人的印象还糟糕十倍。
这道题里的第一个坑是要寻找中值，而不是平均值。大约有10%－20%的人会听题不仔细，或者自己搞不懂中值和平均值的区别，就匆匆忙忙求平均值了。
那么什么是中值？如果有三个数1，2，100，那么中值是2，而平均值则是34左右。在很多场合，中值比平均值更有意义。比如考察一个国家个人的收入。一个好的面试者，如果不确定什么是中值，或者说不确定我所要问的问题，他会先确认一下中值的含义，并且自己举出类似上面那样的例子。
这样有两个好处：其一，即使他没有回答上来，至少说明听懂题目了，并且了解中值的概念；其二，他是一个合格的沟通者，在工作中遇到不确定的要求，会搞清楚以后再动手，而不是一个匆匆忙忙把事情搞砸了的人。
第二个坑是“巨大”这个字眼。当一个题目的规模巨大时，适用于小规模的很多方法就不适用了，有工程经验的人都懂得这一点，而很多刚从学校走出来的学生则缺乏这种概念。
第三个坑是“最有效”这三个字。也就是说，找到中值的方法可以有很多种，找到一个好的还不算数，需要找到最好的。
当然，聪明一点的面试者还会先搞清楚，“最有效”这三个字是指时间上最快，还是最节省空间。如果他这样反问，也说明他有较好的工程素养和沟通技巧。不过在这道题目中，我们追求的是时间上的有效，也就是要速度快。
这个问题还有其他的坑，因为比较复杂，我就省略了。
水平不够又缺乏面试经验的人，会马上提出先排序，再找到中间那个数字的方法。这样的回答比较糟糕。首先，他掉进了题目中第二和第三个坑。排序是一种解决办法，但是绝不是最有效的，而且当面临“巨大的数组”时，为了找到一个数排序，显然做了太多的无用功。其次，他没有体会到考他这道题背后的目的。作为Google这样的公司，面试题不可能太容易，排序这种想法，是个人都能想到。考他这道题，一定是因为对于Google来讲，要处理的数据量太大，必须找到比排序更好的方法。
同样是找不到更好方法，但是善于沟通的人会这么讲：
我知道，你考我这道题不是要寻找排序这样的方法，虽然排序也能解决问题，你能否给我点时间，让我想想更好的方法？
这样的回答有两个好处，首先是告诉对方他知道考这道题的目的，同时自己懂得排序，这是一个好的沟通者。其次，他给自己赢得了时间。当然，如果过了几分钟他还是想不出来，有经验的面试者会说，能否给我点提示呢？在工作中，请求帮助永远比自己闷头做不出来要好。在面试时，大约有20%的人在思考了一段时间后，能够想出更好的办法。
在这个问题上，一些候选人会想出一个比排序更好一点的方法，那就是我们前面提到的“N个加油站中找到K个距离最近的加油站”的那个方法。这里，只要把K设置成N的一半即可。忘了那一期内容的朋友，可以回头再读读那封来信，链接在信的底部。这种方法只对数值小的一半进行了排序，因此大约可以省一半时间。但是正如我们在课程一开始讲的，对于计算机科学来讲，省一半时间意义不是很大，我们追求的是更高的效率。因此，我们还要找更好的方法。
上述方法为什么效率不高呢？其根本的原因是做了太多的无用功！这道题只要求找到中值，至于那些大于中值的数字彼此的关系是什么，小于中值的数字相对的次序是什么，我们其实不用关心。排序的方法，把这些工作也顺带做了，显然多做了很多事情，自然效率高不起来。因此，要想找到好方法，一定要避免排序。
当然，你可能会问了，如果不排序，又怎么知道谁是中值？这确实是一个好问题。在进一步讲解我们的方法之前，我们举一个具体的例子。假如数组中的数字是：
1，－5，3，7，1000，2，－10
排好序后是这样的：
－10，－5，1，2，3，7，1000
这个序列可以看得一目了然，2就是中值，因为比2小的数字都在它的左边，有三个，比它大的数字都在右边，恰好也是三个。但是，如果我们把这七个数字按照下面的方式排列：
－5，1，－10，2，1000，3，7
我们会发现，小于2的在左边，有三个，大于2的在右边，也是三个，因此也能得到2是中值的结论。所不同的是，整个数组并没有从小到大排列。其实，只要我们能够把数组重新整理成后一种样子，对于找中值是足够的。
那么怎么不经过排序，让小的数字都到左边，大的数字都到右边呢？讲起来也很简单。我们可以从数组中随便找一个数字，让它和数组中每一个数字去比较大小。如果比它小，就放在左边，如果比它大就放在右边。这个过程被称为划分（Partition）。
当然，除非你的运气特别好，第一次就随机挑上了中值，否则划分的结果肯定一边多一些，一边少一些。比如有100个数字，第一次划分之后，大的一边有60个，小的一边有40个。很显然，中值一定是在大的一边，也就是有60个数字的一边，而不可能在小的一边。因此第二次我们只要在大的一边随机选取一个数字，再做一次划分，看看是否平衡就可以了。
需要强调的是，第二次分割要考虑的数字比第一次少了一小半，如果还没找到，第三次划分的范围又缩小了一小半，直到找到为止。可以证明，这种方法通常复杂度非常低，大约只相当于把整个数组扫描了三四遍而已。
如果我们要寻找10亿个数字的中值，采用排序的方法大约需要1万亿次计算，而采用这种划分的方法大约只需要30亿次计算，时间相差300倍。这里面效率的提高完全来自于少做了很多无用功。
讲到这里，你已经理解了为什么Google会问这个问题。Google这样的公司，每天都要处理海量的数据，所使用的方法必须是最优化的，否则很轻易地就浪费掉上百倍资源。
如果你还记得我在之前讲过的快速排序算法，对今天的内容是否有似曾相识的感觉呢？事实上今天讲的方法和快速排序的方法非常相似，都是用一个随机的数值对数组进行划分。如果一个候选人掌握了快速排序思想的精髓，而不仅仅是背下来那个算法，这道题应该能很好地解决。实际上，像Google这样公司的面试，很少会直接考书本中的内容，但是通过一个实际问题很容易考察出求职者能否灵活运用所学知识。
从这个例子中我们可以总结出如下三点经验：
1. 少做事是提高效率的关键。
2. 一流人才和二流、三流的差别在于，后者虽然也能完成任务，但是未必能把事情做到最好，而一流的人总是能找到在当下最好的方法。而一种方法的好和坏，可以差出几十、上百倍的效率。这就是我讲的工程师水平差一级，贡献可以差出一个数量级的原因。
3. 对所学内容掌握得好坏高低，通常不是靠直接考核那些内容能知道的，而是要看能否运用所学。只有会用了，才是真的学到手了。
这个问题其实还只是一连串问题的开始。如果候选人很快答上了这个问题，我还会让他证明为什么上述方法的计算复杂度只相当于把数组扫描几遍，最好的情况和最坏的情况会是什么样，什么时候会发生等等。此外，当数组特别特别大，以至于一台服务器都存不下了，应该怎么处理？
因此，一个好的求职者一定是能够活学活用知识的，而不是简单背一下答案。希望这些面试的经验也对你有所启发。
网友评论