Amazon电面，比楼层扔鸡蛋题更难的智力题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Amazon电面，比楼层扔鸡蛋题更难的智力题

Amazon电面，比楼层扔鸡蛋题更难的智力题# JobHunting - 待字闺中

b*e2010-06-10 07:06

1 楼

【以下文字转载自 Biology 讨论区】
发信人: supersunday (Linda), 信区: Biology
标题: FDA批准抗癌新药
发信站: BBS 未名空间站 (Thu Sep 4 18:19:08 2014, 美东)
默克的anti-PD1上市，四位科学家获奖。
http://www.cancerresearch.org/news-publications/our-blog/septem
Tasuku Honjo, M.D., Ph.D., of Kyoto University School of Medicine
Lieping Chen, M.D., Ph.D., of Yale University School of Medicine
Arlene Sharpe, M.D., Ph.D., of Harvard Medical School
Gordon Freeman, Ph.D., of Harvard Medical School and the Dana-Farber Cancer
Institute

j*l2010-06-10 07:06

2 楼

一个俄国人问的题，估计要是fail的话就是栽在这道题目上了。
这题从Goolge的那个百层楼扔鸡蛋题变换而来，原来那道题，只需要从14, 27, 39, 50,
60, 69, 77, 84, 90, 95, 99依次扔第一个鸡蛋就可以了，然后再用第二个鸡蛋线性探测
变体题是这样的，从A地发货到B地，所需要时间是某个常数x, 1 <= x <= 100, 怎么找
出x？
方法是寄东西给顾客，顾客的数量不限制．对每个顾客都承诺一个到达天数t, 如果按
时或者提前收到了，顾客就默认了．如果迟到了，该顾客就一定会在t+1天投诉。
现在要求你用这个方法求出x的准确值, 使得等待天数最短（用最短时间得到x), 要求
最多只能收到两次投诉，收到第三次投诉是不行的。
我明确告诉他，这题和一道经典的扔鸡蛋题类似，大体思路就是用第一次投诉机会确定一个范围，然后再收到投诉后改用线性探测。
他说这题是和那题类似，但是要求不同，所以更难。主要是要求等待天数要尽可能短。所以一开始选50天，不是最好的解法。他还说，这题难，主要是看看你有什么思路想法，不要求一定要给出正确的答案来。
他还说，如果一开始太激进，从比

K*g2010-06-10 07:06

3 楼

麻烦你把google 那题也详细的写一下吧。多谢了

,
探测

【在 j**l 的大作中提到】

: 一个俄国人问的题，估计要是fail的话就是栽在这道题目上了。
: 这题从Goolge的那个百层楼扔鸡蛋题变换而来，原来那道题，只需要从14, 27, 39, 50,
: 60, 69, 77, 84, 90, 95, 99依次扔第一个鸡蛋就可以了，然后再用第二个鸡蛋线性探测
: 变体题是这样的，从A地发货到B地，所需要时间是某个常数x, 1 <= x <= 100, 怎么找
: 出x？
: 方法是寄东西给顾客，顾客的数量不限制．对每个顾客都承诺一个到达天数t, 如果按
: 时或者提前收到了，顾客就默认了．如果迟到了，该顾客就一定会在t+1天投诉。
: 现在要求你用这个方法求出x的准确值, 使得等待天数最短（用最短时间得到x), 要求
: 最多只能收到两次投诉，收到第三次投诉是不行的。
: 我明确告诉他，这题和一道经典的扔鸡蛋题类似，大体思路就是用第一次投诉机会确定一个范围，然后再收到投诉后改用线性探测。

j*l2010-06-10 07:06

4 楼

说说我事后诸葛亮想到的思路吧，面试45分钟想到太难了，就算知道原型的扔鸡蛋题也没有用，而且原型题也不是第一次见到就容易想到的。。。
不妨简化问题便于讨论，设要求的整常数x位于区间[1, 20]之间。
首先，20是不用测的，如果测19的时候收到complain, 则20即所求。
其次，如果不幸收到一个complain, 就好比摔碎了一个鸡蛋，接下来就必须用最慢的线
性探测了。
第一个探测的天数是多少呢？我们先来看看16。
假如探测16收到了complain, 那么我们最坏可能必须线性探测19, 18, 17, 那么总探测
天数是
19 + 18 + 17 + 16 = 70
假如探测16没有complain, 下一个探测的天数是多少呢？
注意到
16 + 15 + 14 + 13 + 12 = 70 <= 70, 再加11就超出
因此我们可以接着探测12
假如探测12收到了complain, 那么最坏可能总探测天数还是70
假如探测12没有complain, 下一个探测的天数是多少呢？
注意到
16 + 12 + 11 + 10 + 9 + 8 = 66 <= 70, 再加7就超出
因此

j*l2010-06-10 07:06

5 楼

100层楼，两个鸡蛋，探测哪层楼摔下鸡蛋仍然不破，而再上一层摔就破。
保证存在n, 1<= n <= 100, 当从n层以及n层以下扔鸡蛋不会破，而从n+1层扔鸡蛋就破
原理，先用第一个鸡蛋确定一个大的范围，再用第二个鸡蛋在这范围内线性探测
答案：
依次从14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99，100层扔第一个鸡蛋，如果摔
碎则线性探测，最坏情况都只需要扔14次

【在 K******g 的大作中提到】

: 麻烦你把google 那题也详细的写一下吧。多谢了
:
: ,
: 探测

b*h2010-06-10 07:06

6 楼

扔14次不是要用14个鸡蛋了吗？直接用binary search不是更快，log（100），7次就可
以了。

【在 j**l 的大作中提到】

: 100层楼，两个鸡蛋，探测哪层楼摔下鸡蛋仍然不破，而再上一层摔就破。
: 保证存在n, 1<= n <= 100, 当从n层以及n层以下扔鸡蛋不会破，而从n+1层扔鸡蛋就破
: 原理，先用第一个鸡蛋确定一个大的范围，再用第二个鸡蛋在这范围内线性探测
: 答案：
: 依次从14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99，100层扔第一个鸡蛋，如果摔
: 碎则线性探测，最坏情况都只需要扔14次

l*y2010-06-10 07:06

7 楼

你只有两个鸡蛋，没法用binary search

【在 b********h 的大作中提到】

: 扔14次不是要用14个鸡蛋了吗？直接用binary search不是更快，log（100），7次就可
: 以了。

j*l2010-06-10 07:06

8 楼

第一个鸡蛋如果没有扔坏，可以接着再扔

【在 b********h 的大作中提到】

: 扔14次不是要用14个鸡蛋了吗？直接用binary search不是更快，log（100），7次就可
: 以了。

O*r2010-06-10 07:06

9 楼

....

【在 j**l 的大作中提到】

: 第一个鸡蛋如果没有扔坏，可以接着再扔

K*g2010-06-10 07:06

10 楼

同意，用Binary search更快.其实就是在一个0/1的有序数组里,找第一个出现的1. O(
logN),但是最坏的情况还是O(N).两题都可以用这种方法解决。比较经典，呵呵。

【在 b********h 的大作中提到】

: 扔14次不是要用14个鸡蛋了吗？直接用binary search不是更快，log（100），7次就可
: 以了。

j*l2010-06-10 07:06

11 楼

只有两个鸡蛋可以扔，还要保证最坏情况下扔的次数最少。
这变体题是最多只能收到两次投诉，还要保证最坏情况下探测等待的总天数最小

【在 K******g 的大作中提到】

: 同意，用Binary search更快.其实就是在一个0/1的有序数组里,找第一个出现的1. O(
: logN),但是最坏的情况还是O(N).两题都可以用这种方法解决。比较经典，呵呵。

K*g2010-06-10 07:06

12 楼

不管怎么样，两个鸡蛋不够啊。
我觉得题目可能是说，让使用的鸡蛋数量最少吧。
谁有这题的原题？

【在 j**l 的大作中提到】

: 第一个鸡蛋如果没有扔坏，可以接着再扔

l*y2010-06-10 07:06

13 楼

你好好看看题吧

【在 K******g 的大作中提到】

: 不管怎么样，两个鸡蛋不够啊。
: 我觉得题目可能是说，让使用的鸡蛋数量最少吧。
: 谁有这题的原题？

i*e2010-06-10 07:06

14 楼

你看看原题目吧

【在 K******g 的大作中提到】

: 不管怎么样，两个鸡蛋不够啊。
: 我觉得题目可能是说，让使用的鸡蛋数量最少吧。
: 谁有这题的原题？

Z*Z2010-06-10 07:06

15 楼

顺便问一下关于这个扔鸡蛋问题的解析解的理解。
假设允许drop次数为d，允许break鸡蛋个数为b，可以测得最大楼层为f（d，b）
那么f（d，b）= C(d, 1) + C(d, 2) + ... + C(d,b)
这个怎么理解？

【在 j**l 的大作中提到】

B*p2010-06-10 07:06

16 楼

不用一个一个测
如果16收到complain,测18,如果complain, x = 17, otherwise, 测20

也没有用，而且原型题也不是第一次
见到就容易想到的。。。

【在 j**l 的大作中提到】

: 说说我事后诸葛亮想到的思路吧，面试45分钟想到太难了，就算知道原型的扔鸡蛋题也没有用，而且原型题也不是第一次见到就容易想到的。。。
: 不妨简化问题便于讨论，设要求的整常数x位于区间[1, 20]之间。
: 首先，20是不用测的，如果测19的时候收到complain, 则20即所求。
: 其次，如果不幸收到一个complain, 就好比摔碎了一个鸡蛋，接下来就必须用最慢的线
: 性探测了。
: 第一个探测的天数是多少呢？我们先来看看16。
: 假如探测16收到了complain, 那么我们最坏可能必须线性探测19, 18, 17, 那么总探测
: 天数是
: 19 + 18 + 17 + 16 = 70
: 假如探测16没有complain, 下一个探测的天数是多少呢？

y*c2010-06-10 07:06

17 楼

明确题意+提供思路，假设第一次探测x
则如果x就complain的总天数 x + \sum_{i=x+1}^{i=99}
如果没有complain, 下一次探测总天数 x' + \sum_{i=x'+1}^{i=x-1}
如此下去得到x序列。
很明显，x 应该是比较接近100的一个数，x'是小于x的一个数。原则是希望每一轮总天
数接近。由于第二个“鸡蛋”的测试带来的是平方项，所以第一个鸡蛋测试的gap肯定
不是线性递减的。具体怎么算我还没什么办法。

j*l2010-06-10 07:06

18 楼

首先测20是无效测试，它总是不会收到complain的
按照你的说法，如果16收到complain, 测18,
如果有complain, 需要测x = 19来确定x是19还是20，如果测19有complain, 那么你就
有三次complain, 算失败
如果没有complain, 需要测x = 17来确定x是17还是18

【在 B*****p 的大作中提到】

: 不用一个一个测
: 如果16收到complain,测18,如果complain, x = 17, otherwise, 测20
:
: 也没有用，而且原型题也不是第一次
: 见到就容易想到的。。。

j*l2010-06-10 07:06

19 楼

在1 <= x <= 20的范围内，我觉得第一次测16是最好的，有complain则线性测19, 18,
17, 在没有complain的情况下接下来依次测12，8，1, 这样能够保证最怀情况下最多等
70天，
19 + 18 + 17 + (16) = 70, 假如第一次测16就收到第一次complain
(16) + 15 + 14 + 13 + (12) = 70, 假如第二次测12的时候才收到第一次complain
(16) + (12) + 11 + 10 + 9 + (8) = 66, 假如第三次测8的时候才收到第一次
complain
(16) + (12) + (8) + 7 + 6 + 5 + 4 + 3 + 2 + (1) = 64, 假如第四次测1的时候才
收到第一次complain
原型题得到的非等差数列，公差依次减少1，能够保证数列到达100层，还能使最坏情况
下，都只需要扔14次。
两题的相似处，都有一系列的插入点，一个是扔第一个鸡蛋的楼层14, 27, 39, 50...,
另一个则是没有收到第一次complain前的一系列探测天数点，比如16, 12,

【在 y*c 的大作中提到】

: 明确题意+提供思路，假设第一次探测x
: 则如果x就complain的总天数 x + \sum_{i=x+1}^{i=99}
: 如果没有complain, 下一次探测总天数 x' + \sum_{i=x'+1}^{i=x-1}
: 如此下去得到x序列。
: 很明显，x 应该是比较接近100的一个数，x'是小于x的一个数。原则是希望每一轮总天
: 数接近。由于第二个“鸡蛋”的测试带来的是平方项，所以第一个鸡蛋测试的gap肯定
: 不是线性递减的。具体怎么算我还没什么办法。

l*m2010-06-10 07:06

20 楼

Amazon 的面试题为什么都是算法相关？没有别的问题吗？如果光作网页开发，用的着
这样吗？

j*l2010-06-10 07:06

21 楼

暂时还没有收到拒信，希望可以挺过去。

j*l2010-06-10 07:06

22 楼

知道思想后应该可以编程穷举，从最大天数开始递减找到第一个合适的测试点，使得后
续的一系列测试点中最小的那个测试点能够到达1，然后穷举就可以停止。

C*Y2010-06-10 07:06

23 楼

我很久以前也被问到扔鸡蛋的题目，当时没看过那道题，挣扎半天弄了一堆方程组没弄
出结果

a*a2010-06-10 07:06

24 楼

唉，赶紧回去补一下知识吧。
记得最初是给灯泡，测试灯泡的质量。

【在 K******g 的大作中提到】

: 不管怎么样，两个鸡蛋不够啊。
: 我觉得题目可能是说，让使用的鸡蛋数量最少吧。
: 谁有这题的原题？

B*t2010-06-10 07:06

25 楼

是个动态规划题，和扔鸡蛋的问题的本质一样，都是求min-max。复杂度O(x^2*(k-
1)), k是第几次投诉就告失败，用上二分的话可以优化到O(xlongx*(k-1)); 扔鸡蛋那
题可以优化到O(x*k),这题估计也可以。
DP方程是：
f[x][k] = min{max{m+f[m][k], (x-m)*(m+x-1)/2}, 1<=m写了个程序，
当x=20, k=3的时候，第一个实验16，最坏情况下必须的天数是70，
不过第一个实验17，最坏情况下必须的天数是69.
x=100, k=3, 第一个应该实验92，最坏情况下必须的最少天数是792

没有用，而且原型题也不是第一次见到就容易想到的。。。
线
探测

【在 j**l 的大作中提到】

j*l2010-06-10 07:06

26 楼

感觉你是对的，1 <= x <= 20的时候，应该从17开始试，最坏情况是69天。
19 + 18 + 17 = 54
17 + 16 + 15 + 14 = 62
17 + 14 + 13 + 12 + 11 = 67
17 + 14 + 11 + 10 + 9 + 8 = 69
17 + 14 + 11 + 8 + 7 + 6 + 5 = 68
17 + 14 + 11 + 8 + 5 + 4 + 3 + 2 + 1 = 65
DP的思路不好理解，感觉作为电面题太难。

【在 B*****t 的大作中提到】

: 是个动态规划题，和扔鸡蛋的问题的本质一样，都是求min-max。复杂度O(x^2*(k-
: 1)), k是第几次投诉就告失败，用上二分的话可以优化到O(xlongx*(k-1)); 扔鸡蛋那
: 题可以优化到O(x*k),这题估计也可以。
: DP方程是：
: f[x][k] = min{max{m+f[m][k], (x-m)*(m+x-1)/2}, 1<=m: 写了个程序，
: 当x=20, k=3的时候，第一个实验16，最坏情况下必须的天数是70，
: 不过第一个实验17，最坏情况下必须的天数是69.
: x=100, k=3, 第一个应该实验92，最坏情况下必须的最少天数是792
:

x*r2010-06-10 07:06

27 楼

Bless!

p*x2010-06-10 07:06

28 楼

大概在700多天可以保证试出结果。思想确实与仍鸡蛋完全一样。考虑把1到100映射到1
至5050（或4950）即可。

s*e2010-06-10 07:06

29 楼

是典型的DP问题，扔鸡蛋也是典型的DP问题。

【在 B*****t 的大作中提到】

s*e2010-06-10 07:06

30 楼

你的DP有点小问题，不是很精确（ (x-m)*(m+1）/2 是k=2是的特例，不能做dp方程）
，探讨一下
F(l,u,k) 是最坏可能下需要的天数。 l 是可能范围的lower bound, u 是upper
bound
K 表示最大可以接受的投诉次数。
F(1,100,2)就是本题所优化的。
当k = 1时，只能从大往小试，承诺99，98，97，。。。。1，所须天数是100+99+98+
97。。。+2。
F(l,u,1) = u + (u-1) + (u-2) … (l+1) = (u+l+1)*(u-l)/2
动态方程是
F(l,u,k) = min { m + 1 + Max( F( l,m,k),F(m+1,u,k-1))} l<=m<=u;

【在 B*****t 的大作中提到】

P*l2010-06-10 07:06

31 楼

bless.

【在 j**l 的大作中提到】

: 暂时还没有收到拒信，希望可以挺过去。

b*p2010-06-10 07:06

32 楼

rl问题，dp解法

j*l2010-06-10 07:06

33 楼

RL是什么意思？对k = 2的特例，DP方程还是好理解的，有助于推广到k更大的情形

【在 b********p 的大作中提到】

: rl问题，dp解法

B*t2010-06-10 07:06

34 楼

多谢指正，我的那个dp方程是K=2的特例，K>2时类似。
用F(l,u,k)表示状态，方程好写，不过复杂度要多乘以O(N),
注意到F(a,b,k)和F(1,b-a+1,k)的关系，可以用F(n,k)表示状态，状态转移的时候
要注意把前面略去的天数补上，具体可以递归的求出应该补上多少天，这样复杂度就可
以降一维。

方程）
upper
100+99+98+

【在 s***e 的大作中提到】

: 你的DP有点小问题，不是很精确（ (x-m)*(m+1）/2 是k=2是的特例，不能做dp方程）
: ，探讨一下
: F(l,u,k) 是最坏可能下需要的天数。 l 是可能范围的lower bound, u 是upper
: bound
: K 表示最大可以接受的投诉次数。
: F(1,100,2)就是本题所优化的。
: 当k = 1时，只能从大往小试，承诺99，98，97，。。。。1，所须天数是100+99+98+
: 97。。。+2。
: F(l,u,1) = u + (u-1) + (u-2) … (l+1) = (u+l+1)*(u-l)/2
: 动态方程是

j*l2010-06-10 07:06

35 楼

对100层楼，2个鸡蛋的问题，共有六组解都能保证最坏情况下最多扔14次
9-->22-->34-->45-->55-->64-->72-->79-->85-->90-->94-->97-->99-->100
10-->23-->35-->46-->56-->65-->73-->80-->86-->91-->95-->98-->100
11-->24-->36-->47-->57-->66-->74-->81-->87-->92-->96-->99-->100
12-->25-->37-->48-->58-->67-->75-->82-->88-->93-->97-->100
13-->26-->38-->49-->59-->68-->76-->83-->89-->94-->98-->100
14-->27-->39-->50-->60-->69-->77-->84-->90-->95-->99-->100
第六组解是网上最常见的解答，求出1 + 2 + ... + 14刚刚超过100
第一组解是动态规划求出的解答。
第一组解，第一个鸡蛋最多共测试14层
第二组和第三组解，第一个鸡蛋最多

l*g2010-06-10 07:06

36 楼

祝福楼主，这种题目关键是得练过吃透，鸡蛋问题有一篇paper找来读读，上面写了
general的情况是怎么解决的，如果看过那片paper，或许这个问题你就好解决了。

j*l2010-06-10 07:06

37 楼

那篇paper的名字？

【在 l*******g 的大作中提到】

: 祝福楼主，这种题目关键是得练过吃透，鸡蛋问题有一篇paper找来读读，上面写了
: general的情况是怎么解决的，如果看过那片paper，或许这个问题你就好解决了。

l*s2010-06-10 07:06

38 楼

嗯，一开始我也把它跟扔鸡蛋相类比，但不像扔鸡蛋题那样，能找出一个关于x 的简单
不等式。于是也 DP了。不过，我的结果和大家有点不同，仔细分析了大家的回复，发
现对这道题的理解略有不同。我觉得有两个问题需要澄清。
为了更清楚地说明我的思法，我定义一个 transaction 为：一个东西从 A 发到 B 地
的某个顾客，并许诺 y 天内到达。而这个 transaction 被认为是完成的，如果：y 天
过去了，没有接到用户投诉，或者接到了用户投诉。
这样，我的两个问题是：
1）能不能在一个transaction T 还没有完成之前，在某一天（可能是和发起 T 同一天
）再发起另一个 transaction W？
2）如果对 1）的回答是肯定的，那么，“最多只准收到两次投诉”，是指在找出 x 之
前，还是在所有已经发起的 transaction 都完成之后？
而我的理解是：
1）可以。否则为何要强调“顾客的数量不限制”呢？
2）都可以说得通。不同的理解有不同的解法。但个人认为，这“最多两次投诉”的限
制应该是在所有已经发起的 transaction 都完成之后，才比较符合原题的意思。
举

【在 j**l 的大作中提到】

: 那篇paper的名字？

Z*Z2010-06-10 07:06

39 楼

我觉得你的优化是对的。
楼主的解法是，在求解f[i]的时候，先发一个时间为j的包裹。用了你的优化，同时再发
一个i-1的包裹，这样原来的一个worst case(sum j ... i-1)就变成了i-1，从而总的时
间变短了。

【在 l********s 的大作中提到】

: 嗯，一开始我也把它跟扔鸡蛋相类比，但不像扔鸡蛋题那样，能找出一个关于x 的简单
: 不等式。于是也 DP了。不过，我的结果和大家有点不同，仔细分析了大家的回复，发
: 现对这道题的理解略有不同。我觉得有两个问题需要澄清。
: 为了更清楚地说明我的思法，我定义一个 transaction 为：一个东西从 A 发到 B 地
: 的某个顾客，并许诺 y 天内到达。而这个 transaction 被认为是完成的，如果：y 天
: 过去了，没有接到用户投诉，或者接到了用户投诉。
: 这样，我的两个问题是：
: 1）能不能在一个transaction T 还没有完成之前，在某一天（可能是和发起 T 同一天
: ）再发起另一个 transaction W？
: 2）如果对 1）的回答是肯定的，那么，“最多只准收到两次投诉”，是指在找出 x 之

j*l2010-06-10 07:06

40 楼

好像是把sum(j .. i-1)优化为sum(j+1 .. i-1), 少用了j天本身

再发
的时

【在 Z*****Z 的大作中提到】

: 我觉得你的优化是对的。
: 楼主的解法是，在求解f[i]的时候，先发一个时间为j的包裹。用了你的优化，同时再发
: 一个i-1的包裹，这样原来的一个worst case(sum j ... i-1)就变成了i-1，从而总的时
: 间变短了。

Z*Z2010-06-10 07:06

41 楼

对，是这样的

【在 j**l 的大作中提到】

: 好像是把sum(j .. i-1)优化为sum(j+1 .. i-1), 少用了j天本身
:
: 再发
: 的时

j*l2010-06-10 07:06

42 楼

路漫漫其修远兮，吾将上下而求索。

x*r2010-06-10 07:06

43 楼

恭喜！恭喜！

【在 j**l 的大作中提到】

: 路漫漫其修远兮，吾将上下而求索。

t*j2010-06-10 07:06

44 楼

我的思路和你一样，不过编程的时候有个要注意的地方：
动态方程是
F(l,u,k) = min { m + 1 + Max( F( l,m,k),F(m+1,u,k-1))} l<=m<=u;
～～～～～～～这边1<=m的。
可是为什么我计算机算出来的没有700天呢？
哪位高人也编一下，咱们对对结果？我的function k=2，x=20的时候返回29.

）
98+

【在 s***e 的大作中提到】