12.3日谷歌面试题详解
题目：你拿着两个鸡蛋站在100层的大楼上。鸡蛋或许结实到从楼顶掉下也不会摔破，或许很易碎，在一楼摔下就破碎。最少试验多少次可以找出鸡蛋不会被摔碎的最高楼层?
解答： 在只有一个鸡蛋时，保险起见，我们只能从一楼开始，一层一层地试验，看看鸡蛋有没有被摔烂。这样最精确，但是消耗的时间也最久。如果我们事先就知道这个鸡蛋不被摔碎的最高落下点在30层到75层之间，我们最多也只要尝试45次就能知道结果。现在我们手上有两个鸡蛋，根据上面的分析，一个合理的策略就是用第一个鸡蛋确定出一个较小的楼层范围，然后在这个范围里用第二个鸡蛋从下往上逐层尝试。
比如说让第一个鸡蛋每隔5层试验一次。当它在某一层被摔烂时，也就意味着确定了一个4层的待测试宽度(为什么是4层呢?假如鸡蛋在5楼的时候没破，10楼的时候破了，那么我们就只需要知道鸡蛋在 6 , 7 , 8 , 9 层的结果)。这时候，用第二颗鸡蛋一层一层地尝试，就能用较少的次数找出鸡蛋刚好摔不烂的高度。
需要注意的是，如果想留给第二颗鸡蛋较小的测试宽度，就要缩短第一个鸡蛋的测试跨度。相应的，也就增加了尝试次数。为了确定合适的跨度，使得总试验次数之和尽可能小，我们可以采取如下的.办法。
设跨度是L，第一颗鸡蛋的尝试次数就是[ 100/L ]，第二颗鸡蛋的尝试次数就是 L - 1，因此尝试次数总和就是 [ 100/L ] + L - 1 。根据这个公式，我们可以列出下面这个表格：
可以看出，我们只需要选 8 - 13 之间的一个宽度，都能使得总尝试次数是19次。
但问题是，这已经是最优策略了吗，有没有更好的方法呢?
有的。上面的方法固定了第一颗鸡蛋的测试跨度，如果我们灵活变动，就能使得总尝试次数变得更少。首先，我们选择从14楼丢下第一颗鸡蛋。如果它破碎了，我们就从1楼开始，逐层丢第二颗鸡蛋，最多试14次便能得到答案。如果它没有破碎，那我们往上走 13 层，在 27 楼第二次丢下第一颗鸡蛋。此时如果鸡蛋碎了，那我们只需要在 15 层到 26 层之间用第二颗鸡蛋进行最多12次试验即可，加上第一颗鸡蛋的两次尝试，仍然是14次。类似的，依次减小测试跨度，如果鸡蛋足够顽强，那我们丢下第一颗鸡蛋的楼层就分别是 14 ， 27 ， 39 ， 50 ， 60 ， 69 ， 77 ，84 ， 90 ， 95 ， 99 以及最后的100层。因为第一颗鸡蛋每多尝试一次，第二颗鸡蛋需要尝试的最大次数就减少一次，因此，总尝试次数的最大可能值一直是不变的，保持在14次。用这种方法，我们只需要不超过14次的尝试就能够找出答案。有没有更优的策略了?感兴趣的读者可以自行思考。
http://jianlimoban.c321.cn/【12.3日谷歌面试题详解】相关文章：
谷歌的面试题目04-11
谷歌工程师的面试题04-11
谷歌薪酬最高十职位10-28
德尔福面试题01-11
移动面试题04-01
英文面试题08-06
mybatis面试题05-09
谷歌创始人送给大学生的毕业留言07-30
华为公司面试题04-29
英语面试题目03-30