如何设计一个地图功能，找到当前最近的加油站？

吴军老师的《硅谷来信》中的第080封信，讲了一道Google面试题。

 

题目如标题，主要考察两方面：

1、考察计算机科学的基本知识

2、看候选人分解问题、解决问题的能力

 

首先处理一个问题要先全面了解问题，否则答非所问或者没有体会出题人的考察点。我刚开始思考这道题，忽略掉了有点个关键点：

1、汽车是移动的，结果会不断更新，计算速度不能很慢。

2、这个产品不同的使用场景，对准确度接受度是不同的。如果两个加油站差200米，司机和行人对200米感受是不一样的。

3、汽车是有方向且移动的。汽车位置只有GPS定位，需要转换成街道地址的范围等。

4、距离的计算。在现实中两点之间的距离不是欧几里得直线距离，车辆不可能穿过建筑直行。两点之间的距离是很多距离片段的叠加，且两点之间每一段距离的线路有N多种组合，怎样找到最短的一条？可以使用动态规则方法找到最短路径。

 

找到所有加油站距离结果的列表之后，按照距离排序所有的加油站。另外需要考虑的几个问题：

1、排序复杂度。北京1000(n)个加油站，普通排序的算法复杂度n*log(n)。

2、计算量级。考虑汽车是移动的每分钟更新3到5次数据。北京有百万辆车在路上，可能有几千辆车在寻找加油站。

3、缩小问题范围。从问题出发了解到只要找到最近的几个加油站，距离比较远的加油站用户并不关心。所以没必要对那么多加油站距离结果进行排序。谈到二叉权一个特殊细类，即“堆”，这个数据结构可以做到只排出前几名，而不用管后面的，这个算法也叫做小规模的堆排序。

注：使用这种算法，计算第一名的复杂度是N，后面第二、第三名等的计算复杂度都是Log(n)。如果只要找到最近的10个加油站，计算的量级大约是1000左右（1000+x*10），这种算法也叫TopN算法。

 

结合真实场景，持续优化：

预先计算+全局优化：把北京所有路口之间点到点的距离事先计算好，当一个人要找加油站时，距离计算就变成汽车从当前的位置出发到附近的几个路口的距离，再算一下某个加油站到它所在地附近路口的距离，由于各个路口点到点的距离 都是事先计算好的，因此做几次加法就可以计算出结果。

 

作者总结了这道题可能带来的几点思维启发：

1、不要做无用功。

2、很多事情都遵循同一个规律。

学习理论（算法）很重要，同时要了解这个理论为什么会提出，解决的应用问题是什么，然后一通百通。

3、解决问题时，尽量避免主观假设。

加油站这道题，我们很长时间都是假设找加油站这件事，是为我个人服务的，并没有考虑，这个假设不在题目中。无法跳出我们的局限性，也就无法进一步优化了。