吳軍

我一直在強(qiáng)調(diào)人要少做事情，因為提高效率的根本在于少做事情，事實(shí)上對計算機(jī)來講也是如此。今天我們再講解一道Google面試題，你會從中進(jìn)一步理解為什么效率的來源在于少做無用功了。

這道題是我最愛考面試人的一道題，因為它說起來簡單，但一大半的面試者做不對，而且對那一小半答對了的人，我還可以不斷追問下去，把9成的面試者難在某個地方。說起來難吧，沒有計算機(jī)背景知識的人也能一聽就懂。這道題是這么說的：

假如有一個巨大的數(shù)組（你可以理解成一串?dāng)?shù)字），如何用最有效的方法找到它的中值？

題目本身就這么簡單的一句話。由于它看上去太簡單了，以至于我每次出這道題之前總要說幾句話做鋪墊，“我們今天從一道簡單的題開始，算是熱熱身，你看好不好？”這樣，面試者不會覺得被一道簡單的題目羞辱了。不過請注意這里有好幾處坑。我常講，很多時候做不出題是因為根本沒有讀懂題，理解題，匆匆忙忙就做了，這比不會做給人的印象還糟糕十倍。

這道題里的第一個坑是要尋找中值，而不是平均值。大約有10%－20%的人會聽題不仔細(xì)，或者自己搞不懂中值和平均值的區(qū)別，就匆匆忙忙求平均值了。

那么什么是中值？如果有三個數(shù)1，2，100，那么中值是2，而平均值則是34左右。在很多場合，中值比平均值更有意義。比如考察一個國家個人的收入。一個好的面試者，如果不確定什么是中值，或者說不確定我所要問的問題，他會先確認(rèn)一下中值的含義，并且自己舉出類似上面那樣的例子。

這樣有兩個好處：其一，即使他沒有回答上來，至少說明聽懂題目了，并且了解中值的概念；其二，他是一個合格的溝通者，在工作中遇到不確定的要求，會搞清楚以后再動手，而不是一個匆匆忙忙把事情搞砸了的人。

第二個坑是“巨大”這個字眼。當(dāng)一個題目的規(guī)模巨大時，適用于小規(guī)模的很多方法就不適用了，有工程經(jīng)驗的人都懂得這一點(diǎn)，而很多剛從學(xué)校走出來的學(xué)生則缺乏這種概念。

第三個坑是“最有效”這三個字。也就是說，找到中值的方法可以有很多種，找到一個好的還不算數(shù)，需要找到最好的。

當(dāng)然，聰明一點(diǎn)的面試者還會先搞清楚，“最有效”這三個字是指時間上最快，還是最節(jié)省空間。如果他這樣反問，也說明他有較好的工程素養(yǎng)和溝通技巧。不過在這道題目中，我們追求的是時間上的有效，也就是要速度快。

這個問題還有其他的坑，因為比較復(fù)雜，我就省略了。

水平不夠又缺乏面試經(jīng)驗的人，會馬上提出先排序，再找到中間那個數(shù)字的方法。這樣的回答比較糟糕。首先，他掉進(jìn)了題目中第二和第三個坑。排序是一種解決辦法，但是絕不是最有效的，而且當(dāng)面臨“巨大的數(shù)組”時，為了找到一個數(shù)排序，顯然做了太多的無用功。其次，他沒有體會到考他這道題背后的目的。作為Google這樣的公司，面試題不可能太容易，排序這種想法，是個人都能想到?？妓@道題，一定是因為對于Google來講，要處理的數(shù)據(jù)量太大，必須找到比排序更好的方法。

同樣是找不到更好方法，但是善于溝通的人會這么講：

我知道，你考我這道題不是要尋找排序這樣的方法，雖然排序也能解決問題，你能否給我點(diǎn)時間，讓我想想更好的方法？

這樣的回答有兩個好處，首先是告訴對方他知道考這道題的目的，同時自己懂得排序，這是一個好的溝通者。其次，他給自己贏得了時間。當(dāng)然，如果過了幾分鐘他還是想不出來，有經(jīng)驗的面試者會說，能否給我點(diǎn)提示呢？在工作中，請求幫助永遠(yuǎn)比自己悶頭做不出來要好。在面試時，大約有20%的人在思考了一段時間后，能夠想出更好的辦法。

在這個問題上，一些候選人會想出一個比排序更好一點(diǎn)的方法，那就是我們前面提到的“N個加油站中找到K個距離最近的加油站”的那個方法。這里，只要把K設(shè)置成N的一半即可。忘了那一期內(nèi)容的朋友，可以回頭再讀讀那封來信，鏈接在信的底部。這種方法只對數(shù)值小的一半進(jìn)行了排序，因此大約可以省一半時間。但是正如我們在課程一開始講的，對于計算機(jī)科學(xué)來講，省一半時間意義不是很大，我們追求的是更高的效率。因此，我們還要找更好的方法。

上述方法為什么效率不高呢？其根本的原因是做了太多的無用功！這道題只要求找到中值，至于那些大于中值的數(shù)字彼此的關(guān)系是什么，小于中值的數(shù)字相對的次序是什么，我們其實(shí)不用關(guān)心。排序的方法，把這些工作也順帶做了，顯然多做了很多事情，自然效率高不起來。因此，要想找到好方法，一定要避免排序。

當(dāng)然，你可能會問了，如果不排序，又怎么知道誰是中值？這確實(shí)是一個好問題。在進(jìn)一步講解我們的方法之前，我們舉一個具體的例子。假如數(shù)組中的數(shù)字是：

1，－5，3，7，1000，2，－10

排好序后是這樣的：

－10，－5，1，2，3，7，1000

這個序列可以看得一目了然，2就是中值，因為比2小的數(shù)字都在它的左邊，有三個，比它大的數(shù)字都在右邊，恰好也是三個。但是，如果我們把這七個數(shù)字按照下面的方式排列：

－5，1，－10，2，1000，3，7

我們會發(fā)現(xiàn)，小于2的在左邊，有三個，大于2的在右邊，也是三個，因此也能得到2是中值的結(jié)論。所不同的是，整個數(shù)組并沒有從小到大排列。其實(shí)，只要我們能夠把數(shù)組重新整理成后一種樣子，對于找中值是足夠的。

那么怎么不經(jīng)過排序，讓小的數(shù)字都到左邊，大的數(shù)字都到右邊呢？講起來也很簡單。我們可以從數(shù)組中隨便找一個數(shù)字，讓它和數(shù)組中每一個數(shù)字去比較大小。如果比它小，就放在左邊，如果比它大就放在右邊。這個過程被稱為劃分（Partition）。

當(dāng)然，除非你的運(yùn)氣特別好，第一次就隨機(jī)挑上了中值，否則劃分的結(jié)果肯定一邊多一些，一邊少一些。比如有100個數(shù)字，第一次劃分之后，大的一邊有60個，小的一邊有40個。很顯然，中值一定是在大的一邊，也就是有60個數(shù)字的一邊，而不可能在小的一邊。因此第二次我們只要在大的一邊隨機(jī)選取一個數(shù)字，再做一次劃分，看看是否平衡就可以了。

需要強(qiáng)調(diào)的是，第二次分割要考慮的數(shù)字比第一次少了一小半，如果還沒找到，第三次劃分的范圍又縮小了一小半，直到找到為止?？梢宰C明，這種方法通常復(fù)雜度非常低，大約只相當(dāng)于把整個數(shù)組掃描了三四遍而已。

如果我們要尋找10億個數(shù)字的中值，采用排序的方法大約需要1萬億次計算，而采用這種劃分的方法大約只需要30億次計算，時間相差300倍。這里面效率的提高完全來自于少做了很多無用功。

講到這里，你已經(jīng)理解了為什么Google會問這個問題。Google這樣的公司，每天都要處理海量的數(shù)據(jù)，所使用的方法必須是最優(yōu)化的，否則很輕易地就浪費(fèi)掉上百倍資源。

如果你還記得我在之前講過的快速排序算法，對今天的內(nèi)容是否有似曾相識的感覺呢？事實(shí)上今天講的方法和快速排序的方法非常相似，都是用一個隨機(jī)的數(shù)值對數(shù)組進(jìn)行劃分。如果一個候選人掌握了快速排序思想的精髓，而不僅僅是背下來那個算法，這道題應(yīng)該能很好地解決。實(shí)際上，像Google這樣公司的面試，很少會直接考書本中的內(nèi)容，但是通過一個實(shí)際問題很容易考察出求職者能否靈活運(yùn)用所學(xué)知識。

從這個例子中我們可以總結(jié)出如下三點(diǎn)經(jīng)驗：

1. 少做事是提高效率的關(guān)鍵。

2. 一流人才和二流、三流的差別在于，后者雖然也能完成任務(wù)，但是未必能把事情做到最好，而一流的人總是能找到在當(dāng)下最好的方法。而一種方法的好和壞，可以差出幾十、上百倍的效率。這就是我講的工程師水平差一級，貢獻(xiàn)可以差出一個數(shù)量級的原因。

3. 對所學(xué)內(nèi)容掌握得好壞高低，通常不是靠直接考核那些內(nèi)容能知道的，而是要看能否運(yùn)用所學(xué)。只有會用了，才是真的學(xué)到手了。

這個問題其實(shí)還只是一連串問題的開始。如果候選人很快答上了這個問題，我還會讓他證明為什么上述方法的計算復(fù)雜度只相當(dāng)于把數(shù)組掃描幾遍，最好的情況和最壞的情況會是什么樣，什么時候會發(fā)生等等。此外，當(dāng)數(shù)組特別特別大，以至于一臺服務(wù)器都存不下了，應(yīng)該怎么處理？

因此，一個好的求職者一定是能夠活學(xué)活用知識的，而不是簡單背一下答案。希望這些面試的經(jīng)驗也對你有所啟發(fā)。