IT邏輯面試題

1、.你的丈夫有外遇嗎一座小鎮(zhèn)里有100對(duì)夫婦，他們都遵守一個(gè)奇怪的風(fēng)俗：如果妻子發(fā)現(xiàn)丈夫背叛了她，那她就會(huì)在當(dāng)天夜里殺死自己的丈夫。小鎮(zhèn)里的女人都知道別人丈夫 的秘密，卻不會(huì)說(shuō)出來(lái)。換言之，每個(gè)女人只知道除自己丈夫之外其他男人的外遇情況。突然有一天鎮(zhèn)長(zhǎng)宣布，至少有一個(gè)男人背叛了他的妻子，假設(shè)鎮(zhèn)長(zhǎng)說(shuō)的是真 話，所有人都相信鎮(zhèn)長(zhǎng)所說(shuō)的，那么接下來(lái)將會(huì)發(fā)生什么？我們不妨先假設(shè)只有1個(gè)男人背叛了他的妻子，這時(shí)那個(gè)男人的妻子會(huì)猛然發(fā)現(xiàn)自己竟然不知道任何男人有外遇的消息（而其他99個(gè)女人知道的都是1個(gè)男 人背叛了自己的妻子，即真相），對(duì)此唯一的解釋便是有且只有一個(gè)有外遇的男人，就是自己的丈夫。所以她會(huì)在當(dāng)天

2、夜里殺死自己的丈夫。然后，沒有然后了。那如果有2個(gè)男人呢？這時(shí)小鎮(zhèn)里有98個(gè)女人知道真相，但另外2個(gè)女人只知道1個(gè)男人有外遇，并不能確定自己的丈夫是否也有外遇。所以在鎮(zhèn)長(zhǎng)宣布此 事的當(dāng)天，全鎮(zhèn)相安無(wú)事。但到了第2天，當(dāng)這2個(gè)女人發(fā)現(xiàn)對(duì)方都未處死自己的老公時(shí)，就會(huì)意識(shí)到不止一個(gè)男人有外遇了。那便是有2個(gè)男人有外遇，這樣的 話，其中1個(gè)肯定是自己的丈夫。于是，這2個(gè)女人會(huì)同時(shí)在夜里處死自己的丈夫。以此類推，很容易歸納出來(lái)，如果小鎮(zhèn)里有n個(gè)不忠的丈夫，他們都會(huì)在鎮(zhèn)長(zhǎng)宣布后的第n天夜里被處死。實(shí)際上，有時(shí)候雖然只有極少量的信息，但只要仔細(xì)分析，一樣可以得出有效的結(jié)論。上述這個(gè)謎題相信有很多人見過，類似

3、的還有著名的 藍(lán)眼睛島問題 ，只是這個(gè)更加復(fù)雜一點(diǎn)。隔離監(jiān)獄中的100個(gè)犯人在一所監(jiān)獄中，關(guān)押了100個(gè)相互隔離的犯人。典獄長(zhǎng)每天隨機(jī)選擇一名犯人（他可能被重復(fù)選中多次），扔到一間小黑屋中關(guān)禁閉。這個(gè)房間中只有一個(gè) 電燈和開關(guān)，除了小黑屋中的人，誰(shuí)都看不到這盞燈，更無(wú)法控制它。關(guān)進(jìn)去的人則可以打開或關(guān)閉電燈，也可以選擇什么都不干。犯人們隨時(shí)可以叫停這場(chǎng)游戲并 告訴典獄長(zhǎng)：“所有犯人都被關(guān)過小黑屋。”如果這句話是真的，所有犯人將會(huì)被釋放；但如果這句話是假的，他們?nèi)繒?huì)被處死。在游戲開始前，犯人們被允許聚 在一起商議對(duì)策，他們?cè)撛趺醋霾拍鼙ＷC自己一定能夠被釋放呢？首先我們隨意選擇一個(gè)犯人A作為計(jì)數(shù)

4、者。現(xiàn)在讓除了A以外的任何一個(gè)犯人進(jìn)入小黑屋后，都將嚴(yán)格遵循下面這個(gè)法則：如果他以前從來(lái)沒有打開過這盞電燈，并且現(xiàn)在這盞電燈是關(guān)著的，那么打開它，除此以外不作任何事情。而如果典獄長(zhǎng)選擇的是A，并且當(dāng)他進(jìn)入這個(gè)房間 以后房間里的電燈是開著的，那么他就把電燈關(guān)掉，并在自己的計(jì)數(shù)里加1。當(dāng)他的計(jì)數(shù)達(dá)到99之日（從1開始），便是所有犯人重獲自由之時(shí)。工作分金問題有個(gè)工人將為你工作七天，你用一塊金條來(lái)支付工資。每天工作結(jié)束以后你都要給工人發(fā)工資，但你只能在這塊金條上折兩次。應(yīng)該如何選擇金條上的折斷位置，以及支付工資的方法？這個(gè)問題并不困難，但如果工人為你工作X天，你該怎么分割這塊金條呢？讓我們先來(lái)回答最

5、初的問題，為讀者做個(gè)啟發(fā)。把金條分成如下三份：第一份是原金條的 17（編號(hào)為1號(hào)金條）；第二份是原金條的 27（2號(hào)金條）；第三份是 47（3號(hào)金條）。接下來(lái)的7天你將這樣支付工資：第1天：給工人1號(hào)金條（此時(shí)你有2號(hào)和3號(hào)金條，工人有1號(hào)金條）第2天：給工人2號(hào)金條，并取回1號(hào)金條（此時(shí)你有1號(hào)和3號(hào)金條，工人有2號(hào)金條）第3天：給工人1號(hào)金條（此時(shí)你有3號(hào)金條，工人有1號(hào)和2號(hào)金條）第4天：給工人3號(hào)金條，并取回1號(hào)和2號(hào)金條（此時(shí)你有1號(hào)和2號(hào)金條，工人有3號(hào)金條）第5天：給工人1號(hào)金條（此時(shí)你有2號(hào)金條，工人有1號(hào)和3號(hào)金條）第6天：給工人2號(hào)金條，并取回1號(hào)金條（此時(shí)你有1號(hào)金條，工

6、人有2號(hào)和3號(hào)金條）第7天：給工人1號(hào)金條，事成收工。有過一些編程經(jīng)驗(yàn)的讀者可能會(huì)馬上意識(shí)到，這其實(shí)正是二進(jìn)制的原理。 1，2，4 三個(gè)十進(jìn)制數(shù)的二進(jìn)制形式分別是 1，10，100，用這三個(gè)數(shù)可以表示 0，7 區(qū)間（換成二進(jìn)制形式即 000，111 區(qū)間）里的所有整數(shù)。同樣的道理可以計(jì)算出，如果有工人為你工作X天，而你依然打算用一塊金條來(lái)支付工資的話，那么最少需要在金條上折斷（ log 2 X+1 - 1 ） 處。尋找次品你有10只裝滿了球的盒子，其中有一只盒子里裝的是次品。已知正常的球每個(gè)重 10g，而次品球每個(gè)重 9g。如何只使用一次電子秤，就找出哪只盒子裝的是次品？我們?cè)诿鎸?duì)這類稱重找次

7、品的問題時(shí)，第一想法通常是從每個(gè)盒子中拿出一個(gè)球來(lái)稱重。然而，這道題的關(guān)鍵恰恰是從不同的盒子里取出不同數(shù)目的球。我們先把 10 只盒子從 0 到 9 編號(hào)，然后從每只盒子中取出與這只盒子編號(hào)數(shù)目相等的球來(lái)，舉例來(lái)說(shuō)，0號(hào)盒子里不需要取球， 1 號(hào)盒子里拿出 1 只球， 2 號(hào)盒子里拿出 2 只球，等等。然后我們這些球一起放到電子秤上。假如所有的球都是正品，那么電子秤上的讀數(shù)應(yīng)該是450g；但是因?yàn)檫@堆球里可能有次品，所以實(shí)際讀數(shù)是 ( 450 - x )g ，其中x是次品球的個(gè)數(shù)，同時(shí)這個(gè)個(gè)數(shù)又恰好次品盒子的編號(hào)。過橋問題四個(gè)人需要在夜間度過一座搖搖晃晃的吊橋。不幸的是，他們只有一個(gè)火把，而這

8、座橋又太危險(xiǎn)了，他們無(wú)法在不借助火把的情況下度過這座危橋。而更不幸 的是，這座橋又不怎么結(jié)實(shí)，最多允許兩個(gè)人同時(shí)度橋。四個(gè)人過橋的速度各不相同，分別是：1分鐘，2分鐘，7分鐘，10分鐘。顯然，兩人同時(shí)度橋，耗時(shí)就 取決于最慢的人。那么，他們?nèi)慷冗^這座橋所需的時(shí)間最短是多少？大部分人的第一想法往往是利用一個(gè)最快的人反復(fù)度橋來(lái)接送其他人，這樣需要的時(shí)間是 2 + 1 + 7 + 1 + 10 = 21 分鐘。的確很快，但是實(shí)際上還有更快的方法。很容易想到的是，我們應(yīng)該能讓 7 和 10 一起過橋。但是接下來(lái)呢？難道讓其中1個(gè)人再回去一趟嗎？不，這樣的話就太耗時(shí)了。如何解決這個(gè)問題呢？我們可以提前

9、讓1個(gè)腳程較快的家伙在橋的對(duì)岸等著。因此就有方案如下：先讓 1 和 2 一起過橋。耗時(shí)2分鐘。讓 1 拿著火把回來(lái)。耗時(shí)1分鐘。讓 7 和 10 一起過橋，耗時(shí)10分鐘。讓 2 拿著火把回來(lái)。耗時(shí)2分鐘。最后再讓 1 和 2 一起過橋。耗時(shí)2分鐘。最后總耗時(shí)為 2 + 1 + 10 + 2 + 2 = 17 分鐘。表針問題一天中時(shí)鐘的時(shí)針和分針重疊幾次？直覺也許會(huì)告訴你24次，但事實(shí)并非如此，我們不妨來(lái)算一下。當(dāng)分針和時(shí)針從 12：00 處開始走動(dòng)后，T個(gè)小時(shí)的時(shí)間里時(shí)鐘的分針走T圈，時(shí)針則是 T12 圈，兩個(gè)表針第一次重合的時(shí)候分針比時(shí)針領(lǐng)先整整一圈，也就是 T = T12 + 1 ，此時(shí)

10、T = 1211 ，也就是表針在 1211 時(shí)（比 1：05 稍微晚一些）第一次重疊。把重疊的次數(shù)換成N，然后把式子中的T換成24，我們就可以得到：24=2+N顯然，N=22即兩個(gè)表針在一天內(nèi)重疊22次。它們從來(lái)不會(huì)在上午或者下午的11點(diǎn)重合，因?yàn)樗鼈円瑫r(shí)到達(dá)表盤的12點(diǎn)方向?？吹竭@里，各位讀者是對(duì)打進(jìn)微軟內(nèi)部更有把握了呢？汽車加油：一輛載油500升的汽車從A開往1000公里外的B，已知汽車每公里耗油量為1升 (2010-10-09 09:35:34)轉(zhuǎn)載標(biāo)簽： 雜談分類： 腦子轉(zhuǎn)轉(zhuǎn)問題：一輛載油 500升的汽車從A開往1000公里外的B，已知汽車每公里耗油量為1升，A處有無(wú)窮多的油，其他任

11、何地點(diǎn)都沒有油，但該車可以在任何地點(diǎn)存放油以備中轉(zhuǎn)，問從A到B最少需要多少油？ 解決方法：1） 將A到B的距離進(jìn)行8等分；若汽車到達(dá)第四點(diǎn)，即500公里時(shí)，油箱中有500升油即可到達(dá)B點(diǎn)，此時(shí)，汽車用油量最少。2） 從開始到第一點(diǎn)，需要汽車第一次從開始裝500升油，到達(dá)第一點(diǎn)，將郵箱中的250升油放到第一點(diǎn)，此時(shí)，汽車從開始到達(dá)第一點(diǎn)已經(jīng)用了125升油，剩下125升，可以回到出發(fā)點(diǎn)，以此類推，汽車要從開始點(diǎn)12次裝500升油，直到第12次，不用回去，直接在從第一點(diǎn)到達(dá)第二點(diǎn)，以此類推，到達(dá)第四點(diǎn)汽車正好有500升油可以使用，因此，12個(gè)500升油，一共是6000升油。在此過程中，在第一點(diǎn)的汽車

12、剩余油量是3125升，在第二點(diǎn)的汽車剩余油量是1500升，在第三點(diǎn)的汽車剩余油量是875升，在第四點(diǎn)的汽車剩余油量是500升，正好在第四點(diǎn)剩余500升，可以完成后續(xù)的路程，到達(dá)B點(diǎn)。微軟面試題：飛機(jī)加油問題2010-02-05 19:34已知（1）每個(gè)飛機(jī)只有一個(gè)油箱；（2）飛機(jī)之間可以相互加油(注意是相互，沒有加油機(jī)) ；（3）一箱油可供一架飛機(jī)繞地球飛半圈。那么為使至少一架飛機(jī)繞地球一圈回到起飛時(shí)的飛機(jī)場(chǎng)，至少需要出動(dòng)幾架飛機(jī)?(所有飛機(jī)從同一機(jī)場(chǎng)起飛，而且必須安全返回機(jī)場(chǎng)，不允許中途降落，中間沒有飛機(jī)場(chǎng))解答：3架飛機(jī)5架次。具體飛法：ABC 3架同時(shí)起飛，1/8處，C給AB加滿油，C返

13、航，1/4處，B給A加滿油，B返航，A到達(dá)1/2處，C從機(jī)場(chǎng)往另一方向起飛，3/4處，C同已經(jīng)空油箱的A平分剩余油量，同時(shí)B從機(jī)場(chǎng)起飛，AC到7/8處同B平分剩余油量，剛好3架飛機(jī)同時(shí)返航。所以是3架飛機(jī)5架次。微軟面試題：給出一種洗牌算法2010-02-28 22:09給出洗牌的一個(gè)算法，并將洗好的牌存儲(chǔ)在一個(gè)整形數(shù)組里。假設(shè)數(shù)組Card0 - 53中的54個(gè)數(shù)對(duì)應(yīng)54張牌，從第一張牌（i = 0）開始直到倒數(shù)第二張牌（i = 52），每次生成一個(gè) i, 53之間的數(shù)r，將Cardi和Cardr中的數(shù)互換。微軟面試題：找到兩個(gè)單向鏈表的第一個(gè)公共節(jié)點(diǎn)2010-02-24 20:37兩個(gè)單向鏈

14、表，可能存在公共節(jié)點(diǎn)。如何判斷是否存在公共節(jié)點(diǎn)，并找出它們的第一個(gè)公共結(jié)點(diǎn)。如果兩個(gè)單向鏈表有公共節(jié)點(diǎn)，則兩個(gè)鏈表會(huì)構(gòu)成Y型結(jié)構(gòu)，最后一個(gè)節(jié)點(diǎn)相同。我們可以從頭開始遍歷兩個(gè)鏈表，找到最后一個(gè)節(jié)點(diǎn)的指針，設(shè)為p_a，p_b。同時(shí)記錄下兩個(gè)鏈表的長(zhǎng)度len_a，len_b（假設(shè)len_a = len_b)。如果p_a = p_b，則說(shuō)明兩個(gè)鏈表有公共節(jié)點(diǎn)，否則沒有。如果有公共節(jié)點(diǎn)，則第一個(gè)公共節(jié)點(diǎn)距起始節(jié)點(diǎn)的距離滿足 len_a - start_a = len_b - start_b。所以第一個(gè)可能的公共節(jié)點(diǎn)距起始節(jié)點(diǎn)的距離是 len_a - len_b, 0。我們從這兩個(gè)節(jié)點(diǎn)開始比較，直到找到第一個(gè)公共節(jié)點(diǎn)。微軟面試題：如何在鏈表里如何發(fā)現(xiàn)循環(huán)鏈接?2010-02-05 19:38如何在鏈表里如何發(fā)現(xiàn)循環(huán)鏈接?解答： 從鏈表的開始處，由兩個(gè)指針A和B同時(shí)開始遍歷鏈表。指針A每向前移動(dòng)一步，指針B都向前移動(dòng)兩步。如果在移動(dòng)了N步以后，指針A和B指向了同一個(gè)節(jié)點(diǎn)，則此鏈表中存在循環(huán)鏈表。分析：當(dāng)然還可以在遍歷的過程中存儲(chǔ)節(jié)點(diǎn)的地址，通過不斷的比較地址來(lái)判斷有沒有循環(huán)鏈表。但這種算法會(huì)使用更多的內(nèi)存。如果考官比較變態(tài)，還可以直接考復(fù)制鏈表。如果復(fù)制前沒有測(cè)試循環(huán)鏈表，那不好意思，只能扣分了。微軟面試題：刪除鏈表中的重復(fù)項(xiàng)一個(gè)沒有排序的鏈表，比如list=a,