程序员有趣的面试智力题及答案

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)的时间找出