Google面试题：如何设计一个地图功能，找到离当前最近的加油

今天我们讲解一个Google的面试题，假如你负责手机或者车载地图这个产品，如何设计这样一个功能，即找到离当前位置最近的几个加油站？这样的面试问题一来是考察计算机科学的基本知识，二来是看候选人分解问题、解决问题的能力。

在解题之前，我们先要把问题理解清楚，而不是一上来就盲目地做。很多人面试失败的主要原因就是答非所问，或者没有体会出题人的考察点。

对于这个问题，如果是车载的地图，需要考虑到汽车是移动的，结果会不断更新，因此那些速度很慢的算法就不适合这个场景了。其次，结果的刷新记录也不必太快，以免用户觉得结果太不确定。事实上，如果有两个加油站，一个距离2.5公里，一个2.3公里，对开车的人来讲差别不是很大，更何况路况的拥堵情况可能让这200米的差距变得越发不重要。但是，如果是行人在手机上寻找最近的7-11便利店，200米的差距就有意义了，而且通常步行不会拥堵，因此少走两百米就省两百米。

在正式解答这一类应用问题之前，可以谈谈不同场景下所需要考虑的因素。事实上，如果一个候选人一上来就将这个问题抽象化，并且解决了问题，有经验的考官最后会和面试者讨论各种应用场景下的变通，看看候选人只是刷题背答案，还是对具体问题有全面的思考。有些时候，一些候选人觉得对方考自己的问题都答上来了，但是没有被录取，其实那些看似轻松随意的讨论，也是考官考察候选人，获取信息的环节，不能轻视。

讲完了考这道题的目的和通常的面试过程，我们接下来就来分析一下这道题，我们以车载系统为例来讲解，这个问题我们需要做三步分解。

首先，我们需要搞清楚每一个加油站的位置和汽车现在的位置，最好同时也搞清楚行车方向。 一般来讲，在遇到课堂上的书面考试题时，已知条件都会写得极清楚，不会多给，也不会少给。而面试的问题，已知条件有时需要和考官沟通确认。在这个问题中，加油站的位置是GPS的坐标，还是街道的名称和号码，或者是什么地图中特定的坐标，这个要和考官沟通清楚。
为了简单起见，我们不妨假设这些信息都有。至于汽车的位置，要更加复杂一点，因为它没有门牌号，只有GPS的定位，可能还需要转换成街道地址的范围（比如在北京朝阳区东方路1号到10号之间）。这些我们假定也都能办到。上述这些都算作确定了的已知条件，接下来的讨论就基于这些已知信息。

第二步，就要说说距离的计算了。  在地面上行驶，两点之间的距离不是欧几里得直线距离，因为车辆不可能穿过建筑直行。因此，两点之间的距离其实是很多距离片段的叠加。在一个城市里，连通两个点之间每一段距离的线路可以有很多种，它们之间的组合呈指数上涨，也就是说，拐几道弯，隔了几个红绿灯，各种路线的组合很容易就有上千种，那么怎么找到上千种路线中最短的一条呢？

在数学中有一种方法叫做动态规划， 可以完成这件事，在上千种组合中用很少的步骤（大约几十步）就能算出最短的路径。真正面试Google这样的公司时，面试官或许会考对方这个算法。这个算法我在《数学之美》一书中介绍了，这里就不赘述了，非计算机专业的朋友只要知道这个名称也就可以了，不必深究细节。

总之，我们是有办法在地图上找到两个点之间最短的行车路径。接下来，我们就可以把汽车和城市里所有的加油站之间的距离列一个表，它的格式可以如下：
加油站G1，距离D1；
加油站G2，距离D2；
……
加油站GN，距离DN。
到此，第二步算是完成了。

接下来的第三步，就是要按照距离排序，找出最近的几个加油站。 我们可以认为这是整个问题的子问题。

对于这个子问题，我遇到过的一些面试者会想到排序。排序当然是一个解决办法，但不是最佳的。对N个加油站根据距离排序大约需要N乘以LogN的计算量，如果像北京这样的城市，有1000个加油站，LogN大约是10。也就是说，计算的复杂度大约是N的10倍这个量级，也就是一万左右。这个计算量对计算机来讲算不上什么，但是如果考虑到汽车在移动，每分钟应该更新三五次数据，北京市有上百万辆车在路上，可能有上千辆车在寻找加油站，这种计算对于地图这种产品，也是一个负担。因此，好的工程师在设计产品时，需要找到更好的方法，这就是我们今天要讲的重点。

怎样找到更好的方法？我们需要回到问题的原点。上述通过排序找到最近的几个加油站的方法，其实做了很多无用功。原来的问题所要求的只是找到最近的几个加油站，提问题的人其实不关心那些距离比较远的加油站的距离和排序， 如果把所有的加油站都按照距离排序，做的工作其实比要求的多，而多做的工作在产品中也没有用途。因此，提高产品的性能，其实就应该从避免做无用功入手。

怎么才能避免做无用功呢？我们不妨回忆一下昨天说的锦标赛排序以及高盛的赛跑问题。锦标赛排序的好处是，它并非要等到所有的排序工作都做完的时候，才知道谁是第一名，而是可以只排出前几名。

事实上，在二叉树这种数据结构中，有一种更特殊的细类，被称为“堆”，用这种数据结构，就可以做到只排出前几名，而不用管后面的名次。因此我们不妨把这种新方法称为小规模的堆排序。如果只需要排出前K名，这种算法得到第一名的复杂度是N，而得到第二、第三、第四名等等的复杂度都只有Log N，比对1000个加油站排序要快得多。如果我们只要找到最近的10个加油站，计算的量级大约是1000左右，比以前说的快速排序降低了10倍。

10倍之差，在工程上显然有意义。如果N非常大，就更有意义了。比如说，淘宝要找到一年之中交易额最高的10个顾客，给予一些奖励。我们假设淘宝的顾客有5亿，那么这种采用堆排序的方法找到前十名的时间，可以比快速排序节省30倍的时间。如果再稍微变通优化一下，则可以省上百倍的时间。在大数据的很多应用中，我们通常只关心前几个，而不需要对所有的数据排序。因此，Google通过这道面试题，其实可以不断地往下追问，全面考察面试者的专业技能。

到此，似乎这道面试题解决得很完美了，那么是否还能继续改进呢？答案是肯定的。

我们在前面做分析时，其实不知不觉地做了一个假设，就是整个算法优化的过程是围绕着一个使用者的某一次使用进行的。但在现实生活中，一个城市里（甚至一个国家），很多人会同时从不同的地方在寻找加油站。类似地，同一个人，在不同时间，也会在某个地方开车时，寻找加油站。

如果考虑到这个真实的应用场景应该是很多人不停地使用这个功能，那么很多计算其实都是可以预先算好的，等到服务的时候，直接把结果调出来即可，而不需要做重复计算。

比如我们可以把北京市所有路口之间点到点的距离事先计算好，当一个人要找加油站时，距离的计算就不再需要实时地采用动态规划来计算了，而只要算一下从当前的位置出发到附近的几个路口的距离，再算一下某个加油站到它所在地附近路口的距离，由于各个路口点到点的距离都是事先计算好的，因此做几次简单的加法即可。这样一来，计算距离的时间就能省几十倍。这就是对上面的问题进行了**全局优化的好处。

我们有时候讲大数据思维，大数据很重要的一条就是不能像过去那样，将各个事件看成彼此独立的，分开来处理，而是要把所有数据集中起来，进行全局优化。
通过找最近的加油站这道面试题，我们可以在思维上得到下面这些启发：

1.不要做无用功。要通过少做事情，特别是少做不必要的事情来提高效率。很多时候，我们很忙，因为做的事情太多，如果这时能回到原点重新审视一下我们的目标，就会发现我们做了很多无用功。把那些无用功去掉，我们就比其他人进步快，产出高了。

2.很多事情都遵循同一个规律， 比如从锦标赛，到找加油站，到处理零售交易，都会用到二叉树，特别是它的一个子类——堆。这些问题，都可以被称为“等价的问题”。在这儿，我们再次看到等价性的重要性。需要强调的是，学习理论很重要。当然，在学习理论的时候，需要了解这个理论为什么会被提出，当时要解决的应用问题是什么，搞清楚这些，便可以一通百通。

3. 我们在解决问题时，很多时候不知不觉地做了一些主观假设，或者说自己给了自己一些前提条件。在上述问题中，我们在很长的时间里，都是假设找最近的加油站这件事，是为我这个人服务的，并没有考虑，这个假设不在题目中，是我们心中缺省默认的。因此我们不会去考虑为我服务和为你服务的关系，在做产品时则不应该有这样的主观假设，否则就把自己限制死了, 无法跳出我们的局限性，进行进一步优化了。

4. 最后，从这个例子你可能已经看出，好的面试官是不怕面试者刷题的，因为他总是可以一层层深入地问下去。而好的面试题不仅可以引导面试往深入进行，而且对从业者还有很深的启发意义。