脑筋急转弯：程序员面试Brain Teaser总结(一)

包子IT面试培训 助你拿到理想的offer!

Brain Teaser 曾经是各个顶尖IT公司在面试程序员过程中必不可少的环节，因为在这些顶尖公司里面，他们的宗旨就是要招到他们认为最聪明的员工进入公司，而Brain Teaser就是作为考察面试者反应能力的一项最为基础的测试。但是随着时间的推移，Brain Teaser已经丧失曾经的辉煌历史，但是仍旧在很多公司的面试过程中占有一定的比重。Brain Teaser的题目通常看起来会觉得毫无意义，其实在面试过程中，面试官出这些题目往往是考察面试者能不能从非常规的角度去看待问题，从而寻求解题的突破口。以下就是一些在著名IT公司面试过程中遇到的题目。

题目：

• 有一个双人下棋游戏在一个圆桌上进行。每个player都有无限多个Coins。他们需要在桌子上轮流放置Coin，每次只能放置一枚，在放置过程中新的Coins不能与原来放过的Cons重叠。如果哪位player没有地方放置新的coin，那么这个player谁输了。请给出一种策略能够保证无论对手怎么下棋，都可以获得胜利。

思考方式：

• 往往面试者遇到这个问题的第一反应就是如何能够让对收没有地方放置Coin，并没有仔细地去思考这个游戏的相关背景，在这到题目中，圆桌就是最为关键的解题突破口。想起圆，这个常见有特殊的形状，学过初中几何的同学都会立马反应出很多相关的定理和特征，但是在这么多特征中想很快的找到解题答案也不是很容易的事情，但是再仔细想想，大家会发现大部分关于圆的特征都有一个特殊的点来作为背后证明的支撑，那就是圆心。如果面试者能够想到圆心这个特殊点，那么这道题的题眼已经被找到了。剩下的就是通过利用圆心这个特殊点来做文章了。

• 我们知道过圆心的直线与圆相交之后所组成的线段称为直径，那么直径的特殊性就可以很快的被找到，那就是在直径上除了圆心之外，任意一点都能有与圆心相应的对称点。找到了这个特征，这道题也就被解出来了。那就是无论对手如何放置，那个对称点总会有位置去放置自己的棋子。那么显而易见，抢圆心点就是这个策略的第一步了。

答案：

• 成为先行者，并且在桌子中心放置第一枚Coin，以后的Coins总是放在与对手刚才放的地方相对称的位置。这样，只要对手能放，玩家一定也有地方放而且必胜。

题目：

• 一个矩形(长方体)蛋糕，蛋糕内部有一块矩形（长方体）的空洞。只用一刀，如何将蛋糕切成大小相等的两块？

思考方式：

• 首先，我们可以把题目先简答化，如果分割一个矩形使得分割出来的两块面积相同，相信这个题不会很难，那就是通过这个矩形中心的直线都能够将矩形分成两个面积相同的图形。
• 然后我们加上这道题的另外的一个特征就是在这个大矩形内还有一个小矩形，然后我们如果想将小矩形也分成两个面积相等的图形，我们必然要经过小矩形的中心，在上面我们已经确定大矩形的中心，这时候我们只要回想起初中几何的那句定理“两点确定一条直线”，我们就能轻而易举地解决这个问题了。

答案：

• 过大矩形和空心矩形各自的中心画一条线，这条线显然把两个矩形都分成了一半并且面积相等。

题目：

• 判断给定的整数是否是一个2的幂

思考方式：

• 第一反应肯定就是判断一个数是不是2的幂最直白的方法就是用这个数一直去除2，直到答案为1为止，但是所有人都知道这肯定不是面试官想要的答案，尤其是在IT公司面试中，类似这样看起来很直白的题目，一旦没有思路的时候，就影响去考虑一些比较tricky的方式。类似这类的问题，我们经常会考虑用bit operation去解决，bit operation也是程序员所必备的brain teaser技能之一。
• 当想到用bit来解决问题之后，我们就需要联想到在计算机里，其实所有的东西都是通过二进制数来表示的。既然这样，我们就应该深度挖掘2的幂的这些数用二进制表示过程中的特征。
• 从上面的例子我们好像可以得到的结果就是在二进制的表达中，只有一位是1，并且在1的右边的所有数字（如果有数字）必须是0。这样我们就能够通过移位来判断这个数是否是2的幂。
• 但是移位是最优解么？我们既然说到用bit operation来操作，那除了移位之外，我们还有位操作呢，比如 AND, OR, XOR。我们知道在做位操作AND的时候只有 1 and 1 = 1。如果你仔细观察那些2的幂的数，你就会发现，他们的二进制表达中只能有一个1，那就意味着比他们这些幂小于1的数中，不可能在有相同位置的1存在。 换句话说就是如果一个数与比它小1的数做位运算AND，如果最终答案是0，那么这个数就是2的整次幂。

答案：

• (b & (b-1)) == 0。

题目：

• 如何快速找出一个32位整数的二进制表达里有多少个"1"？用关于"1"的个数的线性时间？

思考方式：

• 如果看了上面的那个题，那么这个题的思路也就相当明确了，就是通过位运算来解决问题。
• 答案：
• （关于total数字位数线性时间）：for(n=0; b; b >>= 1) if (b & 1) n++;
• （关于total "1"的个数线性时间）：for(n=0; b; n++) b &= b-1;