Apple

## Interview Question

Software Engineer Interview

-

# Unexpected: Puzzle question. If you have 2 eggs, and you want to figure out what's the highest floor from which you can drop the egg without breaking it, how would you do it? What's the optimal solution?

Tags:technical, algorithm

24

This is common sense. Eggs will break even when dropped from a 1 ft. So, keep the eggs and make an omelette.

Alphonse on

6

Assuming the 1st floor does not count, I would start on the third floor. If it breaks, try the next egg on the 2nd floor. The answer would be I can drop it from the 2nd floor, or it will always break (remember the 1st does not count). Now assume the first egg did not break, we know the 3rd floor is safe. You still have one more egg to spare, try it on the 4th floor. The conclusion will be either you can drop an egg on the 3rd floor or 4th floor, based the result of the 2nd egg. Now if the 1st floor counts, minus the floor number by 1 on all the floor numbers above.

Shelby on

4

int get_safefloor( int highest_safe_floor = 1 ) { floor = highest_safe_floor + 2; if( brokenegg( floor ) ) { if( brokenegg( floor - 1 ) ) return floor; else return floor - 1; } return get_safefloor( floor + 2 ); }

Wolvrix on

2

if its two raw eggs I would probably be very careful even on the ground floor.... for a couple of hard boiled eggs I wouldn't worry too much... might be still careful with slightly under or runny ones.... basically before running off to figure out a solution I would like to know about the state of the eggs.... then again if you were to say "assume this is a hypothetical egg with a hypothetical resistance to shattering coefficient" I would just climb the building one floor at a time and drop an egg (and come down to fetch it back then climb to the next floor if its still intact)... so say the egg breaks at floor 5 I can safely say floor 4 is safe for the egg to go diving from.... then proceed to go make me an omelette from the other egg..... see I used both eggs as well....

Imtiaz on

1

Boiled it and drop wherever u are...it won't break!

soumen patra on

1

why would i even need 2 eggs? 1 egg is enough. Drop it from 1st floor, it it breaks then there is no safe floor, as above that it will obviously break from every floor and if it does not break, then just go and take it back! as it has not broken! ryt? then drop it from 2nd floor....and similarily till you find the floor from which it breaks and if it breaks from floor x, then x-1 is the highest safest floor.

Anonymous on

2

Go to the top floor of any building. Drop the egg from a miniscule distance from the floor near your feet. You've dropped the egg from the top floor, and you've not broken it.

Anonymous on

2

every answer above is wrong. The only way, having 2 eggs, is to starts from the 2º floor. CASE 1: egg breaks ---- Go 1 floor down (so floor 1) and try the second egg: -------- CASE 1: egg breaks -> The safe floor is the down floor (ground floor in this case); -------- CASE 2: egg doesn't break -> This floor (floor 1) is the safe one. CASE 2: egg doesn't break -> go 2 floor upstairs and starts again. Complexity of this algorithm: Being N the number of the maximum tried floor, it will be N/2 + 1 in the best, worst and medium case.

Matteo Gobbi on

1

You might at least save yourself the hassle of stair climbing, by tossing the egg up at one in floor increments

jmoore2141 on

1

As already mentioned, optimize summation i.e. X + (X-1) + (X-2) + ... + 1 = Number of Floors, solve X.

Chris on

1

suppose 100 floors make 10 groups ie g1,g2......g10 while(group=true){ t=top floor of group throw egg from t if(not broken){ goto nxt group//break } else{ //1 egg is broken start throwing from 1st floor of that group repeat till second egg is broken floor solution = floor privious to the broken egg } }

optimal solution on

1

I think N/2+1 is the optimal solution, but I think there are a couple ways to get there. 1. Like Gobbi suggested, starting at the bottom, drop the egg from every 2nd floor until you find where it breaks. Worst case, you will find it breaks on the top floor (N/2), and then need one more drop of the other egg on the next floor down to see if that's the floor that breaks the egg. 2. Drop the egg from half way up the building. This divides the search space in half. If it breaks, start on the bottom floor and work your way up. If it doesn't, start on the next floor up and continue up.

Bob W on

0

Dropping eggs from any floor won't break the floor...

Siddhi on

0

Its BinarySearch. return floornumber binarySearch(int numberofFloors, int FloorZero, int FloorN, int Egg)

Imran on

1

int getSafeFloor() { return getSafeFloor(3); } int getSafeFloor(int floor) { if(borkenEgg(floor)) //3 if(brokenEgg(floor -1)//2 return foolor -2; // 1 else return floor - 1; // 2 return getSafeFloor(floor + 2) }

hivehome on

0

If you had infinite eggs, then you can use binary search, but since we have 2 eggs, can't. The key insight to solve this problem is that, it should take the same number of tries for all the possible floors where the egg can break.

Venkat on

1

Let say you have N=100 floors. If you take the square root 10 and you you in steps of 10 (10th, 20th, 90th) form the bottom until the first egg breaks. Suppose it breaks at floor 30. Now you try floor 31,32.... So, this is a maximum of 19 tries. But you can be better. If you start initially with something like floor 14 and then you go 14+13, then 14+13+12... in that case you have at most 15 tries. Find F (the initial floor) so that F*(F+1)/2 >= N. Then you have at most F+1 steps.

Anonymous on

0

People, this is about semantics not physics checking if you can think outside the 'geeky box'. While it is possible indeed to research the minimum kinetic energy an average egg requires to break, conditional on the elasticity of the ground, here the interviewer wants you to be aware if the question implies breaking one of the two eggs or any egg. Best you take it with humour and say you once threw an Microsoft 'Eggsbox'

Jack Easterly on

0

Drop the egg at ground floor, if it breaks stop else double floor number and test until an egg breaks (use both eggs for that so you have to go down and collect the eggs only every second time) if 1 egg is broken go from last save position upwards one by one

dd on

2

Easy. This is done on any floor, the highest or the lowest. Simply drop the egg from one inch above your foot and it will not break.

Anonymous on

0

Start from First floor. Drop the egg. if it does not break, move to second floor and use the same egg.. keep doing this until the egg breaks and you'd have the answer

Anonymous on

0

Just observe how a hen lay eggs. Have you ever seen a hen broken any eggs when she's laying eggs? LOL

Youming on

0

i think its a question if you complicate things up or not...everyone knows from childhood that eggs are extremely fragile...so answer is it will break from every floor if there is no water underground or some soft thing...so you don't need to make experiments. answer is simple they will break from every floor

Anonymous on

2

Let the eggs hatch. The chances are just as favorable for a hen as a rooster. It is likely that you now have an infinite supply of eggs to test all of your theories.

d on

1

...try from the 3rd floor and each odd floor till N/2 floor...

Anonymous on

28

you have to optimize a summation series

Anonymous on

10

Isn't the answer more like, you can drop the egg even from the topmost floor without breaking it. The egg only breaks when it hits the floor.

Harivardhan Pyaram on

0

First l will fill up the water in floor then I will drop the eggs so these egs will not broke also it would floats

murali v on

0

From any floor, because egg can't break the floor

Priyanka Sharma on

2

Assume there are N floors, drop the 1st egg at N/2 + 1 floor. if it breaks, then you need to try the 2nd eggs from the 3rd floor till N/2 floor. (2nd floor don't need to try) If 1st egg breaks at N/2+1 floor....then its so easy you can think of by yourself...

Anonymous on