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

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

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

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

在正式解答这一类应用问题之前，可以谈谈不同场景下所需要考虑的因素。事实上，如果一个候选人一上来就将这个问题抽象化，并且解决了问题，有经验的考官最后会和面试者讨论各种应用场景下的变通，看看候选人只是刷题背答案，还是对具体问题有全面的思考。讲了考这道题的目的和通常的面试过程，我们接下来就来分析一下这个问题。我们以车载系统为例来讲解，这个问题我们需要做三步分解。

• 首先，我们需要搞清楚每一个加油站的位置和汽车现在的位置，最好同时也搞清楚行车方向。一般来讲，在遇到课堂上的书面考试题时，已知条件都会写得极清楚，不会多给，也不会少给。（现实世界里的情况，你就要能甄别出那些是真正有用的信息，哪些是迷惑的信息）。而面试的问题，已知条件有时需要和考官沟通确认。在这个问题中，加油站的位置是GPS的坐标，还是街道的名称和号码（a location, a string, or numbers?）。或者是什么地图中特定的坐标，这个要和考官沟通清楚。为了简单起见，我们不妨假设这些信息都有。至于汽车的位置，要更加复杂一点，因为它没有门牌号，只有GPS的定位，可能还需要转换成街道地址的范围（比如在北京朝阳区东方路1号到10号之间）。这些我们假定也都能办到。上述这些都算作确定了的已知条件，接下来的讨论就基于这些已知信息。
• 第二步，就要说说距离的计算了。在地面上行驶，两点之间的距离不是欧几里得直线距离，两点之间的距离其实是很多距离片段的叠加。在一个城市里，连通两个点之间每一段距离的路线可以有很多种，它们之间的组合呈指数上涨，也就是说，拐几道弯，隔了几个红绿灯，各种路线的组合很容易就有上千种，那么怎么找到上千种路线中最短的一条呢？在数学中有一种方法叫做动态规划（这就是善用工具的好例子, you have to expose yourself to the best things human beings ever created and try to combine them into your work.），可以完成这件事，在上千种组合中用很少的步骤（大约几十步）就能算出最短的路径。真正面试Google这样的公司时，面试官或许会考对方这个算法。这个算法我在《数学之美》一书中介绍了，这里就赘述了，非CS专业的人只要知道这个名称也就可以了，不必深究细节。总之，我们是有办法在地图上找到两个点之间最短的行车路径。接下来，我们就可以把汽车和城市里所有的加油站之间的距离列一个表，它的格式可以如下：
• • 加油站G1，距离D1；
  • 加油站G2，距离D2；
  • 加油站G3，距离D3；
  • ......
  • 加油站GN，距离DN.
• 第三步，就是按照距离排序，找出最近几个加油站。我们可以认为这是整个问题的子问题（To the stars下面是有很多很多个子问题的呀）。对于这个子问题，我遇到过的一些面试者会想到排序。排序当然是一个解决办法，但不是最佳的。对N个加油站根据距离排序大约需要 N * Log(N)的计算量，如果像北京这样的城市，有1000个加油站，LogN大约是10，也就是说，计算的复杂程度大约是N的10倍这个量级，也就是一万左右。这个计算量对于计算机来讲算不上什么，但是如果考虑到汽车在移动，每分钟应该更新三五次数据，北京市有上百万辆车在路上，可能有上千辆车在寻找加油站，这种计算对于地图这种产品，也是一个负担。因此，好的工程师在设计产品时，需要找到更好的办法，这就是我们今天要讲的重点。
• 改进，怎样找到更好的办法呢？我们需要回到问题的原点。上述通过排序找到最近的几个加油站的方法，其实做了很多无用功。原来的问题所要求的只是找到最近的几个加油站，提问题的人其实不关心那些距离比较远的加油站的距离和排序，如果把所有的加油站都按照距离排序，做的工作其实比要求的多，而多做的工作在产品中也没有用途。因此，提高产品的性能，其实就应该从避免做无用功入手。如何避免做无用功呢？回忆一下昨天说的锦标赛排序以及高盛的赛跑问题。锦标赛排序的好处是，它并非要等到所有的排序工作都做完的时候，才知道谁是第一名，而是可以排出前几名。事实上，在Binary Tree这种数据结构中，有一种更特殊的细类，被称为“堆”，用这种数据结构，就可以做到只排出前几名，而不用管后面的名次。因此我们不妨把这种新方法称为小规模的堆排序。如果只需要排出前K名，这种算法得到第一名的复杂度是N，而得到第二、第三第四名等等的复杂度都只有logN（有点迷惑诶），比对1000个加油站排序要快得多。如果我们只要找到最近的10个加油站，计算的量级大约是1000左右，比以前说的快速排序降低了10倍。10倍之差，在工程上显然是有意义的。如果N非常大，就更有意义了。比如说，淘宝要找到一年之中交易额最高的10个顾客，给予一些奖励。我们假设淘宝的顾客有5亿，那么这种采用堆排序的方法找到前十名的时间，可以比快速排序节省30倍的时间（如何计算出的呢？）。如果再稍微变通优化一下，则可以省下上百倍的时间。在大数据的很多应用中，我们通常指关心前几个，而不需要对所有的数据排序。因此，Google通过这道面试题，其实可以不断地追问，全面考察面试者的专业技能。
• （对比下自己上次的答案：）

到此，似乎这道面试题解决得很完美了，那么是否还能继续改进呢？答案是肯定的。我们在前面做分析时，其实不知不觉地做了一个假设，就是整个算法优化的过程是围绕着一个使用者的某一个次使用进行的。但在现实生活中，一个城市里（甚至一个国家），很多人会同时从不同的地方寻找加油站。类似地，同一个人，在不同时间，也会在某个地方开车时，寻找加油站。如果考虑到这个真是的应用场景应该是很多人不停地使用这个功能，那么很多计算其实都是可以预先算好的，等到服务的时候，直接把结果调出来即可，而不需要做重复计算。

比如，我们可以把北京市所有路口之间点到点的距离事先计算好，当一个人要找加油站时，距离的计算就不再需要实时地采用动态规划来计算了，而只要算一下从当前的位置出发到附近的几个路口的距离，再算一下某个加油站到它所在地附近路口的距离，由于各个路口点到点的距离都是事先计算好的，因此做几次简单的加法即可。这样一来，计算距离的时间就能省几十倍。这就是对上面的问题进行了全局优化的好处。我们有时候讲大数据思维，大数据很重要的一条就是不能像过去那样，将各个事件看成彼此独立的，分开来处理，而是要所有的数据集中起来，进行全局优化（卧槽，就是这个感觉！这个statement太牛逼了，so damn conclusive）。

这道找最近加油站的问题能在思维上得到什么启发呢？

• 1. 不要做无用功。（吴军老师不停的在强调少做事情，Jony Ive一句话让我真正理解了一个能力，少做事情的另一个意思是什么？专注。据我所知，还有谁在不停的强调少做事情？巴菲特、芒格、贝索斯、王兴、张小龙、乔布斯、一加手机的两位）要通过少做事情，特别是少做不必要的事情来提高效率。很多时候，我们很忙，因为做的事情太多，如果这时能回到原点重新审视一下我们的目标，就会发现我们做了很多无用功（除此之外，我还想到了什么呢？想到了俞军的“有效产品时”，罗胖提到的“刻意练习”，以及我观察日式剑道后创造的一个词“有效练习时”。为什么这三个点和少做事情有关系呢？简单地讲就是，没有经过大脑深入思考的努力是（此处加个副词：瞎几把）努力，只有经过大脑深度的思考、走出思维惯性的思考、走出舒适圈的思考的努力才能叫做有效。同时，也必须要有好老师好教练提供有效的适合自己的指导和及时的正向反馈。别整天傻不拉几的靠透支意志力的低级努力来感动和麻痹自己的大脑，让自己停止稍微深一点的质疑和思考。多累啊，自己也是人，别上来就送人头，以为只要一愤怒一咬牙一用劲，就能打败对手，多累啊）。把那些无用功去掉，我们就比其他人进步快，产出高了。
• 2. 很多事情都遵循同一个规律。比如从锦标赛，到加油站，到处理零售交易，都用用到Binary Tree，特别是它的一个子类 —— 堆。这些问题，都可以被称为“等价的问题”。在这，我们再次看到等价性的重要性。需要强调的是，学习理论很重要。当然，在学习理论的时候，需要了解这个理论为什么会被提出，当时要解决的应用问题时什么，搞清楚这些，便可以一通百通。（Go deeper, think deeper.）
• 3. 我们在解决问题时，很多时候不知不觉地做了一些主观假设，或者说自己给了自己一些前提条件。在上述问题中，我们在很长的时间里，都是在假设找最近的加州站这件事，是为我这个人服务的，并没有考虑这个假设不在题目中，是我们心中的default。因此我们不会去考虑为我服务和为你服务的关系，但在做产品时则不应该有这样的主观假设，否则就把自己限制死了，无法跳出我们的局限性，进行进一步优化了。
• 4. 好的面试官是不怕面试者刷题的，因为他总是可以一层层深入地问下去。而好的面试题不仅可以引导面试深入进行，而且对从业者还有很深的启发意义。

​