今天我們講解一個 Google 的面試題，假如你負責手機或者車載地圖這個產品，如何設計這樣一個功能，即找到離當前位置最近的幾個加油站？這樣的面試問題一來是考察計算機科學的基本知識，二來是看候選人分解問題、 解決問題的能力。

 

在解題之前，我們先要把問題理解清楚， 而不是一上來就盲目地做。很多人面試失敗的主要原因就是答非所問，或者沒有體會出題人的考察點。

 

對於這個問題，如果是車載的地圖，需要考慮到汽車是移動的，結果會不斷更新，因此那些速度很慢的算法就不適合這個場景了。其次，結果的刷新記錄也不必太快，以免用戶覺得結果太不確定。事實上，如果有兩個加油站，一個距離 2.5 公里，一個 2.3 公里，對開車的人來講差別不是很大，更何況路況的擁堵情況可能讓這 200 米的差距變得越發不重要。但是，如果是行人在手機上尋找最近的 7-11 便利店，200 米的差距就有意義了，而且通常步行不會擁堵，因此少走兩百米就省兩百米。

 

在正式解答這一類應用問題之前，可以談談不同場景下所需要考慮的因素。事實上，如果一個候選人一上來就將這個問題抽象化，並且解決了問題，有經驗的考官最後會和面試者討論各種應用場景下的變通，看看候選人只是刷題背答案，還是對具體問題有全面的思考。有些時候，一些候選人覺得對方考自己的問題都答上來了，但是沒有被錄取，其實那些看似輕鬆隨意的討論，也是考官考察候選人，獲取信息的環節，不能輕視。

 

講完了考這道題的目的和通常的面試過程，我們接下來就來分析一下這道題，我們以車載系統為例來講解，這個問題我們需要做三步分解。

 

1. 首先，我們需要搞清楚每一個加油站的位置和汽車現在的位置，最好同時也搞清楚行車方向。一般來講，在遇到課堂上的書面考試題時，已知條件都會寫得極清楚，不會多給，也不會少給。而面試的問題，已知條件有時需要和考官溝通確認。在這個問題中，加油站的位置是 GPS 的坐標，還是街道的名稱和號碼，或者是什麼地圖中特定的坐標，這個要和考官溝通清楚。

 

為了簡單起見，我們不妨假設這些信息都有。至於汽車的位置，要更加複雜一點，因為它沒有門牌號，只有 GPS 的定位，可能還需要轉換成街道地址的範圍 ( 比如在北京朝陽區東方路1號到10號之間 )。這些我們假定也都能辦到。上述這些都算作確定了的已知條件，接下來的討論就基於這些已知信息。

 

2. 第二步，就要說說距離的計算了。在地面上行駛，兩點之間的距離不是歐幾里得 ( Euclides  ) 直線距離，因為車輛不可能穿過建築直行。因此，兩點之間的距離其實是很多距離片段的疊加。在一個城市裡，連通兩個點之間每一段距離的線路可以有很多種，它們之間的組合呈指數上漲，也就是說，拐幾道彎，隔了幾個紅綠燈， 各種路線的組合很容易就有上千種，那麼怎麼找到上千種路線中最短的一條呢？

 

在數學中有一種方法叫做動態規劃，可以完成這件事，在上千種組合中用很少的步驟（大約幾十步）就能算出最短的路徑。真正面試Google這樣的公司時，面試官或許會考對方這個算法。這個算法我在《數學之美》一書中介紹了，這裡就不贅述了，非計算機專業的朋友只要知道這個名稱也就可以了，不必深究細節。

 

總之，我們是有辦法在地圖上找到兩個點之間最短的行車路徑。接下來，我們就可以把汽車和城市裡所有的加油站之間的距離列一個表，它的格式可以如下：

•  

  • 加油站 G1，距離 D1；

  • 加油站 G2，距離 D2；

  • ……

  • 加油站 GN，距離 DN；

 

到此，第二步算是完成了。

 

3. 接下來的第三步，就是要按照距離排序， 找出最近的幾個加油站。我們可以認為這是整個問題的子問題。

 

對於這個子問題，我遇到過的一些面試者會想到排序。排序當然是一個解決辦法，但不是最佳的。對 N 個加油站根據距離排序大約需要 N 乘以 LogN 的計算量，如果像北京這樣的城市，有 1,000 個加油站，LogN大約是10。也就是說，計算的複雜度大約是 N 的10倍這個量級，也就是一萬左右。這個計算量對計算機來講算不上什麼，但是如果考慮到汽車在移動， 每分鐘應該更新三五次數據，北京市有上百萬輛車在路上，可能有上千輛車在尋找加油站， 這種計算對於地圖這種產品，也是一個負擔。因此，好的工程師在設計產品時，需要找到更好的方法．這就是我們今天要講的重點。

 

怎樣找到更好的方法？我們需要回到問題的原點。上述通過排序找到最近的幾個加油站的方法，其實做了很多無用功。原來的問題所要求的只是找到最近的幾個加油站，提問題的人其實不關心那些距離比較遠的加油站的距離和排序，如果把所有的加油站都按照距離排序，做的工作其實比要求的多，而多做的工作在產品中也沒有用途。因此，提高產品的性能， 其實就應該從避免做無用功入手。

 

怎麼才能避免做無用功呢？我們不妨回憶一下昨天說的錦標賽排序以及高盛的賽跑問題。錦標賽排序的好處是，它並非要等到所有的排序工作都做完的時候，才知道誰是第一名，而是可以只排出前幾名。

 

事實上，在二元樹這種數據結構中，有一種更特殊的細類，被稱為“堆”，用這種數據結構，就可以做到只排出前幾名，而不用管後面的名次。因此我們不妨把這種新方法稱為小規模的堆排序。如果只需要排出前 K 名，這種算法得到第一名的複雜度是N，而得到第二、第三、第四名等等的複雜度都只有 Log N，比對 1,000 個加油站排序要快得多。如果我們只要找到最近的10個加油站，計算的量級大約是 1,000 左右，比以前說的快速排序降低了10 倍。

 

10 倍之差，在工程上顯然有意義。如果 N 非常大，就更有意義了。比如說，淘寶要找到一年之中交易額最高的 10 個顧客，給予一些獎勵。我們假設淘寶的顧客有 5 億，那麼這種採用堆排序的方法找到前十名的時間，可以比快速排序節省 30 倍的時間。如果再稍微變通優化一下，則可以省上百倍的時間。在大數據的很多應用中，我們通常只關心前幾個，而不需要對所有的數據排序。因此，Google 通過這道面試題，其實可以不斷地往下追問，全面考察面試者的專業技能。

 

到此，似乎這道面試題解決得很完美了， 那麼是否還能繼續改進呢？答案是肯定的。

 

我們在前面做分析時，其實不知不覺地做了一個假設，就是整個算法優化的過程是圍繞著一個使用者的某一次使用進行的。但在現實生活中，一個城市裡（甚至一個國家），很多人會同時從不同的地方在尋找加油站。類似地，同一個人，在不同時間，也會在某個地方開車時，尋找加油站。

 

如果考慮到這個真實的應用場景應該是很多人不停地使用這個功能，那麼很多計算其實都是可以預先算好的，等到服務的時候，直接把結果調出來即可，而不需要做重複計算。

 

比如我們可以把北京市所有路口之間點到點的距離事先計算好，當一個人要找加油站時，距離的計算就不再需要實時地採用動態規劃來計算了，而只要算一下從當前的位置出發到附近的幾個路口的距離，再算一下某個加油站到它所在地附近路口的距離，由於各個路口點到點的距離都是事先計算好的，因此做幾次簡單的加法即可。這樣一來，計算距離的時間就能省幾十倍。這就是對上面的問題進行了全局優化的好處。

 

我們有時候講大數據思維，大數據很重要的一條就是不能像過去那樣，將各個事件看成彼此獨立的，分開來處理，而是要把所有數據集中起來：進行全局優化。

 

通過找最近的加油站這道面試題，我們可以在思維上得到下面這些啟發：

 

1. 不要做無用功。

 

要通過少做事情，特別是少做不必要的事情來提高效率。很多時候，我們很忙，因為做的事情太多，如果這時能回到原點重新審視一下我們的目標，就會發現我們做了很多無用功。把那些無用功去掉， 我們就比其他人進步快，產出高了。

 

2. 很多事情都遵循同一個規律。

 

比如從錦標賽，到找加油站，到處理零售交易，都會用到二元樹，特別是它的一個子類一堆。這些問題，都可以被稱為“等價的問題'，。在這兒，我們再次看到等價性的重要性。需要強調的是，學習理論很重要。當然，在學習理論的時候，需要了解這個理論為什麼會被提出， 當時要解決的應用問題是什麼，搞清楚這些， 便可以一通百通。

 

3. 我們在解決問題時，很多時候不知不覺地做了一些主觀假設，或者說自己給了自己一些前提條件。

 

在上述問題中，我們在很長的時間裡，都是假設找最近的加油站這件事，是為我這個人服務的，並沒有考慮，這個假設不在題目中，是我們心中缺省默認的。因此我們不會去考慮為我服務和為你服務的關係，在做產品時則不應該有這樣的主觀假設，否則就把自己限制死了，無法跳出我們的局限性，進行進一步優化了。

 

4. 最後，從這個例子你可能已經看出， 好的面試官是不怕面試者刷題的，因為他總是可以一層層深入地問下去。而好的面試題不僅可以引導面試往深入進行，而且對從業者還有很深的啟發意義。

 

希望這些經驗比這道面試問題本身能給你帶來更多的啟發。

 

最後邀請你思考：能否就提高效率就是要少做無用功，發表你的看法？

 

 

來源：《吳軍-如何設計一個地圖功能，找到離當前最近的加油站？》