Eggs problem
There's a building with 100 levels and you have two eggs. You can drop an egg from any level of the building to check whether it breaks or not. After it broke it is useless.
It is known that below a certain level eggs do not break and from that level up they always break.
The question is that which level it is? Tell me the minimum number of drops that will ALWAYS identify that level!
Generalization: N levels and k eggs...
levy
Levente Mészáros
Wednesday, December 08, 2004
int FindSafeLevel(void) {
int a,
level;
for (level = 10; level <=100; level = level + 10) {
if (EggDrop(level) == EGG_BREAK) {
for (a = level  9; a < level; a++) {
if (EggDrop(a) == EGG_BREAK) {
return a  1;
}
}
return level  1;
}
}
return 100;
}
So, at most 19 tests. Minimum 10 tests.
Am I close?
zekaric
Wednesday, December 08, 2004
Generalization would be...
Square root the total levels and that will be your starting level. Min will be the square root of the levels +/ 1 for integer rounding to a Max of 2 * Min  1 give or take a level.
zekaric
Wednesday, December 08, 2004
I should clarify the minimum tests. The minimum test for the local worst cases of the (multiples of 10)  1.
Actually starting at level 9 and even 8 with a jump of 9 and 8 will yeild the same maximum tests as 10 but have a slightly larger average test count.
zekaric
Wednesday, December 08, 2004
The solution is not so trivial.
http://www.techinterview.org/Solutions/fog0000000143.html
JHY
Wednesday, December 08, 2004
Damn... I guess I'm not hiring material.
zekaric
Thursday, December 09, 2004
It's similar to a binary search. You can determine the floor in log2 (100) = 7.
naveed
Tuesday, December 21, 2004
Recent Topics
Fog Creek Home
