一個有趣的谷歌面試題

4 人贊了文章

今天早上，聽了吳軍老師的矽谷來信，講了一道谷歌的面試題，覺得挺有意思，分享一下。

題目是：給你2個一模一樣的玻璃球，這兩個球如果從一定高度掉落到地上會摔碎，當然，如果從這個高度以下往下扔，怎麼都不會碎，超過這個高度就肯定一次摔碎了。現在已知這個恰好摔碎的高度範圍在一層到100層之間，如何用最少的試驗次數，用這2個玻璃球測試出玻璃球恰好摔碎的樓高。

吳軍老師說，如果你稍微學過點計算機，很可能就會第一時間想到二分發，從50層開始扔，但再仔細想想，就會發現這明顯不對的，比如你隨便嘗試幾下，每20層仍一次，次數就明顯比50層的少，那麼問題來了，我總不能一個一個嘗試吧，怎樣的組合才是最優解呢？這個時候，數學的威力就顯示出來了。

首先，分解問題，條件是2個玻璃球和100層樓，問題是最少次數測出摔碎高度。很明顯，2個玻璃球，就是第一個玻璃球肯定要碎，用它的犧牲換來一個範圍，第二個玻璃球在這個範圍內依次遍歷，最終把第一個玻璃球的測試次數和第二個玻璃球的測試次數相加，得到一個數，如此循環反覆，從2到50，會得49個數，尋找那個最小的就ok了。

我的第一反應是，把整個過程變成函數，求極值，第一個球做範圍查找，我們設為x，即以X為間隔，進行測試，比如x=20的意思就是每隔20層仍一次球，最多仍5次，然後，第一個球碎了之後，用第二個球在這個20的範圍內進行遍歷，具體到公式就是，第一個球的測試次數：100/x，第二個球的次數：x，2次合起來的次數為f(x)=100/x +x, （x取值2-50） 求f(x)的最小值，這樣就轉化為純計算問題，計算如下：

一階導數f(x)=-100/x^2+1

二階導數f(x)=200/x^3,

由於50>x>2，則f(x)>0, 說明函數有最小值

開始計算吧，讓f(x)=0,就可以求出最小值了。

100/x^2=1

x^2=100

x=10

即第一個球每隔10層仍一次，舉例，假設47層為摔碎高度，第一個球扔到第5次時摔碎，範圍劃定為41-50之間，第二個球從41開始一層一層的測，測到第七次摔碎，則5+7=12，最終12次測得摔碎高度，並且這12次是最小測試次數。

但是，接下來吳軍老師又說到了用3個球來測的情況，我突然發現，這個函數不太好寫了，因為出現了2個變數，計算複雜度增加了，這就表明方法有問題，適用性不強，一定有更好的方法。

這個更好的方法就是高中數學中的n個數的算術平均數大於等於幾何平均數的定理，即(x1+x2+…xn)/n>=(x1*x2*…xn)^(1/n)，當x1*x2*…xn為定值時，x1+x2+…xn有最小值，當x1=x2=…xn時，x1+x2+…xn為最小值，這個值就是(x1*x2*…xn)^(1/n)。就這個定理，可能很多人都忘記了，我查了一下，證明很複雜，不用仔細研究，記下結論就行，畢竟站在巨人的肩膀上才能看的更遠，重複造輪子沒必要。有了這個定理，問題一下就簡單很多了，我們看看3個球的情況，假設第一個球測試範圍為a，第二個球測試範圍為b，則第一個球測試次數為100/a，第二個球測試次數為a/b，第三個球測試次數為b，則100/a * a/b* b=100，也就是說，三次測試數量乘積為定值100，根據定理，如果想讓3次測試數量的和為最小，那就讓三次測試次數都相等，最小值為他們的幾何平均數，即100^(1/3)~=4.64，意思就是每個球最多測4.64次，我們算一下，第一個球測4.64次，用100/4.64~=21.55，四捨五入為22，第一個球我們每隔22層就仍一次，第二個球用22/4.64~=4.7，四捨五入為5，即在22這個範圍內，每隔5層仍一次，第三個球我們在5這個範圍內依次遍歷就可以了。

舉個例子，還是假設為47層為摔碎層，3個球的情況下，第一個球每隔22層仍一次，需要仍到第3次才會碎，確定範圍為45-66，接著第二個球，每隔5層仍一次，需要仍1次，確定範圍為45-50，第3個球從45開始測，扔到第3次出結果，總共3+1+3=7次。

那麼我們再引申一下，n個球的情況如何呢，是100^(1/n)嗎，如果不限量供應玻璃球，幾個球是最優的呢？計算機科學裡面有個二分查找，是查找有序數列的最優演算法，應用過來，最多也就是log2(100)次，也就是7個球測7次必出結果，所以，當n>7的時候，多餘的球也就沒有意義了，其實計算一下100^(1/7)，結果是1.96， 相比6更接近2，所以這也是二分法的最佳近似。

總的來說，這個題本質上就是一個有序數列的查找問題，需要簡化為可計算的數學問題才能得到確切的解，跟平常的直接計算問題有很大不同，考驗的是我們的全面的數學應用能力，很有代表性，給谷歌點個贊。