程序员有趣的面试智力题

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))