5个微软变态解谜面试题(中文) & 10 Famous Microsoft Interview Puzzles(英文)附答案

微软这样的大公司,自然是人人都想去的。但能进去的人肯定也不是什么等闲之辈,这光从那些被称为“超变态”的面试题中就可见一斑。不过再变态的题目,也是有解的。那微软这样的大公司,到底有多喜欢“蹂躏”面试者的智商呢?

你的丈夫有外遇吗?

一座小镇里有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 ) 处。

寻找次品

你有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 分钟。

表针问题

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

直觉也许会告诉你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点方向。

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

本文版权属于果壳网(guokr.com),转载请注明出处。

以下为英文原版的10个面试题, 附有原文章答案

10 Famous Microsoft Interview Puzzles

Here is a list of 10 famous puzzles which have been asked on a Microsoft Interview. They are not in any specific order.

Clock Hands

How many times a day do the minute and hour hands of a clock overlap? Answer

Is Your Husband a Cheat?

A certain town comprises of 100 married couples. Everyone in the town lives by the following rule: If a husband cheats on his wife, the husband is executed as soon as his wife finds out about him. All the women in the town only gossip about the husbands of other women. No woman ever tells another woman if her husband is cheating on her.  So every woman in the town knows about all the cheating husbands in the town except her own. It can also be assumed that a husband remains silent about his infidelity. One day, the mayor of the town announces to the whole town that there is at least 1 cheating husband in the town. What do you think happens? Answer

100 Prisoners in Solitary Cells

100 prisoners are stuck in the prison in solitary cells. The warden of the prison got bored one day and offered them a challenge. He will put one prisoner per day, selected at random (a prisoner can be selected more than once), into a special room with a light bulb and a switch which controls the bulb. No other prisoners can see or control the light bulb. The prisoner in the special room can either turn on the bulb, turn off the bulb or do nothing. On any day, the prisoners can stop this process and say “Every prisoner has been in the special room at least once”. If that happens to be true, all the prisoners will be set free. If it is false, then all the prisoners will be executed. The prisoners are given some time to discuss and figure out a solution. How do they ensure they all go free? Answer

The Ant Problem

Three ants are sitting at the three corners of an equilateral triangle. Each ant starts randomly picks a direction and starts to move along the edge of the triangle. What is the probability that none of the ants collide? Answer

Gold for 7 days of Work

You’ve got someone working for you for seven days and a gold bar to pay them. You must pay the worker for their work at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker? (Assuming equal amount of work is done during each day thus requiring equal amount of pay for each day) Answer

Trains and Birds

A train leaves City X for City Y at 15 mph. At the very same time, a train leaves City Y for City X at 20 mph on the same track. At the same moment, a bird leaves the City X train station and flies towards the City Y train station at 25 mph. When the bird reaches the train from City Y, it immediately reverses direction. It then continues to fly at the same speed towards the train from City X, when it reverses its direction again, and so forth. The bird continues to do this until the trains collide. How far would the bird have traveled in the meantime? Answer

A Box of Defective Balls

You have 10 boxes of balls (each ball weighing exactly10 gm) with one box with defective balls (each one of the defective balls weigh 9 gm). You are given an electronic weighing machine and only one chance at it. How will find out which box has the defective balls? Answer

Globe Walker

How many points are there on the globe where, by walking one mile south, then one mile east and then one mile north, you would reach the place where you started? Answer

4 Quarts of Water

If you had an infinite supply of water and a 5 quart and 3 quart pails, how would you measure exactly 4 quarts? and What is the least number of steps you need? Answer

Four People on a Rickety Bridge

Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person:  1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge? Answer

How many questions have you heard before? Post in comments.


Posted

in

by

Tags:

Comments

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

网站由ITGeeker技术奇客开发并管理; 隶属于GeekerCloud奇客罗方智能科技

Site designed and developed by ITGeeker which is a sub-website of GeekerCloud

网站地图 XML | 沪ICP备2021031434号-3