m*******p
发帖数: 141 | 1 哭。。。。。。
电话了大约半个多小时。
是个中国人。 挺nice的。
我自己不争气。。。。。
哭。。。。。。。
题目答不出来， 郁闷地要死。
最后很紧张， 没跟他套近乎。 希望他见谅。 | B*******1
发帖数: 2454 | 2 a? Two eggs?
I was asked by the indian hiring manager in my first phone interview with
Amazon. | w****x
发帖数: 2483 | | H****r
发帖数: 2801 | 4 it's on careercup. DP
【在 m*******p 的大作中提到】
: 哭。。。。。。
: 电话了大约半个多小时。
: 是个中国人。 挺nice的。
: 我自己不争气。。。。。
: 哭。。。。。。。
: 题目答不出来， 郁闷地要死。
: 最后很紧张， 没跟他套近乎。 希望他见谅。
| p*****2
发帖数: 21240 | 5
second
【在 w****x 的大作中提到】
: 问这么恶心的问题.... 真无聊!!
| x*******1
发帖数: 28835 | | e***l
发帖数: 710 | 7 这个题还是很难想明白的。没做过的估计九成做不出来。 | h******6
发帖数: 2697 | 8
不是100， 14么？
【在 x*******1 的大作中提到】
: 不是17么。 呵呵。
| h****e
发帖数: 928 | 9 虽然这些brainteasers的题目不流行了，还是读一两本书
有备无患吧：
How to move Mount Fuji 或
How to ace the brainteaser interview | t**********h
发帖数: 2273 | 10 原题是什么？
哭。。。。。。电话了大约半个多小时。 是个中国人。 挺nice的。 我自己不争气。
。。。。哭。。。。。。。题目答不出来， 郁闷地要死。 最后很紧张， 没跟他套近
乎。 希望他见谅........
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
【在 m*******p 的大作中提到】
: 哭。。。。。。
: 电话了大约半个多小时。
: 是个中国人。 挺nice的。
: 我自己不争气。。。。。
: 哭。。。。。。。
: 题目答不出来， 郁闷地要死。
: 最后很紧张， 没跟他套近乎。 希望他见谅。
| | | K*******i
发帖数: 399 | 11 如果是巧妙的归约到
1 + 2 + ... + N >= 100, 求的最小的N = 14
那是brain teaser 智力题
如果要推广到n层楼m个鸡蛋，那是DP题
参考：http://www.mitbbs.com/article_t/JobHunting/31626309.html
这题从Goolge的那个百层楼扔鸡蛋题变换而来，原来那道题，只需要从14, 27, 39, 50
,60, 69, 77, 84, 90, 95, 99, 100层依次扔第一个鸡蛋就可以了，然后再用第二个鸡
蛋作线性逐层探测。
变体题是这样的，从A地发货到B地，所需要时间是某个常数x, 1 <= x <= 100, 怎么找
出x的准确值？
方法是寄东西给顾客(顾客的数量不限制)．对每个顾客都承诺货物能在天数t内到达,
如果按时或者提前收到货物，顾客就默认。如果迟到了，则顾客就一定会立即投诉。
现在要求你用这个方法求出x的准确值, 使得等待的总天数最短(用最短的时间求得x),
要求最多只准收到两次投诉，收到第三次投诉就告失败。
我明确告诉他，这题和一道经典的楼层扔鸡蛋题类似，大体思路就是先用第一次投诉机
会确定一个范围，收到投诉后再改用线性逐天探测。
他说这题是和那题思想类似，但是要求不同，也更难。主要是要求等待的总天数要尽可
能短。所以一开始选50天不是最好的解法。他还说，这题比较难，主要是看看你有什么
思路想法，不要求一定要给出正确的答案来。
讨论过程中他还说，如果一开始太激进，从比较小的天数尝试起，就会很快把两次投诉
机会耗光。相反，如果比较保守，从很大的天数尝试起，则等待的天数又会太长，难点
在如何找平衡？如何对最坏情况也能达到平衡？
更新解答
实际上这题就是考查动态规划。还是要借鉴扔鸡蛋题的动态规划思想。
扔鸡蛋题要最小化最坏情况下扔鸡蛋的总次数，而这道题要最小化最坏情况下总的等待
天数。
令F[i]表示已知1 <= x <= i的前提下，最坏情况下最少的等待总天数，j用来从1到i-1
穷举，如果承诺j天到货但收到投诉，则改用线性探测，最坏情况总的等待天数是(i -
1) + (i - 2) + (i - 3) + ... + j。 如果承诺j天但没有收到投诉，说明1 <= x <=
j, 则问题就转换为求一个规模更小的子问题F[j], 再加上已经等待了的天数j
所以动态规划的递推方程为
F[i] = min{max((F[j] + j), sum(from j to i-1)), 1 <= j <= i - 1}
基础情形F[1] = 0, F[2] = 1
对原型的扔鸡蛋题，令F[i]表示i层楼在最坏情况下最少的扔鸡蛋总次数。j用来从1到i
穷举，决定从哪层开始扔第一个鸡蛋。如果第一个鸡蛋在第j层碎了，则改用线性探测
，两个鸡蛋最坏情况下共扔了j次。如果第一个鸡蛋在j层没有碎，则从第j+1层开始算
起，上面共有i-j层楼，问题转换为一个规模更小的子问题F[i - j], 再加上已经扔的
次数1。
则有类似的动态规划递推方程
F[i] = min{max((F[i - j] + 1), j), 1 <= j <= i}
基础情形F[0] = 0, F[1] = 1
大家可以看看两个方程的类似之处。
另外如果k > 2, 也就是有三个鸡蛋以上或者允许三次以上投诉，则动态规划方程需要
增加一个关于k的维度进行推广。
附注:
对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 + ... + d
能刚好超过100, 解出d = 14
其它四组解也是对的。数列的共同特点是，二阶等差数列，不考虑边界100，各项间距
依次减少1 | h****e
发帖数: 928 | 12 多谢，好详细的解答。
50
【在 K*******i 的大作中提到】
: 如果是巧妙的归约到
: 1 + 2 + ... + N >= 100, 求的最小的N = 14
: 那是brain teaser 智力题
: 如果要推广到n层楼m个鸡蛋，那是DP题
: 参考：http://www.mitbbs.com/article_t/JobHunting/31626309.html
: 这题从Goolge的那个百层楼扔鸡蛋题变换而来，原来那道题，只需要从14, 27, 39, 50
: ,60, 69, 77, 84, 90, 95, 99, 100层依次扔第一个鸡蛋就可以了，然后再用第二个鸡
: 蛋作线性逐层探测。
: 变体题是这样的，从A地发货到B地，所需要时间是某个常数x, 1 <= x <= 100, 怎么找
: 出x的准确值？
| t**********h
发帖数: 2273 | 13 多谢
50
【在 K*******i 的大作中提到】
: 如果是巧妙的归约到
: 1 + 2 + ... + N >= 100, 求的最小的N = 14
: 那是brain teaser 智力题
: 如果要推广到n层楼m个鸡蛋，那是DP题
: 参考：http://www.mitbbs.com/article_t/JobHunting/31626309.html
: 这题从Goolge的那个百层楼扔鸡蛋题变换而来，原来那道题，只需要从14, 27, 39, 50
: ,60, 69, 77, 84, 90, 95, 99, 100层依次扔第一个鸡蛋就可以了，然后再用第二个鸡
: 蛋作线性逐层探测。
: 变体题是这样的，从A地发货到B地，所需要时间是某个常数x, 1 <= x <= 100, 怎么找
: 出x的准确值？
| k******I
发帖数: 238 | 14 可能是面试官本人出来了
【在 h****e 的大作中提到】
: 多谢，好详细的解答。
:
: 50
| w**z
发帖数: 8232 | 15 赞，能问一下您花了多久码了这些字？
50
【在 K*******i 的大作中提到】
: 如果是巧妙的归约到
: 1 + 2 + ... + N >= 100, 求的最小的N = 14
: 那是brain teaser 智力题
: 如果要推广到n层楼m个鸡蛋，那是DP题
: 参考：http://www.mitbbs.com/article_t/JobHunting/31626309.html
: 这题从Goolge的那个百层楼扔鸡蛋题变换而来，原来那道题，只需要从14, 27, 39, 50
: ,60, 69, 77, 84, 90, 95, 99, 100层依次扔第一个鸡蛋就可以了，然后再用第二个鸡
: 蛋作线性逐层探测。
: 变体题是这样的，从A地发货到B地，所需要时间是某个常数x, 1 <= x <= 100, 怎么找
: 出x的准确值？
| m*******p
发帖数: 141 | 16 谢谢!
学习了。
50
【在 K*******i 的大作中提到】
: 如果是巧妙的归约到
: 1 + 2 + ... + N >= 100, 求的最小的N = 14
: 那是brain teaser 智力题
: 如果要推广到n层楼m个鸡蛋，那是DP题
: 参考：http://www.mitbbs.com/article_t/JobHunting/31626309.html
: 这题从Goolge的那个百层楼扔鸡蛋题变换而来，原来那道题，只需要从14, 27, 39, 50
: ,60, 69, 77, 84, 90, 95, 99, 100层依次扔第一个鸡蛋就可以了，然后再用第二个鸡
: 蛋作线性逐层探测。
: 变体题是这样的，从A地发货到B地，所需要时间是某个常数x, 1 <= x <= 100, 怎么找
: 出x的准确值？
|
|
