程序員面試智力題

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

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

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

4、找出沒有出現(xiàn)過的那個數(shù)（假設(shè)只有一個）。答案：計算數(shù)組中的所有數(shù)的和，再計算出從1到N-1的所有數(shù)的和，兩者之差即為重復(fù)的那個數(shù)。計算數(shù)組中的所有數(shù)的和，再計算出從1到N+1的所有數(shù)的和，兩者之差即為缺少的那個數(shù)。8.給出一行C語言表達(dá)式，判斷給定的整數(shù)是否是一個2的冪。答案：(b&(b-1)=09.地球上有多少個點，使得從該點出發(fā)向南走一英里，向東走一英里，再向北走一英里之后恰好回到了起點？答案：“北極點”是一個傳統(tǒng)的答案，其實這個問題還有其它的答案。事實上，滿足要求的點有無窮多個。所有距離南極點1+1/(2)英里的地方都是滿足要求的，向南走一英里后到達(dá)距離南極點1/(2)的地方，向東走一英

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

6、.一對夫婦邀請N-1對夫婦參加聚會（因此聚會上總共有2N人）。每個人都和所有自己不認(rèn)識的人握了一次手。然后，男主人問其余所有人（共2N-1個人）各自都握了幾次手，得到的答案全部都不一樣。假設(shè)每個人都認(rèn)識自己的配偶，那么女主人握了幾次手？答案：握手次數(shù)只可能是從0到2N-2這2N-1個數(shù)。除去男主人外，一共有2N-1個人，因此每個數(shù)恰好出現(xiàn)了一次。其中有一個人(0)沒有握手，有一個人(2N-2)和所有其它的夫婦都握了手。這兩個人肯定是一對夫妻，否則后者將和前者握手（從而前者的握手次數(shù)不再是0）。除去這對夫妻外，有一個人(1)只與(2N-2)握過手，有一個人(2N-3)和除了(0)以外的其它夫婦都

7、握了手。這兩個人肯定是一對夫妻，否則后者將和前者握手（從而前者的握手次數(shù)不再是1）。以此類推，直到握過N-2次手的人和握過N次手的人配成一對。此時，除了男主人及其配偶以外，其余所有人都已經(jīng)配對。根據(jù)排除法，最后剩下來的那個握手次數(shù)為N-1的人就是女主人了。12.兩個機器人，初始時位于數(shù)軸上的不同位置。給這兩個機器人輸入一段相同的程序，使得這兩個機器人保證可以相遇。程序只能包含“左移n個單位”、“右移n個單位”，條件判斷語句If，循環(huán)語句while，以及兩個返回Boolean值的函數(shù)“在自己的起點處”和“在對方的起點處”。你不能使用其它的變量和計數(shù)器。答案：兩個機器人同時開始以單位速度右移，直到

8、一個機器人走到另外一個機器人的起點處。然后，該機器人以雙倍速度追趕對方。程序如下。while(!at_other_robots_start)move_right 1while(true)move_right 213.如果叫你從下面兩種游戲中選擇一種，你選擇哪一種？為什么？a.寫下一句話。如果這句話為真，你將獲得10美元；如果這句話為假，你獲得的金錢將少于10美元或多于10美元（但不能恰好為10美元）。b.寫下一句話。不管這句話的真假，你都會得到多于10美元的錢。答案：選擇第一種游戲，并寫下“我既不會得到10美元，也不會得到美元”。14.你在一幢100層大樓下，有21根電線線頭標(biāo)有數(shù)字1.21。

9、這些電線一直延伸到大樓樓頂，樓頂?shù)木€頭處標(biāo)有字母A.U。你不知道下面的數(shù)字和上面的字母的對應(yīng)關(guān)系。你有一個電池，一個燈泡，和許多很短的電線。如何只上下樓一次就能確定電線線頭的對應(yīng)關(guān)系？答案：在下面把2,3連在一起，把4到6全連在一起，把7到10全連在一起，等等，這樣你就把電線分成了6個“等價類”，大小分別為1,2,3,4,5,6。然后到樓頂，測出哪根線和其它所有電線都不相連，哪些線和另外一根相連，哪些線和另外兩根相連，等等，從而確定出字母A.U各屬于哪個等價類。現(xiàn)在，把每個等價類中的第一個字母連在一起，形成一個大小為6的新等價類；再把后5個等價類中的第二個字母連在一起，形成一個大小為5的新等價

10、類；以此類推?；氐綐窍拢研碌牡葍r類區(qū)別出來。這樣，你就知道了每個數(shù)字對應(yīng)了哪一個原等價類的第幾個字母，從而解決問題。15.某種藥方要求非常嚴(yán)格，你每天需要同時服用A、B兩種藥片各一顆，不能多也不能少。這種藥非常貴，你不希望有任何一點的浪費。一天，你打開裝藥片A的藥瓶，倒出一粒藥片放在手心；然后打開另一個藥瓶，但不小心倒出了兩粒藥片?，F(xiàn)在，你手心上有一顆藥片A，兩顆藥片B，并且你無法區(qū)別哪個是A，哪個是B。你如何才能嚴(yán)格遵循藥方服用藥片，并且不能有任何的浪費？答案：把手上的三片藥各自切成兩半，分成兩堆擺放。再取出一粒藥片A，也把它切成兩半，然后在每一堆里加上半片的A?，F(xiàn)在，每一堆藥片恰好包含兩

11、個半片的A和兩個半片的B。一天服用其中一堆即可。16.你在一個飛船上，飛船上的計算機有n個處理器。突然，飛船受到外星激光武器的攻擊，一些處理器被損壞了。你知道有超過一半的處理器仍然是好的。你可以向一個處理器詢問另一個處理器是好的還是壞的。一個好的處理器總是說真話，一個壞的處理器總是說假話。用n-2次詢問找出一個好的處理器。答案：給處理器從1到n標(biāo)號。用符號a-b表示向標(biāo)號為a的處理器詢問處理器b是不是好的。首先問1-2，如果1說不是，就把他們倆都去掉（去掉了一個好的和一個壞的，則剩下的處理器中好的仍然過半），然后從3-4開始繼續(xù)發(fā)問。如果1說2是好的，就繼續(xù)問2-3，3-4，直到某一次j說j+

12、1是壞的，把j和j+1去掉，然后問j-1-j+2；或者從j+2-j+3開始發(fā)問，如果前面已經(jīng)沒有j-1了（之前已經(jīng)被去掉過了）。注意到你始終維護(hù)著這樣一個“鏈”，前面的每一個處理器都說后面那個是好的。這條鏈里的所有處理器要么都是好的，要么都是壞的。當(dāng)這條鏈越來越長，剩下的處理器越來越少時，總有一個時候這條鏈超過了剩下的處理器的一半，此時可以肯定這條鏈里的所有處理器都是好的?；蛘?，越來越多的處理器都被去掉了，鏈的長度依舊為0，而最后只剩下一個或兩個處理器沒被問過，那他們一定就是好的了。另外注意到，第一個處理器的好壞從來沒被問過，仔細(xì)想想你會發(fā)現(xiàn)最后一個處理器的好壞也不可能被問到（一旦鏈長超過剩余

13、處理器的一半，或者最后沒被去掉的就只剩這一個了時，你就不問了），因此詢問次數(shù)不會超過n-2。17.一個圓盤被涂上了黑白二色，兩種顏色各占一個半圓。圓盤以一個未知的速度、按一個未知的方向旋轉(zhuǎn)。你有一種特殊的相機可以讓你即時觀察到圓上的一個點的顏色。你需要多少個相機才能確定圓盤旋轉(zhuǎn)的方向？答案：你可以把兩個相機放在圓盤上相近的兩點，然后觀察哪個點先變色。事實上，只需要一個相機就夠了?？刂葡鄼C繞圓盤中心順時針移動，觀察顏色多久變一次；然后讓相機以相同的速度逆時針繞著圓盤中心移動，再次觀察變色的頻率。可以斷定，變色頻率較慢的那一次，相機的轉(zhuǎn)動方向是和圓盤相同的。今天考完美國結(jié)構(gòu)語言學(xué)，稍微輕松了一些。

14、我把前幾天向大家推薦的網(wǎng)頁好好看了一遍，挑選了10個比較精彩的、不是很常見的、本Blog之前沒有提過的智力題，并且把它們都整理到了一起，與大家一同分享。希望大家能夠大呼過癮1.給一個瞎子52張撲克牌，并告訴他里面恰好有10張牌是正面朝上的。要求這個瞎子把牌分成兩堆，使得每堆牌里正面朝上的牌的張數(shù)一樣多。瞎子應(yīng)該怎么做？答案：把撲克牌分成兩堆，一堆10張，一堆42張。然后，把小的那一堆里的所有牌全部翻過來。2.如何用一枚硬幣等概率地產(chǎn)生一個1到3之間的隨機整數(shù)？如果這枚硬幣是不公正的呢？答案：如果是公正的硬幣，則投擲兩次，“正反”為1，“反正”為2，“正正”為3，“反反”重來。如果是不公正的硬幣

15、，注意到出現(xiàn)“正反”和“反正”的概率一樣，因此令“正反反正”、“反正正反”、“正反正反”分別為1、2、3，其余情況重來。另一種更妙的辦法是，投擲三次硬幣，“正反反”為1，“反正反”為2，“反反正”為3，其余情況重來。3.30枚面值不全相同的硬幣擺成一排，甲、乙兩個人輪流選擇這排硬幣的其中一端，并取走最外邊的那枚硬幣。如果你先取硬幣，能保證得到的錢不會比對手少嗎？答案：先取者可以讓自己總是取奇數(shù)位置上的硬幣或者總是取偶數(shù)位置上的硬幣。數(shù)一數(shù)是奇數(shù)位置上的面值總和多還是偶數(shù)位置上的面值總和多，然后總是取這些位置上的硬幣就可以了。4.一個環(huán)形軌道上有n個加油站，所有加油站的油量總和正好夠車跑一圈。證

16、明，總能找到其中一個加油站，使得初始時油箱為空的汽車從這里出發(fā)，能夠順利環(huán)行一圈回到起點。答案：總存在一個加油站，僅用它的油就足夠跑到下一個加油站（否則所有加油站的油量加起來將不夠全程）。把下一個加油站的所有油都提前搬到這個加油站來，并把油已被搬走的加油站無視掉。在剩下的加油站中繼續(xù)尋找油量足以到達(dá)下個加油站的地方，不斷合并加油站，直到只剩一個加油站為止。顯然從這里出發(fā)就能順利跑完全程。另一種證明方法：先讓汽車油箱里裝好足夠多的油，隨便從哪個加油站出發(fā)試跑一圈。車每到一個加油站時，記錄此時油箱里剩下的油量，然后把那個加油站的油全部裝上。試跑完一圈后，檢查剛才路上到哪個加油站時剩的油量最少，那么

17、空著油箱從那里出發(fā)顯然一定能跑完全程。5.初始時，兩個口袋里各有一個球。把后面的n-2個球依次放入口袋，放進(jìn)哪個口袋其概率與各口袋已有的球數(shù)成正比。這樣下來，球數(shù)較少的那個口袋平均期望有多少個球？答案：先考慮一個看似無關(guān)的問題怎樣產(chǎn)生一個1到n的隨機排列。首先，在紙上寫下數(shù)字1；然后，把2寫在1的左邊或者右邊；然后，把3寫在最左邊，最右邊，或者插進(jìn)1和2之間總之，把數(shù)字i等概率地放進(jìn)由前面i-1個數(shù)產(chǎn)生的（包括最左端和最右端在內(nèi)的）共i個空位中的一個。這樣生成的顯然是一個完全隨機的排列。我們換一個角度來看題目描述的過程：假想用一根繩子把兩個球拴在一起，把這根繩子標(biāo)號為1。接下來，把其中一個小球

18、分裂成兩個小球，這兩個小球用標(biāo)號為2的繩子相連。總之，把“放進(jìn)第i個球”的操作想象成把其中一個球分裂成兩個用標(biāo)有i-1的繩子相連的小球。聯(lián)想我們前面的討論，這些繩子的標(biāo)號事實上是一個隨機的全排列，也就是說最開始繩子1的位置最后等可能地出現(xiàn)在每個地方。也就是說，它兩邊的小球個數(shù)(1,n-1)、(2,n-2)、(3,n-3)、(n-1,1)這n-1種情況等可能地發(fā)生。因此，小袋子里的球數(shù)大約為n/4個。準(zhǔn)確地說，當(dāng)n為奇數(shù)時，小袋子里的球數(shù)為(n+1)/4；當(dāng)n為偶數(shù)時，小袋子里的球數(shù)為n2/(4n-4)。6.考慮一個n*n的棋盤，把有公共邊的兩個格子叫做相鄰的格子。初始時，有些格子里有病毒。每一

19、秒鐘后，只要一個格子至少有兩個相鄰格子染上了病毒，那么他自己也會被感染。為了讓所有的格子都被感染，初始時最少需要有幾個帶病毒的格子？給出一種方案并證明最優(yōu)性。答案：至少要n個，比如一條對角線上的n個格子。n個格子也是必需的。當(dāng)一個新的格子被感染后，全體被感染的格子所組成的圖形的周長將減少0個、2個或4個單位（具體減少了多少要看它周圍被感染的格子有多少個）。又因為當(dāng)所有格子都被感染后，圖形的周長為4n，因此初始時至少要有n個被感染的格子。7.在一個m*n的棋盤上，有k個格子里放有棋子。是否總能對所有棋子進(jìn)行紅藍(lán)二染色，使得每行每列的紅色棋子和藍(lán)色棋子最多差一個？答案：可以。建一個二分圖G(X,Y

20、)，其中X有m個頂點代表了棋盤的m個行，Y有n個頂點代表了棋盤的n個列。第i行第j列有棋子就在X(i)和Y(j)之間連一條邊。先找出圖G里的所有環(huán)（由于是二分圖，環(huán)的長度一定是偶數(shù)），把環(huán)里的邊紅藍(lán)交替染色。剩下的沒染色的圖一定是一些樹。對每棵樹遞歸地進(jìn)行操作：去掉一個葉子節(jié)點和對應(yīng)邊，把剩下的樹進(jìn)行合法的紅藍(lán)二染色，再把剛才去掉的頂點和邊加回去，給這個邊適當(dāng)?shù)念伾詽M足要求。8.任意給一個8*8的01矩陣，你每次只能選一個3*3或者4*4的子矩陣并把里面的元素全部取反。是否總有辦法把矩陣?yán)锏乃袛?shù)全部變?yōu)?？答案：不能。大矩陣中有36個3*3的小矩陣和25個4*4的小矩陣，因此總共有61種可能的操作。顯然，給定一個操作序列，這些操作的先后順序是無關(guān)緊要的；另外，在一個操作序列中使用兩種或兩種以上相同的操作也是無用的。因此，實質(zhì)不同的操作序列只有261種。但8*8的01矩陣一共有264種，因此不是每種情況都有辦法達(dá)到目的。9.五個洞排成一排，其中一個洞里藏有一只狐貍。每個夜晚，狐貍都會跳到一個相鄰的洞里；每個白天