死理性派教你做微软面试题

标签: 理性 微软 面试 | 发表时间:2011-08-30 10:03 | 作者:(author unknown) Hing Sar
出处:http://www.guokr.com/

经常能在网上看到各种不知真假,却被转烂了的“超变态但很经典的微软面试题”。那微软这样的大公司,到底有多喜欢“蹂躏”面试者的智商呢?本文就从一套广为流传的的“10个最著名微软面试题”中选取了几个最经典的,来和它们较量较量。

闲话少叙,解题吧。


你的丈夫有外遇吗

一座小镇里有100对夫妇,他们都遵守一个奇怪的风俗:如果妻子发现丈夫背叛了她,那她就会在当天夜里杀死自己的丈夫。小镇里的女人都知道别人丈夫的秘密,却不会说出来。换言之,每个女人只知道除自己丈夫之外其他男人的外遇情况。突然有一天镇长宣布,至少有一个男人背叛了他的妻子,假设镇长说的是真话,所有人都相信镇长所说的,那么接下来将会发生什么?

我们不妨先假设只有1个男人背叛了他的妻子,这时那个男人的妻子会猛然发现自己竟然不知道任何男人有外遇的消息(而其他99个女人知道的都是1个男人背叛了自己的妻子,即真相),对此唯一的解释便是有且只有一个有外遇的男人,就是自己的丈夫。所以她会在当天夜里杀死自己的丈夫。然后,没有然后了。

那如果有2个男人呢?这时小镇里有98个女人知道真相,但另外2个女人只知道1个男人有外遇,并不能确定自己的丈夫是否也有外遇。所以在镇长宣布此事的当天,全镇相安无事。但到了第2天,当这2个女人发现对方都未处死自己的老公时,就会意识到不止一个男人有外遇了。那便是有2个男人有外遇,这样的话,其中1个肯定是自己的丈夫。于是,这2个女人会同时在夜里处死自己的丈夫。

以此类推,很容易归纳出来,如果小镇里有n个不忠的丈夫,他们都会在镇长宣布后的第n天夜里被处死。

实际上,有时候虽然只有极少量的信息,但只要仔细分析,一样可以得出有效的结论。上述这个谜题相信有很多人见过,类似的还有著名的 蓝眼睛岛问题 ,只是这个更加复杂一点。


隔离监狱中的100个犯人

在一所监狱中,关押了100个相互隔离的犯人。典狱长每天随机选择一名犯人(他可能被重复选中多次),扔到一间小黑屋中关禁闭。这个房间中只有一个电灯和开关,除了小黑屋中的人,谁都看不到这盏灯,更无法控制它。关进去的人则可以打开或关闭电灯,也可以选择什么都不干。犯人们随时可以叫停这场游戏并告诉典狱长:“所有犯人都被关过小黑屋。”如果这句话是真的,所有犯人将会被释放;但如果这句话是假的,他们全部会被处死。在游戏开始前,犯人们被允许聚在一起商议对策,他们该怎么做才能保证自己一定能够被释放呢?

首先我们随意选择一个犯人A作为计数者。

现在让除了A以外的任何一个犯人进入小黑屋后,都将严格遵循下面这个法则:

如果他以前从来没有打开过这盏电灯,并且现在这盏电灯是关着的,那么打开它,除此以外不作任何事情。而如果典狱长选择的是A,并且当他进入这个房间以后房间里的电灯是开着的,那么他就把电灯关掉,并在自己的计数里加1。当他的计数达到99之日(从1开始),便是所有犯人重获自由之时。


工作分金问题

有个工人将为你工作七天,你用一块金条来支付工资。每天工作结束以后你都要给工人发工资,但你只能在这块金条上折两次。应该如何选择金条上的折断位置,以及支付工资的方法?

这个问题并不困难,但如果工人为你工作X天,你该怎么分割这块金条呢?

让我们先来回答最初的问题,为读者做个启发。把金条分成如下三份:第一份是原金条的 1/7(编号为1号金条);第二份是原金条的 2/7(2号金条);第三份是 4/7(3号金条)。接下来的7天你将这样支付工资:

第1天:给工人1号金条(此时你有2号和3号金条,工人有1号金条)

第2天:给工人2号金条,并取回1号金条(此时你有1号和3号金条,工人有2号金条)

第3天:给工人1号金条(此时你有3号金条,工人有1号和2号金条)

第4天:给工人3号金条,并取回1号和2号金条(此时你有1号和2号金条,工人有3号金条)

第5天:给工人1号金条(此时你有2号金条,工人有1号和3号金条)

第6天:给工人2号金条,并取回1号金条(此时你有1号金条,工人有2号和3号金条)

第7天:给工人1号金条,事成收工。

有过一些编程经验的读者可能会马上意识到,这其实正是二进制的原理。 1,2,4 三个十进制数的二进制形式分别是 1,10,100,用这三个数可以表示 [0,7] 区间(换成二进制形式即 [000,111] 区间)里的所有整数。

同样的道理可以计算出,如果有工人为你工作X天,而你依然打算用一块金条来支付工资的话,那么最少需要在金条上折断( log 2 [X+1] - 1 ) 处。


寻找次品

/gkimage/b4/5q/d7/b45qd7.png

你有10只装满了球的盒子,其中有一只盒子里装的是次品。已知正常的球每个重 10g,而次品球每个重 9g。如何只使用一次电子秤,就找出哪只盒子装的是次品?

我们在面对这类称重找次品的问题时,第一想法通常是从每个盒子中拿出一个球来称重。然而,这道题的关键恰恰是从不同的盒子里取出不同数目的球。

我们先把 10 只盒子从 0 到 9 编号,然后从每只盒子中取出与这只盒子编号数目相等的球来,举例来说,0号盒子里不需要取球, 1 号盒子里拿出 1 只球, 2 号盒子里拿出 2 只球,等等。

然后我们这些球一起放到电子秤上。假如所有的球都是正品,那么电子秤上的读数应该是450g;但是因为这堆球里可能有次品,所以实际读数是 ( 450 - x )g ,其中x是次品球的个数,同时这个个数又恰好次品盒子的编号。


过桥问题

四个人需要在夜间度过一座摇摇晃晃的吊桥。不幸的是,他们只有一个火把,而这座桥又太危险了,他们无法在不借助火把的情况下度过这座危桥。而更不幸的是,这座桥又不怎么结实,最多允许两个人同时度桥。四个人过桥的速度各不相同,分别是:1分钟,2分钟,7分钟,10分钟。显然,两人同时度桥,耗时就取决于最慢的人。那么,他们全部度过这座桥所需的时间最短是多少?

大部分人的第一想法往往是利用一个最快的人反复度桥来接送其他人,这样需要的时间是 2 + 1 + 7 + 1 + 10 = 21 分钟。的确很快,但是实际上还有更快的方法。

很容易想到的是,我们应该能让 7 和 10 一起过桥。但是接下来呢?难道让其中1个人再回去一趟吗?不,这样的话就太耗时了。如何解决这个问题呢?我们可以提前让1个脚程较快的家伙在桥的对岸等着。因此就有方案如下:

先让 1 和 2 一起过桥。耗时2分钟。

让 1 拿着火把回来。耗时1分钟。

让 7 和 10 一起过桥,耗时10分钟。

让 2 拿着火把回来。耗时2分钟。

最后再让 1 和 2 一起过桥。耗时2分钟。

最后总耗时为 2 + 1 + 10 + 2 + 2 = 17 分钟。

表针问题

/gkimage/83/l0/84/83l084.png

一天中时钟的时针和分针重叠几次?

直觉也许会告诉你24次,但事实并非如此,我们不妨来算一下。

当分针和时针从 12:00 处开始走动后,T个小时的时间里时钟的分针走T圈,时针则是 T/12 圈,两个表针第一次重合的时候分针比时针领先整整一圈,也就是 T = T/12 + 1 ,此时 T = 12/11 ,也就是表针在 12/11 时(比 1:05 稍微晚一些)第一次重叠。把重叠的次数换成N,然后把式子中的T换成24,我们就可以得到:

24=2+N

显然,N=22

即两个表针在一天内重叠22次。它们从来不会在上午或者下午的11点重合,因为它们要同时到达表盘的12点方向。

看到这里,各位读者是对打进微软内部更有把握了呢?


本文改编自:MY TECH INTERVIEWS。原文点 这里

相关 [理性 微软 面试] 推荐:

死理性派教你做微软面试题

- Hing Sar - 果壳网 guokr.com - 果壳网
经常能在网上看到各种不知真假,却被转烂了的“超变态但很经典的微软面试题”. 那微软这样的大公司,到底有多喜欢“蹂躏”面试者的智商呢. 本文就从一套广为流传的的“10个最著名微软面试题”中选取了几个最经典的,来和它们较量较量. 一座小镇里有100对夫妇,他们都遵守一个奇怪的风俗:如果妻子发现丈夫背叛了她,那她就会在当天夜里杀死自己的丈夫.

重启开源,分享无限--微软面试187题精选

- Feng - 结构之法 算法之道
                      重启开源,分享无限--诚邀你加入微软面试187题的解题中.     我想,只要是稍微浏览过我博客的朋友都知道,本博客内总体上大致分为两个部分的内容:1、算法(如十六个经典算法研究系列);2、面试与编程(涉及到微软面试100题系列,程序员编程艺术系列,海量数据处理面试题集锦等等).

死理性派教你做谷歌面试题

- han - 果壳网 guokr.com - 果壳网
长久以来,谷歌都因为拥有世界上最自由和优越的环境,让全人类羡慕不已. 不过,谷歌这样一个以创造力为生的神奇地方,对应聘对象来说,想成为其中一员可是有着不小的难度. 想进谷歌,先试试这些早已遍布互联网的谷歌面试题吧. 三个人打算分一个矩形的蛋糕,可是有一个人已经偷偷地切走了一小块矩形的部分. 如果只能直直地切一刀,那么另外两个人应该怎么切才能体积均匀地分掉剩下的部分呢.

微软面试题—无聊的话可以来提高下智商哦

- bin - 无聊哦
你让工人为你工作7天,回报是一根金条,这个金条平分成相连的7段,你必须在每天结束的时候给他们一段金条. 如果只允许你两次把金条弄断,你如何给你的工人付费. 有一辆火车以每小时15公里的速度离开北京直奔广州,同时另一辆火车每小时20公里的速度从广州开往北京. 如果有一只鸟,以30公里每小时的速度和两辆火车同时启动,从北京出发,碰到另一辆车后就向相反的方向返回去飞,就这样依次在两辆火车之间来回地飞,直到两辆火车相遇.

9个offer,12家公司,35场面试,从微软到谷歌

- - CSDN博客移动开发推荐文章
毕业答辩搞定,总算可以闲一段时间,把这段求职经历写出来,也作为之前三个半月的求职的回顾. 首先说说我拿到的offer情况:. 1) 微软,3面->终面,搞定(+1). 2) 百度,3面->终面,口头offer(+1). 5) 布丁移动,3面,搞定(+1). 6) 涂鸦游戏,3面,搞定(+1). 7) 友盟,3面->CEO面,搞定(+1).

[来自iPc.me] 18条有趣的微软面试题,自认IQ智商高的朋友来挑战一下吧!

- 刚子 - iPc.me
你让工人为你工作7天,回报是一根金条,这个金条平分成相连的7段,你必须在每天结束的时候给他们一段金条. 如果只允许你两次把金条弄断,你如何给你的工人付费. [ 请大家更新订阅地址 http://feed.ipc.me ]. iPc.me 猜你可能还会喜欢:IE9正式版疑难解答与使用技巧分享. 成长中的80后们所面临的十大心理问题.

变态面试

- Tony - 叫兽与你同在

RoBa:Facebook 面试 Q&A

- - 博客 - 伯乐在线
前言:本文作者 RoBa ,据其个人博客中简绍是在腾讯北京搜索部门做后台开发工作. 他最近拿到 Facebook 入职 Offer 后,不少读者对此事有些提问. 本文是 Roba 做的问题答复总结. 说实话,其实我的眼界从来很狭窄,以前想的是,如果能在天朝帝都扎下脚跟,过上老婆孩子热炕头的日子,对我来说已很满足.

Hibernate面试题

- - ITeye博客
什么是Hibernate的并发机制. Hibernate并发机制:. a、Hibernate的Session对象是非线程安全的,对于单个请求,单个会话,单个的工作单元(即单个事务,单个线程),它通常只使用一次,. 如果一个Session 实例允许共享的话,那些支持并发运行的,例如Http request,session beans将会导致出现资源争用.

java面试题

- - Java - 编程语言 - ITeye博客
 抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地注意与当前目标有关的方面. 抽象并不打算了解全部问题,而只是选择其中的一部分,暂时不用部分细节. 抽象包括两个方面,一是过程抽象,二是数据抽象.  继承是一种联结类的层次模型,并且允许和鼓励类的重用,它提供了一种明确表述共性的方法. 对象的一个新类可以从现有的类中派生,这个过程称为类继承.