一道有趣的Java面试题


  一个鸡蛋从第N层及以上的楼层落下来会摔破?


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


  下面是一道很经典的智力型面试题,是一位Java老师的朋友去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,即


  1x+(x-1)+(x-2)+...+1>=100


  2(x+1)*x/2 >= 100


  3


  得出答案是14。


  


上一篇:Java中Varargs机制的理解
下一篇:动力节点国庆三重礼

开班信息