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:

«Oldest   ‹Older   201 – 208 of 208
marcus benson said...

I want to share this wonderful testimony to the Good people all over the world on how I was able to Enlarge my Penis by Dr. zubby. I was living a shameful life from my young age, just last month as I was browsing on the internet about Penis size and Enlargement Products, I saw a testimony of a Man called George , testifying of how he was able to get his penis Enlarged by Dr. zubby and I decided to also Email Dr.zubby for my small penis size and he quickly respond to me and gave me the normal instructions which i did and then he shipped the product to me here in the united state which i received in just 3 working days and today i am very happy because i started seeing positive changes in my penis size in just 7 days of use. Dr zubby herbal product is the best recommended for you and to whom ever suffering from this shame or having any other diseases as well should Contact this great herbal doctor via his Email : dr.zubbysolutionhome@gmail.com and WhatsApp Him on   +2348070673249

Phases of the Moon said...

I read your blog. Its so nice and also provide such a good knowledge for us. I really like it, Thanks to write this blog.
Free phases of moon
Montessori moon puzzle
Cycles of moon
Lunar phases of moon

Monika said...

It is very important to have good thoughts in mind to write a beautiful post and your mind seems very clear only then you have written such a beautiful post, this post is worth praising, it will be less than the praise of this post.
gurgaon call girls
neemrana call girls
call girls in gurugram
call girls in gurugram
Gurugram escorts
hot call girls in gurugram
VIP Girls
escort service gurugram

shipra shah said...

If you keep writing this kind of post then I will be very happy because this post is very good and I am very happy that I saw this post and today I am very happy to see this post, I have also written a lot of websites and blogs. . I am giving you in the link, you can see if you want.
escorts service in sector 40
call girls in gurugram
Colorful call girls
gurugram escorts
Monito every escorts
Love
sector 41 escorts

shipra shah said...

It is very important to have good thoughts in mind to write a beautiful post, and your mind seems very clear, that is why you have written such a beautiful post, this post is worthy of praise, the praise of this post will be less.
Escorts Services in Palam Farms
gurugram event
call girls in noida
DLF Cyber city Escorts
escorts in gurugram
Escorts Service in Sector 15
Sector 46 Escorts
bilaspur independent escorts

Digital Marketing Brains said...

Play free 2 player word games and
online multiplayer scrabble puzzle game

Anonymous said...


I'm giving gratitude to Mr Pedro for all of his help in securing our loan for our new home here in Fruitland. You were organized & thorough & professional, as well as kind which made all of the difference in our interactions with you. We put our trust in you and you most definitely came through for us. Thank you for your patience as well as treating us as people rather than just home loan customers. You stand above the rest, I want to recommend anyone here looking for loan or investors to contact Mr Pedro and his staff because they are good people with gentle heart,
Mr Pedro Email Contact : pedroloanss@gmail.com



Regards,
John Burley! Our hats off to you!!"

ossawrd said...

Amazing post! .I appreciate your hard work. Thank you for sharing. I have also shared some useful information about
EggFecto Egg Cooker Review > on Ossward.org

«Oldest ‹Older   201 – 208 of 208   Newer› Newest»