Tuesday, December 5, 2006

Google Interview Puzzle : 2 Egg Problem


My intention here is not to trouble Google interviewers. I was just collecting some classic puzzles and found this one and a small Google search showed me that this is a Google interview puzzle to my pleasant surprise. But many of the answers I found were either wrong or totally twisted. I am making no surety of the answer I give and I am open to your remarks or suggestion or corrections.


The Standard Problem in simple writing goes like this:

* You are given 2 eggs.
* You have access to a 100-storey building.
* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process



If you are one of the people who likes to solve a puzzle before seeing the answer you must quit the blog now and come back later for checking the answer.


Now that this is a Google interview question I am taking the normal "Interview-Style" of solving a problem. Simply saying thinking aloud through the solution from worst to the best correcting the flows optimizing the solution or taking the 5-minute hard thinking acting pause to a problem, which you know already and just want to make your interviewer think that you are a challenge lover.


Solution

Drop the first egg from 50.If it breaks you can try the same approach for a 50-storey building (1 to 49) and try it from 25th floor. If it did not break try at 75th floor. And use linear search with the remaining portion of storey we need to test. For example if the first egg breaks at 50 we need to try all possibilities from 1 to 49.

Now this looks a feasible solution. In computer student's jargon do a binary search with first egg and linear search with the second one. Best case is log (100) and worst is 50.


Now the optimal solution for the problem is that you figure out that you will eventually end up with a linear search because you have no way of deciding the highest floor with only one egg (If you broke one egg and you have to find the answer among 10 all you can do is start from the lowest to the highest and the worst is the total number of floors). So the whole question grinds up to how to make use of the first egg to reduce the linear testing of the egg.


(For strict computer science students, well this problem can be solved using binary search on the number of drops needed to find the highest floor.)

Now let x be the answer we want, the number of drops required.

So if the first egg breaks maximum we can have x-1 drops and so we must always put the first egg from height x. So we have determined that for a given x we must drop the first ball from x height. And now if the first drop of the first egg doesn’t breaks we can have x-2 drops for the second egg if the first egg breaks in the second drop.

Taking an example, lets say 16 is my answer. That I need 16 drops to find out the answer. Lets see whether we can find out the height in 16 drops. First we drop from height 16,and if it breaks we try all floors from 1 to 15.If the egg don’t break then we have left 15 drops, so we will drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd floor we can try all the floors from 17 to 31 in 14 drops (total of 16 drops). Now if it did not break then we have left 13 drops. and we can figure out whether we can find out whether we can figure out the floor in 16 drops.

Lets take the case with 16 as the answer

1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45 .....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task


Now finding out the optimal one we can see that we could have done it in either 15 or 14 drops only but how can we find the optimal one. From the above table we can see that the optimal one will be needing 0 linear trials in the last step.

So we could write it as

(1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.

Let 1+p=q which is the answer we are looking for

q (q+1)/2 >=100

Solving for 100 you get q=14.
So the answer is: 14
Drop first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).

Please feel free to correct or post any comment on the solution or the answer.

Links I found useful

208 comments:

1 – 200 of 208   Newer›   Newest»
matthew said...

I find this sentence in the problem statement very confusing:
"Eggs can be very hard or very fragile."

It made me believe that different eggs have different degrees of hardness, and therefore will break at different heights. Which made the problem a lot harder than the solution indicated.

Maybe I'm overthinking it -- but what exactly is that sentence supposed to communicate?

Unknown said...

I was not asked this at Google but I was asked this at Yahoo

max said...

Same as Matthew, the "fragile or very hard" threw me off totally. You should re-word it.

SSP said...

I think i have made the changes required.In case of any ambiguity pls comment.And i am looking for more interesting solutions also.

zforest said...

It's another "we ll make you look like a fool by ask you interesting problems that you ll unlikely to encounter if you are hired" question!

By the way, if you interview for graphics/math/physics related technical position at least you are likely to be given questions pertinent to your expected duty.

Clayton Rabenda said...

"Maybe I'm overthinking it -- but what exactly is that sentence supposed to communicate?" It only meant that the eggs are likely to break at 100 or 1.

TomP said...

This is a very pertinent problem for a software engineer - you're being asked to devise a search algorithm. You need to identify the optimal strategy and characterize its worst-case behavior.

Unknown said...

The real solution:

1. Drop egg from second floor. Watch it break. Curse under your breath.

2. Go down to first floor, drop second egg. Soon realize that even a 1 story drop is too much for a freaking egg.

3. Degrade your interviewer and dare him to get an egg to not break more than 1 time in a row from any freaking window in that whole stupid building.

4. Get promoted.

Doug said...

You'll end up hiring people who don't care about the fact that they are working on trivial, contrived, and pointless problems.

Unknown said...

I've been asked questions like this before. There might be a mathmatical answer ( I don't know ), but questions like this are possed to gain insight into how a person thinks. It's a stress test. Does this person, just for the sake of it, come up with some absurdly complicated bullcrap answer? Does one realize that the answer is very simple (eg: the egg is most likely gonna break if you drop it from 1 foot). They could be testing you for creative thinking as well.

If i was being interviewed I would say, " I don't need any eggs. I don't need to waste the company's resourses and time to know that the answer is that the egg is gonna break if you drop it from any height."

Wise Bread said...

"You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking."

If that's the exact wording, then I can give you the answer right now:

ZERO

The question asks about "an egg." Not necessarily one of the eggs given to you, but just "an egg."

Well, common sense will tell you that an egg (either raw or boiled) will break upon impact pretty easily.

I would say zero and ask for my raise.

inerte said...

The first solution I thought:

Drop an egg from the second floor. Does it break? Drop the other from the 1st floor. If the second egg breaks, your answer is the 1st floor, otherwise it's the 2nd floor.

The first egg didn't break? Drop it from the fourth floor. Broken egg? Drop the other from the 3rd floor.

So... it's "floor that breaks egg" / 2, perhaps -1. That means if the 80th floor breaks eggs, I would discover it in the 40th drop, if it's the 79th floor, in 41 drops.

Unknown said...

What about the cost of going up and down the elevator? It would seem the higher floors would be more "expensive" to get to than the lower floors. I imagine the algorithm of starting at 50 and then binary "up" searching the upper floors would be more efficient in this case, since the floors are not random access.

Also, I like the comments about these being eggs. Of course they're going to break from the first or second floor. Unless this building is in a micro gravity environment or the ground is made out of some extreme material; questions like these are often designed to see how well one understands what the assumptions are.

TomP said...

Since no one else has commented on your solution, I also ended up with 14 drops as the best worst-case number of drops, following the same strategy you outlined. Realizing that you're going to have to do a linear search with the second egg is the key.

Unknown said...

2! you're only given two eggs

manapakkam said...

It is very clear

1) You are given 2 eggs.

2) Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.

--> Means out of two egg one will break even in first floor i.e.fragile or stronger i.e.may not even break if dropped from 100 th floor.

3) So drop any one from first floor if it breaks then second one won't break even 100 th floor.

so the Answer is 1 time broken and 100 th floor :-)

Unknown said...

There are plenty of other factors which need to be considered:
- The way it hits the floor.
- The floor surface.
- If there are any environmental factors while you are dropping it (wind, rain...)
- What is the definition of 'broken'. If the shell breaks doesnt mean you can't still eat the egg after having fallen 100 floors.
- ... etc

Anyways, there are so many angles which you need to consider before attempting to answer.

I don't think an interviewer will appreciate it if you say that the answer is just something like 'let me do a binary search because I am into computers' without considering other factors.

Christer Claesson said...

Nice solution. And by the way, there is nothing that says the egg in question is from a hen. Could be a alien egg or from freaky creature with very sturdy eggs. You just don't know exactly how sturdy and thus the test.

Brian said...

My solution was:

Use the first egg in 10 floor increments.
So, for Egg 1:
Drop at floor 10, 20, 30 etc... until it breaks.

If the first egg breaks at say floor 40, go back to 31 with the second egg and drop it at each floor until it breaks - then you have your critical floor.

Worst case scenario, it takes 9 drops for egg 1 (breaks at floor 90) and then another 9 drops for egg 2 (breaks at 89). So in the worst case it takes 18 drops.

Best case: Egg 1 breaks at floor 10 , Egg 2 breaks at floor 1. So best case is 2 drops.

Unknown said...

drop an egg from the first floor... if it breaks its fragile and thus the other egg is also fragile because they are identical. And both eggs cannot be dropped.

If it doesnt break they are both very hard and the highest floor they can be dropped from without breaking is the 100th floor.

the answer is the 100th floor... that is if u assume that a drop from 101 would break it.

the words "may" and "can" are both uncertain... an egg may be hard and if it is hard enough when dropped from the 100th floor it may not break. thats your answer

Peldin said...

Wow, I'm surprised. I initially solved this problem trying to minimize average case rather than worst case, and I still got a worse answer than you. I ended up with an answer of 10.8995 (which turns into 10.9 if you actually use an integer grouping), but the average case using your algorithm (of which mine was a variation) is actually 10.35.

Peldin said...

Incidentally, my attempted solution was to divide the 100 floors up into groups of X floors and then do a linear search on each group. In other words, basicaly the same as yours, but with each grouping the same size.

Chris DiBona said...

Since we're going to ban this question anyhow, now solve for N eggs, N floors and tell the Big-O time for each.

Unknown said...

I don't think you can solve this problem with only 2 eggs. If you start at floor 50, and the egg breaks, you then have to go to floor 25 and if it still breaks, you're out of luck.

Or you could start at floor 2 and see if it breaks. It will, so the answer is floor 1.

I thought of another way to potentially eliminate many of the floors. Objects that are falling have some terminal velocity. If the terminal velocity is such that the egg reaches it fairly quickly, it doesn't make any difference if you drop it from a higher floor than the floor required to reach that velocity.

You can calculate it by dropping the egg from the highest floor and counting how many seconds it takes to hit the ground. Then calculate the speed and determine how far it would have to fall to reach that speed. This isn't entirely accurate, because it will not reach terminal velocity at exactly the same time an object in a vacuum would, but it should be fairly close.

If this number indicates, for example, that the egg reaches terminal velocity when dropped from the 20th floor, then you know that if it doesn't break at the 20th floor it shouldn't break at the 100th, and so on.

But none of these cases let you determine the actual maximum floor with only 2 eggs, unless the maximum happens to be 1, 100 or 50.

Or am I missing something?

Unknown said...

DUH.

Of course. You just drop it from the first floor, and if it doesn't break, drop it from the second floor, and so on, until you reach the floor it breaks on.

This, of course, assumes that there is no build-up of damage that makes it break sooner after multiple drops.

Which isn't realistic either.

Alex Chapman said...

Thanks Polysage, I was going crazy reading all these complex solutions to a simple problem. The trick is to take what's given in the problem and not apply any common sense to it. In that case we realise we can solve the problem by breaking no more than one egg.

Unknown said...

inerte has posted the only correct answer. However, I like the terminal velocity comment... that shows creative thinking and would certainly get extra bonus points.

Shawn said...

Why couldn't you just start at the bottom floor and work your way up until the egg breaks? the floor under that one is the highest floor you could drop the egg from.

Anonymous said...

Question, if the eggs are identical in every way, does this mean that both eggs will break from the same floor? I am confused as to what you are even asking. There would need to be a pretext of an impossible ideal situation in order for the physics of your answer to make sense.

Joe said...

I know I'm late, but you should ask which planet the building is on, and if it's underwater.

"If you can't blind them with brilliance, bury them in bullshit."

R said...

This solution is guaranteed to complete in total_floors /5 +2.
so in this case it takes maximum 22 steps.


1.drop the egg from the 5th floor.
2.if it breaks drop egg from 2nd floor.
3. if it breaks then 1st floor is max.
4.if it doesnt break than drop it from 4th floor.
if it breaks than 3rd floor is max.
else 4th floor is max.

If it does not break, then go up 5 floors and drop it again,repeating steps one thru five as if the bottom floors didnt exist.

Unknown said...

You hire/find a temp and say, "Here are two nice, tasty eggs.

Take this one egg, and go drop it out of the window, then go outside and get it. Then go up to the second floor and try again. When you find the egg breaks call me and I'll let you keep the second one for lunch"

When they ask why, say

"It might seem a menial task now, but the experience will come in useful"

JP said...

Hi,

Well i am poor in solving puzzles and this puzzle did help me.

Thanks for posting.

Unknown said...

Was this a typo in the original post?

"If the egg don’t break then we have left 15 drops, so we will drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd floor we can try all the floors from 17 to 31 in 14 drops"

From the example underneath that, you show the second drop (after no breakage) as 31 which seems right. Also, isn't 17 to 31 = 15 drops? I think maybe it should read as follows:

If the egg don’t break then we have left 15 drops, so we will drop it from 16+15 =31st floor. The reason being if it breaks at 31st floor we can try all the floors from 17 to 30 in 14 drops

Chakravarthi said...

Hi,instead of applying binary search type technique on the number of floor, I frefer applying it on the velocity of the egg that hits the floor. If we asume the hieght of a floor is 10 meters, based on the formula v*v - u*u=2as the velocity of the egg when it hits the floor, is given in the below table when you drop from a floor.

FLOOR VELOCITY
1 14
2 19.79898987
3 24.24871131
4 28
5 31.30495168
6 34.2928564
7 37.04051835
8 39.59797975
9 42
10 44.27188724
11 46.43274706
12 48.49742261
13 50.47771786
14 52.38320341
15 54.22176685
16 56
17 57.72347876
18 59.39696962
19 61.02458521
20 62.60990337
21 64.15605973
22 65.66582064
23 67.14164133
24 68.5857128
25 70
26 71.38627319
27 72.74613392
28 74.08103671
29 75.3923073
30 76.68115805
31 77.94870108
32 79.19595949
33 80.42387705
34 81.63332653
35 82.82511696
36 84
37 85.15867542
38 86.30179604
39 87.42997198
40 88.54377448
41 89.64373932
42 90.73036978
43 91.80413934
44 92.86549413
45 93.91485505
46 94.95261976
47 95.97916441
48 96.99484522
49 98
50 98.99494937
51 99.979998
52 100.9554357
53 101.9215384
54 102.8785692
55 103.8267788
56 104.7664068
57 105.6976821
58 106.6208235
59 107.5360405
60 108.4435337
61 109.3434955
62 110.2361102
63 111.1215551
64 112
65 112.8716085
66 113.7365377
67 114.5949388
68 115.4469575
69 116.2927341
70 117.1324037
71 117.9660968
72 118.7939392
73 119.6160524
74 120.4325537
75 121.2435565
76 122.0491704
77 122.8495014
78 123.6446521
79 124.4347218
80 125.2198067
81 126
82 126.7753919
83 127.5460701
84 128.3121195
85 129.0736224
86 129.8306589
87 130.5833067
88 131.3316413
89 132.0757358
90 132.8156617
91 133.5514882
92 134.2832827
93 135.0111107
94 135.735036
95 136.4551208
96 137.1714256
97 137.8840092
98 138.5929291
99 139.2982412
100 140

First i choose the floor where if I drop the egg, the speed will be (140+14)/2 ie 77 ie.. 31st floor. The mid is calculated based on the velocity. It works recursively. Sounds good?

$uprema said...
This comment has been removed by the author.
$uprema said...

@chakravarthi

using velocity complicates the problem doesnt it?

I think it might be better to split the floors in groups and perform linear search. In this case. groups of 10 would do. In genereal, it would be groups of the nearest square root of the total floors.

Drop eggs grom 10,20,30 in progressive intervals of 10. when an egg breaks, we have identified the interval. Then it would be simple to identify the exact floor using linear search.

So worst case wud be 2(x-1) where x is the square root of floors in question.

jp4tne77 said...

This problem can be solved in 7 steps, maximum, contrary to the other solutions posted. The way to accomplish this is to zero in on the number by finding the amount of times 2 can be squared into before going over the number of floors (since there are 100 floors, the highest we can go is 64, or 2^6). For instance, let's the magic floor is the 27th floor, or the last floor before the egg will break, if it was dropped any higher.

1.Start by dropping from the 64th floor, the egg will break.

2.So divide by 2 and travel down to the 32nd floor, where the egg will still break.

3.Divide this by two, move 16 floors and go to the 16th floor, the egg will not break.

4.Divide by two,move 8 floors and go up to the 24th floor. The egg will not break.

5.Divide by two, move 4 floors and go up to the 28th floor. The egg breaks.

6. Divide by 2, move 2 floors down and go to the 26th floor. The egg does not break.

7. Divide by 2, move 1 floor up and go to the 27th floor. The egg does not break.

Thus, we know that the 27th floor is the last floor on which the egg will not break.

This works with any number between 1-100.

If there were more floors, just find the great square of 2 that goes into x number of floors, and keep dividing it by two to find your answer for the most efficient method to this problem.

Ex. 150 floors- start at floor 128, go up and down by 64, 32, 16, 8, 4, 2, and 1 to zero in on your answer.

Email me at jfortney@artsci.wustl.edu if you have any questions

jp4tne77 said...

Actually just realized that we only get two chances to break the egg, so disregard my post above. My mistake!

Suman said...

Thats a nice one. Thank you very much as it is very much useful to me.

--------------
My blogs:
http://onepuzzleaday.blogspot.com
http://justriddles.blogspot.com
http://justfungames.blogspot.com
---------------

Sashi said...

Throw the egg from 10th floor.

Breaks --> 1 to 9 linear

Doesnt Break --> From 20th.

Breaks --> 11 to 19 linear.

This way.. 10,20,30,..100 => 10 times
If it breaks anywhere u got 9 searches.

Resulting in a total of 19!!

Sashi said...
This comment has been removed by the author.
Rajesh said...

What do u mean ...
I opened link with lot of expectation to find an interesting question...confused to find a confusing problem description..
Really really sloppy attitude..
What is it..2 egg stuff?
Do you mean 2 types of egg.
You are a good mathematician or logical thinker..what is the use if you dn't communicate it clearly to other..U have wasted my time...Some one broad minded please explain me the problem once again before I read the solution and understand the problem..
Amature bloggers should learn how to make their stuff clear for readers..........

happydude said...

The instructions never say that the egg must be dropped out of the building. It asked you "to figure out the highest floor of a 100-storey building an egg can be dropped without breaking."

I am sure that I could drop and egg 1cm off the ground on the 100th story of the building and keep it from breaking. Therefore my answer would be the 100th story. This may not have been the spirit of the posting but...there's your answer.

Trilok said...

I've never found more weird and absurd comments for any blog post/Puzzle, ever, that I find in this post :P

Unknown said...

The confusion here is due to the fact that the puzzle itself was never properly articulated.

The key points:

1. You have 2 eggs to work with.
2. If you drop an egg and it does not break, it is assumed that the egg is not weakened and can be used again in another test.

The inefficient way of solving the problem is to start by dropping an egg at floor 1 and progressively going higher until the egg broke.

The efficient method, as others have pointed out, is to use the first egg to divide the dataset (number of floors) into half by dropping it from 50. If it doesn't break, you drop it from 75 and so on ... When it does break, you perform a linear search starting just above the lowest floor where it has been dropped but hasn't broken.

IGotYerBlog said...

Assuming we know nothing about the strength of these two identical eggs, the likelihood of any floor being the highest one at which the egg won't break is 1 in 100.

Previous approaches recognize that there are two phases, the optimistic phase, in which we use a binary search, and which continues until the first breakage, and the slow phase, in which we slog up one floor at a time starting from the last non-breaking floor tested, plus one.

If we start the binary search at floor 50, we have a 1 in 2 chance of being at or above the floor we want, which means we incur a penalty of up to 49 more tests (which on average will mean 24.5 tests if I'm not mistaken). Also a 1 in 2 chance of continuing the binary search at floor 75, with a 1 in 2 chance of needing up to 24 more tests (avg. 12), etc.

Floor 30, 3 in 10 chance of up to 29 more tests (avg. 14.5) if the egg doesn't break and 6 in 10 of continuing a binary search of the upper 70 floors, etc.

I'm sure probability theory gives us a way to express this algebraically and solve for the starting floor that yields, on average, the least number of tests, but I can't supply it.

IGotYerBlog said...

Two comments on my previous comment.

1. Previous approaches recognize that there are two phases, the optimistic phase, in which we use a binary search,...

Let me restate that. Previous approaches consist of an initial phase in which as many floors as possible are eliminated quickly,....

Binary search was not advocated previously, the closest was a kind of radix search. I apologize for my mischaracterization.

2. If the goal is to find the best worst-case, then the ten-floor radix search is about as good as it gets. I think you can do it in 17 drops if you use 9 instead of 10 as the chunk of floors to test with each drop of the first egg. The problem I'm addressing is best most-likely case.

Unknown said...

Number of drops = CEIL(Highest Floor / 2)+1

where CEIL(5.5) = 6
CEIL(10) = 10 etc.

If higest floor is 11th, then
x = CEIL(11/2) + 1 = 7

Therefore, number of drops = 7

Gregou said...

My creative answer to this question will be:
“I just need one egg, or maybe 0. I go on the Google, look for “math forum puzzle”, and chose the most geeky/active forum in the first page, then I check if somebody already ask the question. If I don’t find something that look like a correct answer, I post the question myself on the website, giving one egg as a reward for the best proposition, and come back the day after. Meanwhile I have time to propose you what we can do with the spare egg.”

Why losing time to answer a question somebody probably already wrote a blog about?

Deepak said...

My way of interpreting the problem ( for a computer science student )-
Number of attempts = Number of bits available.

Number of breakable eggs = Number of bits that can be set (among those available ofcourse).

Count of numbers availble meeting the above conditions = Maximum number of floors in the building.

Hence the solution to the above problem would boil down to number of bits needed to count 100 numbers provided only 2 bits are set, which equals 14.

Naagas said...

Some tough questions like this have been provide elegant solutions at
http://placementsindia.blogspot.com/search/label/Google

Narendran Kumaragurunathan said...

You should be dropping the first egg like this
2nd floor
4th floor
8th floor
16th floor
32nd floor
64th floor
82th floor
91th floor
95th floor
97th floor
99th floor

If in any of the above step, the first egg breaks, then use the second egg & drop it incrementally from the previous slab.
eg. if the egg breaks at drop from 32nd floor, then start the second egg from
17th floor,
18th floor... and so on until u find the solution.

Nitin said...

I was asked this problem in the interview at MobiSoc...and they asked to to generalise teh solution for 3 eggs, 4 eggs and so on

Bharath said...

It is a NP hard problem. NP standing for non polynomial.

nightwalker said...
This comment has been removed by the author.
nightwalker said...
This comment has been removed by the author.
nightwalker said...
This comment has been removed by the author.
nightwalker said...

publishing the comment 4th time to fix typo errors :)

#x= solution for x no of eggs

#1 #2 #3 #4 #5 #6
01 01 01 01 01 01
02 03 04 05 06 07
03 06 10 15 21 28
04 10 20 35 56 84
05 15 35 70 126 210
06 21 56 126
07 28 84
08 36 120
09 45
10 55
11 66
12 78
13 91
14 105
.
.
.
98
99
100

very easy to guess how this table is formed(just add element x-1 of current and x-1 of previous column to get x element of current column. In other words x of current column is sum of all the x elements of the previous column)

Now to find out how may attempts you will take for worst case for x no of eggs all you have to do is

1. go to the column for no of eggs you have. eg. if you have 3 eggs then go to #3 column

2. find then no greater than 100
eg. in #3 you have 120

3. Now from 120 try to reach 1st element in #1 column. Each movement horizontal or vertical is one step. Count the steps.

4. Then no of steps is your answer
so in our eg. it will be 9

so from this you can find out that in case of 100 floors
solution for worst case if you have
1 egg = 100
2 eggs = 14
3 eggs = 9
4 eggs = 8
5 eggs = 8
6 eggs = 9

So now you know that its of no use to have more than 4 eggs to optimize your worst solution as it can never go down below 8. Also following the strategy will be harmful if you have more than 5 eggs. In fact if you have more than 4 eggs then it better to go with this strategy for 4 eggs and us the remaining for binary search in last interval.

This solution can be expanded for any no of floors.

Now some simple exercises for the readers.
1. What will be exact steps that you will follow for a set no of eggs. eg. first drop it from x floor. check the result and then drop it from y floor. you can build a table for that also.

2. Find the prnciple behind this table. Hint: it is very simple and intuitive. Don't overstress your grey cells.

Ankush Bindlish said...

Another way of understanding the problem is through recursion.

When we have dropped one egg then we are atworst left with N-1 eggs, so We need to find the last solution till that drop.

TillNow(N) + (N-1) egg solution to this problem till this drop.

for #2, to get 6
(TillNow(N) =3) + Prev Sol with 1 egg = 3
3+3 =6

for #6, to get 28
(TillNow(6) =7) + Prev Sol with 5 eggs = 21
7+21 =28

Ravi Lodhiya said...

the correct answer is maximum 34 drops we need to figure out the highest floor of a building an egg can be dropped without breaking.


ok how ?

1st drop from 3rd floor
if break
2nd attempt from 1st Floor
if break then 0 is answer
else 2nd floor is answer. - Min 2 attempt

not break
2nd drop from 6th floor


not break
3rd drop from 9th floor

not break
4th drop from 12th floor

not break
5th drop from 15th floor

not break
6th drop from 18rd floor


not break
7th drop from 21th floor

not break
8th drop from 24st floor



.....

till
not break
32nd drop from 96th floor

not break
33th drop from 99th floor

not break
34th drop from 100th floor answer found.


min attempt required 2 and max attempt 34 to figure out exactly which floor where we can drop egg without break.

Ravi Lodhiya said...

in above correction

1st drop from 3rd floor
if break
2nd attempt from 1st Floor
if break then 0 is answer
else "2nd floor is answer." - Min 2 attempt


in above correction

1st Floor is answer..

Justino said...

You guys are all so silly. You have to guarantee that you know the lowest floor that these eggs break and during testing you only break 2 eggs. It's asking for the worst case on how many drops it would take to find such an answer. That means that you must start by dropping at floor 50. If it breaks then you only have one egg left to test with, so you'd better know the answer when that egg breaks. In order to know the answer in the case where the first egg broke at 50 you must start at 1 and increase by one until you find your answer. So the worst case is if the lowest floor at which the egg breaks is floor 49, in which case you've tested 50 using 50 drops (first floor 50, plus floors 1 through 49). 50 drops is the answer.

Unknown said...

The question is not clear. I took it as the EGG will never break either from 100th or 1000th floor. It should be clearly mentioned the egg is being thrown from 100th floor to the ground level. You can drop the EGG from 100th floor to floor of 100th floor.

There is no point in relating the EGG with height of floor. The question must be re-worded clearly.

Thanks,
Sam Bill

Xanadu said...

Nice blog dude. Check out an amazing series of puzzles here.

http://www.mindinsight.com/pages/game/boggle.html

I bet you cant cross level 10 without scratching your head.

Unknown said...

I guess more than half of the people in this world are moron and the greater part have proved this by their 'Great' comments in the blog... :)

Ganesh said...

I think this is the better solution. Lets take the worst case, 99th floor.

Drop the first egg starting from 10th floor, then drop it from multiples of 10th floor till it breaks.
So u will drop the first egg from 10,20,30...100 th floor. so in our case, in 10 drops u will break the first egg.

Then from the 91st floor(as the first egg didnt break from 90th floor) go till 99. so it takes only 19 drops to find even the worst case

Formula can be genralised to

Ceil(N/n) + ((N%n) -1)
where in my case N=100, n=10

matt said...

I think everyone is thinking too hard about this question. It says how high of a floor can the egg be dropped. it says nothing about where the egg lands. You go to the 100th floor with an egg and some sort of net to catch the egg without it breaking. Put the net right below your hand and drop the egg in the net. technically you dropped the egg off the 100th floor without it breaking.

Unknown said...

buy wow goldAsesor ProfessionalUruguayProfessionalbuy wow goldOfficeLinksNotice

Anonymous said...

Have you heared about 9Dragons which you need use Tales Of Pirates gold to play, and you can also borrow Tales Of Pirates money from other players? But you can buy Tales Of Pirates Gold, or you will lose the choice if you do not have cheap Tales Of Pirates gold. If you get it, you can continue this game.
Have you heared about 9Dragons which you need use priston tale Gold to play, and you can also borrow priston tale Money from other players? But you can buy priston tale Gold, or you will lose the choice if you do not have cheap priston tale Gold. If you get it, you can continue this game.

Anonymous said...

I always heard something from my neighbor that he sometimes goes to the internet bar to play the game which will use him some Perfect World Gold,he usually can win a lot of Buy Perfect World Gold,then he let his friends all have some Perfect World Silver,his friends thank him very much for introducing them the Perfect World money,they usually cheap Perfect World Gold together. And get more fun from the pw gold.
I am so happy to get some Pirates of the Burning Sea Gold and the potbs gold is given by my close friend who tells me that the potbs Doubloon is the basis to enter into the game. Therefore, I should potbs money with the spare money and I gain some buy potbs Doubloon from other players.

Anonymous said...

Do you know Asda Story gold? I like it.
My brother often go to the internet bar to buy Asda Story money and play it.
After school, He likes playing games using these buy Asda Story Gold with his friend.
I do not like to play it. Because I think that it not only costs much money but also spend much time. One day, he give me manycheap Asda Story gold and play the game with me.

Do you know Archlord gold? I like it.
My brother often go to the internet bar to buy Archlord money and play it.
After school, He likes playing games using these archlord online Gold with his friend.
I do not like to play it. Because I think that it not only costs much money but also spend much time. One day, he give me many cheap Archlord gold and play the game with me.
I came to the bar following him and found buy Archlord gold was so cheap. After that, I also go to play game with him.

Unknown said...

Nice one. My approach turned out to be the same, but couldn't arrive at the math formula. I believe the derivation is by induction.

Unknown said...

Nice one. My approach turned out to be the same, but couldn't arrive at the math formula. I believe the derivation is by induction.

Unknown said...

i see it's been a while, so you might not be checking anymore...

somebody recently asked me this question, which i enjoyed solving, but i had no idea it was supposed to be a compsci question... until i searched for other solutions on the web.

anyway, i agree that the solution for general n (floors) is to drop from \sqrt(2n) and then progress recursively (self-consistently), i.e. drop from \sqrt(2n) + \sqrt[2n - 2\sqrt(2n)] etc.

this gives the worst case scenario of \sqrt(2n) and the expectation value of (2/3)*\sqrt(2n) = 0.94\sqrt(n).

in comparison, the cruder strategy i first though of, to explore with the first egg in equal steps of \sqrt(n), gives a worst case scenario of 2\sqrt(n), but the expectation value of \sqrt(n), i.e. only marginally worse than the optimal solution.

i thought that the prefactor of 2/3 between the expectation value and worst case scenario was neat, and it led me to understand that the probability for the total number of drops must grow linearly, and only then why.
so it was very interesting to see that that was the end you actually started from!
(i set up the recursive equations for the worst case and for the expectation value, and solved the two cases separately - both are simple differential equations.)

but what still bugs me is this - i did not see before solving the two cases separately that the same strategy optimizes the worst case scenario and the expectation value.

do you maybe see a simple reason why that had to be the case?

DMTMACHINEELVES said...

http://www.moneytoyourdoor.net
mortgage
credit
mortgage interest rates
current mortgage interest rates
mortgage payments
monthly payment
mortgages
rates
interest
amortization
mortgage rates
refinance news and calculator
mortgage lender directory

http://www.top98freeonlinegames.info
top free online games
online games
free online games
games

M Vaqqas said...

I think the solution can be further optimized by droping the second egg on alternate floors. supppose if the first eg breaks at floor 50 (worst case). then drop the second egg from floor 2, 4, 6, 8...
Mohammad Vaqqas

M Vaqqas said...

oops i would like to correct my solution. if the first egg breaks at 50th floor then there is no need to start from 2nd floor. as you have alredy tried 39th floor, start from 41s and then move to 43, 45, 47, 79... and you will have solution in just 8 steps!!
-Mohammad Vaqqas

Manish Puri said...

I have a different solution to this problem.
Using divide and conquer, lets divide the 100 story building into 10 parts.
10,20,30 ........ 90, 100.

Drop the 1st egg from the top of 10th building and continue to next(+10) till it breaks and then continue with the ((current-10) + 1) th bulding.

Worst Case: when the answer is 99.

Drop the 1st egg from 10,then 20 ...till 100.
It breaks at 100.
Now continue from 100-10+1= 91.
try 91,92....99.
Since 99 is the answer,
total number of drops = 10+9 = 19.

So in any case, the max number of drops required is 19.

WHY divide 100 into 10 parts?????
I think u can easily figure it out.
Please tell me if the solution is fine.

immwhim said...

Canon Camcorder Battery|Hitachi Camcorder Battery|JVC Camcorder Battery|Panasonic Camcorder Battery|Samsung Camcorder Battery|Sharp Camcorder Battery

Unknown said...

Interview Questions Logic and Puzzles

Coolll

Stuffs get out of my head said...

none .

Anonymous said...

All of these people got job at Google! You'll all hired!

Unknown said...

Can we assume the two eggs have the same hardness? My original assumption was that they were different but from your solution you appear to assume they are the same.

milla said...

this type of information is what I like to me that explain how things went as on-site buy viagra

Ed said...

Too many "non-engineering" types posting.

How about we change "eggs" to light bulbs. A manufacturer wants you to test their advertised "unbreakable" light bulbs. They will only give you two of the bulbs for testing.

What is the minimum number of "drops" you must make in order to determine the floor at which a light bulb breaks.

BTW, the correct answer is indeed 14.

icemi said...

ffaspire 5500 btp-arj1 batbl50l6 travelmate 4200 d630 d820 inspiron 1520 inspiron 1525 Inspiron-630m Inspiron-6400 Inspiron-9300 Inspiron-B130 Inspiron-mini-9 m1210 xps M1330 dv1000 dv2000 dv8000 dv9000 nc8230 r3000 8375 bp-8089 pa3395u-1brs pa3465u-1brs

icemi said...

Inspiron 1100 Inspiron 1150 p90x Inspiron 1210 Inspiron 1300 Inspiron 1318 Inspiron 1420 inspiron 1425 Inspiron 1501 Inspiron 1520 Inspiron 1521 Inspiron 1525 Inspiron 1526 Inspiron 1720 Inspiron 1721 INSPIRON 2600 INSPIRON 2650 Inspiron 4000 Inspiron 4100 Inspiron 4150 Inspiron 500m Inspiron 5100 Inspiron 510m Inspiron 5150 Inspiron 5160 Inspiron 6000 Inspiron 600m Inspiron 630m

icemi said...

Inspiron XPS Gen 2 . Laptop Batteries , Batteries , hip hop abs ,hip hop abs , hip hop abs coupon , hip hop abs dvd , miami vice dvd Insanity , insanity popular ,Insanity , Insanity Workout , The Beatles ,The Beatles DVD ,The Beatles , miami vice The Beatles DVDs ,The Beatles Stereo CD DVD Box set ,The Beatles Mono CD Box Set ,The Beatles Postcard Box Set ,Rosetta Stone , p90x , rosetta stone spanish , Rosetta Stone OEM . Buy OEM Rosetta Stone , Learn Spanish , Learn Russian . Learn-Japanese , Learn German

Ravinder Singh said...

well i dint go through all the comments but i hav a solution fr which the best case,worst case as well as average case is better thn urs!

xy=100
min(x+y)

so go to 10,20,30...100 for first egg thn linear search with 2nd egg.

best case: 10
worst case: 19
average case(say egg breaks at 49th floor): 14

Ravinder
EE(final year)
National institute of tech karnataka india.

KUNAL said...

Eggs can be very hard or very fragile..
and eggs are identical...
means only 1 drop is required to find our whether they are very hard or very fragile...

laptop battery said...

I must say this is a great article i enjoyed reading it keep the good work.
Dell Inspiron 1150 battery
Dell Inspiron 1200 battery
Dell Inspiron 1300 battery
Dell Inspiron 1501 battery
Dell Inspiron 1520 battery
Dell Inspiron 1521 battery
Dell Inspiron 1525 battery
Dell Inspiron 1526 battery
Dell Inspiron 1720 battery
Dell Inspiron 1721 battery
Dell Inspiron 2100 battery
Dell Inspiron 2200 battery
Dell Inspiron 2500 battery
Dell Inspiron 2600 battery
Dell Inspiron 2650 battery

Maria said...

Assuming we know nothing about the strength of these two identical eggs, the likelihood of any floor being the highest one at which the egg won't break is 1 in 100.
britney spears perfume
ed hardy perfume
vera wang perfume
calvin klein perfume
paris hilton perfume

Anonymous said...

Hi

I read this post two times.

I like it so much, please try to keep posting.

Let me introduce other material that may be good for our community.

Source: Building interview questions

Best regards
Henry

Unknown said...

At first, to avoid prevent stains, you, wholesale purses, should immediately, leather key holder, treat your Louis Vuitton, kelly 32, handbag with a leather protector. The Fashion Bags will look, cheap monogram, gracefully after the leather in your new bag is not treated. This aging process is typical which, louis vuitton damier canvas, makes your Louis Vuitton distinctly yours!The second, take your handbag away from makeup, food, and especially anything that is oil based.

Admin said...

visit code-forum.blogspot
for this puzzle solution

Unknown said...

Just drop an egg from the 100th floor with a parachute and thats your answer, floor 100!

Unknown said...

Sorry I mean the answer is one drop if you follow directions above.

Anonymous said...

With great pleasure I read your blog. The information is very interesting. My gratitude to you. Buy metformin online
Metformin 850 mg
Metformin 500 mg

Anonymous said...

Outstanding!This article is creative,tRight here are a Great deal of new idea,it gives me inspiration.I think I will also inspired by you and think about more new ideas.Online Medical Transcription

Anonymous said...

teşekkürler


puzzle satış

DomoMaster said...

It took me some time to find the answer.

Caro
sudoku

marven said...

I got many more information about Google puzzle, Its very best and interesting .business logo design

Unknown said...

I got the same initial response using the binary search/ linear search combo to get 50 drops. I thought it was interesting that my mathematician friend go the same initial max by dropping the first egg on every other floor. If it broke, he knew it was the previous floor. It saved an egg, so I have to give credit to it being slightly more efficient than mine. From either one, you can then see that you need to make more efficient bounds with the first egg and get the correct answer, which is indeed 14.

Anonymous said...

It is best to participate in a contest for among the best blogs on the web. I'll recommend this website!
Vimax Pills Enhance VigRX Plus metropathies Male Extra Amp Do VigRX Plus pills really work mastoidal

Madiha Shoukat said...

I certainly enjoyed the way you explore your experience and knowledge of the subject! Keep up on it. Thanks for sharing the info
African Mango

jelish said...

The design of Christian Louboutin Peep toe is very unique and sexy. We have to be amazed and excited for its shape. As long as you wear it, you must be more beautiful and attracting, you can try it!The elegant new style Christian Louboutin Peep toe can make you more confident and charming, expanse your taste. These sandals are not only gorgeous but are also comfortable. The elegant sandal of Christian Louboutin is a miracle!
http://www.louboutins-christian-louboutins.com

RichardCorbett said...
This comment has been removed by the author.
RichardCorbett said...
This comment has been removed by the author.
man said...

I think i have made the changes required.In case of any ambiguity pls comment.And i am looking for more interesting solutions also.
Dripping Springs Remodeling Contractor

tommygunn said...

Calculate the distance it takes for an egg to reach terminal velocity. Any egg dropped from this distance or higher will definitely break. Once you have determined this distance, drop the first egg from the floor lower than this distance. When you find that it breaks, go to the first level, drop the egg there and figure out that an egg is going to break at almost any height higher than 2-4 inches! 2 Drops, answer achieved through math!

Unknown said...

Wow! What can I say?Truely a nice article and thanks for your great work. By the way,welcome to our websites. You most definitely have made this article into something special. At the same time,Welcome to look at my website ghd uk and hope we can become good friends, and exchange and to help each other! Thanks.Best Ghd Hair Straightener
What's more, you can visit Ghd Australia to browse New Hair Straighteners
You may also like Ghd Australia, Ghd Hair Straightener and Ghd Australia.
http://www.ghd-chi-australia.com

Unknown said...

Hi guys, I want to say thanks for this useful information, I shared it on my wall to be honnest cause I LIKE it(:

Acheter cialis

Satya said...

I have one doubt in this answer.
1. There is only two eggs while when I am droping it from 50th floor suppose 1st egg is broken then I have only one so How we can test its hardness without knowing it that it will not break from its lower one and if it will break from 25th floor then there is nothing to test.

marven said...

This does work for a select few people, it does not work for everyone. Myself being one of them. It was worth a shot though! custom logo design

glass dining table said...

Thanks for such a great post! I struggle with this and usually just leave it empty because I don't know what to do. I know not to keep it set, but I do at Christmas and it makes me happy. :-) Love a runner and tray of goodies!glass dining table

Unknown said...

Nice post! Thanks for sharing!
Buy Viagra

Anonymous said...

Hi

I read this post 2 times. It is very useful.

Pls try to keep posting.

Let me show other source that may be good for community.

Source: Problem solving interview questions

Best regards
Jonathan.

sachin said...

End result you want is to find out how many drops need to check egg is hard or fragiles..

Assuming I have 2 egges..I will go to first floor and will drop one out of that..so I will come to know which out of that is hard or fragile egg, assuming its fragile..I will go ahead & take another egg..& will do same exercise..so thats my 2nd drop..the 2 eggs will remain..I will to 100 floor and will drop one egge out of that..so I will come to know weather it is hard or fragile..so in three drops only..I will come to know answ!!

Netent Casinos said...
This comment has been removed by the author.
Ana Boks said...

Some one research on eggs problem.How you say that egg is so tough and rough????

Facebook Developer
|
Seo Expert Services

adlai said...

wow. . .really nice puzzle. . .it really exercised my mind. .. wow. . .
phone spy software for the safety of my phone.Android phone locator for the tracking of my location.
android gps apps locator and tracking my route.

android tracker also a tracker for my gps.

how to track a cell phone
track cell phone
cell tracker
gps track cell phone
cell phone tracker software

Abhishek Singh Sambyal said...

Waste comments.
One person is saying binary search, some one is saying linear search and guess what one of the comment is NP problem.
Do that person knows what is NP problem?
NP problem is: on given correct input if our algorithm gives polynomial time complexity; it is known as NP problem.
I don't know how many of comments are posted by computer science students but almost every comment has no logic.

Fara Fae said...

Your blog is really excellent. It inspires the readers who has that great desire to lead a better and happier life. Thanks for sharing this information and hope to read more from you. Great information…

doctor ratings and reviews | find doctor list | doctor reviews by patients | doctor ratings and reviews by patients

anita grace said...

Awesome pictures and interesting information and attractive.This blog is really rocking...
Birthday parties for kids in Miami
Kids birthday parties in Miami

Farrah Khan said...

Interesante post. Me he estado preguntando acerca de este tema, así que gracias por publicar.

nutricionista Barcelona | dietista Barcelona | dietas Barcelona

Unknown said...

Nice information,Ankara escort
many thanks to the author.Ankara escort
It is incomprehensible to me nowAnkara escort
, but in general,Escort ankara bayan
the usefulness and significance is overwhelming.Ankara escort
Thanks again and good luck!
Ankara escort
became the first designer in Wimbledon's 133-year history to create official uniforms for the tournamentescort bayan ankara
As part of this year's event, which starts next week.
will introduces the first ...Escort ankara
determinationEscort ankara
to maintain and enhance the values for which our two brands are famous throughout the world.Escort ankara
The rugby ralph lauren brand brings to Wimbledon the look of timeless elegance,Escort ankara
drawing on our rich history and traditionsEscort ankara
expert and i like your blog and the information you have
mentioned in this post about the Google tools is really great!
escort bayan
escort
escort istanbul
Bayan Escort
escort bayan ankara
escort bayan ankara
escort bayan ankara kızılay
Escort ankara bayan
escort bayan ankara çankaya
Ankara escort bayan
Ankara escort bayan
Ankara Escort
Ankara Escort


Thanks for sharing. Very impressive

Unknown said...

google da ilk sayfa çalışmalarına verilen isime seo denir.

Unknown said...

From your post:
"so we will drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd floor we can try all the floors from 17 to 31 in 14 drops (total of 16 drops)."

I think 32 should be replace by 31. the next floor to try is 31st but no 32nd.

Silviu said...

Wow!That;s one lomng solution!I thought that is just a paragraph :)
Jacob Helmsy

bharat said...

I think this can be done in 16 steps ....

Drop from : 1,20,40,60,80,100 floors in worst case [let it breaks at 99] so total drops are : 6 + 10 = 16.

Or

Drop from : 1,25,50,75,100 floors in worst case [Let it breaks at 99] so total drops are :5 + 12 = 17

So i think first one is right ...in 15 steps ...

Mustang666 said...
This comment has been removed by the author.
Mustang666 said...

The maximum no. of attempts for the above problem is 6. The method is to drop the first egg at a floor with no. half of 100 i.e 50. If it breaks, throw another form 75th(as it is in the mid of 100), if it doesn't,throw it from the 25th floor. The algorithm for finding the maximum no. of attempts for an 'n' story building is-
"2^x < n",
whr x= the max power of 2 for which the value is less than n & x gives the value of the max. no of attempts.

P.S- if anyone has anything to ask,feel free to contact me. My id is usankrityayan@gmail.com.

avi said...

take the sum f natural nos 4m 1 to dat no. x(answer)..jus enough 2 b greatr dan da no. f stories f da building....ex 4 100 storey building...da sum wud b 4m 1 to 14....ie 1+2+3+4.....+14=105 hence 14 s answr....4 50 storey building ans wob b 10 as 1+2+3+4+5+6+7+8+9+10=55

anita grace said...

organic vitamins

Tubal Ligation Reversal is the best way to be pregnant after tubal ligation.

0Zero7 said...

I agree that handwriting can say a great deal about a person. I think that men whose handwriting in incomprehensible care only about themselves and do not value others’ opinions.
web hosting Pakistan

domina said...

I love to solve the puzzles and i could solve some of them very well..
Register website domain

domina said...

It was nice and i had good brain exercise..
Master in real estate

Elysian said...

This is one of the best post that I have ever read. You have provided a great piece of information. I will definitely share it with my other friends. Keep up the good work, I would to stay in contact with your posts.
Dubai property

Kyle Grando said...

This is a smart blog. i read all the post its so interesting and informative please keep it up and share more awesome posts. Thank you for the review.

St Louis Hotel Packages

marven said...

I never knew Heckler until i have read this post. I did enjoy reading it trying to understand.wireless internet .

escort ankara said...

Ankara Escort,
Escort Bayan Ankara,
Ankara Escort,
Escort Ankara,
Escort Ankara,
Ankara Escort,
Escort Bayan Ankara,
Ankara Escort,
Escort Bayan Ankara,
Escort Ankara,
Escort Bayan Ankara,
Escort Bayan Kayseri,
Escort Kayseri,
Kayseri Escort,
Escort Ankara,

Anonymous said...

. But many of the answers I found were either wrong or totally twisted. I am making generic levitra no surety of the answer I give and I am open to your remarks or suggestion or corrections.

Piyush Kapoor said...

This can be done by dynamic programming,(for a more general version of the problem, Let there be K eggs and N floors) ,
f(K,N)=1+[for all 1<=j<=N] min(max(f(K-1,j-1),f(K,N-j)))

speechless said...

For any given floors ,find the factor with minimal sum. [2 if two eggs]
if 100 : then 10 * 10 and sum = 20, tries = 19
if 150 : then 15 * 10 and sum = 25,tries = 24.

use one for the jump and the second factor-1 for the linear search.
-Srijit Nair

This will gives us the minimal tries in the worst case.

Unknown said...

if there are n floors in the building you can drop the egg from every sqrt(n)th floor and once it breaks, iterate through that segment with the other egg. This has a complexity of = 2 * sqrt(n)

Unknown said...

if there are n floors in the building you can drop the egg from every sqrt(n)th floor and once it breaks, iterate through that segment with the other egg. This has a complexity of = 2 * sqrt(n)

Unknown said...

i don't know what's all this fuss about. Let me just give a very trivial algorithm for solving it:


for(int i=2;i<=100;i+=2)
{
bool egg_broken = drop_the_egg(i);
if(egg_broken){
bool second_egg_broken=drop_second_egg(i-1);
second_egg_broken ? printf("%d\n",i-1); : printf("%d\n",i);
}

}

well that's all about it and as WE CAN BREAK ONLY TWO EGGS this is the only solution i think possible of the few answers i have come across this blog.

cool said...

dont mess with eggs let allow the chickens to come out then they breed to produce more eggs then using 2 eggs easliy apply binary search
Be patient!!!!

Anonymous said...

This is a nice post, but I think there is an even better explanation of the puzzle here:

2 Eggs 100 Floors Puzzle

Gordon Stubbs Locksmith said...

I like this post it is full of information to know i really love this .I will share this to my friends .Thanks for this.

Unknown said...

here is a quick program to iteratively calculate the expected number of drops before finding the answer for a building of n stories. finding the optimal behavior is a trivial extension.

num_stories = 1000
T = [0]
E_T = lambda n, m, T: (m/n)*((m+1)/2-1/m) + (1-m/n)*T[n-m] + 1
for n in range(1,num_stories):
T.append(min([E_T(n,m,T) for m in range(1,n+1)]))

Unknown said...

I think I'll try some of these on my family! Great collection! Logical Puzzle Asked In Interview

Dexter said...

This problem is great! And, by the way, I agree with your solution - I think it is optimal, e.g. no solution can have a better worst case than 14...

Unknown said...

if 13 times, then it will be less than 100, if 14 times it will be more than 100.
So 14 times(exactly for 104 floors) still waste drops.

I always thinks that 14 is a little more, but we have no other choices, right?

driqbal said...

its really very shameful for all my mathematician frinds and computer programmers......they never think about real solution.

My answer is only 10 drops even in worst case........this was very simple puzzle and has very simple solution.

yes my friends answer is only 10 drops...please retry...if u still cant solve email me ......

driqbalahamed@gmail.com

Akash said...
This comment has been removed by the author.
Akash said...
This comment has been removed by the author.
Akash said...
This comment has been removed by the author.
Akash said...
This comment has been removed by the author.
Akash said...
This comment has been removed by the author.
Akash said...

Here is a generalized solution for any number of eggs:

TWO EGGS PROBLEM

Unknown said...
This comment has been removed by the author.
tarun said...

Detailed generic solution: http://www.writeulearn.com/3-egg-problem/

PRAVEEN said...

Good problem.
For the time being, lets forget the number of eggs, so what should be our approach?

This should be "Binary Search".

Drop the egg from 1st, 2nd, 4th, 8th, 16th, 32nd, 64th till the egg does NOT break.

In worst case, it does NOT break even from 64th floor (i.e. we have already made 7 drops).
So, Now try out the same methodology for 100-64 = 26 floors i.e. drop the egg from 65th (1), 66th(2), 68th(4), 72nd(8), 80th(16), 96th(32).
Now, again in worst case, the egg does not break even from 96th floor. (i.e. total drops now became 7+6=13).

now, continue the same process....

Unknown said...

Guru Maa is one of the most famous and best astrologer in delhi with over 40years of experience. She is a vashikaran and balckmagic specialist. You can get your love back easily by blackmagic, vashikaran or pooja with her God gift expertise in this filed of religion and sprituality.

Get My Love Back By Pooja


Black Magic

Unknown said...

This is a good puzzle for interviewing software developers or other people who need to work with algorithms.

The largest possible number of floors you can "cover" with n coconuts and m floor-visits is represented by calling a recursive function on n and m.

In MATLAB code it looks like:

function floors_covered = floors(m,n)

if m == 0,
floors_covered = 0;
else
if n == 0,
floors_covered = 0;
else
init_value = m;
for i = 1:(m-1),
init_value = init_value + floors(i,n-1);
end
floors_covered = init_value;
end
end

This yields 105 floors for 14 visits and 2 eggs.

The 2 egg case is actually very simple, with the closed-form solution trianglesum(14), where trianglesum(n) is 1 + 2 + ... + (n-1) + n. So 1 + 2 + ... + 14 = 105.

But the interviewer probably wants to hear you reason backwards in the 2 eggs case, and (if it's a tough interviewer) will probably ask you the 3 egg case after you crack the 2 egg case (pun intended), and then finally give you the n egg case.

So it is best not to immediately deliver the general algorithm in an interview. Better still, if you've heard it before you should own up and say you've heard it before - that scores you major integrity points.

Unknown said...

Drop the egg from 100th floor to 99th.. like that 100th to 98... with one egg u will find out the breaking point.
100 - floor at which it broke.

:) rags.mpl@gmail.com

Unknown said...

4 drops. 2 from floor 100 and hope 1 egg in 2 is hard enough to survive. 2 from 99 floor. hope some more.

Himanshu said...

Instead of going into programming... If u think practically, egg breaks if u drop it from your hand (approximate height 4-5 ft)
Assuming height of a floor 10ft then there should be no integer solution of this question.
Second thing is that, between 0 to 5 feet, there are infinite num of points. You have only 2 eggs with you whereas you need infinite numbers of eggs.
Best thing you can do is boil them and have a nice breakfast. :)

Unknown said...

why cant we drop egg from 100th floor to 99th floor and then if it doesnt break, then drop it from 100th to 98th and so on...
so example if it breaks in 97th floor, then 100-97 is 3 floors. Simple:)

charlie said...

All I need is 13

Unknown said...

Hi...
I like this post...
If you know about natural treatment for Penis Enlargement.
visit here :-http://www.aboutherbal.com/male-health/penis-enlargement-cream/

Unknown said...

The exercise of fingernail design has been around for the last 5000 years and can be tracked to the people of Indian who ornamented their claws with henna. Now go toward 1932, when the France organization Revlon launched its first fingernail enhance. It was available in an extensive range of colors and used pigmentation instead of colors. Since the Thirties, fingernail art has come a long way.

Magic Hair Building Fiber in Pakistan

Unknown said...

The exercise of fingernail design has been around for the last 5000 years and can be tracked to the people of Indian who ornamented their claws with henna. Now go toward 1932, when the France organization Revlon launched its first fingernail enhance. It was available in an extensive range of colors and used pigmentation instead of colors. Since the Thirties, fingernail art has come a long way.

Magic Hair Building Fiber in Pakistan

Kabir said...


Great thoughts you got there, believe I may possibly try just some of it throughout my daily life.

Friends Phone  Cover

Unknown said...
This comment has been removed by the author.
Unknown said...

Thanks for informing us in which there is authentic description for users. I hope you will share some more info regarding this.

Money For Junk Cars | Junk cars | Junk Yard

Unknown said...

The best way to recover data from broken, dead or water damaged iPhone is restoring backup file. Users can take the help of iTunes utility in order to backup or restore iPhone data with ease. In case if you are facing any kind of issue with iTunes then in such situation you will have to opt for third party iPhone Recover Software in order to recover all lost iPhone files.

Unknown said...

This is really a nice blog in which you discuss some useful things, thanks for sharing this and keep going on.

Building Solutions | Building Construction

Unknown said...

This is very informative post. Thanks For sharing more information.
House Relocation Perth

Unknown said...

This is very nice post. Thanks for sharing more information.
Professional Removalists Melbourne

Anonymous said...

Smartphone cases or Mobile Covers come in many different forms such as plastic, leather or metal. You can purchase the best size cover because a wide range of numerous sizes and shapes covers are available in the market. They will be a perfect fit for your smartphone which will make your smartphone easy to carry and better in grip. Most importantly, smartphone cases or mobile covers are the most affordable way to give your smartphone a perfect protection which will allow you to avoid any kind of unnecessary fund expenditure or investment in repairing or replacing conditions due to bad handling. It will clearly save you a lot of money and it will increase the lifespan of your smartphone as well!

Brooke said...

Thanks for the puzzle. I've done the 2 egg problem before but just showed my son. Also here's a classic riddle that I wanted to share with everyone. Let me know if you can figure it out: What Has One Eye But Cannot See

expertshelp said...

I wasn't aware that this kind of a post would be possible to find, on until i came across this post. It would wow you how easy it is to read and how hard it is to forget relevant information. That's the beauty of it. While at that, you can always find the best information on Web Pages Organizing Help by checking the link. The best is guaranteed.

Pradeep Lamba said...
This comment has been removed by the author.
Dave said...

The most poorly posed question ever

"You are given two eggs", therefore the most attempts you can have is 2!? In any case the best way you can find out is to weigh the eggs, then push an egg against the ground until it cracks (whilst measuring the force needed to crack them). Then using the acceleration due to gravity calculate the speed at each floor and relate that to the impact force on the egg, then find the height needed to crack the egg, find the floor above this height.

So you need 1 egg.

Unknown said...

This is a nice article here with some useful tips for those who are not used-to comment that frequently. Thanks for this helpful information I agree with all points you have given to us. I will follow all of them.


Digital Marketing Company in India
Web Development Company in India
Web Design Company in Chennai
Android app development company in Chennai
Mobile App Development Companies in Chennai
Ios app development company in chennai

Pradeep Lamba said...
This comment has been removed by the author.
Pradeep Lamba said...

Thanks for great information you write it very clean. I am very lucky to get this tips from you...

Industrial Flooring in India
concrete flooring in india
Laser Screed Flooring in India
concrete polishing in india
Superflat Floors

Naveen Chauhan said...

Bed manufacturers in Delhi- RC Furniture is one of the leading bed manufacturers in rohini, bed suppliers in rohini and bed dealers in rohini, delhi. VIEW MORE- Bed manufacturers in Delhi

Admin said...

top bangat

Admin said...

sip...

isabellajones said...

Nice Blog

Unknown said...

I in addition to my friends came reading the nice information and facts located on your site and then immediately developed a horrible feeling I never thanked the blog owner for those tips. All the ladies were definitely certainly happy to read through them and now have definitely been making the most of those things. Appreciate your getting very accommodating and also for deciding upon some exceptional ideas most people are really eager to learn about. My very own honest apologies for not saying thanks to earlier.height shoes for men

Unknown said...


Cheating is something that is very, very hard to deal with in a relationship, but if you're looking for ways to win your partner's heart back after separation Pls contact dr_mack@yahoo.com, he restored my relationship and mine is perfect now

Unknown said...

Anyone looking for Research papers help check out our Sample Essays and the assignments we have done before

alex lee said...

We create best products.Each garment is designed to be long-lasting, durable and competitively priced for wholesale and retail environments. Our best products includes classic poloshirts

Well Saxon said...

Thanks for posting this blog, I am very impressed with your blog and it is very useful for me and other. Please visit at buy wow classic gold U4GM has a large stock of WOW Classic gold for each Server so that we can make delivery within 10Mins. Here you can enjoy the best 7x24 friendly service and low price, help you enjoy World of Warcraft Classic - https://www.u4gm.com/wow-classic-gold

Well Saxon said...

Thanks for posting this blog, I am very impressed with your blog and it is very useful for me and other. Please visit at buy wow classic gold U4GM has a large stock of WOW Classic gold for each Server so that we can make delivery within 10Mins. Here you can enjoy the best 7x24 friendly service and low price, help you enjoy World of Warcraft Classic - https://www.u4gm.com/

«Oldest ‹Older   1 – 200 of 208   Newer› Newest»