谷歌那些刁難工程師的難題解答

谷歌面試未來的工程師的題目一向是很難的。但下面這些不同于以往你看到的那些，因?yàn)樗鼈冞€需要你具備一定的計(jì)算和邏輯基礎(chǔ)。

1.一排房子涂色的問題解答

2012-7-18 09:48:38 上傳下載附件 (26.47 KB)

問題：我們會(huì)有一排房子，你可以理解為“N”間，其中N是整數(shù)。每個(gè)房子可以涂成紅色、綠色或藍(lán)色。每幢房子和相鄰間的房子必須是不一樣的，因?yàn)槊糠N顏色的成本不同，所以還要考慮到盡可能降低成本。

答案：這個(gè)問題可以建模變成一個(gè)“動(dòng)態(tài)編程”問題的解決方法，這會(huì)有效地解決大范圍的搜索和優(yōu)化問題。

這里有代碼可以供大家參考：C[c] = H[c] + min(C[i-1][x]) x belongs to {Red, Blue, Green} x belongs to c.

2.在一個(gè)句子中實(shí)現(xiàn)每個(gè)單詞的反向字符

2012-7-18 09:48:38 上傳下載附件 (20.27 KB)

問題：Convert “——— “my career stack” ———” to “”——— “ym reerac kcats” ———”.

答案：不僅僅是翻轉(zhuǎn)每個(gè)字符，還需要采取一個(gè)更聰明的方式。

你可以通過翻轉(zhuǎn)每個(gè)字符的方式解決這個(gè)問題，但有一個(gè)更聰明的叫遞歸的辦法來解決它。這才是谷歌想要的結(jié)果：找到解決問題最聰明的工程師，而不僅僅是獲得一個(gè)正確的解決方案。

3.找到購買和出售股票的最好時(shí)間

2012-7-18 09:48:38 上傳下載附件 (25.68 KB)

問題：如果你只能購買和出售相同的股票份額，找到一個(gè)買入和賣出的最佳時(shí)間。

答案：記住你在買股票之前，可以把它賣掉。這一點(diǎn)限制實(shí)際上完全改變了問題的結(jié)果。所以，現(xiàn)在你要跟蹤最低值指數(shù)。下面是整體解決方案：

為了有效地解決這個(gè)問題，你需要跟蹤最低值的指數(shù)。你需要尋遍并發(fā)現(xiàn)最低值指數(shù)達(dá)到一個(gè)新的最小值。然后，比較最低值與當(dāng)前元素的差異。在買進(jìn)和賣出時(shí)的差異確定是最大的差異。

4.N個(gè)硬幣一排怎么選最大

2012-7-18 09:48:38 上傳下載附件 (23 KB)

問題：一排硬幣由兩名球員輪流各取一枚，直到拿完為止，誰拿到的金額大誰就贏了。

答案：你一定要先拿！如果你考慮奇數(shù)或者偶數(shù)的硬幣，那么你至少不會(huì)輸。這其實(shí)是另一種“動(dòng)態(tài)編程”的問題。

5.懸空指針是什么?

2012-7-18 09:48:38 上傳下載附件 (18.67 KB)

問題：很簡單對(duì)嗎？

答案：那是毀滅性的錯(cuò)誤。懸空的指針是一個(gè)不再分配到存儲(chǔ)的指針。但有一個(gè)問題，這個(gè)程序在創(chuàng)建之后不會(huì)崩潰，而回執(zhí)行很長一段時(shí)間。每個(gè)工程師都了解這些問題，因?yàn)樗鼈冏罱K會(huì)殺死一些最大、最復(fù)雜的服務(wù)。

[!--empirenews.page--]

6.從不公平的硬幣上找到一個(gè)公平的結(jié)果

2012-7-18 09:48:38 上傳下載附件 (18.63 KB)

問題：我們有一個(gè)不公平的硬幣，因?yàn)槠湔磧擅娼Y(jié)果的概率不同，如何才能得到公平的結(jié)果。

答案：拋兩次硬幣。有四種可能發(fā)生，如果有兩個(gè)正面或者反面的結(jié)果，你應(yīng)該放棄。然后留下一個(gè)正面、一個(gè)反面的結(jié)果，這才是你想要的結(jié)果。

7.在字典中找到一個(gè)單詞是由兩個(gè)單詞組成的

2012-7-18 09:48:38 上傳下載附件 (26.87 KB)

問題：在字典里找到一個(gè)單詞是由兩個(gè)單詞組成的，比如“newspaper”是由“news”和“paper”組成的。

答案：將單詞分成兩個(gè)部分。比如你將“newspaper”分成“newsp”和“aper”兩個(gè)部分。然后你查字典看看有沒有這兩個(gè)單詞，如果沒有，那么重新對(duì)這個(gè)單詞進(jìn)行分隔，直到找到答案。

8.一個(gè)停車位有三分之一時(shí)間是空閑的

2012-7-18 09:48:38 上傳下載附件 (17.79 KB)

問題：一個(gè)停車位有時(shí)候你會(huì)發(fā)現(xiàn)連續(xù)9天都是停了車的，但第10天卻沒有停車，你怎么能判斷？

答案：這是一個(gè)棘手的概率問題，所以就需要答案合乎邏輯。在概率問題上,如果一個(gè)事件已經(jīng)發(fā)生,它不會(huì)對(duì)未來起到任何影響，即使已經(jīng)停了9天，也不能證明第10天就一定是空閑的，所以你需要計(jì)算題目中那個(gè)三分之二的概率實(shí)際中到底有多大幾率。