平分被有缺失的蛋糕

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

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

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

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

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

假設(shè)一個(gè)村子里，村民們都有重男輕女的觀念，每一對(duì)夫妻都會(huì)不斷地生產(chǎn)，直到生出一個(gè)男孩。如果生男生女的概率是一樣的，那這個(gè)村子最終的男女比例應(yīng)該是多少？

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

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

怎么測(cè)雞蛋的強(qiáng)度最方便

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

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

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

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

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

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

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

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

孩子多大了

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

老張：這些年怎么樣啊。

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

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

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

老張：我還是猜不出來。

小王：我的大兒子剛開始學(xué)鋼琴。

老張：哦，我知道了！

問：小王的三個(gè)兒子分別多大呢？

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

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

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

2, 6, 6

3, 3, 8

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

貨真價(jià)實(shí)的谷歌面試題

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

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

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

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

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

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

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

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

注意到 B [ i ] 可以看作是兩個(gè)部分的乘積， 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 ] 組成。計(jì)算 B [ i ] 時(shí)的許多乘法在計(jì)算 B [ i + 1 ] 的時(shí)候又進(jìn)行了一遍，因此可以重復(fù)利用上一次運(yùn)算的結(jié)果，以避免無謂的運(yùn)算。從這點(diǎn)出發(fā)，我們構(gòu)造兩個(gè)新的數(shù)列：

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

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

因?yàn)樯赏暾?S [ 1 .. n ] 和 T [ 1 .. n ] 都能在 O ( n ) 的時(shí)間內(nèi)完成，那么根據(jù) B [ i ] = S [ i ] * T [ i ] 這條式子，生成整個(gè) B [ 1 .. n ] 便也能夠在 O ( n ) 的時(shí)間內(nèi)完成了。

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

相關(guān)閱讀： 死理性派教你做微軟面試題