- 相關(guān)推薦
程序員面試智力題
如下收集到的這些面試試題,是應(yīng)聘程序員的朋友做的題,下面附有答案,大家也來(lái)回答下吧!看看你能答對(duì)多少?問(wèn)題內(nèi)容如下:
1、考慮一個(gè)雙人游戲。游戲在一個(gè)圓桌上進(jìn)行。每個(gè)游戲者都有足夠多的硬幣。他們需要在桌子上輪流放置硬幣,每次必需且只能放置一枚硬幣,要求硬幣完全置于桌面內(nèi)(不能有一部分懸在桌子外面),并且不能與原來(lái)放過(guò)的硬幣重疊。誰(shuí)沒(méi)有地方放置新的硬幣,誰(shuí)就輸了。游戲的先行者還是后行者有必勝策略?這種策略是什么?
答案:先行者在桌子中心放置一枚硬幣,以后的硬幣總是放在與后行者剛才放的地方相對(duì)稱的位置。這樣,只要后行者能放,先行者一定也有地方放。先行者必勝。
2、 用線性時(shí)間和常數(shù)附加空間將一篇文章的單詞(不是字符)倒序。
答案:先將整篇文章的所有字符逆序(從兩頭起不斷交換位置相對(duì)稱的字符);然后用同樣的辦法將每個(gè)單詞內(nèi)部的字符逆序。這樣,整篇文章的單詞順序顛倒了,但單詞本身又被轉(zhuǎn)回來(lái)了。
3、 用線性時(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)部有一塊矩形的空洞。只用一刀,如何將蛋糕切成大小相等的兩塊?
答案:注意到平分矩形面積的線都經(jīng)過(guò)矩形的中心。過(guò)大矩形和空心矩形各自的中心畫一條線,這條線顯然把兩個(gè)矩形都分成了一半,它們的差當(dāng)然也是相等的。
5、 一塊矩形的巧克力,初始時(shí)由N x M個(gè)小塊組成。每一次你只能把一塊巧克力掰成兩個(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ù)的線性時(shí)間?
答案1(關(guān)于數(shù)字位數(shù)線性):for(n=0; b; b >>= 1) if (b & 1) n++;
答案2(關(guān)于"1"的個(gè)數(shù)線性):for(n=0; b; n++) b &= b-1;
7、 一個(gè)大小為N的數(shù)組,所有數(shù)都是不超過(guò)N-1的正整數(shù)。用O(N)的時(shí)間找出重復(fù)的那個(gè)數(shù)(假設(shè)只有一個(gè))。一個(gè)大小為N的數(shù)組,所有數(shù)都是不超過(guò)N+1的正整數(shù)。用O(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í)上,滿足要求的點(diǎn)有無(wú)窮多個(gè)。所有距離南極點(diǎn)1 + 1/(2π)英里的地方都是滿足要求的,向南走一英里后到達(dá)距離南極點(diǎn)1/(2π)的地方,向東走一英里后正好繞行緯度圈一周,再向北走原路返回到起點(diǎn)。事實(shí)上,這仍然不是滿足要求的全部點(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拿到箱子后,再在箱子上加一把自己的鎖。箱子運(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ì)夫妻,否則后者將和前者握手(從而前者的握手次數(shù)不再是0)。除去這對(duì)夫妻外,有一個(gè)人(1)只與(2N-2)握過(guò)手,有一個(gè)人(2N-3)和除了(0)以外的其它夫婦都握了手。這兩個(gè)人肯定是一對(duì)夫妻,否則后者將和前者握手(從而前者的握手次數(shù)不再是1)。以此類推,直到握過(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è)返回Boolean值的函數(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_right 2
}
13、 如果叫你從下面兩種游戲中選擇一種,你選擇哪一種?為什么?
a. 寫下一句話。如果這句話為真,你將獲得10美元;如果這句話為假,你獲得的金錢將少于10美元或多于10美元(但不能恰好為10美元)。
b. 寫下一句話。不管這句話的真假,你都會(huì)得到多于10美元的錢。
答案:選擇第一種游戲,并寫下“我既不會(huì)得到10美元,也不會(huì)得到10000000美元”。
14、你在一幢100層大樓下,有21根電線線頭標(biāo)有數(shù)字1..21。這些電線一直延伸到大樓樓頂,樓頂?shù)木頭處標(biāo)有字母A..U。你不知道下面的數(shù)字和上面的字母的對(duì)應(yīng)關(guān)系。你有一個(gè)電池,一個(gè)燈泡,和許多很短的電線。如何只上下樓一次就能確定電線線頭的對(duì)應(yīng)關(guān)系?
答案:在下面把2,3連在一起,把4到6全連在一起,把7到10全連在一起,等等,這樣你就把電線分成了6個(gè)“等價(jià)類”,大小分別為1, 2, 3, 4, 5, 6。然后到樓頂,測(cè)出哪根線和其它所有電線都不相連,哪些線和另外一根相連,哪些線和另外兩根相連,等等,從而確定出字母A..U各屬于哪個(gè)等價(jià)類。現(xiàn)在,把每個(gè)等價(jià)類中的第一個(gè)字母連在一起,形成一個(gè)大小為6的新等價(jià)類;再把后5個(gè)等價(jià)類中的第二個(gè)字母連在一起,形成一個(gè)大小為5的新等價(jià)類;以此類推;氐綐窍拢研碌牡葍r(jià)類區(qū)別出來(lái)。這樣,你就知道了每個(gè)數(shù)字對(duì)應(yīng)了哪一個(gè)原等價(jià)類的第幾個(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。你如何才能嚴(yán)格遵循藥方服用藥片,并且不能有任何的浪費(fèi)?
答案:把手上的三片藥各自切成兩半,分成兩堆擺放。再取出一粒藥片A,也把它切成兩半,然后在每一堆里加上半片的A,F(xiàn)在,每一堆藥片恰好包含兩個(gè)半片的A和兩個(gè)半片的B。一天服用其中一堆即可。
16、 你在一個(gè)飛船上,飛船上的計(jì)算機(jī)有n個(gè)處理器。突然,飛船受到外星激光武器的攻擊,一些處理器被損壞了。你知道有超過(guò)一半的處理器仍然是好的。你可以向一個(gè)處理器詢問(wèn)另一個(gè)處理器是好的還是壞的。一個(gè)好的處理器總是說(shuō)真話,一個(gè)壞的處理器總是說(shuō)假話。用n-2次詢問(wèn)找出一個(gè)好的處理器。
答案:給處理器從1到n標(biāo)號(hào)。用符號(hào)a->b表示向標(biāo)號(hào)為a的處理器詢問(wèn)處理器b是不是好的。首先問(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í)可以肯定這條鏈里的所有處理器都是好的;蛘,越來(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)了),因此詢問(wèn)次數(shù)不會(huì)超過(guò)n-2。
17、一個(gè)圓盤被涂上了黑白二色,兩種顏色各占一個(gè)半圓。圓盤以一個(gè)未知的速度、按一個(gè)未知的方向旋轉(zhuǎn)。你有一種特殊的相機(jī)可以讓你即時(shí)觀察到圓上的一個(gè)點(diǎn)的顏色。你需要多少個(gè)相機(jī)才能確定圓盤旋轉(zhuǎn)的方向?
答案:你可以把兩個(gè)相機(jī)放在圓盤上相近的兩點(diǎn),然后觀察哪個(gè)點(diǎn)先變色。事實(shí)上,只需要一個(gè)相機(jī)就夠了?刂葡鄼C(jī)繞圓盤中心順時(shí)針移動(dòng),觀察顏色多久變一次;然后讓相機(jī)以相同的速度逆時(shí)針繞著圓盤中心移動(dòng),再次觀察變色的頻率?梢詳喽,變色頻率較慢的那一次,相機(jī)的轉(zhuǎn)動(dòng)方向是和圓盤相同的。
18、有25匹馬,速度都不同,但每匹馬的速度都是定值。現(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è)谇?場(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,2,3,4,5
從現(xiàn)在所得到的信息,我們可以知道哪些馬已經(jīng)被排除在3名以外。只要已經(jīng)能確定有3匹或3匹以上的馬比這匹馬快,那么它就已經(jīng)被淘汰了?梢钥吹,只有上表中粗體藍(lán)色的那5匹馬才有可能為2、3名的。即:A組的2、3名;B組的1、2名,C組的第1名。取這5匹馬進(jìn)行第7場(chǎng)比賽,第7場(chǎng)比賽的前兩名就是25匹馬中的2、3名。故一共最少要賽7場(chǎng)。
這道題有一些變體,比如64匹馬找前4名。方法是一樣的,在得出第1名以后尋找后3名的候選競(jìng)爭(zhēng)者就可以了。
19、IBM筆試題:一普查員問(wèn)一女人,“你有多少個(gè)孩子,他們多少歲?”
女人回答:“我有三個(gè)孩子,他們的歲數(shù)相乘是36,歲數(shù)相加就等于旁邊屋的門牌號(hào)碼。“普查員立刻走到旁邊屋,看了一看,回來(lái)說(shuō):“我還需要多少資料。”女人回答:“我現(xiàn)在很忙,我最大的孩子正在樓上睡覺(jué)。”普查員說(shuō):”謝謝,我己知道了。”
問(wèn)題:那三個(gè)孩子的歲數(shù)是多少。
36 = 1 × 2 × 2 × 3 × 3
所有的可能為
1,1,36;sum = 38
1,2,18;sum = 21
1,3,12;sum = 16
1,4,9;sum = 14
1,6,6;sum = 13
2,2,9;sum = 13
2,3,6;sum = 11
3,3,4;sum = 10
由于普查員知道了年齡和之后還是不能確定每個(gè)孩子的年齡,所以可能性為
1,6,6;sum = 13
2,2,9;sum = 13
由于最大(暗含只有一個(gè)最大)的孩子在睡覺(jué),所以只可能是
2,2,9;sum = 13
20、有7克、2克砝碼各一個(gè),天平一只,如何只用這些物品三次將140克的鹽分成50、90克各一份?
答:第一步:把140克鹽分成兩等份,每份70克。
第二步:把天平一邊放上2+7克砝碼,另一邊放鹽,這樣就得到9克和61克分開(kāi)的鹽。
第三步:將9克鹽和2克砝碼放在天平一邊,另一邊放鹽,這樣就得到11克和50克。于是50和90就分開(kāi)了。
21、有三筐水果,一筐裝的全是蘋果,第二筐裝的全是橘子,第三筐是橘子與蘋果混在一起?鹕系臉(biāo)簽都是騙人的,(比如,如果標(biāo)簽寫的是橘子,那么可以肯定筐里不會(huì)只有橘子,可能還有蘋果)你的任務(wù)是拿出其中一筐,從里面只拿一只水果,然后正確寫出三筐水果的標(biāo)簽。
答:從貼有蘋果和橘子標(biāo)簽的筐中拿出一個(gè)水果,如果是蘋果,說(shuō)明這個(gè)筐中全是蘋果,那么貼蘋果標(biāo)簽的筐里裝的全是桔子,則貼有桔子標(biāo)簽的筐中裝的蘋果和桔子;如果拿出的一個(gè)水果是桔子,說(shuō)明這個(gè)筐中全是桔子,那么貼桔子標(biāo)簽的筐里裝的全是蘋果,貼蘋果標(biāo)簽的筐里裝的是蘋果和桔子。
22、題目如下:
0 1 2 3 4 5 6 7 8 9
_ _ _ _ _ _ _ _ _ _
在橫線上填寫數(shù)字,使之符合要求。
要求如下:對(duì)應(yīng)的數(shù)字下填入的數(shù),代表上面的數(shù)在下面出現(xiàn)的次數(shù),比如3下面是1,代表3要在下面出現(xiàn)一次。
正確答案是:0 1 2 3 4 5 6 7 8 9
6 2 1 0 0 0 1 0 0 0
http://fnhaliao.com/【程序員面試智力題】相關(guān)文章:
聯(lián)想面試的三道智力題07-19
intel筆試面試題目智力題附答案07-27
程序員面試技巧07-19
程序員面試技巧精選08-04
程序員的面試技巧07-24
給程序員的面試技巧09-25
面試程序員自我介紹程序員面試自我介紹12-18
變態(tài)智力題大串燒:微軟面試問(wèn)題(附答案)07-30
程序員面試技巧大全09-24