程序員智力面試題解析

1、1、考慮一個(gè)雙人游戲。游戲在一個(gè)圓桌上進(jìn)行。每個(gè)游戲者都有足夠多的硬 幣。他們需要在桌子上輪流放置硬幣，每次必需且只能放置一枚硬幣，要求硬幣完 全置于桌面內(nèi)（不能有一部分懸在桌子外面），并且不能與原來(lái)放過(guò)的硬幣重疊。 誰(shuí)沒(méi)有地方放置新的硬幣，誰(shuí)就輸了。游戲的先行者還是后行者有必勝策略？這種 策略是什么？答案：先行者在桌子中心放置一枚硬幣，以后的硬幣總是放在與后 行者剛才放的地方相對(duì)稱(chēng)的位置。這樣，只要后行者能放，先行者一定也有地方 放。先行者必勝。2、用線(xiàn)性時(shí)間和常數(shù)附加空間將一篇文章的單詞（不是字符） 倒序。答案：先將整篇文章的所有字符逆序（從兩頭起不斷交換位置相對(duì)稱(chēng)的字 符）；然后用同樣的

2、辦法將每個(gè)單詞內(nèi)部的字符逆序。這樣，整篇文章的單詞順序 顛倒了，但單詞本身又被轉(zhuǎn)回來(lái)了。3、用線(xiàn)性時(shí)間和常數(shù)附加空間將一個(gè)長(zhǎng)度為n的字符串向左循環(huán)移動(dòng) m位（例如，abcdefg移動(dòng)3位就變成了 defgabc）。 答案：把字符串切成長(zhǎng)為 m和n-m的兩半。將這兩個(gè)部分分別逆序，再對(duì)整個(gè)字 符串逆序。4、一個(gè)矩形蛋糕，蛋糕內(nèi)部有一塊矩形的空洞。只用一刀，如何將蛋 糕切成大小相等的兩塊？ 答案：注意到平分矩形面積的線(xiàn)都經(jīng)過(guò)矩形的中心。過(guò) 大矩形和空心矩形各自的中心畫(huà)一條線(xiàn)，這條線(xiàn)顯然把兩個(gè)矩形都分成了一半，它 們的差當(dāng)然也是相等的。5、一塊矩形的巧克力，初始時(shí)由 N x M個(gè)小塊組成。 每一次你

3、只能把一塊巧克力掰成兩個(gè)小矩形。最少需要幾次才能把它們掰成N x M塊1x1的小巧克力？答案：N x M - 1次顯然足夠了。這個(gè)數(shù)目也是必需的，因?yàn)?每掰一次后當(dāng)前巧克力的塊數(shù)只能增加一，把巧克力分成N x M塊當(dāng)然需要至少掰N x M - 1次。6、如何快速找出一個(gè)32位整數(shù)的二進(jìn)制表達(dá)里有多少個(gè)1 ?用 關(guān)于1的個(gè)數(shù)的線(xiàn)性時(shí)間？ 答案1 （關(guān)于數(shù)字位數(shù)線(xiàn)性）：for（n=0; b; b = 1 if （b & 1 n+;答案 2 （關(guān)于1的個(gè)數(shù)線(xiàn)性）：for（n=0; b; n+ b &= b-1; 7、一個(gè)大小 為N的數(shù)組，所有數(shù)都是不超過(guò) N-1的正整數(shù)。用0（N的時(shí)間找出重復(fù)的那個(gè)

4、數(shù) （假設(shè)只有一個(gè)）。一個(gè)大小為 N的數(shù)組，所有數(shù)都是不超過(guò) N+1的正整數(shù)。用 0（N的時(shí)間找出沒(méi)有出現(xiàn)過(guò)的那個(gè)數(shù)（假設(shè)只有一個(gè)）。答案：計(jì)算數(shù)組中的所有數(shù)的和，再計(jì)算出從1到N-1的所有數(shù)的和，兩者之差即為重復(fù)的那個(gè)數(shù)。計(jì)算 數(shù)組中的所有數(shù)的和，再計(jì)算出從1到N+1的所有數(shù)的和，兩者之差即為缺少的那個(gè)數(shù)。8 給出一行C語(yǔ)言表達(dá)式，判斷給定的整數(shù)是否是一個(gè) 2的幕。答案：（b &（b-1 = 0 9、地球上有多少個(gè)點(diǎn)，使得從該點(diǎn)出發(fā)向南走一英里，向東走一英 里，再向北走一英里之后恰好回到了起點(diǎn)？答案：北極點(diǎn)”是一個(gè)傳統(tǒng)的答案，其實(shí)這個(gè)問(wèn)題還有其它的答案。事實(shí)上，滿(mǎn)足要求的點(diǎn)有無(wú)窮多個(gè)。所有距

5、離南極 點(diǎn)1 + 1/（2英里的地方都是滿(mǎn)足要求的，向南走一英里后到達(dá)距離南極點(diǎn)1/（2 的地方，向東走一英里后正好繞行緯度圈一周，再向北走原路返回到起點(diǎn)。事實(shí)上， 這仍然不是滿(mǎn)足要求的全部點(diǎn)。距離南極點(diǎn)1 + 1/（2k的地方都是可以的，其中k可以是任意一個(gè)正整數(shù)。10、A、B兩人分別在兩座島上。B生病了，A有B所需 要的藥。C有一艘小船和一個(gè)可以上鎖的箱子。C愿意在A和B之間運(yùn)東西，但東西只能放在箱子里。只要箱子沒(méi)被上鎖，C都會(huì)偷走箱子里的東西，不管箱子里有什么。如果A和B各自有一把鎖和只能開(kāi)自己那把鎖的鑰匙，A應(yīng)該如何把東西安全遞交給B ?答案：A把藥放進(jìn)箱子，用自己的鎖把箱子鎖上。B拿

6、到箱子后，再在箱子上加一把自己的鎖。箱子運(yùn)回A后，A取下自己的鎖。箱子再運(yùn)到B手中時(shí)，B取下自己的鎖，獲得藥物。11、一對(duì)夫婦邀請(qǐng)N-1對(duì)夫婦參加聚會(huì) （因此聚會(huì)上總共有2N人）。每個(gè)人都和所有自己不認(rèn)識(shí)的人握了一次手。然 后，男主人問(wèn)其余所有人（共2N-1個(gè)人）各自都握了幾次手，得到的答案全部都 不一樣。假設(shè)每個(gè)人都認(rèn)識(shí)自己的配偶，那么女主人握了幾次手？答案：握手次數(shù)只可能是從0到2N-2這2N-1個(gè)數(shù)。除去男主人外，一共有 2N-1個(gè)人，因此每 個(gè)數(shù)恰好出現(xiàn)了一次。其中有一個(gè)人（0沒(méi)有握手，有一個(gè)人（2N-2和所有其它的夫 婦都握了手。這兩個(gè)人肯定是一對(duì)夫妻，否則后者將和前者握手（從而前者

7、的握手 次數(shù)不再是0）。除去這對(duì)夫妻外，有一個(gè)人（1只與（2N-2握過(guò)手，有一個(gè)人（2N-3 和除了 （0以外的其它夫婦都握了手。這兩個(gè)人肯定是一對(duì)夫妻，否則后者將和前 者握手（從而前者的握手次數(shù)不再是 1）。以此類(lèi)推，直到握過(guò) N-2次手的人和握 過(guò)N次手的人配成一對(duì)。此時(shí)，除了男主人及其配偶以外，其余所有人都已經(jīng)配 對(duì)。根據(jù)排除法，最后剩下來(lái)的那個(gè)握手次數(shù)為N-1的人就是女主人了。 12、兩個(gè)機(jī)器人，初始時(shí)位于數(shù)軸上的不同位置。給這兩個(gè)機(jī)器人輸入一段相同的程序， 使得這兩個(gè)機(jī)器人保證可以相遇。程序只能包含左移n個(gè)單位”、右移n個(gè)單 位”條件判斷語(yǔ)句If,循環(huán)語(yǔ)句while，以及兩個(gè)返回Bo

8、olean值的函數(shù)在自己 的起點(diǎn)處”和在對(duì)方的起點(diǎn)處”你不能使用其它的變量和計(jì)數(shù)器。 答案：兩個(gè)機(jī) 器人同時(shí)開(kāi)始以單位速度右移，直到一個(gè)機(jī)器人走到另外一個(gè)機(jī)器人的起點(diǎn)處。然后，該機(jī)器人以雙倍速度追趕對(duì)方。程序如下。while(!at_other_robots_start move_right 1 while(true move_right2 13、如果叫你從下面兩種游戲中選擇一種，你選擇哪一種？為什么？a.寫(xiě)下一句話(huà)。如果這句話(huà)為真，你將獲得10美元；如果這句話(huà)為假，你獲得的金錢(qián)將少 于10美元或多于10美元(但不能恰好為10美元)。b.寫(xiě)下一句話(huà)。不管這句話(huà) 的真假，你都會(huì)得到多于10美元的

9、錢(qián)。答案：選擇第一種游戲，并寫(xiě)下 我既不 會(huì)得到10美元，也不會(huì)得到10000000美元” 14、你在一幢100層大樓下，有21 根電線(xiàn)線(xiàn)頭標(biāo)有數(shù)字1.21。這些電線(xiàn)一直延伸到大樓樓頂，樓頂?shù)木€(xiàn)頭處標(biāo)有字 母A.U。你不知道下面的數(shù)字和上面的字母的對(duì)應(yīng)關(guān)系。你有一個(gè)電池，一個(gè)燈 泡，和許多很短的電線(xiàn)。如何只上下樓一次就能確定電線(xiàn)線(xiàn)頭的對(duì)應(yīng)關(guān)系？答案：在下面把2,3連在一起，把4到6全連在一起，把7到10全連在一起，等 等，這樣你就把電線(xiàn)分成了 6個(gè) 等價(jià)類(lèi)”大小分別為1,2, 3, 4, 5, 6然后到樓 頂，測(cè)出哪根線(xiàn)和其它所有電線(xiàn)都不相連，哪些線(xiàn)和另外一根相連，哪些線(xiàn)和另外 兩根相連，等等

10、，從而確定出字母 A.U各屬于哪個(gè)等價(jià)類(lèi)?，F(xiàn)在，把每個(gè)等價(jià)類(lèi) 中的第一個(gè)字母連在一起，形成一個(gè)大小為6的新等價(jià)類(lèi)；再把后5個(gè)等價(jià)類(lèi)中的第二個(gè)字母連在一起，形成一個(gè)大小為 5的新等價(jià)類(lèi)；以此類(lèi)推?；氐綐窍?，把新 的等價(jià)類(lèi)區(qū)別出來(lái)。這樣，你就知道了每個(gè)數(shù)字對(duì)應(yīng)了哪一個(gè)原等價(jià)類(lèi)的第幾個(gè)字 母，從而解決問(wèn)題。15、某種藥方要求非常嚴(yán)格，你每天需要同時(shí)服用A、B兩種藥片各一顆，不能多也不能少。這種藥非常貴，你不希望有任何一點(diǎn)的浪費(fèi)。一 天，你打開(kāi)裝藥片A的藥瓶，倒出一粒藥片放在手心；然后打開(kāi)另一個(gè)藥瓶，但 不小心倒出了兩粒藥片?，F(xiàn)在，你手心上有一顆藥片A，兩顆藥片B，并且你無(wú)法區(qū)別哪個(gè)是A，哪個(gè)是B。你

11、如何才能?chē)?yán)格遵循藥方服用藥片，并且不能有任何的 浪費(fèi)？答案：把手上的三片藥各自切成兩半，分成兩堆擺放。再取出一粒藥片 A，也把它切成兩半，然后在每一堆里加上半片的A。現(xiàn)在，每一堆藥片恰好包含兩個(gè)半片的A和兩個(gè)半片的B。一天服用其中一堆即可。16、你在一個(gè)飛船上，飛船上的計(jì)算機(jī)有n個(gè)處理器。突然，飛船受到外星激光武器的攻擊，一些處理器 被損壞了。你知道有超過(guò)一半的處理器仍然是好的。你可以向一個(gè)處理器詢(xún)問(wèn)另一 個(gè)處理器是好的還是壞的。一個(gè)好的處理器總是說(shuō)真話(huà)，一個(gè)壞的處理器總是說(shuō)假 話(huà)。用n-2次詢(xún)問(wèn)找出一個(gè)好的處理器。答案：給處理器從1到n標(biāo)號(hào)。用符號(hào)a-b表示向標(biāo)號(hào)為a的 處理器詢(xún)問(wèn)處理器b是

12、不是好的。首先問(wèn)1-2,如果1說(shuō)不是，就把他們倆都去 掉（去掉了一個(gè)好的和一個(gè)壞的，則剩下的處理器中好的仍然過(guò)半），然后從 3- 4開(kāi)始繼續(xù)發(fā)問(wèn)。如果1說(shuō)2是好的，就繼續(xù)問(wèn)2-3, 3-4，直到某一次j說(shuō) j+1是壞的，把j和j+1去掉，然后問(wèn)j-1 - j+2 ;或者從j+2 - j+3開(kāi)始發(fā)問(wèn)，如果 前面已經(jīng)沒(méi)有j-1 了（之前已經(jīng)被去掉過(guò)了）。注意到你始終維護(hù)著這樣一個(gè)鏈”前面的每一個(gè)處理器都說(shuō)后面那個(gè)是好的。這條鏈里的所有處理器要么都是 好的，要么都是壞的。當(dāng)這條鏈越來(lái)越長(zhǎng)，剩下的處理器越來(lái)越少時(shí)，總有一個(gè)時(shí) 候這條鏈超過(guò)了剩下的處理器的一半，此時(shí)可以肯定這條鏈里的所有處理器都是好 的

13、?；蛘撸絹?lái)越多的處理器都被去掉了，鏈的長(zhǎng)度依舊為0,而最后只剩下一個(gè)或兩個(gè)處理器沒(méi)被問(wèn)過(guò)，那他們一定就是好的了。另外注意到，第一個(gè)處理器的好 壞從來(lái)沒(méi)被問(wèn)過(guò)，仔細(xì)想想你會(huì)發(fā)現(xiàn)最后一個(gè)處理器的好壞也不可能被問(wèn)到（一旦 鏈長(zhǎng)超過(guò)剩余處理器的一半，或者最后沒(méi)被去掉的就只剩這一個(gè)了時(shí)，你就不問(wèn) 了），因此詢(xún)問(wèn)次數(shù)不會(huì)超過(guò) n-2。17、一個(gè)圓盤(pán)被涂上了黑白二色，兩種顏色各 占一個(gè)半圓。圓盤(pán)以一個(gè)未知的速度、按一個(gè)未知的方向旋轉(zhuǎn)。你有一種特殊的相 機(jī)可以讓你即時(shí)觀察到圓上的一個(gè)點(diǎn)的顏色。你需要多少個(gè)相機(jī)才能確定圓盤(pán)旋轉(zhuǎn) 的方向？答案：你可以把兩個(gè)相機(jī)放在圓盤(pán)上相近的兩點(diǎn)，然后觀察哪個(gè)點(diǎn)先變 色。事實(shí)上

14、，只需要一個(gè)相機(jī)就夠了?？刂葡鄼C(jī)繞圓盤(pán)中心順時(shí)針移動(dòng)，觀察顏色 多久變一次；然后讓相機(jī)以相同的速度逆時(shí)針繞著圓盤(pán)中心移動(dòng)，再次觀察變色的 頻率?？梢詳喽?，變色頻率較慢的那一次，相機(jī)的轉(zhuǎn)動(dòng)方向是和圓盤(pán)相同的。18、有25匹馬，速度都不同，但每匹馬的速度都是定值?，F(xiàn)在只有 5條賽道，無(wú) 法計(jì)時(shí)，即每賽一場(chǎng)最多只能知道 5匹馬的相對(duì)快慢。問(wèn)最少賽幾場(chǎng)可以找出 25 匹馬中速度最快的前3名？（百度2008年面試題）每匹馬都至少要有一次參賽的 機(jī)會(huì)，所以25匹馬分成5組，一開(kāi)始的這5場(chǎng)比賽是免不了的。接下來(lái)要找冠軍也很容易，每一組的冠軍在一起賽一場(chǎng)就行了（第 6場(chǎng)）。最后就是要找第2和第 3名。我們按照第6場(chǎng)比賽中得到的名次依次把它們?cè)谇?5場(chǎng)比賽中所在的組命名 為A、B、C、D、E。即：A組的冠軍是第6場(chǎng)的第1名，B組的冠軍是第6場(chǎng)的 第2名每一組的5匹馬按照他們已經(jīng)賽出的成績(jī)從快到慢編號(hào)：A組：1,2, 3, 4, 5 B 組：1, 2, 3, 4, 5 C組：1, 2, 3, 4, 5 D 組：1,2, 3, 4, 5 E組：1,