2022年程序员面试智力题 .pdf

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) = 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 取下自己的锁，获得药物。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 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 ，循环语句 while ，以及两个返回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 。你不知道下面的数字和上面的字母的对应关系。你有一个电池，一个灯泡，和许多很短的电线。如何只上下楼一次就能确定电线线头的对应关系？答案：在下面把2,3 连在一起，把4 到 6 全连在一起，把7 到 10 全连在一起，等等，这样你就把电线分成了6 个“ 等价类 ” ，大小分名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 别为 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 了（之前已经被去掉过了）。注意到你始终维护着这样一个“ 链” ，前面的每一个处理器都说后面那个是好的。这条链里的所有处理器要么都是好的，要么都是坏的。当这条链越来越长，剩下的处理器越来越少时，总有一个时候这条链超过了剩下的处理器的一半，此时可以肯定这条链里的所有处理器都是好的。或者，越来越多的处理器都被去掉了，链的长度依旧为0，而最后只剩下一个或两个处理器没被问过，那他们一定就是好的了。另外注意到，第一个处理器的好坏从来没被问过，仔细想想你会发现最后一个处理器的好坏也不可能被问到（一旦链长超过剩余处理器的一半，或者最后没被去掉的就只剩这一个了时，你就不问了），因此询问次数不会超过 n-2 。 17. 一个圆盘被涂上了黑白二色，两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向？答案：你可以把两个相机放在圆盘上相近的两点，然后观察哪个点先变色。事实上，只需要一个相机就够了。控制相机绕圆盘中心顺时针移动，观察颜色多久变一次；然后让相机以相同的速度逆时针绕着圆盘中心移动，再次观察变色的频率。可以断定，变色频率较慢的那一次，相机的转动方向是和圆盘相同的。今天考完美国结构语言学，稍微轻松了一些。我把前几天向大家推荐的网页好好看了一遍，挑选了10 个比较精彩的、不是很常见的、本Blog 之前没有提过的智力题，并且把它们都整理到了一起，与大家一同分享。希望大家能够大呼过瘾 1. 给一个瞎子52 张扑克牌，并告诉他里面恰好有10 张牌是正面朝上的。要求这个瞎子把牌分成两堆，使得每堆牌里正面朝上的牌的张数一样多。瞎子应该怎么做？答案：把扑克牌分成两堆，一堆10 张，一堆42 张。然后，把小的那一堆里的所有牌全部翻过来。2. 如何用一枚硬币等概率地产生一个1 到 3 之间的随机整数？如果这枚硬币是不公正的呢？答案：如果是公正的硬币，则投掷两次，“ 正反 ” 为 1 ，“ 反正 ” 为 2，“ 正正 ” 为 3 ，“ 反反 ” 重来。如果是不公正的硬币，注意到出现“ 正反 ” 和 “ 反正 ” 的概率一样，因此令“ 正反反正 ” 、“ 反正正反 ” 、“ 正反正反 ” 分别为 1、2、3 ，其余情况重来。另一种更妙的办法是，投掷三次硬币，“ 正反反 ” 为 1，“ 反正反 ” 为 2，“ 反反正 ” 为 3，其余情况重来。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 3. 30枚面值不全相同的硬币摆成一排，甲、乙两个人轮流选择这排硬币的其中一端，并取走最外边的那枚硬币。如果你先取硬币，能保证得到的钱不会比对手少吗？答案：先取者可以让自己总是取奇数位置上的硬币或者总是取偶数位置上的硬币。数一数是奇数位置上的面值总和多还是偶数位置上的面值总和多，然后总是取这些位置上的硬币就可以了。4. 一个环形轨道上有n 个加油站，所有加油站的油量总和正好够车跑一圈。证明，总能找到其中一个加油站，使得初始时油箱为空的汽车从这里出发，能够顺利环行一圈回到起点。答案：总存在一个加油站，仅用它的油就足够跑到下一个加油站（否则所有加油站的油量加起来将不够全程）。把下一个加油站的所有油都提前搬到这个加油站来，并把油已被搬走的加油站无视掉。在剩下的加油站中继续寻找油量足以到达下个加油站的地方，不断合并加油站，直到只剩一个加油站为止。显然从这里出发就能顺利跑完全程。另一种证明方法：先让汽车油箱里装好足够多的油，随便从哪个加油站出发试跑一圈。车每到一个加油站时，记录此时油箱里剩下的油量，然后把那个加油站的油全部装上。试跑完一圈后，检查刚才路上到哪个加油站时剩的油量最少，那么空着油箱从那里出发显然一定能跑完全程。5. 初始时，两个口袋里各有一个球。把后面的n-2 个球依次放入口袋，放进哪个口袋其概率与各口袋已有的球数成正比。这样下来，球数较少的那个口袋平均期望有多少个球？答案：先考虑一个看似无关的问题 怎样产生一个1 到 n 的随机排列。 首先，在纸上写下数字1 ； 然后，把 2 写在 1 的左边或者右边；然后，把 3 写在最左边，最右边，或者插进1 和 2 之间 总之，把数字i 等概率地放进由前面i-1 个数产生的（包括最左端和最右端在内的）共i 个空位中的一个。这样生成的显然是一个完全随机的排列。我们换一个角度来看题目描述的过程：假想用一根绳子把两个球拴在一起，把这根绳子标号为1。接下来，把其中一个小球分裂成两个小球， 这两个小球用标号为2 的绳子相连。 总之， 把 “ 放进第 i 个球 ” 的操作想象成把其中一个球分裂成两个用标有i-1 的绳子相连的小球。联想我们前面的讨论，这些绳子的标号事实上是一个随机的全排列，也就是说最开始绳子1 的位置最后等可能地出现在每个地方。也就是说，它两边的小球个数(1,n-1)、 (2,n-2)、(3,n-3)、(n-1,1)这 n-1种情况等可能地发生。因此，小袋子里的球数大约为n/4个。准确地说，当n 为奇数时，小袋子里的球数为(n+1)/4；当 n 为偶数时，小袋子里的球数为n2/(4n-4)。6. 考虑一个n*n 的棋盘，把有公共边的两个格子叫做相邻的格子。初始时，有些格子里有病毒。每一秒钟后，只要一个格子至少有两个相邻格子染上了病毒，那么他自己也会被感染。为了让所有的格子都被感染，初始时最少需要有几个带病毒的格子？给出一种方案并证明最优性。答案：至少要n 个，比如一条对角线上的n 个格子。 n 个格子也是必需的。当一个新的格子被感染后，全体被感染的格子所组成的图形的周长将减少0 个、 2 个或 4 个单位（具体减少了多少要看它周围被感染的格子有多少个）。又因为当所有格子都被感染后，图形的周长为 4n ，因此初始时至少要有n 个被感染的格子。7. 在一个 m*n的棋盘上，有k 个格子里放有棋子。是否总能对所有棋子进行红蓝二染色，使得每行每列的红色棋子和蓝色棋子最多差一个？答案：可以。建一个二分图G(X,Y) ，其中 X 有 m 个顶点代表了棋盘的m 个行， Y 有 n 个顶点代表了棋盘的n 个列。第i 行第 j 列有棋子就在 X(i) 和 Y(j) 之间连一条边。先找出图G 里的所有环（由于是二分图，环的长度一定是偶数），把环里的边红蓝交替染色。剩下的没染色的图一定是一些树。对每棵树递归地进行操作：去掉一个叶子节点和对应边，把剩下的树进行合法的红蓝二染色，再把刚才去掉的顶点和边加回去，给这个边适当的颜色以满足要求。8. 任意给一个8*8的 01 矩阵，你每次只能选一个3*3或者 4*4的子矩阵并把里面的元素全部取反。是否总有办法把矩阵里的所有数全部变为1？答案：不能。大矩阵中有36 个 3*3的小矩阵和25 个 4*4 的小矩阵，因此总共有61 种可能的操作。显然，给定一个操作序列，这些操作的先后顺序是无关紧要的；另外，在一个操作序列中使用两种或两种以上相同的操作也是无用的。因此，实质不同的操作序列只有261种。但 8*8的 01 矩阵一共有264种，因此不是每种情况都有办法达到目的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 9. 五个洞排成一排，其中一个洞里藏有一只狐狸。每个夜晚，狐狸都会跳到一个相邻的洞里；每个白天，你都只允许检查其中一个洞。怎样才能保证狐狸最终会被抓住？答案：按照2, 3, 4, 2, 3, 4的顺序检查狐狸洞可以保证抓住狐狸。为了说明这个方案是可行的，用集合F 表示狐狸可能出现的位置，初始时 F = 1, 2, 3, 4, 5。如果它不在2 号洞，则第二天狐狸已经跑到了F = 2, 3, 4, 5。如果此时它不在3 号洞，则第三天狐狸一定跑到了F = 1, 3, 4, 5。 如果此时它不在4 号洞，则再过一晚后F = 2, 4。 如果此时它不在2 号洞，则再过一天F = 3, 5。如果此时它不在3 号洞，再过一天它就一定跑到4 号洞了。方案不是唯一的，下面这些方案都是可行的：2, 3, 4, 4, 3, 2 4, 3, 2, 2, 3, 4 4, 3, 2, 4, 3, 2 10. 一个经典老题是说，把一个3*3*3的立方体切成27 个单位立方体，若每一刀切完后都允许重新摆放各个小块的位置，最少可以用几刀？答案仍然是6 刀， 因为正中间那个单位立方体的6 个面都是后来才切出来的，因此怎么也需要6 刀。 考虑这个问题： 若把一个 n*n*n的立方体切成一个个单位立方体，最少需要几刀？答案：事实上，从一个更强的命题出发反而能使问题变得更简单。对于一个a*b*c的长方体，我们需要f(a)+f(b)+f(c)刀，其中f(x)=?log(x)/log(2)?。只需要注意到，在整个过程中的任何一步，切完当前最大的块所需要的刀数也就等于整个过程还需要的刀数，因为其它小块需要的刀数都不会超过最大块所需刀数，它们都可以与最大块一道并行处理。这表明，我们的最优决策即是让当前的最大块尽可能的小，也就是说要把当前的最大块尽可能相等地切成两半。利用数学归纳法，我们可以很快得到本段开头的结论。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -