程序員有趣的面試智力題及答案

2024年3月29日發(作者：寫景的片段)

程序員有趣的面試智力題及答案

1、考慮一個雙人游戲。游戲在一個圓桌上進行。每個游戲者都

有足夠多的硬幣。他們需要在桌子上輪流放置硬幣，每次必需且

只能放置一枚硬幣，要求硬幣完全置于桌面內（不能有一部分

懸在桌子外面），并且不能與原來放過的硬幣重疊。誰沒有地方

放置新的硬幣，誰就輸了。游戲的先行者還是后行者有必勝策

略？這種策略是什么？

答案：先行者在桌子中心放置一枚硬幣，以后的硬幣總是放在與

后行者剛才放的地方相對稱的位置。這樣，只要后行者能放，先

行者一定也有地方放。先行者必勝。

2、用線性時間和常數附加空間將一篇文章的單詞（不是字符）

倒序。

答案：先將整篇文章的所有字符逆序（從兩頭起不斷交換位置相

對稱的字符）；然后用同樣的辦法將每個單詞內部的字符逆序。

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

3、用線性時間和常數附加空間將一個長度為n的字符串向左循

環移動m位（例如，"abcdefg"移動3位就變成了"defgabc"）。

答案：把字符串切成長為m和n-m的兩半。將這兩個部分分別逆

序，再對整個字符串逆序。

4、一個矩形蛋糕，蛋糕內部有一塊矩形的空洞。只用一刀，如

何將蛋糕切成大小相等的兩塊？

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

空心矩形各自的中心畫一條線，這條線顯然把兩個矩形都分成了

一半，它們的差當然也是相等的。

5、一塊矩形的巧克力，初始時由NxM個小塊組成。每一次你

只能把一塊巧克力掰成兩個小矩形。最少需要幾次才能把它們掰

成NxM塊1x1的小巧克力？

答案：NxM-1次顯然足夠了。這個數目也是必需的，因為每

掰一次后當前巧克力的塊數只能增加一，把巧克力分成NxM

塊當然需要至少掰NxM-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)的時間找出