死理性派教你做谷歌面試題

　　長久以來，谷歌都因?yàn)閾碛惺澜缟献钭杂珊蛢?yōu)越的環(huán)境，讓全人類羨慕不已。不過，谷歌這樣一個(gè)以創(chuàng)造力為生的神奇地方，對應(yīng)聘對象來說，想成為其中一員可是有著不小的難度。想進(jìn)谷歌，先試試這些早已遍布互聯(lián)網(wǎng)的谷歌面試題吧。

　　平分有缺失的蛋糕

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

　　解答： 如果這個(gè)村子里有C對夫妻，那最后就有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 。

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

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

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

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

　　需要注意的是，如果想留給第二顆雞蛋較小的.測試寬度，就要縮短第一個(gè)雞蛋的測試跨度。相應(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)策略了嗎，有沒有更好的方法呢?

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

http://m.fuchuonang.cn/

【死理性派教你做谷歌面試題】相關(guān)文章：

谷歌的面試題目04-11

谷歌工程師的面試題04-11

怎樣回答名師哲理性面試題09-23

銷售技巧：教你做人做事10-17

谷歌薪酬最高十職位10-28

教你做好面試前的準(zhǔn)備08-01

久坐會(huì)死，椅子要命！02-10

青春派觀后感05-13

圣誕美食派的做法12-11

青春派經(jīng)典臺(tái)詞05-29