梦想破碎是没有声音的,它只是缓慢又沉默地离开了。 by 苏更生

一道有趣的面试题

面试 Jay13 20823℃ 15评论

现在很多大型IT企业在面试时都喜欢问一些智力相关的题目,虽然智力面试题在面试笔试中占的比例不大,但很多时候,面试环节中智力题往往会成为我们拿offer的最大拦路虎。因为有些面试官认为通过智力题可以考查你的思维能力、抽象问题的能力。

下面是一道很经典的智力型面试题,也是我一朋友在BAT面试中亲身见识过的一道题。各位来体验一下,看看自己的大脑是不是好使。

题目:

有一栋楼共100层,一个鸡蛋从第N层及以上的楼层落下来会摔破, 在第N层以下的楼层落下不会摔破。给你2个鸡蛋,设计方案找出N,并且保证在最坏情况下, 最小化鸡蛋下落的次数。(假设每次摔落时,如果没有摔碎,则不会给鸡蛋带来损耗)

形形色色的解答:

在参考下面的解答之前,请你先仔细思考10分钟。看你给出的方案最小下落次数是多少。如果题目总分10分,看看自己能得几分。

===========================答案分割线================================

解答1:得0分的答案

用二分法。

这基本可以说就是没有通过大脑得出来的答案,而且还貌似很牛掰的样子,并常常带着一个lgn的复杂度。如果你接着问怎么个二分法,他就答不上来了。

这个答案不是我杜撰出来的,而是我拿这个题目问过身边的一些人,其中有几个人真的随口就把二分法给说出来了。每当我听到二分法时,当我没问。

 

解答2:得5分的答案

如果我们动一下脑子仔细思考这个问题,我们会得到一个相对不错的答案。参加BAT面试那位朋友就给出了下面的这种方案,并自认为是一种很完美的答案。但面试官给出的回答是:我还是不满意。

据说,他这种思路的灵感来自于数学中的求极值问题。

已知两个自然数的和为25,求这两个数的平方和的最大、最小值。

解:设一个自然数为x 另一个自然数为25-x

x²+(25-x)²
=2x²-50x+625
=2(x²-25x+312.5)
=2[(x-12.5)²-156.25+312.5]
=2[(x-12.5)²+156.25]

所以可得:
当x取12.5时 有最小值2×156.25=312.5  (当x==y==12.5时取得极小值
当x取25时 有最大值2×(12.5²+156.5)=625

因此,很容易得到启发(当然,这只是一种直觉,并没有什么理论依据。)。100层楼,平均分成10分,每份刚好10层。

那么我们的做法如下:

将100层楼分成10分,每一份就是10层楼。首先,将鸡蛋从第10层楼开始扔。那么结果有两种可能:
情况1:如果碎了,说明临界楼层在1到10之间,但现在只剩下一个鸡蛋了,只能从第一层一直到第10层。
情况2:如果没有碎,接下来从第20层扔鸡蛋。
该方法的思路是,用一个鸡蛋来试探,找到临界楼层的大致范围[1~10]、[11-20]….[91-100]。然后用另一个鸡蛋在大致范围内找出精确楼层。该方法的最坏次数是:18次。(自己去算,如果你算出来是17次,那就17次呗:))

 

解答3:得10分的答案

这是真正有理有据的解答。具体如下所述:

我们先假设最坏情况下,鸡蛋下落次数为x,即我们为了找出N,一共用鸡蛋做了x次的实验。 那么,我们第一次应该在哪层楼往下扔鸡蛋呢?先让我们假设第一次是在第y层楼扔的鸡蛋, 如果第一个鸡蛋在第一次扔就碎了,我们就只剩下一个鸡蛋,要用它准确地找出N, 只能从第一层向上,一层一层的往上测试,直到它摔坏为止,答案就出来了。 由于第一个鸡蛋在第y层就摔破了, 所以最坏的情况是第二个鸡蛋要把第1到第y-1层的楼都测试一遍,最后得出结果, 噢,原来鸡蛋在第y-1层才能摔破(或是在第y-1层仍没摔破,答案就是第y层。) 这样一来测试次数是1+(y-1)=x,即第一次测试要在第x层。OK, 那如果第一次测试鸡蛋没摔破呢,那N肯定要比x大,要继续往上找,需要在哪一层扔呢? 我们可以模仿前面的操作,如果第一个鸡蛋在第二次测试中摔破了, 那么第二个鸡蛋的测试次数就只剩下x-2次了(第一个鸡蛋已经用了2次)。 这样一来,第二次扔鸡蛋的楼层和第一次扔鸡蛋的楼层之间就隔着x-2层。 我们再回过头来看一看,第一次扔鸡蛋的楼层在第x层,第1层到第x层间共x层; 第1次扔鸡蛋的楼层到第2次扔鸡蛋的楼层间共有x-1层(包含第2次扔鸡蛋的那一层), 同理继续往下,我们可以得出,第2次扔鸡蛋的楼层到第3次扔鸡蛋的楼层间共有x-2层, ……最后把这些互不包含的区间数加起来,应该大于等于总共的楼层数量100,即

得出答案是14。

即我先用第1个鸡蛋在以下序列表示的楼层数不断地向上测试,直到它摔破。 再用第2个鸡蛋从上一个没摔破的序列数的下一层开始,向上测试, 即可保证在最坏情况下也只需要测试14次,就能用2个鸡蛋找出从哪一层开始, 往下扔鸡蛋,鸡蛋就会摔破。

比如,我第1个鸡蛋是在第77层摔破的,那么我第2个鸡蛋就从第70层开始,向上测试, 第二个鸡蛋最多只需要测试7次(70,71,72,73,74,75,76),加上第1个鸡蛋测试的 7次(14,27,39,50,60,69,77),最坏情况只需要测试14次即可得出答案。

这个问题还有一个泛化的版本,即d层楼,e个鸡蛋,然后设计方案找出N, 使最坏情况下测试的次数最少。维基上给出了DP的解法,感兴趣的话也可以看看以下链接: 在第12章有比较详细的介绍。

The puzzle of eggs and floors

作者:快课网——Jay13

喜欢 (65)or分享 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(15)个小伙伴在吐槽
  1. 使用二分法: 1.用地一个鸡蛋从1、2、4、8、16……这样开始尝试,肯定在某个楼层鸡蛋破碎,假设这时楼层数为x。 2.使用第二个鸡蛋,从 (x/2)+1 、 (x/2)+2、(x/2)+3……x-1 层依次尝试。某层(假设为y)鸡蛋破碎。则答案为 y-1. 个人感觉,这个是一个朴素和直观的解答吧,就像准备丢弃的原始版本一样。解答3应该不是突然冒出来的吧?应该是对朴素解法有深刻理解之后一个升华(重构)吧。
    tjl2014-09-17 01:25 回复
  2. 只有在第0层才不会被摔坏,鸡蛋那么脆一米就会摔坏啦。这还用想吗????
    忽左忽右2014-09-17 01:29 回复
    • Jay13
      膜拜一下! :mrgreen:
      Jay132014-09-17 02:34 回复
  3. 看了半天 我都不知道是什么意思,鸡蛋能摔破 肯定调到一楼了
    janecer2014-09-17 02:30 回复
    • Jay13
      好吧,你把鸡蛋想成是玻璃球!
      Jay132014-09-17 03:56 回复
  4. 二分法逆向查找就行,但是最坏比较次数很大,能在10分钟之内相处第3种解答办法的人能占多少比重?在日常生活中,10分钟能想出第2种的应该是10分
    oliver2014-09-17 03:01 回复
    • Jay13
      很少很少。后来我们好几个人讨论了,我就想出了第二种方法。后面在CTCI上才看到第3种解答!
      Jay132014-09-17 03:59 回复
      • 墨 虺
        站长大人求指点.....2015-04-08方案
        墨 虺2015-04-08 08:27 回复
  5. 微软的面试官都没有常识吗?100层的楼,从1楼扔就可以了,不用想,只要人类能直立行走进去的楼,1楼不碎的几率小于50%。
    中专毕业代码写手2014-10-16 08:20 回复
    • 微软亚洲研究院就喜欢搞这种奇奇怪怪的东西。
      1angxi2014-11-28 15:44 回复
  6. 墨 虺
    我来颠覆三观啦啦啦........ [三分法取最小值]: 第一眼看到这个题目,先是想到了二分法,,,但立刻就觉得发现了一个亮点:我有两个鸡蛋诶,和一个鸡蛋情况相比,我做出了一个假设,三分法,[除数进行四舍五入,这点很关键](不好意思献丑 :mrgreen: ).....先进行第一步规划:拆分100层为33,66,100.接下来取最小值33用鸡蛋测试.....这里如果摔碎,最坏的情况是33以下进行三分法测试(每次取规划的区间最小值)只要8次!!!!!而如果鸡蛋没有碎的话,我们就可以上溯33以上的区域,经过演算最坏情况是要10次!!!!!具体演算过程我就不说了,不信的小伙伴可以自己试一试....我的演算没有用代码实现....但我相信,这个方案的次数应该是最少的了..... 要是有哪位小伙伴写好了验证程序,发个源码给我,邮箱:fyl1748262862@163.com :oops: :smile:
    墨 虺2015-04-08 08:18 回复
    • 你根本没有第二次3分的机会,只要第一个蛋破了,你就只能一层一层地试了。
      大魔王2016-06-03 05:21 回复
  7. 根据实操经验鸡蛋从我手中掉落即损,所以我选择问面试官要2鸡蛋做早餐 :wink: ,并入职担当“狮猴”进化导师,成为BAT高层领袖 :cool: 要是BAT不给发Offer,就在其面试官头顶进行落蛋试验 :lol:
    luke2016-02-09 00:40 回复
  8. 最少应该是10次。20,38,54,68,80,90,98,100。如果第一只鸡蛋在第20层摔碎则让第二只鸡蛋依次从第2,4,…,18层摔,最坏情况下要10次。第一只鸡蛋在后续楼层摔碎的情况可以此类推
    elvis wang2016-05-01 19:32 回复
    • 你也是错了,只要第一个蛋碎了,接下来就只能一层一层试了。
      大魔王2016-06-03 05:25 回复