吳軍
我一直在強(qiáng)調(diào)人要少做事情，因?yàn)樘岣咝实母驹谟谏僮鍪虑椋聦?shí)上對(duì)計(jì)算機(jī)來(lái)講也是如此。今天我們?cè)僦v解一道Google面試題，你會(huì)從中進(jìn)一步理解為什么效率的來(lái)源在于少做無(wú)用功了。
這道題是我最?lèi)?ài)考面試人的一道題，因?yàn)樗f(shuō)起來(lái)簡(jiǎn)單，但一大半的面試者做不對(duì)，而且對(duì)那一小半答對(duì)了的人，我還可以不斷追問(wèn)下去，把9成的面試者難在某個(gè)地方。說(shuō)起來(lái)難吧，沒(méi)有計(jì)算機(jī)背景知識(shí)的人也能一聽(tīng)就懂。這道題是這么說(shuō)的：
假如有一個(gè)巨大的數(shù)組（你可以理解成一串?dāng)?shù)字），如何用最有效的方法找到它的中值？
題目本身就這么簡(jiǎn)單的一句話。由于它看上去太簡(jiǎn)單了，以至于我每次出這道題之前總要說(shuō)幾句話做鋪墊，“我們今天從一道簡(jiǎn)單的題開(kāi)始，算是熱熱身，你看好不好？”這樣，面試者不會(huì)覺(jué)得被一道簡(jiǎn)單的題目羞辱了。不過(guò)請(qǐng)注意這里有好幾處坑。我常講，很多時(shí)候做不出題是因?yàn)楦緵](méi)有讀懂題，理解題，匆匆忙忙就做了，這比不會(huì)做給人的印象還糟糕十倍。
這道題里的第一個(gè)坑是要尋找中值，而不是平均值。大約有10%－20%的人會(huì)聽(tīng)題不仔細(xì)，或者自己搞不懂中值和平均值的區(qū)別，就匆匆忙忙求平均值了。
那么什么是中值？如果有三個(gè)數(shù)1，2，100，那么中值是2，而平均值則是34左右。在很多場(chǎng)合，中值比平均值更有意義。比如考察一個(gè)國(guó)家個(gè)人的收入。一個(gè)好的面試者，如果不確定什么是中值，或者說(shuō)不確定我所要問(wèn)的問(wèn)題，他會(huì)先確認(rèn)一下中值的含義，并且自己舉出類(lèi)似上面那樣的例子。
這樣有兩個(gè)好處：其一，即使他沒(méi)有回答上來(lái)，至少說(shuō)明聽(tīng)懂題目了，并且了解中值的概念；其二，他是一個(gè)合格的溝通者，在工作中遇到不確定的要求，會(huì)搞清楚以后再動(dòng)手，而不是一個(gè)匆匆忙忙把事情搞砸了的人。
第二個(gè)坑是“巨大”這個(gè)字眼。當(dāng)一個(gè)題目的規(guī)模巨大時(shí)，適用于小規(guī)模的很多方法就不適用了，有工程經(jīng)驗(yàn)的人都懂得這一點(diǎn)，而很多剛從學(xué)校走出來(lái)的學(xué)生則缺乏這種概念。
第三個(gè)坑是“最有效”這三個(gè)字。也就是說(shuō)，找到中值的方法可以有很多種，找到一個(gè)好的還不算數(shù)，需要找到最好的。
當(dāng)然，聰明一點(diǎn)的面試者還會(huì)先搞清楚，“最有效”這三個(gè)字是指時(shí)間上最快，還是最節(jié)省空間。如果他這樣反問(wèn)，也說(shuō)明他有較好的工程素養(yǎng)和溝通技巧。不過(guò)在這道題目中，我們追求的是時(shí)間上的有效，也就是要速度快。
這個(gè)問(wèn)題還有其他的坑，因?yàn)楸容^復(fù)雜，我就省略了。
水平不夠又缺乏面試經(jīng)驗(yàn)的人，會(huì)馬上提出先排序，再找到中間那個(gè)數(shù)字的方法。這樣的回答比較糟糕。首先，他掉進(jìn)了題目中第二和第三個(gè)坑。排序是一種解決辦法，但是絕不是最有效的，而且當(dāng)面臨“巨大的數(shù)組”時(shí)，為了找到一個(gè)數(shù)排序，顯然做了太多的無(wú)用功。其次，他沒(méi)有體會(huì)到考他這道題背后的目的。作為Google這樣的公司，面試題不可能太容易，排序這種想法，是個(gè)人都能想到?？妓@道題，一定是因?yàn)閷?duì)于Google來(lái)講，要處理的數(shù)據(jù)量太大，必須找到比排序更好的方法。
同樣是找不到更好方法，但是善于溝通的人會(huì)這么講：
我知道，你考我這道題不是要尋找排序這樣的方法，雖然排序也能解決問(wèn)題，你能否給我點(diǎn)時(shí)間，讓我想想更好的方法？
這樣的回答有兩個(gè)好處，首先是告訴對(duì)方他知道考這道題的目的，同時(shí)自己懂得排序，這是一個(gè)好的溝通者。其次，他給自己贏得了時(shí)間。當(dāng)然，如果過(guò)了幾分鐘他還是想不出來(lái)，有經(jīng)驗(yàn)的面試者會(huì)說(shuō)，能否給我點(diǎn)提示呢？在工作中，請(qǐng)求幫助永遠(yuǎn)比自己悶頭做不出來(lái)要好。在面試時(shí)，大約有20%的人在思考了一段時(shí)間后，能夠想出更好的辦法。
在這個(gè)問(wèn)題上，一些候選人會(huì)想出一個(gè)比排序更好一點(diǎn)的方法，那就是我們前面提到的“N個(gè)加油站中找到K個(gè)距離最近的加油站”的那個(gè)方法。這里，只要把K設(shè)置成N的一半即可。忘了那一期內(nèi)容的朋友，可以回頭再讀讀那封來(lái)信，鏈接在信的底部。這種方法只對(duì)數(shù)值小的一半進(jìn)行了排序，因此大約可以省一半時(shí)間。但是正如我們?cè)谡n程一開(kāi)始講的，對(duì)于計(jì)算機(jī)科學(xué)來(lái)講，省一半時(shí)間意義不是很大，我們追求的是更高的效率。因此，我們還要找更好的方法。
上述方法為什么效率不高呢？其根本的原因是做了太多的無(wú)用功！這道題只要求找到中值，至于那些大于中值的數(shù)字彼此的關(guān)系是什么，小于中值的數(shù)字相對(duì)的次序是什么，我們其實(shí)不用關(guān)心。排序的方法，把這些工作也順帶做了，顯然多做了很多事情，自然效率高不起來(lái)。因此，要想找到好方法，一定要避免排序。
當(dāng)然，你可能會(huì)問(wèn)了，如果不排序，又怎么知道誰(shuí)是中值？這確實(shí)是一個(gè)好問(wèn)題。在進(jìn)一步講解我們的方法之前，我們舉一個(gè)具體的例子。假如數(shù)組中的數(shù)字是：
1，－5，3，7，1000，2，－10
排好序后是這樣的：
－10，－5，1，2，3，7，1000
這個(gè)序列可以看得一目了然，2就是中值，因?yàn)楸?小的數(shù)字都在它的左邊，有三個(gè)，比它大的數(shù)字都在右邊，恰好也是三個(gè)。但是，如果我們把這七個(gè)數(shù)字按照下面的方式排列：
－5，1，－10，2，1000，3，7
我們會(huì)發(fā)現(xiàn)，小于2的在左邊，有三個(gè)，大于2的在右邊，也是三個(gè)，因此也能得到2是中值的結(jié)論。所不同的是，整個(gè)數(shù)組并沒(méi)有從小到大排列。其實(shí)，只要我們能夠把數(shù)組重新整理成后一種樣子，對(duì)于找中值是足夠的。
那么怎么不經(jīng)過(guò)排序，讓小的數(shù)字都到左邊，大的數(shù)字都到右邊呢？講起來(lái)也很簡(jiǎn)單。我們可以從數(shù)組中隨便找一個(gè)數(shù)字，讓它和數(shù)組中每一個(gè)數(shù)字去比較大小。如果比它小，就放在左邊，如果比它大就放在右邊。這個(gè)過(guò)程被稱(chēng)為劃分（Partition）。
當(dāng)然，除非你的運(yùn)氣特別好，第一次就隨機(jī)挑上了中值，否則劃分的結(jié)果肯定一邊多一些，一邊少一些。比如有100個(gè)數(shù)字，第一次劃分之后，大的一邊有60個(gè)，小的一邊有40個(gè)。很顯然，中值一定是在大的一邊，也就是有60個(gè)數(shù)字的一邊，而不可能在小的一邊。因此第二次我們只要在大的一邊隨機(jī)選取一個(gè)數(shù)字，再做一次劃分，看看是否平衡就可以了。
需要強(qiáng)調(diào)的是，第二次分割要考慮的數(shù)字比第一次少了一小半，如果還沒(méi)找到，第三次劃分的范圍又縮小了一小半，直到找到為止。可以證明，這種方法通常復(fù)雜度非常低，大約只相當(dāng)于把整個(gè)數(shù)組掃描了三四遍而已。
如果我們要尋找10億個(gè)數(shù)字的中值，采用排序的方法大約需要1萬(wàn)億次計(jì)算，而采用這種劃分的方法大約只需要30億次計(jì)算，時(shí)間相差300倍。這里面效率的提高完全來(lái)自于少做了很多無(wú)用功。
講到這里，你已經(jīng)理解了為什么Google會(huì)問(wèn)這個(gè)問(wèn)題。Google這樣的公司，每天都要處理海量的數(shù)據(jù)，所使用的方法必須是最優(yōu)化的，否則很輕易地就浪費(fèi)掉上百倍資源。
如果你還記得我在之前講過(guò)的快速排序算法，對(duì)今天的內(nèi)容是否有似曾相識(shí)的感覺(jué)呢？事實(shí)上今天講的方法和快速排序的方法非常相似，都是用一個(gè)隨機(jī)的數(shù)值對(duì)數(shù)組進(jìn)行劃分。如果一個(gè)候選人掌握了快速排序思想的精髓，而不僅僅是背下來(lái)那個(gè)算法，這道題應(yīng)該能很好地解決。實(shí)際上，像Google這樣公司的面試，很少會(huì)直接考書(shū)本中的內(nèi)容，但是通過(guò)一個(gè)實(shí)際問(wèn)題很容易考察出求職者能否靈活運(yùn)用所學(xué)知識(shí)。
從這個(gè)例子中我們可以總結(jié)出如下三點(diǎn)經(jīng)驗(yàn)：
1. 少做事是提高效率的關(guān)鍵。
2. 一流人才和二流、三流的差別在于，后者雖然也能完成任務(wù)，但是未必能把事情做到最好，而一流的人總是能找到在當(dāng)下最好的方法。而一種方法的好和壞，可以差出幾十、上百倍的效率。這就是我講的工程師水平差一級(jí)，貢獻(xiàn)可以差出一個(gè)數(shù)量級(jí)的原因。
3. 對(duì)所學(xué)內(nèi)容掌握得好壞高低，通常不是靠直接考核那些內(nèi)容能知道的，而是要看能否運(yùn)用所學(xué)。只有會(huì)用了，才是真的學(xué)到手了。
這個(gè)問(wèn)題其實(shí)還只是一連串問(wèn)題的開(kāi)始。如果候選人很快答上了這個(gè)問(wèn)題，我還會(huì)讓他證明為什么上述方法的計(jì)算復(fù)雜度只相當(dāng)于把數(shù)組掃描幾遍，最好的情況和最壞的情況會(huì)是什么樣，什么時(shí)候會(huì)發(fā)生等等。此外，當(dāng)數(shù)組特別特別大，以至于一臺(tái)服務(wù)器都存不下了，應(yīng)該怎么處理？
因此，一個(gè)好的求職者一定是能夠活學(xué)活用知識(shí)的，而不是簡(jiǎn)單背一下答案。希望這些面試的經(jīng)驗(yàn)也對(duì)你有所啟發(fā)。
