Thomson Reuters Interview Question
Software Engineer / DevelopersTeam: Eikon
Country: United States
Interview Type: In-Person
This is a classic one. You start from the second floor - if the egg breaks, then quit. Else go up one level with the same egg and try again. Once this egg breaks, you find the answer. Actually don't know what the second egg is for.
In worst case,u need to try 99 times. Try to minimize number of trials. It is possible.
With 2 eggs, with a modified version of helen2211's method, you can get the worst tries to 50 times.
Drop first egg from the 50 floor
if(first breaks){
start dropping second egg from 1st floor
// You may find egg breaks on the first floor.
// worst case, max 50 tries
}else{
start dropping the second egg from 51st going to 100th floor
// max 50 tries
}
Minimum number will be 19. y = (100/X) + X-1 . Maximize y. Hence, X will be 10. Hence , throw eggs at every interval of 10 and then go linear.
There are two ways to solve this problem :
* binary search for the first egg (risked to know where we need to look up)
* Fibonaccy sequence search 1,2,3,5,8,13,21,34,55,89 for the first egg
Once first egg is broken we know where we need to look:
binary example: we tried 50 if it broke we search from 1 to 50 incrementing by 1 if not we throw it from 50+100/2 (75) if it broke we search from 50 to 75 if not we throw it from 75+100/2 (87) if it broke we search from 75 to 87 incemrenting by one floor at a time and so on and so forth.
fibonacy example: same thing : we try 1,2,3,5,8.13,...
if first egg broke we get back to the last interval's minimum and increment by 1.
say there's a minimal number of tryouts X, then you want to try the Xth floor and if it breaks you try every floor 1..X-1 (that's how you get no more than X tryouts).
- avico81 November 13, 2012Thus, if the egg doesn't break you jump X-1 floors, since you already used 1 tryout, and again if it breaks this time you try the floors X+1..(X+[X-1] - 1) , or in other words all the floors between those two you tried.
Again, the next jump will be X-2 since you tried twice already.
In order to find X you need X+[X-1]+[X-2]+...+2+1 >= 100 (floors)
Sum(X=13) = (1+13)*(13/2) = 91 < 100
Sum(X=14) = (1+14)*(14/2) = 105 >= 100
So that X is 14.