程序員有趣的面試智力題

2024年3月29日發(作者：作家老舍)

程序員有趣的面試智力題

1、考慮一個雙人游戲。游戲在一個圓桌上進行。每個游戲者都有足夠多的硬幣。他

們需要在桌子上輪流放置硬幣，每次必需且只能放置一枚硬幣，要求硬幣完全置 于桌面

內(不能有一部分懸在桌子外面)，并且不能與原來放過的硬幣重疊。誰沒有地方放置新的

硬幣，誰就輸了。游戲的先行者還是后行者有必勝策略,這種策略 是什么, 答案:先行者在

桌子中心放置一枚硬幣，以后的硬幣總是放在與后行者剛才放的地方相對稱的位置。這

樣，只要后行者能放，先行者一定也有地方放。先行者必勝。

2、 用線性時間和常數附加空間將一篇文章的單詞(不是字符)倒序。 答案:先將整篇文

章的所有字符逆序(從兩頭起不斷交換位置相對稱的字符);然后用同樣的辦法將每個單詞內

部的字符逆序。這樣，整篇文章的單詞順序顛倒了，但單詞本身又被轉回來了。

3、 用線性時間和常數附加空間將一個長度為n的字符串向左循環移動m位(例如，

"abcdefg"移動3位就變成了"defgabc")。

答案:把字符串切成長為m和n-m的兩半。將這兩個部分分別逆序，再對整個字符串

逆序。

4、一個矩形蛋糕，蛋糕內部有一塊矩形的空洞。只用一刀，如何將蛋糕切成大小相

等的兩塊,

答案:注意到平分矩形面積的線都經過矩形的中心。過大矩形和空心矩形各自的中心

畫一條線，這條線顯然把兩個矩形都分成了一半，它們的差當然也是相等的。

5、 一塊矩形的巧克力，初始時由N x M個小塊組成。每一次你只能把一塊巧克力

掰成兩個小矩形。最少需要幾次才能把它們掰成N x M塊1x1的小巧克力, 答案:N x M -

1次顯然足夠了。這個數目也是必需的，因為每掰一次后當前巧克力的塊數只能增加一，

把巧克力分成N x M塊當然需要至少掰N x M - 1次。

6、如何快速找出一個32位整數的二進制表達里有多少個"1",用關于"1"的個數的線

性時間,

答案1(關于數字位數線性):for(n=0; b; b >>= 1) if (b & 1) n++;

答案2(關于"1"的個數線性):for(n=0; b; n++) b &= b-1;

7、 一個大小為N的數組，所有數都是不超過N-1的正整數。用O(N)的時間找出重

復的那個數(假設只有一個)。一個大小為N的數組，所有數都是不超過N+1的正整數。

用O(N)的時間找出沒有出現過的那個數(假設只有一個)。

答案:計算數組中的所有數的和，再計算出從1到N-1的所有數的和，兩者之差即為

重復的那個數。計算數組中的所有數的和，再計算出從1到N+1的所有數的和，兩者之

差即為缺少的那個數。

8、 給出一行C語言表達式，判斷給定的整數是否是一個2的冪。 答案:(b & (b-1))