平分被有缺失的蛋糕

三個人打算分一個矩形的蛋糕，可是有一個人已經偷偷地切走了一小塊矩形的部分。如果只能直直地切一刀，那么另外兩個人應該怎么切才能體積均勻地分掉剩下的部分呢？

解答： 也許有人會說：橫著切，將蛋糕分成兩個等高的部分就好了嘛。但是一般蛋糕上層是奶油，下層只有干巴巴的面包，所以我們不準備把這個作為答案之一。

如果這個蛋糕沒有被切走一部分，應該如何平分呢？方法當然有很多，但是所有的切法都有一個共同點，那就是這一刀一定經過矩形的中心點。反之亦然，所有經過中心點的直線都能將矩形平均分成兩部分。帶著這個結論回到開始的問題上，如果一刀經過大小兩個矩形中心點，就能將大矩形 ABCD 和小矩形 AGFE 都分成面積相等的兩部分，這樣，我們的問題也就解決了。

在上圖中，矩形AEFG是被偷偷挖走的部分。H和I是大小兩個矩形的中心，直線JLK經過這兩個中心點?？梢钥闯鏊倪呅蜛JLG和JLFE的面積是相等的，而四邊形AJKD和JKCB的面積也是相等的，因此剩下的深藍色與綠色的面積也是相等的。

重男輕女的地方男女的比例是多少

假設一個村子里，村民們都有重男輕女的觀念，每一對夫妻都會不斷地生產，直到生出一個男孩。如果生男生女的概率是一樣的，那這個村子最終的男女比例應該是多少？

解答： 如果這個村子里有C對夫妻，那最后就有C個男孩。而女孩的數(shù)量呢？這是一個數(shù)學上求期望值的問題。

不妨任選一戶人家來分析，設這戶人家有n個女孩。如果 n = 0 ，也就是說這戶人家第一次就生了個男孩，那么這個概率便是1／2。 n = 1 時，便是先女后男，概率是 1／2 * 1／2 = 1／4 。n = 2 時，便是前兩次生了兩個女孩，第三次生了男孩，概率是 1/2*1/2*1/2 = 1/8 。以此類推，一戶人家出現(xiàn)n個女孩的概率是 1／2n+1 。由此可以算出一戶人家女孩數(shù)量的期望值是 0 + 1／4 + 2／8 + 3／16 + … = 1 。因此，C戶人家的女孩數(shù)量的期望值便是C，女孩和男孩的數(shù)量在期望上是相等的。也就是說，即使是在一個重女輕男的地方，男女比例仍然是 1 : 1 。

怎么測雞蛋的強度最方便

現(xiàn)在你在一棟 100 層高的大樓門口，手頭上有兩顆完全一樣的神奇雞蛋。如果你想知道這兩個雞蛋最高能從多少樓摔下而不破碎，用什么策略能保證你的嘗試次數(shù)盡可能少呢？

解答： 在只有一個雞蛋時，保險起見，我們只能從一樓開始，一層一層地試驗，看看雞蛋有沒有被摔爛。這樣最精確，但是消耗的時間也最久。如果我們事先就知道這個雞蛋不被摔碎的最高落下點在30層到75層之間，我們最多也只要嘗試45次就能知道結果?，F(xiàn)在我們手上有兩個雞蛋，根據(jù)上面的分析，一個合理的策略就是用第一個雞蛋確定出一個較小的樓層范圍，然后在這個范圍里用第二個雞蛋從下往上逐層嘗試。

比如說讓第一個雞蛋每隔5層試驗一次。當它在某一層被摔爛時，也就意味著確定了一個4層的待測試寬度（為什么是4層呢？假如雞蛋在5樓的時候沒破，10樓的時候破了，那么我們就只需要知道雞蛋在 6 , 7 , 8 , 9 層的結果）。這時候，用第二顆雞蛋一層一層地嘗試，就能用較少的次數(shù)找出雞蛋剛好摔不爛的高度。

需要注意的是，如果想留給第二顆雞蛋較小的測試寬度，就要縮短第一個雞蛋的測試跨度。相應的，也就增加了嘗試次數(shù)。為了確定合適的跨度，使得總試驗次數(shù)之和盡可能小，我們可以采取如下的辦法。

設跨度是L，第一顆雞蛋的嘗試次數(shù)就是[ 100／L ]，第二顆雞蛋的嘗試次數(shù)就是 L - 1，因此嘗試次數(shù)總和就是 [ 100／L ] + L - 1 。根據(jù)這個公式，我們可以列出下面這個表格：

可以看出，我們只需要選 8 - 13 之間的一個寬度，都能使得總嘗試次數(shù)是19次。

但問題是，這已經是最優(yōu)策略了嗎，有沒有更好的方法呢？

有的。上面的方法固定了第一顆雞蛋的測試跨度，如果我們靈活變動，就能使得總嘗試次數(shù)變得更少。首先，我們選擇從14樓丟下第一顆雞蛋。如果它破碎了，我們就從1樓開始，逐層丟第二顆雞蛋，最多試14次便能得到答案。如果它沒有破碎，那我們往上走 13 層，在 27 樓第二次丟下第一顆雞蛋。此時如果雞蛋碎了，那我們只需要在 15 層到 26 層之間用第二顆雞蛋進行最多12次試驗即可，加上第一顆雞蛋的兩次嘗試，仍然是14次。類似的，依次減小測試跨度，如果雞蛋足夠頑強，那我們丟下第一顆雞蛋的樓層就分別是 14 ， 27 ， 39 ， 50 ， 60 ， 69 ， 77 ，84 ， 90 ， 95 ， 99 以及最后的100層。因為第一顆雞蛋每多嘗試一次，第二顆雞蛋需要嘗試的最大次數(shù)就減少一次，因此，總嘗試次數(shù)的最大可能值一直是不變的，保持在14次。用這種方法，我們只需要不超過14次的嘗試就能夠找出答案。有沒有更優(yōu)的策略了？感興趣的讀者可以自行思考。

孩子多大了

兩個數(shù)學家在某次會議上又見面了——他們是老朋友，可是有十幾年沒見了。

老張：這些年怎么樣啊。

小王：挺好的，我結婚了，現(xiàn)在都是三個孩子的爸爸了。

老張：那很幸福啊，孩子們多大了？

小王：他們年齡乘積是72，年齡的和與你的出生日期一樣（8月的某號）。

老張：我還是猜不出來。

小王：我的大兒子剛開始學鋼琴。

老張：哦，我知道了！

問：小王的三個兒子分別多大呢？

解答： 這道題的思考比較繁瑣，讓我們一步一步地分析。

三個孩子年齡的乘積是72。年齡的和是8月份的某一號，也就是是在 1 ~ 31 之間。我們首先把符合所有上面兩個條件的數(shù)列出來。

這是根據(jù)小王的一句話所能得到的信息。雖然我們不知道老張的生日是幾號，但老張自己肯定知道，所以他只要找出哪個數(shù)對的和與自己的生日相同便能確定?？墒撬麉s說“我還是猜不出來”，那就表明和等于他自己生日的數(shù)對不止一個。因此可篩選出如下兩組數(shù)：

2, 6, 6

3, 3, 8

這兩組數(shù)的和都是14，所以老張無法判斷。這時小王說“我的大兒子剛開始學鋼琴”。在 2 , 6 , 6 和 3 , 3 , 8 中，能確定大兒子的是第二組。所以到這里，老張就知道了小王三個孩子的年齡。這個問題本身并不算難，但如果被當面問這個問題并要求很快答出來，那就需要一定能力了。

貨真價實的谷歌面試題

不同于上面的“流傳”，下面兩道是已被確認了的google面試題。

第一題，給你一個長度為 N 的鏈表。N 很大，但你不知道 N 有多大。你的任務是從這 N 個元素中隨機取出 k 個元素。你只能遍歷這個鏈表一次，且必須保證取出的元素是完全隨機的（出現(xiàn)概率均等）。

第二題，給你一個數(shù)組 A [ 1 .. n ] ，請你在 O ( n ) 的時間里構造一個新的數(shù)組 B [ 1 .. n ] ，使得 B [ i ] = A [ 1 ] * A [ 2 ] * ... * A [ n ]／A [ i ] 。你不能使用除法運算。

這兩道題目看起來很專業(yè)，但有趣的是，即使沒有學過信息學的人也可以想到答案。

第一題的意思就是有一大串物品，它們能且僅能逐個經過你眼前一次。你不知道它們的個數(shù)，要求你從中隨機地抽取 k 個物品，同時必須保證取出的元素是完全隨機的（出現(xiàn)概率均等）。

第二題給出了一個數(shù)列 A [ 1 .. n ] ，要求在較短的時間內不用除法構造一個新數(shù)列 B [ 1 .. n ] ，使得 B [i] = A [ 1 ] * A [ 2 ] * ... * A [ n ]／A [ i ] 。 n是這個數(shù)組的長度。而 O ( n ) 是評判計算方法速度的標準。如果一個解答方法在n任意變化的情況下，都能滿足總共的計算次數(shù)相當于是 n 乘以一個常數(shù)C這個條件，那么就稱這個解答方法是 O ( n ) 的；如果這個解答方法能滿足總共的計算次數(shù)是 n ² 乘以常數(shù)C，那么這個解答方法就被稱作是 O ( n ² ) 的。

第一題沒有告訴我們物品的個數(shù)N，所以我們沒法算出 k／N，連最基本的每樣物品被選中的概率都不知道，還怎么繼續(xù)操作呢？既然我們不知道一共有多少個物品，那我們就應該在所有的物品都經過我們眼前之后再做抉擇。當每個物品經過我們眼前的時候，可以設法對應地給它生成一個 0 到 1 之間的隨機數(shù)。等到我們見過了所有的物品之后，只需要選擇對應的隨機數(shù)最大的前 k 個物品就行了。

第二題不允許用除法增加了不少難度。 B [ i ] 不用除法來表示的話就是： B [ i ] = A [ 1 ] * ... * A [ i - 1 ] * A [ i + 1 ] * ... * A [ n ] 。若按照這個表達式進行計算，生成每個 B[ i ] 的時候要進行n - 1次乘法，這樣一來完全生成 B [ 1 .. n ] 就需要 O ( n ² ) 的時間了。我們需要通過減少重復的運算來提高效率。

注意到 B [ i ] 可以看作是兩個部分的乘積， A [ 1 ] * ... * A [ i - 1 ] 和 A [ i + 1 ] * ... * A [ n ] 。同理 B [ i + 1 ] 就由 A [ 1 ] * ... * A [ i - 1 ] * A [ i ] 和 A [ i + 2 ] * ... * A [ n ] 組成。計算 B [ i ] 時的許多乘法在計算 B [ i + 1 ] 的時候又進行了一遍，因此可以重復利用上一次運算的結果，以避免無謂的運算。從這點出發(fā)，我們構造兩個新的數(shù)列：

S [ i ] = A [ 1 ] * ... * A [ i – 1 ]

T [ i ] = A [ i + 1 ] * ... * A [ n ]

因為生成完整的 S [ 1 .. n ] 和 T [ 1 .. n ] 都能在 O ( n ) 的時間內完成，那么根據(jù) B [ i ] = S [ i ] * T [ i ] 這條式子，生成整個 B [ 1 .. n ] 便也能夠在 O ( n ) 的時間內完成了。

不得不說，谷歌是個很愛玩的公司。它曾在MIT校園內到處張貼著一份密碼，據(jù)說，這份密碼包含了一個Google Jobs的電話號碼，解開密碼的人可以通過此電話留下自己的個人信息，進入谷歌工作。各位讀者，你能解開這個密碼嗎？如果有漂亮的解答，我會在這里貼出來。

相關閱讀： 死理性派教你做微軟面試題