今天我们讲解一个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. 最后,从这个例子你可能已经看出,好的面试官是不怕面试者刷题的,因为他总是可以一层层深入地问下去。而好的面试题不仅可以引导面试往深入进行,而且对从业者还有很深的启发意义。
本文转载自:无
作者:无
原文链接:无
推荐阅读