谷歌面试扔鸡蛋问题

JustYY.com 小赖子的英国生活和资讯

8 years ago

floor-n-drop-eggs 谷歌面试扔鸡蛋问题 ACM题解学习笔记数学数据结构与算法有意思的程序员程序设计算法编程计算机软件工程面试

扔鸡蛋算法问题

这题据说是 GOOGLE的面试题, 但是却真实的被一些软件公司拿来考应聘者. 比如我在前几年面试剑桥的博通公司/Broadcom, 在第二轮也被问到了这个问题.

题意是: 给你两个鸡蛋, 有个100层楼, 你可以把鸡蛋从任意一层楼扔下, 鸡蛋可能破, 也可能不破, 如果不破的话, 你可以继续用这个鸡蛋扔. 你需要用这两个鸡蛋来试出鸡蛋会破的最小楼层高度. 这两个鸡蛋一模一样. 问你采用什么策略可以使最坏情况下的尝试次数最少?

什么是最差情况? 如果你只有一个鸡蛋, 那么你最坏需要100次(需要从1层楼开始测试)才可以得到结论.

最直接的做法就是从第一层开始试, 然后第二层以此类推, 但是这种方法只需要用到1个鸡蛋即可. 如果第N层鸡蛋没碎但是第N+1层碎了, 答案就是N. 这种情况下最坏需要尝试100次.

如果我们在第50层扔呢? 如果鸡蛋碎了, 那么答案就在第1到第49层, 反之答案就在第51到第100. 鸡蛋碎了, 我们只有一个鸡蛋, 就只能从1试到49, 最坏情况下是 1 + 49次, 这种情况比上面最直接的做法(49)还差. 如果鸡蛋没碎, 那么我们还有两个鸡蛋, 但是层数只有50层了, 这时候就是一个子问题了.

同样, 再举个例子, 如果我们第一次在第33层, 鸡蛋碎了, 我们需要最坏情况下再试32次, 答案是32+1次. 如果鸡蛋不碎, 我们需要用两个鸡蛋试一下剩下的67层.

也就是说, 如果我们用 f(n) 来表示在第 n 层扔鸡蛋最差情况下的次数, 我们有两种可能, 再试 n – 1 次或者在剩下 n – i 层里用两个鸡蛋(子问题)的次数的最大值.

所以, 问题也就是找出所有情况下使 1 + max(i – 1, f(n – i)) 值最小的次数. 这里 1 就是因为你已经扔了一次了.

f(n) = min(1 + max(i – 1, f(n – i))) i 的范围从1到n
显然 f(1) = 1

用 C++ 来算算:

// cached results;
vector<int> cache(101, 0);

int f(int n) {
    if (n == 1) {
        return 1;
    }
    if (cache[n] > 0) { // 已经计算出结果了. 
        return cache[n];
    }
    auto v = n + 1; 
    for (auto i = n - 1; i >= 2; -- i) {
        v = min(v, 1 + max(i - 1, f(n - i)));
    }
    cache[n] = v;  // 把中间结果保存起来, 避免重复计算. 
    return v;
}

这里是把递归求解变成一个动态规化的最简单的方法, 就是缓存中间结果, 否则程序算不出结果. 以上求解得 14.

PS: 这题还有个升级版本(力扣887 Super Egg Drop), 需要结构二分搜索来解决.

英文: Google’s Two Egg’s Problem

面试经历

面试题

面试技巧

面试其它

强烈推荐

英国代购-畅购英伦
TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
Quidco 返现 (也是很不错的英国返现网站, 返现率高)
注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
注册就送10美元, 免费使用2个月的阿里云主机(性价比超高, 每月只需4.5美元)
注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
刷了美国运通信用卡一年得到的积分换了 485英镑
注册就送50英镑 – 英国最便宜最划算的电气提供商
能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版

面试经历

面试题

面试技巧

面试其它

强烈推荐

相关文章：