# TechnicalArchitectureWorx

## Interviewing Question: The Eggs and the Tower

Posted by archworx on February 19, 2007

Think of this, you have a building which is 100 floors high and you have 3 eggs. You can throw an egg from any floor and it might or might not break, but there is a certain floor (a threshold floor) afterwhich eggs are guranteed to break for all floors above this certain floor.  If We want to know exactly which floor is the threshold floor, what is the minimum number of egg throws do we have do make?

Remember: You have only 3 eggs,  so if you break all the 3 eggs without finding the threshold floor then you have failed. Also remember that we want the minimum number of throws.

zero!!

2. ### archworxsaid

MMK: I just asked the author of this question, and he says that the fact that it is an egg (and can break very easily) is immaterial. It could be a piano or a marble egg or anything else for that matter. So the answer will have to rely on algorithmic intelligence.

So what will it be?

3. ### yshahinsaid

I think that to solve the problem we should consider that the building is an bool array that says false except for the floor that we need therefore we can just use any search algorithm on the array that will give us the location of the cell with the true in it

4. ### yshahinsaid

I think that to solve the problem we should consider that the building is an bool array that says false except for the floor that we need therefore we can just use any search algorithm on the array that will give us the location of the cell with the true in it
but then the problem becomes which search algorithm will give us the best result based on the fact that we only have 3 eggs

5. ### Ahmed Fathallasaid

It is indeed a searching problem. But I think the fact that it is a bool array not very relevant. I’d like to think of it as an int array ordered ascendingly…Hahaaaaa…..that’s a cool hint isn’t it..so can anyone come up with the answer!!

Min Number = Floor Number + 1 !!

..any floor and it might or might not break(uncertainty)+2?!

its an egg question 🙂

8. ### David Chingsaid

I think this problem is not solvable. Even if you went to the 100th floor and dropped all 3 eggs and they all broke, it doesn’t guarantee all eggs will break on the 100th floor. This is because an egg breaking doesn’t set the threshold since “at any floor, it might or might not break” and the 4th egg you dropped might not break.

9. ### yshahinsaid

Ahmed Fathalla
it doesn’t have to be an int array because if i understand what your thinking
you want an int array for counting the floors
and the index is our counter the bool is just to identify the break point

and David Ching i think that your talking about the philosophy of the problem.
Just assume that they all have the same threshold and what happens to one will happen to the other under equal conditions

I think the answer is 4 Throws

10. ### David Chingsaid

OK I was misreading the problem and believe I understand now. Well, the Computer Science way is to do a binary search, so log(2)100 = 7 eggs. But if we only have 3 eggs, we can’t do a straight binary search, since we might break 6 eggs before we found the threshold.

Since we only have 3 eggs, the safe way is to start on Floor 1, try it, if it doesn’t break, go to Floor 2, try it, repeating until the egg breaks, and that is the threshold floor. But if that is Floor 100, it would take 100 tries.

So what if we start with the binary search, until we break 2 eggs. Then since we have only one left, we need to switch to the safe way. The worst case is we break 2 eggs immediately, during the binary search. At this point, the binary search will have reduced the possibilities by 4, so there are 25 floors still to check. We switch to the safe way and try up to 24 floors.

So the worst case is 2+24 = 26 tries, guaranteeing we don’t break more than 3 eggs.

yes, thats the simple Data structre problem and solution. anyway 7asal 7’ee r 🙂 any cool hypothetical questions for tommorw 🙂

12. ### fathallasaid

Excellent contribution Mr.David, actually there is a better answer where we can get it in 12 throws 🙂 Can you think about it !!!
N.B. Thank you for being an active contributor on our blog 🙂

from ground-up, on every 10 floors boundries.

and we can only hope that the tower got an elevator 🙂

Thanks, Fathalla Basha!

14. ### David Chingsaid

Thank you Fathalla, these questions are a lot of fun. I was wondering if you are really interviewing and need the answers? 🙂

I can’t think of how to do it in 12 tries, will think some more. Or just tell us! 🙂

Cheers,
David

15. ### fathallasaid

Its nice to have received all these comments on this post. Now, it’s time to reveal the answer. 🙂
I think the best worst case is 12 throws . The key here is dividing by 3. So Imagine you threw the first egg off the 33rd floor and it broke. Divide by 3 and throw it off the 11th floor, it breaks. Now we know for certain that the threshold floor is between 1 and 11. Now, since you have only one egg, you go sequentially from the first floor to the 10th floor. In the worst case this would mean 10 more throws, add those to the original 2 throws where you broke the 2 eggs. This would give a sum of 12 in the worst case. I think this is the best worst case achievable under all scenarios.

16. ### David Chingsaid

Clever Fathalla! 🙂

But consider, what is the “worst case”? Both our solutions assumed it is when the eggs break right away, which forces us to the “safe way” earlier and thus use more throws on the safe way.

But what if the worst case is when the eggs don’t break? Here, the binary search eliminates the most floors per try and has an advantage over dividing by 3.

It seems if the first egg breaks, your answer will have less throws, but if not, then my answer will have less throws, since you have 67 more floors to test, and I have only 50. So if the threshold floor is evenly distributed (i.e. it can be any floor with equal probability), then you have a 33% chance of winning, and I have a 67% chance of winning.

And math was never my strength! 🙂

Cheers,
David

it can be done in 6

18. ### souravsaid

it can be done in 9 ways… think of this formulae {(n)*(n+1)}/2

I’ve found a few ways to solve it with 10 drops as an absolute worst case. The trick to trying to minimize your attempts is to narrow it down as best you can with the first 2 eggs, because you are forced to do a sequential search with the final egg.

20. ### Ricksaid

At EVERY floor before the threshold floor the egg WILL NOT break. So you can keep using it. You only need 1 egg.

@ Rick
I think that sol. is the answer ..

22. ### Vikramsaid

Rick, your answer would have been correct if the question was to find out the minimum number of eggs required.
The Question however, is to find out the minimum number of throws needed to find out the threshold floor. If the threshold floor is the 100th floor and we start from the first then we need 100 throws, which is not minimum.

23. ### tonysaid

mine 50 10 20 30 40 31 32 33 34 35 36 37 38 39 worst case 14
fathalla 33 66 44 55 45 46 47 48 49 50 51 52 53 54 worst case 14 (i think) because I dont think you would do floor 99 and I dont know what your approach would be for floors 67-100

``` var threshold; var floors = new Array(); var trys = new Array(); var stories = 100; for(i = 1;i <=stories; i++) floors.push(i); for(threshold = 1; threshold 1){ // two eggs left while(eggs > 2){ // three eggs left broken = false; // we don't want the outer loop to run immediately floor = Math.ceil( ( upper - lower ) / 2 ) + lower; //binary if(floor > threshold){ trys[threshold-1]++; if(quick){ // one egg left eggs=1; }else{ eggs--; broken = true; upper = floor; } }else if(floor = upper){ // last 9 numbers to check quick=true; eggs = 3; broken = false; }else{ if(floor > threshold){ trys[threshold-1]++; eggs--; }else if(floor < threshold){ trys[threshold-1]++; lower = floor; }else{ lower = floor - 1; eggs = 1; } } } broken=true; // start running outer loop } lower++; trys[threshold-1]++; } } document.write("floortrys"); for(i = 0; i < floors.length; i++) document.write("" + floors[i] + "" + trys[i] + "") document.write(""); ```

24. ### tonysaid

doh well the formatting disappeared, it is written in javascript and the document.write is missing the table formatting. and some variables disappeared

The correct (optimal) solution for this is 12 drops.

FOR EGG 1:
======================
1st drop : 36th floor
2nd drop : 64th floor
3rd drop : 85th floor
4th drop : 100th floor

If egg1 breaks at 36th floor: ( EGG 2 )
==========================================
5th drop : 0 + 8 = 8th floor (for egg3 worst case: + 7 drops = 12 drops)
6th drop : 8 + 7 = 15th floor (for egg3 worst case: + 6 drops = 12 drops)
7th drop : 15 + 6 = 21st floor (for egg3 worst case: + 5 drops = 12 drops)
8th drop : 21 + 5 = 26th floor (for egg3 worst case: + 4 drops = 12 drops)
9th drop : 26 + 4 = 30th floor (for egg3 worst case: + 3 drops = 12 drops)
10th drop : 30 + 3 = 33rd floor (for egg3 worst case: + 2 drops = 12 drops)
11th drop : 33 + 2 = 35th floor (for egg3 worst case: + 1 drops = 12 drops)

If egg1 breaks at 64th floor: ( EGG 2 )
==========================================
5th drop : 0 + 43 = 43th floor (for egg3 worst case: + 6 drops = 11 drops)
6th drop : 43 + 6 = 49th floor (for egg3 worst case: + 5 drops = 11 drops)
7th drop : 49 + 5 = 54th floor (for egg3 worst case: + 4 drops = 11 drops)
8th drop : 54 + 4 = 58th floor (for egg3 worst case: + 3 drops = 11 drops)
9th drop : 58 + 3 = 61st floor (for egg3 worst case: + 2 drops = 11 drops)
10th drop : 61 + 2 = 63rd floor (for egg3 worst case: + 1 drops = 11 drops)

If egg1 breaks at 85th floor: ( EGG 2 )
==========================================
5th drop : 0 + 70 = 70th floor (for egg3 worst case: + 5 drops = 10 drops)
6th drop : 70 + 5 = 75th floor (for egg3 worst case: + 4 drops = 10 drops)
7th drop : 75 + 4 = 79th floor (for egg3 worst case: + 3 drops = 10 drops)
8th drop : 79 + 3 = 82th floor (for egg3 worst case: + 2 drops = 10 drops)
9th drop : 82 + 2 = 84th floor (for egg3 worst case: + 1 drops = 10 drops)

If egg1 breaks at 100th floor: ( EGG 2 )
==========================================
5th drop : 0 + 90 = 90th floor (for egg3 worst case: + 4 drops = 9 drops)
6th drop : 90 + 4 = 94th floor (for egg3 worst case: + 3 drops = 9 drops)
7th drop : 94 + 3 = 97th floor (for egg3 worst case: + 2 drops = 9 drops)
8th drop : 97 + 2 = 99th floor (for egg3 worst case: + 1 drops = 9 drops)

Hence, in the worst case, you need 12 drops..

26. ### miteshsaid

We need to do the following:
I. propose algorithm;
II. make upper bound estimation of number of steps.
We do not intent to proof that the algorithm is optimal in any sense, just providing some bound.
I. Algorithm
Let us fist consider at first three more simple algorithms, and the will get to our more complex and
efficient one.
1. Trivial algorithm is then we throw egg starting from floor 1 and up. Clearly we can get K steps in
worst case and don’t leverage the second egg;
2. The most obvious way of adding second egg is to throw the first egg on each even floor starting
from the ground and up, and when it will be broken check previous (odd) floor with second one.
This will take K/2 + 1 steps in worst case;
3. The next algorithm is based on observation, that we actually can break K into bigger chunks
using the first egg to significantly lower the worst case scenario. Let’s make number of chunks
equal to chunk size, so that we have 𝐾 chunks with size 𝐾. Then the worst case is then we go
through upper bounds of all (except the last one) chunks with first egg and then in last chunk we
go linearly from ground up with second egg. So we have in total 𝐾 − 1 + 𝐾 − 1 = 2 𝐾 − 2
steps which is already good but still is worse than we want to get with K big enough.
Our proposed algorithm is based on 3rd one and observation that we want to make chunks less and less
each time so that the more steps we do to find right chunks, the less time we need to go through it
linearly with the second egg. Obviously, since each next chunk top requires one first egg throw we need
each next chunk size to be smaller by one to keep worst-case scenario number of steps the same for
each chunk. And we need to ensure that 𝑐ℎ�𝑛𝑘 ��𝑧𝑒 ≥ 𝐾
��𝑒𝑡�
,Clearly since we decrease chunk size .
the last size can be just 1.So, we get the following algorithm: if x is number of worst-case steps, we throw the first egg from floor x
on step one, then from floor x+(x-1) on second step, then from floor x+(x-1) + (x-2) on third, etc.,
decreasing chunk size by 1 on each step until the last chunk will be of size 1. If the first egg is broken on
some step t0 have 2
roots. Here 𝐷 = 1 + 8𝐾 which means that one of the roots is always negative in our case, as soon as we
need only positive one we have 𝑥 =
−1+ 1+8𝐾
2
= 2𝐾 +
1
4

1
2
.Q.E.D .
End of the proof.
Example: For K=100 we have 𝑥 = 13.65 = 14 so we throw egg from floor 14 first, than from floor
27 = 14 + 13, than from floor 39 = 14 + 13 + 12, than from floors 50, 60, 69, 77, 84, 90, 95, 99, 100,
which are the tops of chunks. You can easily check that this will not work for K=100 and x=13 (you will
have too much floors left for the last chunk).

27. ### Alex Minsaid

it can be done in 10 drops.

drop your first egg on the 50th floor. If it breaks, then you look from the 1st floor to the 50th floor. Otherwise you look from the 51st floor to the 100th floor.

let’s say the egg broke on the 50th floor.

now drop the second egg from the 10th floor, if it breaks, then try from 1st floor until the third egg breaks. = 10 tries if the egg breaks on the 9th floor.

if the second egg didnt break from the 9th floor, drop the second egg from the 19th floor…then the 27th floor.. then 34th floor…then 40…then 45…then 49.

10 drops!

• ### Alex Minsaid

it can be done in 10 drops.

drop your first egg on the 50th floor. If it breaks, then you look from the 1st floor to the 50th floor. Otherwise you look from the 51st floor to the 100th floor.

let’s say the egg broke on the 50th floor.

now drop the second egg from the 10th floor, if it breaks, then try from 1st floor until the third egg breaks. = 10 tries if the egg breaks on the 9th floor.

if the second egg didnt break from the 10th floor, drop the second egg from the 19th floor…then the 27th floor.. then 34th floor…then 40…then 45…then 49.

10 drops!