面试智力题

绳子类

1、 一条绳子(粗细不均,长短不一),从一头点燃,全部烧完要耗时1个小时,问如何用这条绳子测出半个小时?(初级)

2、 有一些绳子(粗细不均,长短不一),但是每根绳子点燃后都烧一个小时,问用什么方法可以用这些绳子计算45分钟的时间,计算1小时15分钟时间呢?(中级)

(分析)这类题目比较简单。由于绳子是双向的,只需同时点燃绳子的两端,便可得到1/2小时的时间,这种方法暗含着以一个绳子单向点燃时间作为参照物;同时点燃两根绳子,一根双向点燃,另一根单向点燃,待第一根绳子燃烧完毕后,点燃第二根绳子的另一端,便得到45分钟时间;同理,可计算1小时15分钟时间。

博弈类

1、 假设排列着100个乒乓球,由两个人轮流拿球装入口袋,能拿到第100个乒乓球的人为胜利者。条件是:每次拿球者至少要拿1个,但最多不能超过5个,问:如果你是最先拿球的人,你该拿几个?以后怎么拿就能保证你能得到第100个乒乓球?(中级)

2、 16个硬币,A和B轮流拿走一些,每次拿走的个数只能是1,2,4中的一个数。谁最后拿硬币谁输。问:A或B有无策略保证自己赢?假设都很聪明。(高级)

3、 传说,从前有五个海盗抢得了100枚金币.他们通过了一个如何确定选用谁的分配方案的安排.即:

1.抽签决定各人的号码(1,2,3,4,5);

2.先由1号提出分配方案,然后5个人表决.当且仅当超过半数人同意时,方案才算被通过,否则他将被扔入大海喂鲨鱼;

3.当1号死后,再由2号提方案,4个人表决,当且仅当超过半数同意时,方案才算通过,否则2号同样将被扔入大海喂鲨鱼;

4.往下依次类推……

根据上面的这个故事,现在提出如下的一个问题.即:

我们假定每个海盗都是很聪明的人,并且都能够很理智地判断自己的得失,从而做出最佳的选择,那么第一个海盗应当提出怎样的分配方案才能够使自己不被扔入大海喂鲨鱼,而且收益还能达到最大化呢?

(分析)博弈类的题目往往需要逆向思维考虑问题,这两道题目也不例外。

对于问题1,要确保自己能拿到最后一个球,应该在最后一轮(“一轮”定义为对方和自己依次取一次球)中剩余6个求,这样,对方拿x个,你拿剩下的6-x个便可以获胜,…,依次往前推,100个乒乓球可包含100/6=16轮,剩下100%6=4个。于是,可以得到答案:自己先取4个球,然后对方取x个,自己取6-x个,这样便可保证自己取到第100个球。

对于问题2,与问题1类似,需要针对A拿的硬币个数,确定B对应拿几个(假设B赢)。采用逆推的方法,最后必须剩余1个,且此时让A拿,倒数第二轮可剩余3个或者6个,这样,A拿1个,B对应拿2个;A拿2个,B对应拿1个;A拿4个,B对应拿2个,…,依次逆推,16个硬币最多进行16/3=5轮,最后正好剩余16%3=1个。

对于问题3

倒水类

1、 假设有一个池塘,里面有无穷多的水。现有2 个空水壶,容积分别为 5 升和6 升。问题是如何只用这2 个水壶从池塘里取得3 升的水?(初级)

2、 如果有无穷多的水,一个3公升的桶,一个5公升的桶,两只桶形状上下都不均匀,问你如何才能准确称出4公升的水?(初级)

3、 如上题,如果是7公升和11公升的桶,怎样准确量出2公升的水?(初级)

11=7 = 4   7-4 = 3  11- 3 = 8  8-7 =1

4、 有三个酒杯,其中两个大酒杯每个可以装8两酒,一个可以装3两酒。现在两个大酒杯都装满了酒,只用这三个杯子怎么把酒平均的分给4个人喝?(中级)

5、 一共12 个一样的小球, 其中只有一个重量与其它不一样( 未知轻重) ,给你一个天平, 只称三次, 找出那个不同重量的球?(初级)

 

6、 如果一共13 个一样的小球, 其中只有一个重量与其它不一样( 未知轻重) ,给你一个天平, 只称三次, 找出那个不同重量的球?(高级)

诡异类

1、 2个盲人每人买了2双黑袜2双白袜,(每双袜子连在一起,)不小心吧这把8双袜子混在了一起,请问他俩怎样才能拿回自己的袜子?

2、 有23枚硬币在桌上,10枚正面朝上。假设别人蒙住你的眼睛,而你的手又摸不出硬币的反正面。让你用最好的方法把这些硬币分成两堆,每堆正面朝上的硬币个数相同(你可以随便翻转任何一枚硬币)。

3、 一群人开舞会,每人头上都戴着一顶帽子。帽子只有黑白两种,黑的至少有一顶。每个人都能看到其他人帽子的颜色,却不知自己的。主持人先让大家看看别人头上戴的什么帽子,然后关灯,如果有人认为自己戴的是黑帽子,就打自己一个耳光。第一次关灯,没有声音。于是再开灯,大家再看一遍,关灯时仍然鸦雀无声。一直到第三次关灯,才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子?

4、 有3顶红帽子,4顶黑帽子,5顶白帽子。让10个人从矮到高站成一队,给他们每个人头上戴一顶帽子。每个人都看不见自己戴的帽子的颜色,却只能看见站在前面那些人的帽子颜色。(所以最后一个人可以看见前面9个人头上帽子的颜色,而最前面那个人谁的帽子都看不见。现在从最后那个人开始,问他是不是知道自己戴的帽子颜色,如果他回答说不知道,就继续问他前面那个人。假设最前面那个人一定会知道自己戴的是黑帽子。为什么?

(分析)这类题目粗看摸不到头脑,感觉题目意思有点诡异的,但仔细分析问题后,便会得到结果。

对于问题1,每个盲人只需要拿走所有成双袜子中的一只即可。

对于问题2,只需将23枚硬币分成两组,一组10个,另一组13个,然后将10个的那组中所有硬币翻转即可。

对于问题3,可采用递推+联想的方法。首先,假设只有1个人戴黑帽子,则第一次熄灯时,便会出现清晰的打耳光的声音(你可以联想,N个人中,只有你一个人戴黑帽子,第一次熄灯之前,你看到其他所有人戴白帽子,你很容易想到只有自己戴黑帽子,那么熄灯后赶快给自己一个耳光,O(∩_∩)O~);然后,再假设有两个人戴黑帽子(设这两个人分别为A,B),第一次熄灯前,A或者B都看到对方戴黑帽子,熄灯后,他们均不会打自己,然而,第二次熄灯前,对于A,他想到上次B没有打自己,说明B看到了有人带黑帽子,而A,B看到的除自己以外所有人均是相同的,即均戴白帽子,则A想:B一定看到了自己戴黑帽子,同理,B也会这样想,于是第二次熄灯时,AB均会打自己,…,这样可以归纳,如果第n次熄灯后,出现打耳光的声音,则共有n个人戴黑帽子。

对于问题4

最优化类

1、 一个小猴子边上有100 根香蕉,它要走过50 米才能到家,每次它最多搬50 根香蕉,每走1 米就要吃掉一根,请问它最多能把多少根香蕉搬到家里。

2、 1元钱一瓶汽水,喝完后两个空瓶换一瓶汽水,问:你有20元钱,最多可以喝到几瓶汽水?

3、 有一个100层高的大厦,你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎,用你手中的这两个玻璃围棋子,找出一个最优的策略,来得知那个临界层面。

(分析)这类题目需要根据具体情况,利用简单的数学知识进行解答。

对于问题1,由于猴子一次只能搬50根,则他需要在中途返回一趟,取剩下的香蕉。设猴子在中途x米处返回,则最优的情况是:在x米处需存储至少50根香蕉,然后义无反顾地回家(不再返回)。显然,(50-2x)+(50-x)>= 50,求得x<=16.6,则x取16,此时,猴子可带回家16根香蕉。

对于问题2,可采用递推的方法。20元钱,可买20瓶汽水,然后用这20个空瓶换10瓶汽水,之后用这10个空瓶换5瓶汽水,再之后用这5个空瓶换2瓶汽水,之后用这3个空瓶换1瓶汽水,然后用剩下的2个空瓶换1瓶汽水,最后,借一个空瓶,换一瓶汽水,并将空瓶换回去。共20+10+5+2+1+1+1=40瓶。另外两种思路:解题思路2: 先看1元钱最多能喝几瓶汽水。喝1瓶余1个空瓶,借商家1个空瓶,2个瓶换1瓶继续喝 ,喝完后把这1个空瓶还给商家。即1元钱最多能喝2瓶汽水。20元钱当然最多能喝40瓶汽水 。 解题思路3: 两个空瓶换一瓶汽水,可知纯汽水只值5角钱。20元钱当然最多能喝40瓶的纯汽水。N元钱当然最多能喝2N瓶汽水。

此题目可推广为:1元钱一瓶汽水,喝完后两个空瓶换一瓶汽水,则N元钱,可买2N瓶汽水。

对于问题3,实际上是一个有序数组上的搜索问题,但由于只有两个玻璃围棋子可用,所有不可以采用二分查找的方法。该题的解决思路是,首先在第x层仍一个玻璃围棋子,如果碎了,则利用另一个玻璃围棋子依次从1~x-1层试探,查找临界层;如果第x层未碎,则在第x+(x-1)=2x-1层仍一个玻璃围棋子,如果碎了,则利用另一个玻璃围棋子一次从x+1~2x-2层查找临界层,…,这样,可得到表达式:x+x-1+…+1>=100,可得到x=14,即:

先从14层扔(碎了试1-13)

再从27层扔(碎了试15-26)

再从39层扔(碎了试28-38)

再从50层扔(碎了试40-49)

再从60层扔(碎了试51-59)

再从69层扔(碎了试61-68)

再从77层扔(碎了试70-76)

再从84层扔(碎了试78-83)

再从90层扔(碎了试85-89)

再从95层扔(碎了试91-94)

再从99层扔(碎了试96-98)

最后从100层扔‘’

 

这道题其实就是让玻璃摔碎的可能性一样 

1、等比数列通项公式、求和公式:

2、等差数列通项公式、求和公式:

IT思想类

1、 有1000瓶水,其中有一瓶有毒,小白鼠只要尝一点带毒的水24小时后就会死亡,至少要多少只小白鼠才能在24小时时鉴别出那瓶水有毒?(中级)

2、 共有三类药,分别重1g,2g,3g,放到若干个瓶子中,现在能确定每个瓶子中只有其中一种药,且每瓶中的药片足够多,能只称一次就知道各个瓶子中都是盛的哪类药吗?

如果有4类药呢?5类呢?N类呢(N可数)?(高级)

如果是共有m个瓶子盛着n类药呢(m,n为正整数,药的质量各不相同但各种药的质量已知)?你能只称一次就知道每瓶的药是什么吗?

(分析) 这类题目比较适合IT人做,因为要使用计算机中的概念或者思想。

对于问题1,需采用二进制思想。至少采用10只小鼠,这样,2^10=1024>1000。方法是:对老鼠和水进行编号,分别为1~10和1~1000,水的每个编号对应一个10位的二进制数,如编号为100的水对应二进制0001100100,其中第3,6,7个bit为1,则该水需编号为3,6,7的老鼠品尝,最后,统计死亡的老鼠的编号,如,死亡的老鼠编号为3,6,7,则编号为100的水有毒。也就是说,通过二进制思想,在老鼠的死亡组合方式与水的编号之间产生了一一对应关系

(布隆过滤器一样的思想)

 改变下条件,如果你有两个星期的时间(换句话说你可以做两轮实验),为了从1000个瓶子中找出毒药,你最少需要几只老鼠?注意,在第一轮实验中死掉的老鼠,就无法继续参与第二次实验了

7只老鼠就足够了。事实上,7只老鼠足以从 3^7 = 2187 个瓶子中找出毒药来。首先,把所有瓶子从0到999编号,然后全部转换为7位三进制数。现在,让第一只老鼠喝掉所有三进制数右起第一位是 2 的瓶子,让第二只老鼠喝掉所有三进制数右起第二位是2的瓶子,等等。一星期之后,如果第一只老鼠死了,就知道毒药瓶子的三进制编号中,右起第一位是2;如果第二只老鼠没死,就知道毒药瓶子的三进制编号中,右起第二位不是2,只可能是0或者1……也就是说,每只死掉的老鼠都用自己的生命确定出了,三进制编号中自己负责的那一位是2;但每只活着的老鼠都只能确定,它所负责的那一位不是2。于是,问题就归约到了只剩一个星期时的情况。在第二轮实验里,让每只活着的老鼠继续自己未完成的任务,喝掉它负责的那一位是 1 的所有瓶子。再过一星期,毒药瓶子的三进制编号便能全部揭晓了

总结:n只小白鼠t周的时间可以从至多(t+1)^n个瓶子中检验出毒药(一瓶)来

 

于问题2,如果是三类药,我们第一瓶取一颗,第二瓶取10壳,第三瓶取100颗即可,称得总重量,那么个位上的数代表第一类药的重量,十位上的数代表第二类药的重量,….

如果药的种类变多,这种方案的代价过高,我们可以考虑最重的药多重,然后采用对应的进制。如3类药,最重的是3g,则可以采用4进制而不是十进制,即,三种药,每类依次取4^0,4^1,4^2个,然后称重,得到的十进制重量转化为4进制,…。

如果是共有m个瓶子盛着n类药,若m>n就是以上情况。(若m<n,则不同药装在相同的瓶中,应该没有这种情况)这里m的作用是,它决定最后的结果有m为数,而n的作用只表示在这m位数中有n种不同的数。
综上所述,若共有m个瓶子盛着n类药,且这n种中最重药片重量为A,所有药片的重量均为正整数,
则我们可以给瓶子编号分别为1号至m号。
现从1号瓶取出1片,2号瓶取出(A+1)片,3号瓶取出(A+1)^2片,N号瓶取出(A+1)^(m-1)片,上秤称,再把重量用(A+1)进制数表示,即可从右到左读出1至m号瓶内药片的重量。从而区分每一个瓶中药的种类。

 

飞机加油问题

每个飞机只有一个油箱,飞机之间可以相互加油(注意是相互,没有加油机) 一箱油可供一架飞机绕地球飞半圈。 为使至少一架飞机绕地球一圈回到起飞时的飞机场,至少需要出动几架飞机?(所有飞机从同一机场起飞,而且必须安全返回机场,不允许中途降落,中间没有飞机场) (很难)

(分析)在网上查找该题目,会发现该题目答案五花八门。本人认为,该题的最佳答案应该是5架飞机,具体可参考:http://blog.sina.com.cn/s/blog_48ef377d0100089h.html

本题分析思路应该是从一架开始逐步增多,直到找不最少的数目;同时应该注意,(1) 本题允许飞机反向接应 (2)每个飞机油箱大小时固定的。

硬币翻转问题

一个圆盘上放4枚硬币,正反不确定(非4个正面朝上),排成正方型。你蒙着眼睛,每次可以翻转任意几枚 硬币一次(摸不出正反面)。每次翻转以后圆盘会随机的旋转一次若干个90度。然后你再翻转硬币,8。请问如果要想肯定结束游戏,你至少要翻转多少次?(非常难)

(分析) 这个题目非常难,但去年(2010年)某一师兄在某一家公司面试时遇到了该题目实际上是一个自动机状态转换问题,已知初始状态和结束状态,让构造状态转换方式。

http://blog.sina.com.cn/s/blog_17f3b16300102xe3j.html

概率题

1、 你有两个罐子,50个红色弹球,50个蓝色弹球,随机选出一个罐子,随机选取出一个弹球放入罐子,怎么给红色弹球最大的选中机会?在你的计划中,得到红球的准确几率是多少?

2、 有一栋10层的楼,在每个升降机门跟前放上一颗钻石,这些个钻石巨细差别。一人坐升降机从1楼到10楼,升降机每一到一层楼就开一次门,怎么样能拿到最大的钻石?只有一次时机(就是出了升降机门就进不来了)

3、 三个小伙子同时爱上了一个姑娘,为了决定他们谁能娶这个姑娘,他们决定***进行一次决斗。阿历克斯的命中率是30%,克里斯比他好些,命中率是50%,最出色的枪手是鲍博,他从不失误,命中率是100%。由于这个显而易见的事实,为公平起见,他们决定按这样的顺序:阿历克斯先开枪,克里斯第二,鲍博最 后。然后这样循环,直到他们只剩下一个人。那么这三个人中谁活下来的机会最大呢?他们都应该采取什么样的策略?

 

(分析)对于这类问题,一般要采用数据概率的方法进行计算,得出结果。

对于问题1,需要打破思维,不要总想着两个罐子放入相同的球。如果想使取到红球的概率最大,最好能够做到一个罐子中全是红球(从这个罐子中获取红球的概率为1),另一个罐子中红球尽可能多,于是便得到 答案:往一个罐子中放一个红球,剩余的球全部放到另一个罐子中,这样,获取红球的概率为1/2+1/2*49/100

对于问题2,是一个难度较大的概率计算问题。这个模型变形于博弈论中的“秘书问题”,也曾是微软的应聘试题之一。秘书问题是这样的:要聘请一名秘书,有n人来面试。每次面试一人,面试过后便要即时决定聘不聘他,如果当时决定不聘他,他便不会回来。面试时总能清楚了解求职者的适合程度,并能和之前的每个人作比较。问凭甚么策略,才使选得到最适合担任秘书的人的机率最大?基本解决策略如下:对于某些整数r,其中,先面试首r人,都不聘请他们,在之后的n − r人中,如果任何一人比之前面试的人都更佳,便聘请他。

r的值应该是甚么呢?答案是r≈n/e≈0.368n(可以用概率公式推导出来),其中e是自然对数的底。使用这个r的值的成功率是0.368n。在提问的电梯问题中,楼层数n=10,求得r≈3.68,取其最近的整数为4。即:前4层都不选,但记下所见过的最大钻石的大小,从第5层开始遇到与该钻石大小最相近的一个就选。

对于问题3(网上答案http://wenku.baidu.com/view/1d816c4fe518964bcf847c60.html ) ,

设:A——阿历克斯、B——克里斯、C——鲍博

只有AB相对

A活下来的可能性为

30%+70%×50%×30%+70%×50%×70%×50%×30%+……=0.3/0.65

B活下来的可能性为

70%×50%+70%×50%×70%×50%+70%×50%×70%×50%×70%×50%+……=0.35/0.65

应该恰好等于1-0.3/0.65。

只有AC相对

A活下来的可能性为30%

C活下来的可能性为70%

只有BC相对

B活下来的可能性为50%

C活下来的可能性为50%

三人相对

A活下来有三种情况

1.A杀了C,B杀不死A,A又杀了B,概率30%×50%×0.3/0.65

2.A杀不死C,B杀了C,A杀了B,概率70%×50%×0.3/0.65

3.A杀不死C,B杀不死C,C杀了B,A杀了C,概率70%×50%×30%

所以A活下来的可能性为0.105+3/13≈0.336大于三分之一,比较幸运了。

B活下来有三种情况

1.A杀了C,B杀了A,概率30%×50%

2.A杀不死C,B杀了C,AB相对的情况下B杀了A,概率70%×50%×0.35/0.65

3.A杀了C,B杀不了A,AB相对的情况下B杀了A,概率30%×50%×0.35/0.65

所以B活下来的可能性为0.15+3.5/13≈0.419大于三分之一,非常幸运了。

C活下来只有一种情况

1.A杀不死C,B杀不死C,C杀了B,A杀不死C,C杀了A,概率70%×50%×70%

所以C活下来的可能性为0.245小于三分之一,非常不幸。

而且ABC活下来可能性之和恰为1。

 

圆环问题

两个圆环,半径分别是1和2,小圆在大圆内部绕大圆圆周一周,问小圆自身转了几周?如果在大圆的外部,小圆自身转几周呢?

(分析) 该题目比较简单。小圆旋转的距离取决于圆心运动的圆周周长,在大圆外部时,小圆运动轨迹的半径为3,而在大圆内部时,小圆运动轨迹的半径为1。