程序员面试智力题(1)
余年寄山水
909次浏览
2021年01月30日 02:03
最佳经验
本文由作者推荐
伤感的个性签名-口才
1.
考虑一个双人游戏。
游戏在一个圆桌上进行。
每个游戏者都有 足够多的硬
币。
他们需要在桌子上轮流放置硬币，
每次必需且只能放置一枚硬币，要求硬币
完全置于桌面内
（不能有一部分悬在桌子外面）
，
并且不能与原 来放过的硬币重
叠。
谁没有地方放置新的硬币，
谁就输了。
游戏的先行者还是 后行者有必胜策略？
这种策略是什么？
答案：先行者在桌子中心放 置一枚硬币，以后的硬币总是放在与后行者刚才
放的地方相对称的位置。这样，只要后行者能放，先行者 一定也有地方放。先行
者必胜。
2.
用线性时间和常数附加空间将一篇文章的单词（不是字符）倒序。
答案：
先将整篇文章的所有字符逆序
（从两头起不断交换位置相对称的字符）
；
然后用同样的办法将每个单词内部的字符逆序。
这样，
整篇文章的单词顺序颠倒
了， 但单词本身又被转回来了。
3.
用线性时间和常数附加空间将一个长度为
n
的字符串向左循环移动
m
位
（例如，
移动
3
位就变成了
）。
答案：把字符串切成长为< br>m
和
n-m
的两半。将这两个部分分别逆序，再对
整个字符串逆序。< br>
4.
一个矩形蛋糕，蛋糕内部有一块矩形的空洞。只用一刀，如何将蛋糕切 成
大小相等的两块？
答案：注意到平分矩形面积的线都经过矩形的 中心。过大矩形和空心矩形各
自的中心画一条线，
这条线显然把两个矩形都分成了一半，
它们的差当然也是相
等的。
5.
一块矩形的巧克力，初始时由
N x M
个小块组成。每一次你只能把一块
巧 克力掰成两个小矩形。最少需要几次才能把它们掰成
N x M
块
1x1
的小巧克
力？
答案：
N x M - 1
次显然足够了。这个数目也是必需的，因为每掰一次后当< br>前巧克力的块数只能增加一，把巧克力分成
N x M
块当然需要至少掰
N x M - 1
次。
6.
如何快速找出一个
32
位整数的二进制表达里有多少个
？用关于
的
个数的线性时间 ？
答案
1
（关于数字位数线性）：
for(n=0; b; b >>= 1) if (b & 1) n++;
答案
2
（关于
的个数线性）：
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)) == 0
9.
地球上有多少个点，使得从该点出发向南走一英里，向东走一英里，再向
北走一英里之后恰好回到了起点？
答案：
“
北极点”
是一个传统的答案，
其实这个问题还有其它的答案。
事实上，
满足要求 的点有无穷多个。所有距离南极点
1 + 1/(2π)
英里的地方都是满足要
求的， 向南走一英里后到达距离南极点
1/(2π)
的地方，向东走一英里后正好绕
行纬度圈 一周，
再向北走原路返回到起点。
事实上，
这仍然不是满足要求的全部
点。距 离南极点
1 + 1/(2kπ)
的地方都是可以的，其中
k
可以是任意一个正整
数。
10. A
、
B
两人分别在两座岛上。
B
生病了，
A
有
B
所需要的药。
C
有一艘小
船和一个可以上锁 的箱子。
C
愿意在
A
和
B
之间运东西，但东西只能放在箱子
里。只要箱子没被上锁，
C
都会偷走箱子里的东西，不管箱子里有什么。如果
A
和
B
各自有一把锁和只能开自己那把锁的钥匙，
A
应该如何把东西 安全递交给
B
？
答案：
A
把药放进箱子 ，用自己的锁把箱子锁上。
B
拿到箱子后，再在箱子
上加一把自己的锁。箱子运回A
后，
A
取下自己的锁。箱子再运到
B
手中时，
B取下自己的锁，获得药物。
11.
一对夫妇邀请
N-1对夫妇参加聚会（因此聚会上总共有
2N
人）。每个
人都和所有自己不认识的人握 了一次手。然后，男主人问其余所有人（共
2N-1
个人）
各自都握了几次手，
得到的答案全部都不一样。
假设每个人都认识自己的
配偶，那么女主人握了几次手？
答案：握手次数只可能是从
0
到
2N-2
这
2N-1
个数。除去男主人外，一共
有
2N-1
个人，因此每个数恰好出现 了一次。其中有一个人
(0)
没有握手，有一
个人
(2N-2)
和所 有其它的夫妇都握了手。这两个人肯定是一对夫妻，否则后者
将和前者握手
（从而前者的握手次 数不再是
0
）
。
除去这对夫妻外，
有一个人
(1)
只与
(2N-2)
握过手，有一个人
(2N-3)
和除了
(0)以外的其它夫妇都握了手。这
两个人肯定是一对夫妻，
否则后者将和前者握手
（从 而前者的握手次数不再是
1
）
。
以此类推，直到握过
N-2
次手的人和握过
N
次手的人配成一对。此时，除了男
主人及其配偶以外，
其余 所有人都已经配对。
根据排除法，
最后剩下来的那个握
手次数为
N-1
的人就是女主人了。
12.
两个机器人，初始时位于数轴上的不 同位置。给这两个机器人输入一段相
同的程序，
使得这两个机器人保证可以相遇。
程序 只能包含
“
左移
n
个单位
”
、
“
右
移
n
个单位
”
，条件判断语句
If
，循环语句
w hile
，
以及两个返回
Boolean
值的
函数
“
在自己的起点处
”
和
“
在对方的起点处
”
。你不能使用其 它的变量和计数器。
答案：两个机器人同时开始以单位速度右移，直到一个 机器人走到另外一个
机器人的起点处。然后，该机器人以双倍速度追赶对方。程序如下。
while(!at_other_robots_start) {
move_right 1
}
while(true) {
move_right 2
}
13.
如果叫你从下面两种游戏中选择一种，你选择哪一种？为什么？
a.
写下一句话。如果这句话为真，你将获得
10
美元；如果这句话为假，
你获得 的金钱将少于
10
美元或多于
10
美元（但不能恰好为
10
美元）。
b.
写下一句话。不管这句话的真假，你都会得到多于
10
美元的钱。
答案：选择第一种游戏，并写下
“
我既不会得到
10
美元，也不会得 到
10000000
美元
”
。
14.
你在一幢
100
层大楼下，有
21
根电线线头标有数字
1. .21
。这些电线
一直延伸到大楼楼顶，楼顶的线头处标有字母
A..U
。你 不知道下面的数字和上
面的字母的对应关系。你有一个电池，一个灯泡，和许多很短的电线。如何只上< br>下楼一次就能确定电线线头的对应关系？
答案：在下面把
2 ,3
连在一起，把
4
到
6
全连在一起，把
7
到10
全连在一
起，
等等，
这样你就把电线分成了
6
个< br>“
等价类
”
，
大小分别为
1, 2, 3, 4, 5, 6
。
然后到楼顶，
测出哪根线和其它所有电线都不相连，
哪些线和另外一根相连 ，
哪
些线和另外两根相连，等等，从而确定出字母
A..U
各属于哪个等价类 。现在，
把每个等价类中的第一个字母连在一起，形成一个大小为
6
的新等价类；再把
后
5
个等价类中的第二个字母连在一起，形成一个大小为
5
的新等价 类；以此
类推。回到楼下，把新的等价类区别出来。这样，你就知道了每个数字对应了哪
一个原 等价类的第几个字母，从而解决问题。
15.
某种药方要求非常严格，你 每天需要同时服用
A
、
B
两种药片各一颗，
不能多也不能少。这种药 非常贵，你不希望有任何一点的浪费。一天，你打开装
药片
A
的药瓶，倒出一粒药片放 在手心；然后打开另一个药瓶，但不小心倒出
了两粒药片。现在，你手心上有一颗药片
A
，两颗药片
B
，并且你无法区别哪个
是
A
，哪个是
B。你如何才能严格遵循药方服用药片，并且不能有任何的浪费？
答案： 把手上的三片药各自切成两半，分成两堆摆放。再取出一粒药片
A
，
也把它切成两半， 然后在每一堆里加上半片的
A
。现在，每一堆药片恰好包含两
个半片的
A和两个半片的
B
。一天服用其中一堆即可。
16.
你在一个飞船上，飞船上的计算机有
n
个处理器。突然，飞船受到外星
激光武器的攻击 ，
一些处理器被损坏了。
你知道有超过一半的处理器仍然是好的。
你可以向一个处理器 询问另一个处理器是好的还是坏的。
一个好的处理器总是说
真话，一个坏的处理器总是说假话。 用
n-2
次询问找出一个好的处理器。
答案：给处理器从
1
到
n
标号。用符号
a->b
表示向标号为
a的处理器询问
处理器
b
是不是好的。首先问
1->2
，如果1
说不是，就把他们俩都去掉（去掉
了一个好的和一个坏的，
则剩下的处理器中好 的仍然过半）
，
然后从
3->4
开始
继续发问。如果
1说
2
是好的，就继续问
2->3
，
3->4
，
……
直到某一次
j
说
j+1
是坏的，把
j
和
j+1
去掉，然后问
j-1 -> j+2
；或者从
j+2 -> j+3
开始
发问，如果前面已经没有
j-1
了（之前已经被去掉过了）。注意到你始 终维护着
这样一个
“
链
”
，
前面的每一个处理器都说后面那 个是好的。
这条链里的所有处理