Sunday, August 24, 2014

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




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个状态。最后逆推结果的时候,可以适当用纸币勾画一个具体例子,然后归纳演绎,问题得解。

2 comments:

  1. 一个健康强大的大脑保证了一个积极和满足的生活。 在今天快节奏的生活中,绝大多数人无法保持正常的运动时间表。 由于他们忙碌的习惯,他们通常没有足够的时间参加其他健康活动。 我为留学生论文找到一个非常好的网站,如果你想访问这个网站。

    ReplyDelete