程序員有趣的面試智力題

偶然間在網(wǎng)上看到幾個原來沒見過的面試智力題，有幾個題目在國內(nèi)流傳相當廣,什么n個人怎么分餅最公平，屋里的三個燈泡分別由哪個開關(guān)控制，三架飛機環(huán)游世界，用火柴和兩根繩子測量45分鐘之類的題目，火星得已經(jīng)可以考古了，這里就不再說了。1、 考慮一個雙人游戲。游戲在一個圓桌上進行。每個游戲者都有足夠多的硬幣。他們需要在桌子上輪流放置硬幣，每次必需且只能放置一枚硬幣，要求硬幣完全置于桌面內(nèi)（不能有一部分懸在桌子外面），并且不能與原來放過的硬幣重疊。誰沒有地方放置新的硬幣，誰就輸了。游戲的先行者還是后行者有必勝策略？這種策略是什么？答案：先行者在桌子中心放置一枚硬幣，以后的硬幣總是放在與后行者剛才放的地方相對稱的位置。這樣，只要后行者能放，先行者一定也有地方放。先行者必勝。2、 用線性時間和常數(shù)附加空間將一篇文章的單詞（不是字符）倒序。答案：先將整篇文章的所有字符逆序（從兩頭起不斷交換位置相對稱的字符）；然后用同樣的辦法將每個單詞內(nèi)部的字符逆序。這樣，整篇文章的單詞順序顛倒了，但單詞本身又被轉(zhuǎn)回來了。3、 用線性時間和常數(shù)附加空間將一個長度為n的字符串向左循環(huán)移動m位（例如，"abcdefg”移動3位就變成了"defgabc”）。答案：把字符串切成長為m和n-m的兩半。將這兩個部分分別逆序，再對整個字符串逆序。4、 一個矩形蛋糕，蛋糕內(nèi)部有一塊矩形的空洞。只用一刀，如何將蛋糕切成大小相等的兩塊？答案：注意到平分矩形面積的線都經(jīng)過矩形的中心。過大矩形和空心矩形各自的中心畫一條線，這條線顯然把兩個矩形都分成了一半,它們的差當然也是相等的。5、 一塊矩形的巧克力，初始時由NxM個小塊組成。每一次你只能把一塊巧克力掰成兩個小矩形。最少需要幾次才能把它們掰成NxM塊1x1的小巧克力？答案：NxM-1次顯然足夠了。這個數(shù)目也是必需的，因為每掰一次后當前巧克力的塊數(shù)只能增加一，把巧克力分成NxM塊當然需要至少掰NxM-1次。6、 如何快速找出一個32位整數(shù)的二進制表達里有多少個"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)的時間找出重復的那個數(shù)(假設(shè)只有一個)。一個大小為N的數(shù)組，所有數(shù)都是不超過N+1的正整數(shù)。用O(N)的時間找出沒有出現(xiàn)過的那個數(shù)(假設(shè)只有一個)。答案：計算數(shù)組中的所有數(shù)的和，再計算出從1到N-1的所有數(shù)的和，兩者之差即為重復的那個數(shù)。計算數(shù)組中的所有數(shù)的和，再計算出從1到N+1的所有數(shù)的和，兩者之差即為缺少的那個數(shù)。&給出一行C語言表達式，判斷給定的整數(shù)是否是一個2的幕。答案：(b&(b-1))==09、 地球上有多少個點，使得從該點出發(fā)向南走一英里，向東走一英里，再向北走一英里之后恰好回到了起點？答案：“北極點”是一個傳統(tǒng)的答案，其實這個問題還有其它的答案。事實上，滿足要求的點有無窮多個。所有距離南極點1+1/(2n)英里的地方都是滿足要求的，向南走一英里后到達距離南極點1/(2n)的地方，向東走一英里后正好繞行緯度圈一周，再向北走原路返回到起點。事實上，這仍然不是滿足要求的全部點。距離南極點1+1/(2kn)的地方都是可以的，其中k可以是任意一個正整數(shù)。10、 A、B兩人分別在兩座島上。B生病了，A有B所需要的藥。C有一艘小船和一個可以上鎖的箱子。C愿意在A和B之間運東西，但東西只能放在箱子里。只要箱子沒被上鎖，C都會偷走箱子里的東西，不管箱子里有什么。如果A和B各自有一把鎖和只能開自己那把鎖的鑰匙，A應該如何把東西安全遞交給B？答案：A把藥放進箱子，用自己的鎖把箱子鎖上。B拿到箱子后，再在箱子上加一把自己的鎖。箱子運回A后，A取下自己的鎖。箱子再運到B手中時，B取下自己的鎖，獲得藥物。11、 一對夫婦邀請N-1對夫婦參加聚會(因此聚會上總共有2N人)。每個人都和所有自己不認識的人握了一次手。然后，男主人問其余所有人(共2N-1個人)各自都握了幾次手，得到的答案全部都不一樣。假設(shè)每個人都認識自己的配偶，那么女主人握了幾次手？答案：握手次數(shù)只可能是從0到2N-2這2N-1個數(shù)。除去男主人外，一共有2N-1個人，因此每個數(shù)恰好出現(xiàn)了一次。其中有一個人(0)沒有握手，有一個人(2N-2)和所有其它的夫婦都握了手。這兩個人肯定是一對夫妻，否則后者將和前者握手(從而前者的握手次數(shù)不再是0)。除去這對夫妻外，有一個人(1)只與(2N-2)握過手，有一個人(2N-3)和除了(0)以外的其它夫婦都握了手。這兩個人肯定是一對夫妻，否則后者將和前者握手(從而前者的握手次數(shù)不再是1)。以此類推,直到握過N-2次手的人和握過N次手的人配成一對。此時，除了男主人及其配偶以外，其余所有人都已經(jīng)配對。根據(jù)排除法，最后剩下來的那個握手次數(shù)為N-1的人就是女主人了。12、兩個機器人，初始時位于數(shù)軸上的不同位置。給這兩個機器人輸入一段相同的程序，使得這兩個機器人保證可以相遇。程序只能包含“左移n個單位”、“右移n個單位”，條件判斷語句If,循環(huán)語句while，以及兩個返回Boolean值的函數(shù)“在自己的起點處”和“在對方的起點處”。你不能使用其它的變量和計數(shù)器。答案：兩個機器人同時開始以單位速度右移，直到一個機器人走到另外一個機器人的起點處。然后，該機器人以雙倍速度追趕對方。程序如下。while(!at_other_robots_start){move_right1}while(true){move_right2}13、如果叫你從下面兩種游戲中選擇一種，你選擇哪一種？為什么？寫下一句話。如果這句話為真，你將獲得10美元；如果這句話為假，你獲得的金錢將少于10美元或多于10美元(但不能恰好為10美元)。寫下一句話。不管這句話的真假，你都會得到多于10美元的錢。答案：選擇第一種游戲，并寫下“我既不會得到10美元，也不會得到10000000美元”。14、你在一幢100層大樓下，有21根電線線頭標有數(shù)字仁21。這些電線一直延伸到大樓樓頂，樓頂?shù)木€頭處標有字母A..U。你不知道下面的數(shù)字和上面的字母的對應關(guān)系。你有一個電池，一個燈泡，和許多很短的電線。如何只上下樓一次就能確定電線線頭的對應關(guān)系？答案：在下面把2,3連在一起，把4到6全連在一起，把7到10全連在一起，等等，這樣你就把電線分成了6個“等價類”，大小分別為1,2,3,4,5,6。然后到樓頂，測出哪根線和其它所有電線都不相連，哪些線和另外一根相連，哪些線和另外兩根相連，等等，從而確定出字母A..U各屬于哪個等價類?，F(xiàn)在，把每個等價類中的第一個字母連在一起，形成一個大小為6的新等價類；再把后5個等價類中的第二個字母連在一起，形成一個大小為5的新等價類；以此類推?；氐綐窍?，把新的等價類區(qū)別出來。這樣，你就知道了每個數(shù)字對應了哪一個原等價類的第幾個字母，從而解決問題。15、 某種藥方要求非常嚴格，你每天需要同時服用A、B兩種藥片各一顆，不能多也不能少。這種藥非常貴，你不希望有任何一點的浪費。一天，你打開裝藥片A的藥瓶，倒出一粒藥片放在手心；然后打開另一個藥瓶，但不小心倒出了兩粒藥片?，F(xiàn)在，你手心上有一顆藥片A,兩顆藥片B,并且你無法區(qū)別哪個是A，哪個是B。你如何才能嚴格遵循藥方服用藥片，并且不能有任何的浪費？答案：把手上的三片藥各自切成兩半，分成兩堆擺放。再取出一粒藥片A，也把它切成兩半，然后在每一堆里加上半片的A。現(xiàn)在，每一堆藥片恰好包含兩個半片的A和兩個半片的B。一天服用其中一堆即可。16、 你在一個飛船上，飛船上的計算機有n個處理器。突然，飛船受到外星激光武器的攻擊，一些處理器被損壞了。你知道有超過一半的處理器仍然是好的。你可以向一個處理器詢問另一個處理器是好的還是壞的。一個好的處理器總是說真話，一個壞的處理器總是說假話。用n-2次詢問找出一個好的處理器。答案：給處理器從1到n標號。用符號a->b表示向標號為a的處理器詢問處理器b是不是好的。首先問1->2，如果1說不是，就把他們倆都去掉（去掉了一個好的和一個壞的，則剩下的處理器中好的仍然過半），然后從3->4開始繼續(xù)發(fā)問。如果1說2是好的，就繼續(xù)問2->3,3->4,……直到某一次j說j+1是壞的，把j和j+1去掉，然后問j-1->j+2；或者從j+2->j+3開始發(fā)問，如果前面已經(jīng)沒有j-1了（之前已經(jīng)被去掉過了）。注意到你始終維護著這樣一個“鏈”，前面的每一個處理器都說后面那個是好的。這條鏈里的所有處理器要么都是好的,要么都是壞的。當這條鏈越來越長，剩下的處理器越來越少時，總有一個時候這條鏈超過了剩下的處理器的一半，此時可以肯定這條鏈里的所有處理器都是好的?；蛘?，越來越多的處理器都被去掉了，鏈的長度依舊為0而最后只剩下一個或兩個處理器沒被問過，那他們一定就是好的了。另外注意到，第一個處理器的好壞從來沒被問過，仔細想想你會發(fā)現(xiàn)最后一個處理器的好壞也不可能被問到（一旦鏈長超過剩余處理器的一半，或者最后沒被去掉的就只剩這一個了時，你就不問了），因此詢問次數(shù)不會超過n-2。17、 一個圓盤被涂上了黑白二色，兩種顏色各占一個半圓。圓盤以一個未知的速度、按一個未知的方向旋轉(zhuǎn)。你有一種特殊的相機可以讓你即時觀察到圓上的一個點的顏色。你需要多少個相機才能確定圓盤旋轉(zhuǎn)的方向？答案：你可以把兩個相機放在圓盤上相近的兩點，然后觀察哪個點先變色。事實上，只需要一個相機就夠了?？刂葡鄼C繞圓盤中心順時針移動，觀察顏色多久變一次;然后讓相機以相同的速度逆時針繞著圓盤中心移動，再次觀察變色的頻率?？梢詳喽?，變色頻率較慢的那一次，相機的轉(zhuǎn)動方向是和圓盤相同的。18、 有25匹馬，速度都不同，但每匹馬的速度都是定值?，F(xiàn)在只有5條賽道,無法計時，即每賽一場最多只能知道5匹馬的相對快慢。問最少賽幾場可以找出25匹馬中速度最快的前3名？（百度2008年面試題每匹馬都至少要有一次參賽的機會，所以25匹馬分成5組，一開始的這5場比賽是免不了的。接下來要找冠軍也很容易，每一組的冠軍在一起賽一場就行了（第6場）。最后就是要找第2和第3名。我們按照第6場比賽中得到的名次依次把它們在前5場比賽中所在的組命名為A、B、C、D、E。即：A組的冠軍是第6場的第1名，B組的冠軍是第6場的第2名……每一組的5匹馬按照他們已經(jīng)賽出的成績從快到慢編號：A組：1，2，3，4，5B組：1，2，3，4，5C組：1，2，3，4，5D組：1，2，3，4，5E組：1，2，3，4，5從現(xiàn)在所得到的信息，我們可以知道哪些馬已經(jīng)被排除在3名以外。只要已經(jīng)能確定有3匹或3匹以上的馬比這匹馬快，那么它就已經(jīng)被淘汰了?？梢钥吹?，只有上表中粗體的那5匹馬是有可能為2、3名的。即：A組的2、3名；B組的1、2名，C組的第1名。取這5匹馬進行第7場比賽，第7場比賽的前兩名就是25匹馬中的2、3名。故一共最少要賽7場。這道題有一些變體，比如64匹馬找前4名。方法是一樣的，在得出第1名以后尋找后3名的候選競爭者就可以了。19、 題目如下：0123456789在橫線上填寫數(shù)字，使之符合要求。要求如下：對應的數(shù)字下填入的數(shù)，代表上面的數(shù)在下面出現(xiàn)的次數(shù)，比如3下面是1,代表3要在下面出現(xiàn)一次。正確答案是：01234567896210001000我的思路是：因為第二行的數(shù)字是第一行的數(shù)在下面出現(xiàn)的次數(shù)，下面10個格子，總共10次。。。所以第2排數(shù)字之和為10。首先從0入手，先填9,肯定不可能，9下面要是1,只剩8個位填0,不夠填8,8下面要填1，1要至少填2,后面不用再想，因為已經(jīng)剩下7個位置，不夠填0 如此類推。到0下面填6的時候就得到我上面的答案了。。其實可以推出這個題目的兩個關(guān)鍵條件：1、 第2排數(shù)字之和為10。2、 兩排數(shù)字上下相乘之和也是10！滿足這兩個條件的就是答案，下面來編寫程序?qū)崿F(xiàn)！[cpp]viewplaincopyprint?//原始數(shù)值：0,1,2,3,4,5,6,7,8,9//出現(xiàn)次數(shù):6,2,1,0,0,0,1,0,0,0#include"iostream"usingnamespacestd;#definelen10classNumberTB{private:inttop[len];intbottom[len];boolsuccess;public:NumberTB();int*getBottom();voidsetNextBottom();intgetFrequecy(intnum);};NumberTB::NumberTB(){success=false;//formattopfor(inti=0;i<len;i++)TOC\o"1-5"\h\z{top[i]=i;}}int*NumberTB::getBottom(){inti=0;while(!success){i++;setNextBottom();}returnbottom;}//setnextbottomvoidNumberTB::setNextBottom(){boolreB=t