Home » Interview Puzzle »
Google Interview Puzzle : 2 Egg Problem...
Tuesday, March 16, 2010
This Puzzle is asked by Google while they had an interview to a select student
for their company. Then many companies asked this Puzzle during their
interview or written test in campus. This puzzle is famously known as 2 Egg
Problem. The puzzle is given below.
for their company. Then many companies asked this Puzzle during their
interview or written test in campus. This puzzle is famously known as 2 Egg
Problem. The puzzle is given below.
Puzzle : Two Egg Problem:
* You are given 2 eggs.
* You have access to a 100storey 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 100storey 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 "InterviewStyle" 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 5minute 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.
Answer :
Let x be the answer we want, the number of drops required.
So if the first egg breaks maximum we can have x1 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 x2 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+(p1))+ (1+(p2)) + .........+ (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).
SE5NFN73424QSo if the first egg breaks maximum we can have x1 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 x2 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+(p1))+ (1+(p2)) + .........+ (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).
Posted in
Google Puzzle
,
Interview Puzzle
Related posts:
If you enjoyed this article, subscribe to receive more great content just like it.
Search
Sponsors
Popular Posts

Aeroplane. Puzzle : The puzzle question is : On Bagshot Island, there is an airport. The airport is the homebase of an unlimited n...

Infosys interview puzzles with Answers Puzzle 1 : 9 cards are there. u have to arrange them in a 3*3 matrix. cards are of 4 colors.they ...

You have a set of 3 light switches outside a closed door. One of them controls the light inside the room. With the door closed fr...

Puzzle : 5 pirates of different ages have a treasure of 100 gold coins. On their ship, they decide to split the coins using ...

Puzzle : This problem is also called Jelly Beans problem. You have three jars that are all mislabeled. one contains apples, another ...

This Puzzle is asked by Google while they had an interview to a select student for their company. Then many companies asked this Puzzle ...

The Puzzles Puzzle 1. The man in the Elevator A man lives on the tenth floor of a building. Every day he takes the elevator to go down ...
Sponsors
Recent Stories
Connect with Facebook
Google Connect
Tag Cloud
 Adobe Interview puzzles (2)
 Amazon Interview Puzzle (5)
 Automation Testing (4)
 Einstein Puzzles (3)
 Feature (3)
 Google Interview puzzles (5)
 Google Puzzle (6)
 HR Interview Questions (2)
 Image puzzles (5)
 Induction Puzzles (5)
 Infosys puzzles (2)
 Interview Puzzle (19)
 Lateral Thinking Puzzles (8)
 Microsoft Puzzles (8)
 SoapUI (6)
 Trilogy interview puzzle (2)