Someone from the previous Flatiron class (class 04-15, wish I could remember his name) sat with me and Sarah for a while, like, a long while sometime in the middle of August to walk us through a couple of questions that he or his classmates had been asked during technical interviews. One was the “Birthday Paradox” and the other was the “Two Egg Problem”.
The Setup:
It goes something like this: There is a 100 story building. You have two identical eggs. An egg, when dropped from a floor will either break or not break. If the egg breaks when dropped from some floor ‘n’ then it would have broken from every floor above that floor. If the egg does not breaks when dropped from some floor ‘n’ then it would have survived the fall from every floor below the floor ‘n’. If the egg is unbroken it can be picked up and dropped again. What strategy should you adopt to minimize the number of egg drops it takes to find the highest floor from which an egg can be dropped without breaking.
The REAL Question:
The solution that interviewer is looking for optimizes for the worst case scenario, or, as phrased in the DataGenetics article linked below, “Minimization of Maximum Regret”. So what does that mean? Your solution should ensure that, in the absolute worst case scenario, finding the floor from which a dropped egg will break takes as few drops as possible. Or, stated a bit differently, the most number of drops required to identify the floor from which the egg will break is as small as possible.
The Buildup:
First let’s examine the “One Egg Problem”.
Ok, so worst case scenario is that the egg breaks only when dropped from the 100th floor. How do we find this out? Well, since we only have one egg to work with we have to start at the first floor (the floor above the ground floor. Let’s do this European Style, ok?) and work our way up one floor at a time. If we skipped up a floor, say instead of starting on the first floor, we start on the second, and the egg breaks we can’t know if it would have also broken when dropped from the first floor because we are out of eggs. So, worst case scenario we have to drop that damn egg 100 times and either we get to know the inside of the elevator reeeeeeeeal well or we’re exhausted from a 100 storey climb.
Now let’s examine the “Many Egg Problem”.
So now we have infinite eggs. Omelettes forever!!!!!!! The problem is now a binary search, broken or unbroken after a drop. We halve the search range after each test. We drop an egg from floor 50 and it survives. We now only have 50 floors to search through. We test in the middle of the remaining floors (75) and the egg survives again. Two drops and we’ve narrowed the range down to 25. We halve the range again- floor 87- and the super egg still doesn’t break. Three drops. Half again, 93rd floor, egg survives. Four. And again, 96th, egg survives. Five. Again, 98, survives. Six. Again, 99, survives. Seven and we know the floor that causes the break is the 100th.
The Solution:
Back to Two Eggs. I miss my infinite eggs already. Later little buddies:
Ok, so we have two eggs. Where do we start? Let’s just say we want to halve the search range so we drop an egg at floor 50. It survives. So now we floor by floor. Finally second egg drops on floor 100. Our test took 51 drops. That’s a lot better than 100 like we had using only one egg but still a lot of drops.
Let’s try it again but this time let’s start at floor ten and go up by ten floor each time. Drop @10. Egg survives. @20, @30, @40, @50, @60, @70, @80, @90. That tenacious egg survives them all. We go up 10 floor again to floor 100 and the egg breaks! You are not indestructible my ovoid friend! Back down to floor 91 and step up one by one until… Hey, it survives every one! So thats 19 drops by my count. A lot better. But what if it had broken at floor 50 instead? That would mean drops @10, @20, @30, @40, @50, @41..@49 if the egg were to break at the 49th floor. Sooo, 14 drops. There’s a bit of a gap there in the number of drops it took to reach an answer when the highest safe drop floor was 99 versus 49, and in that gap is the heart of the problem. We want to make that distribution in the number of drops required more uniform.
The number of drops it takes to figure out the answer in the worst case scenario should always be the same. That’s the goal in making a uniform distribution. So let’s say that the egg drops at floor 9. Going by tens it takes a drop at floor 10, then 1..9 for a total of 10 drops. Now let’s say that it breaks at floor 19. Again going by ten it takes drops at 10, 20, 11..19 for a total of 11 drops. If we want to create a uniform distribution in the number of drops to find the answer in the worst case scenario we have to account for the extra drop that it took to from the first case (breaks at 9) to the second case (breaks at 19). If instead of jumping up 10 floors from 10 to 10 we instead jump up 9 floors from 10 to 19 (accounting for the extra multi-floor step) then the worst case scenario- the egg breaks at floor 18- takes drops at 10, 19, 11..18 for 10 drops again! There, there is an even distribution! So that’s the trick of it. Every time we make a multi-story leap up the building the distance that we go up should be reduced by one in order to account for the additional drop.
Now that we have the concept of it we can go a little more abstract. If we call the first floor from which we drop an egg ‘n’ then the next floor from which we drop an egg should be n-1 above the first drop point. The one after that should be n-2 above the last and so on. So it end up looking something like:
n + (n-1) + (n-2) + (n-3) + … + 1 >= (number of floors in the building)
This summation is identical to the formula for Triangular Numbers which simplifies to n(n+1)/2. So, I guess it’s assumed that you would know this. Don’t ask me why. For 100 floors that’s 100 = n(n+1)/2 which is equivalent to n2 + n - 200. If you solve that equation for n using the quadratic equation you get ~ 13.65. Let’s round that up to 14 since we are working with whole floors. So, after all that, our strategy is to drop the egg at floor 14 (n), 27 (n + n-1), 39, 50, 60, 69, 77, 84, 90, 95, and 100. Every worst case scenario requires 14 drops and we are done!
