数学

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

微软面试题答案,微软面试题怎么做?详解

梦里醉逍遥 发表于  2011-08-29 18:32

经常能在网上看到各种不知真假,却被转烂了的“超变态但很经典的微软面试题”。那微软这样的大公司,到底有多喜欢“蹂躏”面试者的智商呢?本文就从一套广为流传的的“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。原文点 这里

热门评论

显示所有评论

全部评论(176)
  • 1楼
    2011-08-29 18:42 Home

    杀花?犯人问题未免时间太长了点吧……

    [0] 评论
  • 2楼
    2011-08-29 18:43 nasdaq 软件工程师,小众软件爱好者

    杀花!每次看这些问题都好纠结。不能理解前提条件。比如那个杀丈夫的,为什么要一天看一次,聚在一起不是一会儿就杀完了么
    所以我去不了微软么

    [1] 评论
  • 3楼
    2011-08-29 18:47 nasdaq 软件工程师,小众软件爱好者
    引用nasdaq的回应:杀花!每次看这些问题都好纠结。不能理解前提条件。比如那个杀丈夫的,为什么要一天看一次,聚在一起不是一会儿就杀完了么
    所以我去不了微软么

    貌似前提要加上每天只有晚上才能杀老公、第二天全镇人才知道。不然的话没法计算吧。

    [0] 评论
  • 4楼
    2011-08-29 18:47 大叔碎碎念

    偶的天。。。这让我现场做。。。也就能做出一两道。。。

    [0] 评论
  • 5楼
    2011-08-29 18:49 MelpoMene

    我也纠结了…………

    [0] 评论
  • 6楼
    2011-08-29 18:50 sssssummer

    有好几个看过了呢!
    不过这些题目还真的不错,打破常规思维

    [0] 评论
  • 7楼
    2011-08-29 18:52 nasdaq 软件工程师,小众软件爱好者
    引用nasdaq的回应:
    貌似前提要加上每天只有晚上才能杀老公、第二天全镇人才知道。不然的话没法计算吧。

    如果是按照题目写的“马上”杀老公,那么这个时间应该是不一定的。需要视每个人观念中“马上”的时间长度而定。一旦每个人对于“马上”的理解不同的话。就没法得出杀光外遇男的结论。

    [0] 评论
  • 8楼
    2011-08-29 19:01 馒头老妖 有机化学博士,法学学士

    微软面试就是反人类。

    [6] 评论
  • 9楼
    2011-08-29 19:01 Cerberus

    3个不会……计算机专业悲剧了……我还怎么活……

    [0] 评论
  • 10楼
    2011-08-29 19:02 Buddy松

    表示目标是苹果

    [0] 评论
  • 11楼
    2011-08-29 19:08 流氓神猫

    我数学不好,晕!还有一个100盏灯问题,可是我已经忘记约数是什么了。

    [0] 评论
  • 12楼
    2011-08-29 19:32 sqybi 计算机科学与工程专业本科生,口琴控,动漫迷

    囧,怀疑此文中题目来自微软面试的说法会被谣言粉碎机粉碎。。。

    [0] 评论
  • 13楼
    2011-08-29 19:34 多棱镜

    那个100盏灯不懂啊……高中生压力很大……

    [2] 评论
  • 14楼
    2011-08-29 19:48 kk19938

    竟然都看懂了

    [0] 评论
  • 15楼
    2011-08-29 19:49 王小成

    +1

    引用馒头老妖的回应:微软面试就是反人类。
    [0] 评论
  • 16楼
    2011-08-29 19:50 Keep_AI

    烧脑阿.

    [0] 评论
  • 17楼
    2011-08-29 20:13 程序猿啊~

    表示面试中都碰过了。。。日而不语~

    [0] 评论
  • 18楼
    2011-08-29 20:17 流氓神猫

    其实你们没有想过么,正是这样的面试题让公司内部人员变得同质化,大家都只会一样的事,怎么能解决问题?假如旧人能解决的话就不需要聘用新人,假如聘用的新人和旧人一样有屁用?

    [0] 评论
  • 19楼
    2011-08-29 20:22 子树

    引题“来看看它们是怎么被死理性派一一推到的吧。”
    “推到”别字。应为“推倒”。

    [0] 评论
  • 20楼
    2011-08-29 20:25 子树

    “每个女人都知道除自己丈夫之外其他男人的外遇情况”——这是一个怎样yd河蟹的小镇……

    [0] 评论
  • 21楼
    2011-08-29 20:27 吴师傅 数学专业
    引用sqybi的回应:囧,怀疑此文中题目来自微软面试的说法会被谣言粉碎机粉碎。。。


    说了哈 不确定啊 就是不保证真实性的。

    [0] 评论
  • 22楼
    2011-08-29 20:46 千克每二次方秒每米
    引用nasdaq的回应:杀花!每次看这些问题都好纠结。不能理解前提条件。比如那个杀丈夫的,为什么要一天看一次,聚在一起不是一会儿就杀完了么
    所以我去不了微软么

    杀老公,杀花……

    [0] 评论
  • 23楼
    2011-08-29 20:55 Dreaskt

    没一个有难度

    [0] 评论
  • 24楼
    2011-08-29 20:55 sx349

    过桥问题在多人情况下有贪心算法
    按照过桥时间排序后,每次考虑接下来两个人Ai和Ai+1(i>=3;假设时间最短的是A1 A2),有两种方案:
    1.A1A2过去,A1回来,Ai Ai+1过去,A2回来
    2.A1Ai过去,A1回来,A1 Ai+1过去 A1回来
    如果方案1快,用方案1;
    如果方案2快,把Ai送过去,Ai+1作为下一个考虑对象。
    经过动态规划对拍,贪心没有问题

    [0] 评论
  • 25楼
    2011-08-29 20:55 梦里醉逍遥 coder,历史爱好者
    引用nasdaq的回应:
    如果是按照题目写的“马上”杀老公,那么这个时间应该是不一定的。需要视每个人观念中“马上”的时间长度而定。一旦每个人对于“马上”的理解不同的话。就没法得出杀光外遇男的结论。

    小声说,其实我挺赞同你的…… = =

    [0] 评论
  • 26楼
    2011-08-29 20:58 oldherl

    第一个,如果镇长宣布的是错误的,实际上没有人有外遇,那么这些男人都要在第一天不幸地被杀掉……

    [0] 评论
  • 27楼
    2011-08-29 21:01 帝归 程序员

    (所以你知道为什么微软一直被程序员们鄙视了吧)

    [0] 评论
  • 28楼
    2011-08-29 21:05 Maigo-_- 语言爱好者
    引用nasdaq的回应:
    如果是按照题目写的“马上”杀老公,那么这个时间应该是不一定的。需要视每个人观念中“马上”的时间长度而定。一旦每个人对于“马上”的理解不同的话。就没法得出杀光外遇男的结论。

    赞同,“天”这个单位不知道从哪儿冒出来的。

    [0] 评论
  • 29楼
    2011-08-29 21:06 Maigo-_- 语言爱好者

    还有,如果镇长宣布有人有外遇,而实际上所有的男人都很老实的话……那就杯具了……

    [0] 评论
  • 30楼
    2011-08-29 21:15 氧气1996

    看了解析都不懂的是不是彻底没戏了(……)。

    [0] 评论

显示所有评论

你的评论

登录 发表评论

梦里醉逍遥
梦里醉逍遥 coder,历史爱好者

作者的其他文章

更多科研事,扫码早知道

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区