脑筋不转弯啦，程序猿和攻城狮面试Brain Teaser总结(二)

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

我们不久前发表了 脑筋急转弯：程序员面试Brain Teaser总结(一). However, real world work makes us dumb and rusty..  今天脑筋继续转起来！

Brain teaser，顾名思义，脑筋急转弯的意思，但同时这类问题往往还要求一定程度的数理基础，需要作出合理的逻辑推理和演绎，并且能够完成相对准确完整的表达，难度并不低。另外，Brain teaser的存在其实是有一定争议的，大部分业内人士认为这类题目并不能完全考察一个人的聪明程度，因为『是否之前见过类似题目』非常影响答题效果，很多公司已经放弃使用brain teaser作为面试题目。但根据小编的自身经历，还是有很多公司在电话面试中会问一道brain teaser的题目，通常作为编程题目之后一道小菜，目的是看看应试者的沟通表达能力和解决问题的思路。由于是小菜，一般来说做不出brain teaser不会特别影响最终面试结果，但是做的比较好确实容易给自己加分，因此我们来简单看看下面几个套路brain teaser.

1. 有一项体育锦标赛，淘汰赛制，有64位选手参加。两两配对比赛分出胜负（被淘汰选手不再比赛），然后胜利的选手进入下一轮淘汰赛，如此进行直到决出冠军。请问这届锦标赛一共发生了多少场比赛？(如果你的面试官是个体育爱好者，没准就会那这个来试试你)

思路：

Brain teaser的题目往往比较长，因此如果没有听懂的地方一定要确认或者请别人重复一遍。弄清题目要求之后可以问问相关问题，比如这里的64是2整次方，需不需要考虑非2的整次方数的问题（往往面试官会说可以之后考虑，但是先做目前这个条件）。

进一步解决问题，最直观的解法当然是一轮一轮的数，64进32的时候有32场，32进16有16场...循环加起来32+16+8+4+2+1 = 63场；这个方法行得通，但是显得比较笨拙，如果选手是111人，多余的人轮空本轮，那么挨轮数的办法并不好用。

对于这类问题，往往最重要的是挖掘问题的本质。问题是统计比赛的场数，比赛的场数又和比赛的人数直接相关。但是这个关系可以更深入的解读：一场比赛有两名选手参加，需要淘汰一名选手。换一种想法，每淘汰一名选手，需要一场比赛。那么n个选手决出冠军，自然需要淘汰n-1名选手，因此需要n-1场比赛。问题解决。

点评：

对这类问题，给出一个答案不难，难的是快速的看透复杂问题的本质，然后在最接近问题本质的关系上，多角度思考，多问自己几个为什么，往往会有启发。

2.  1000瓶酒，已知有且仅有1瓶有毒。酒中的毒素在进入机体内10个小时之后发作致死。目前你有若干只小白鼠可做你的实验品，但是你只有11个小时的时间，请问最少需要多少只小白鼠才能确定哪瓶是有毒的酒？

思路：听懂问题仍然是第一要务，如果有不清楚的地方一定要及时问面试官，这是考察沟通能力的一部分。比如『一只小白鼠可以喝多瓶酒么？』『可以』；『多只小白鼠可以喝一瓶酒么？』『可以』等等。

题目的本质是什么？

仔细想想，用一句话来表达的话，那么：由于11/10个小时的限制，那么其实这个题目本质上就是希望在一轮酒分配之后，通过小白鼠的生死状况来判断哪瓶酒是毒酒。

最直观的当然是用1000只小白鼠，10小时候死的那只小白鼠喝的酒是毒酒。（或者999只，如果都没死，那么所有小白鼠没喝的那一瓶是毒酒），仍然是可行，但是笨拙，没有利用到小白鼠喝多瓶酒的组合，显然会有更优解。

回到我们之前得出的问题本质，最终的最终，我们需要用小白鼠的生死来判断结果。那么小白鼠最后的状态其实非生即死，想的快的同学可能马上反应过来，这不就是1和0两个状态嘛。那么，1只小白鼠可以有2个状态（生、死），2只小白鼠可以有4个状态（1生2生、1生2死、1死2生、1死2死），归纳演绎，10只小白鼠就可以有2的10次方个状态，即1024个状态，完全可以覆盖1000瓶酒，似乎解决了问题！

答案是对的，但是我们怎么想出一个安排小白鼠喝酒的方法，能使最后10只小白鼠的生死状态对应一瓶酒呢？

我们来看一个10位的2进制的数字：

1 0 0 0 0 0 0 1 1 1 => 对应了所有处于”1”位的小白鼠死去、其他位的小白鼠活着的一个结果，这个结果转换成10进制就是”519”这瓶酒，一一对应。

进一步讲，每一只小白鼠的生死应该能确定这个2进制数中每一位的状态（0/1)。怎么做呢？拿最高位的那一只小白鼠来举例子，让它喝所有最高位上为1的瓶号的酒，(1 *********), 共有512瓶，如果它最后死了，那么这一位一定是1，否则是0；对其他位的小白是使用相同的方法，即可得解。

点评：

对于数字的敏感是解决这个问题的关键，当你看到『生死』这种二元的状态和1000这个数的时候，IT界的朋友应该马上可以联想到2的10次方是1024，可以完全覆盖1000个状态。最后逆推结果的时候，可以适当用纸币勾画一个具体例子，然后归纳演绎，问题得解。