* 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.

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

Preparing For a Software Engineering Interview

Google's recruitment procedure

### Comments (58) -

Add comment

biuquote

- Comment
- Preview

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.

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.

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.

placementsindia.blogspot.com/search/label/Google

#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.

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.

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.

“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?

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

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.

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.

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.

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.

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..........

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!!

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

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.

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?

"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

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

Thanks for posting.

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"

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.

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

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.

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?

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

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.

- 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.

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

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.

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.

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.

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."

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.

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.

"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?