Tags: , | Posted by Admin on 12/5/2006 2:06 AM | Comments (58)
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

How to get hired at Google

Preparing For a Software Engineering Interview

Google's recruitment procedure

Comments (58) -

Lombard on 11/29/2006 2:42 PM 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.
Kevin on 11/29/2006 5:00 PM 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.
Kendrick on 11/29/2006 7:18 PM 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.
James on 11/29/2006 9:36 PM 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.
Drew on 11/29/2006 11:54 PM 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.
Doyle on 11/30/2006 2:12 AM Some tough questions like this have been provide elegant solutions at
placementsindia.blogspot.com/search/label/Google
Adley on 11/30/2006 4:30 AM publishing the comment 4th time to fix typo errors Smile

#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.
Carver on 11/30/2006 6:48 AM It is a NP hard problem. NP standing for non polynomial
Bond on 11/30/2006 9:06 AM 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
Bartholomew on 11/30/2006 11:24 AM 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.
Marcus on 11/30/2006 1:42 PM 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.
Jonathan on 11/30/2006 4:00 PM 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?
Edan on 11/30/2006 6:18 PM 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
Earl on 11/30/2006 8:36 PM 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.
Durwin on 11/30/2006 10:54 PM 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.
Driscoll on 12/1/2006 1:12 AM 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.
Conan on 12/1/2006 3:30 AM I've never found more weird and absurd comments for any blog post/Puzzle, ever, that I find in this post Tong
Claude on 12/1/2006 5:48 AM 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.
Austin on 12/1/2006 8:06 AM 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..........
Stallone on 12/1/2006 10:24 AM 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!!
Marcus on 12/1/2006 12:42 PM Actually just realized that we only get two chances to break the egg, so disregard my post above. My mistake!
Malcolm on 12/1/2006 3:00 PM 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
Lombard on 12/1/2006 5:18 PM @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.
Lionel on 12/1/2006 7:36 PM 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?
Lincoln on 12/1/2006 9:54 PM 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
Lambert on 12/2/2006 12:12 AM Hi,

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

Thanks for posting.
Kenway on 12/2/2006 2:30 AM 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"
Kelvin on 12/2/2006 4:48 AM 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.
Kendrick on 12/2/2006 7:06 AM 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."
Jonathan on 12/2/2006 9:24 AM 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.
Foster on 12/2/2006 11:42 AM 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.
Ellery on 12/2/2006 2:00 PM 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.
Egil on 12/2/2006 4:18 PM 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.
Edan on 12/2/2006 6:36 PM 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.
Earl on 12/2/2006 8:54 PM 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?
Driscoll on 12/2/2006 11:12 PM Since we're going to ban this question anyhow, now solve for N eggs, N floors and tell the Big-O time for each.
Dillon on 12/3/2006 1:30 AM 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.
David on 12/3/2006 3:48 AM 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.
Damon on 12/3/2006 6:06 AM 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
Adley on 12/3/2006 8:24 AM 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.
Cyril on 12/3/2006 10:42 AM 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.
Cuthbert on 12/3/2006 1:00 PM 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.
Conan on 12/3/2006 3:18 PM 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 Smile
Claude on 12/3/2006 5:36 PM 2! you're only given two eggs
Chandler on 12/3/2006 7:54 PM 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.
Carver on 12/3/2006 10:12 PM 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.
Calvert on 12/4/2006 12:30 AM 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.
Benjamin on 12/4/2006 2:48 AM "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.
Barrett on 12/4/2006 5:06 AM 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."
Baldwin on 12/4/2006 7:24 AM You'll end up hiring people who don't care about the fact that they are working on trivial, contrived, and pointless problems.
Austin on 12/4/2006 9:42 AM 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.
aggie on 12/4/2006 12:00 PM 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.
Addison on 12/4/2006 2:18 PM "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.
Adam on 12/4/2006 4:36 PM 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.
Antony on 12/4/2006 6:54 PM I think i have made the changes required.In case of any ambiguity pls comment.And i am looking for more interesting solutions also.
Stallone on 12/4/2006 9:12 PM Same as Matthew, the "fragile or very hard" threw me off totally. You should re-word it.
Mike on 12/4/2006 11:30 PM I was not asked this at Google but I was asked this at Yahoo
John on 12/5/2006 1:48 AM 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?

Add comment




  Country flag
biuquote
  • Comment
  • Preview
Loading