Google 面试题 - 玻璃球

本贴最后更新于 1615 天前,其中的信息可能已经水流花落

题目

给你两个一模一样的玻璃球. 这两个球如果从一定高度掉到地上就会摔碎, 当然, 如果在这个高度以下往下扔, 怎么都不会碎, 超过这个高度肯定就一次摔碎.
现在已知这个恰巧摔碎的高度范围在 1 楼到 100 层之间, 如何用最少的试验次数, 用这两个玻璃球测试出玻璃球恰好摔碎的楼高

一般策略

逐一法

第 1 颗球: 从 1 楼开始, 逐一往上加, 直到摔碎为止, 则找到位置

二分法

第 1 颗球, 从 50 楼(1/2 的位置)开始, 如果未碎, 接着 75 楼, 如碎了
第 2 颗球, 从 51 楼开始, 逐一法到碎为止, 则找到位置.

粗选细选

第 1 颗球, 从 10 楼开始, 逐 10 往上加, 直到摔碎为止. 比如, 玻璃球在 50 楼碎了
第 2 颗球, 从 41 楼开始, 逐一法到碎为止, 则找到位置

分析

基本逻辑

  1. 如果只有一个球, 用逐一法是唯一可解决问题的方案.
  2. 如果有无限多的球, 用二分法是最优解(在没有任何额外提醒的情况下, 二分法一定是最优的)

双球的策略分析

从基本逻辑思考, 1 颗球必须用于逐一法, 1 颗球用于二分法. 有个困难点是在只有 2 颗球的情况下如何进行二分法.

可以通过如下方式

左边:二分/逐一混合算法, 是在第 1 颗球成功的情况下, 由于第 1 颗球还可以继续使用, 使用混合算法
右边: 逐一法, 第 1 颗一旦失败, 后面就只能用逐一法进行)
以左右两边的次数一致的原则, 进行二分法.
image.png

逐一递推

  1. 2 : 2
  2. 4 : 3
  3. 7 : 4
  4. 11 : 5
  5. 16 : 6
  6. 22 : 7
  7. 29 : 8
  8. 37 : 9
  9. 46 : 10
  10. 56 : 11
  11. 65 : 12
  12. 77 : 13
  13. 90 : 14

最佳答案

第 1 颗从第 15(14+1)楼开始, 运气最差的情况下, 试验 14 次, 可获得准确楼层.

  • Google

    Google(Google Inc.,NASDAQ:GOOG)是一家美国上市公司(公有股份公司),于 1998 年 9 月 7 日以私有股份公司的形式创立,设计并管理一个互联网搜索引擎。Google 公司的总部称作“Googleplex”,它位于加利福尼亚山景城。Google 目前被公认为是全球规模最大的搜索引擎,它提供了简单易用的免费服务。不作恶(Don't be evil)是谷歌公司的一项非正式的公司口号。

    49 引用 • 192 回帖
  • 面试

    面试造航母,上班拧螺丝。多面试,少加班。

    324 引用 • 1395 回帖
  • 数学
    18 引用 • 77 回帖 • 2 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • Rabbitzzc

    x = 100/x + 100% -1

  • emm 大概就是 第一个球是用来牺牲以少的次数判定区间,第二个球是用来在区间内查找正确的位置.

  • someone
    作者

    公式应该是 1+ (1+2+3+4+5 + ... + x) = 100 转换后, 1 + (1+x)*x/2 = 100, 然后求解, x=13.几