J**B
发帖数: 204 | 1 2个鸡蛋测试第N层楼掉下去鸡蛋会碎，100层楼。
没看明白逻辑。 |
L***Q
发帖数: 508 | 2 举个例子，比如从50楼开始扔鸡蛋就会碎。第一次你从49楼扔，鸡蛋没碎，那你可以拿
这个蛋继续扔，并且你知道49楼不是答案。假设第一次你从50楼扔，蛋就碎了，你只剩
一个鸡蛋可以接着扔，你得到的信息是从50楼往上鸡蛋都会扔碎。
idea：两个蛋，一个拿去试出一个范围，然后用另一个蛋在这个范围内确定具体是哪一
层。
【在 J**B 的大作中提到】
: 2个鸡蛋测试第N层楼掉下去鸡蛋会碎，100层楼。
: 没看明白逻辑。
|
J**B
发帖数: 204 | 3 开锁哪题呢？多谢多谢！
【在 L***Q 的大作中提到】
: 举个例子，比如从50楼开始扔鸡蛋就会碎。第一次你从49楼扔，鸡蛋没碎，那你可以拿
: 这个蛋继续扔，并且你知道49楼不是答案。假设第一次你从50楼扔，蛋就碎了，你只剩
: 一个鸡蛋可以接着扔，你得到的信息是从50楼往上鸡蛋都会扔碎。
: idea：两个蛋，一个拿去试出一个范围，然后用另一个蛋在这个范围内确定具体是哪一
: 层。
|
S****h
发帖数: 115 | 4 记得看过解法，我试着explain下，练练手。
题目是求minimum的test 次数（就是说在最坏的情况下也能保证找到break floor）
假设最优解为n次试验能够确保找到safe floor
test NO.1 如果第一次试验鸡蛋就打碎，那么用第二个鸡蛋需要在(n-1）次试验内找出
break floor。 因为只有一个鸡蛋了，所以只能把剩下uncertain的楼层从低到高逐个
检验。因此，这次试验的高度为 testHeight = safe_florr + n;(如果高于这个值，那
么第一个鸡蛋一旦打碎，用第二个鸡蛋进行剩下的n-1次试验不可能找出safeFloor) 对
第一次试验来讲safe_floor是0层。所以testHeight = 0 + n;
test NO.2 同上，如果第一个鸡蛋没打碎，现在需要选择的 testHeight = safeFloor
+ (n-1) ==> testHeight = n +（ｎ- 1）；
．．．
test No.n testHeight = n + (n-1) + ... + 1
最后只要满足 testHeight >= 100 也就是 (1+n) * n / 2 >= 100
得出 n >= 14
【在 J**B 的大作中提到】
: 2个鸡蛋测试第N层楼掉下去鸡蛋会碎，100层楼。
: 没看明白逻辑。
|
J**B
发帖数: 204 | 5 开锁那题 本来锁都是关的，然后全被打开。(step=1)
1. step=factor of the number of door 的时候锁会被switch一次。
2. 第odd次touch 过锁头的时候，锁头会被打开。
3. 下面的就理解不了，请给解释下。 |
J**B
发帖数: 204 | 6 对的和书上一样的 开锁那题怎么解释的？
safeFloor
【在 S****h 的大作中提到】
: 记得看过解法，我试着explain下，练练手。
: 题目是求minimum的test 次数（就是说在最坏的情况下也能保证找到break floor）
: 假设最优解为n次试验能够确保找到safe floor
: test NO.1 如果第一次试验鸡蛋就打碎，那么用第二个鸡蛋需要在(n-1）次试验内找出
: break floor。 因为只有一个鸡蛋了，所以只能把剩下uncertain的楼层从低到高逐个
: 检验。因此，这次试验的高度为 testHeight = safe_florr + n;(如果高于这个值，那
: 么第一个鸡蛋一旦打碎，用第二个鸡蛋进行剩下的n-1次试验不可能找出safeFloor) 对
: 第一次试验来讲safe_floor是0层。所以testHeight = 0 + n;
: test NO.2 同上，如果第一个鸡蛋没打碎，现在需要选择的 testHeight = safeFloor
: + (n-1) ==> testHeight = n +（ｎ- 1）；
|
J**B
发帖数: 204 | 7 3.只有被touch了奇数次的锁最后才会是被打开的。就是从1~100寻找有odd个factor的
数。（晕，1是不是factor啊，小学的东东忘记光了，我这里假设是）。
【在 J**B 的大作中提到】
: 开锁那题 本来锁都是关的，然后全被打开。(step=1)
: 1. step=factor of the number of door 的时候锁会被switch一次。
: 2. 第odd次touch 过锁头的时候，锁头会被打开。
: 3. 下面的就理解不了，请给解释下。
|
d**0
发帖数: 124 | 8 这题有个变体 如果有三个鸡蛋怎么办 也是很有意思的问题
【在 L***Q 的大作中提到】
: 举个例子，比如从50楼开始扔鸡蛋就会碎。第一次你从49楼扔，鸡蛋没碎，那你可以拿
: 这个蛋继续扔，并且你知道49楼不是答案。假设第一次你从50楼扔，蛋就碎了，你只剩
: 一个鸡蛋可以接着扔，你得到的信息是从50楼往上鸡蛋都会扔碎。
: idea：两个蛋，一个拿去试出一个范围，然后用另一个蛋在这个范围内确定具体是哪一
: 层。
|
S****h
发帖数: 115 | 9 这个是DP问题，觉得光凭说不是很容易理解。不过DP从来只要知道怎么从sub optimal
solution得到最优解就好了。试试~
问题：N个鸡蛋，H层高楼，最少需要多少次trial可能确定safe floor?
Let S(n,h) be the minimum required number of trials for the conditon:
n eggs and h uncertain floor (不确定是否safe的楼层数，不是总的楼层高度)
假设此次试验在 x 层， x ∈ [1 ..h],并不是绝对楼层数，而是h个不确定的楼层中的
某一层。测试结果分为两种情况：
1. 鸡蛋打碎
s(n,h) = 1 + s(n-1, x -1);
2.鸡蛋完好无损
s(n,h) = 1 + s(n, h - x);
考虑到所有可能的x的取值[1..h]
s(n, h) = 1 + min{ max {s(n-1, x-1), s(n, h-x)}} x ∈ [1..h]
然后base case
s(n,h) = 1 //h == 1 只有一层，无论几个鸡蛋
= h //n == 1 只有一个鸡蛋，无论几层
= min{....} //above
【在 d**0 的大作中提到】
: 这题有个变体 如果有三个鸡蛋怎么办 也是很有意思的问题
|
J**B
发帖数: 204 | 10 开锁那题我看明白是最后要找1～100里有奇数个factor的数（这里我认为1也是factor
），请问这个DP怎么实现的(FAINT，DP是data path么，我不是CS的，面A家）。
【在 d**0 的大作中提到】
: 这题有个变体 如果有三个鸡蛋怎么办 也是很有意思的问题
|
p*****2
发帖数: 21240 | 11 觉得这题没什么意思？我感觉面试不会考到。有人考到吗？ |
h****e
发帖数: 928 | 12 扔鸡蛋的题目是一个经典的Brainteaser题目，在好几本面试书上都
讲过了，如CareerCup, How would you move Mount Fujian等。
开锁的也是。应该不会再考了吧。不过搞懂还是有用的。 |
f**********2
发帖数: 2401 | 13 开锁那个题，寻找1－100之间，factor为奇数的数，也就是完全平方数。只有完全平方
数＝某整数的平方，这样才有可能为奇数。比如25＝5*5＝1*25,factor为1,5,25. 其他
数的因子必然偶数。1可以是因子。 |
l*********8
发帖数: 4642 | 14 有奇数个factor的数是某个数的平方，就是 1,4, 9, 16,25,36,49,64, 81, 100. 共
十把锁。
factor
【在 J**B 的大作中提到】
: 开锁那题我看明白是最后要找1～100里有奇数个factor的数（这里我认为1也是factor
: ），请问这个DP怎么实现的(FAINT，DP是data path么，我不是CS的，面A家）。
|
