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

281 comments:

«Oldest   ‹Older   201 – 281 of 281
Farrah 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

Bloglarım said...

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

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

brandan said...

You are a Great while writing in the blogs it is awesome I liked it too much good and informative thanks for the sharing.
buy medicine

Silviu said...

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

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

anita grace said...

organic vitamins
The blog is to good and informative where i like to discuss about this in my blog thanks for sharing.

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

saim said...

It was very useful for me. Keep sharing such ideas in the future as well. This was actually what I was looking for, and I am glad to come here! Thanks for sharing the such information with us



natural supplements

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

cahill said...

Hi

Tks very much for post:

I like it and hope that you continue posting.

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

Source: Case manager interview questions

Best rgs
David

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,

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

Ravi Singh 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)

Ravi Singh 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)

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

escort ankara said...


Hi, Thank you write.
to share is Ankara Escort thank you share.
good site admin


Escort Ankara
Ankara Escort
Escort Bayan Ankara
Escort Bayan Ankara
Ankara Escort
Escort Ankara
Escort Ankara
Escort Ankara
Escort Bayan Ankara
Escort Ankara
Escort Ankara
Escort Ankara
Escort Ankara
Ankara Escort

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

Russell Stewart 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)]))

Sumera Riaz said...

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

Unknown said...

Site's character and a great color match .. Göğüs estetiğiI will recommend your site to the other platforms.

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

xian wang 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?

Mohit Mishra said...

Computer Science Interview Questions

Interview Questions
Prepare For Exam
Facebook

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

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

Maa Guru 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

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

rags bhat 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

Ema Banu 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. :)

rags bhat 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:)

Sri Ram said...

single try is enough when i boils the egg

xmen said...

Tks very much for your post.

Avoid surprises — interviews need preparation. Some questions come up time and time again — usually about you, your experience and the job itself. We've gathered together the most common questions so you can get your preparation off to a flying start.

You also find all interview questions at link at the end of this post.

Source: Download Ebook: Ultimate Guide To Job Interview Questions Answers:

Best rgs

charlie said...

All I need is 13

Kix Mr said...

Tks very much for your post.

Avoid surprises — interviews need preparation. Some questions come up time and time again — usually about you, your experience and the job itself. We've gathered together the most common questions so you can get your preparation off to a flying start.

You also find all interview questions at link at the end of this post.

Source: Top 10 interview questions and answers

Best rgs

Iram Khan 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/

Fan 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

Fan 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

Nitin Gohil said...

Very informative post.
For more information on complete flooring solutions click here

Angela Navejas said...
This comment has been removed by the author.
Angela Navejas 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

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

Harshit Kappor 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

Nick Ponting said...

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

Bull18 Movers Melbourne said...

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

mk said...

Gay Sex Cams


Gay Webcams


Free Video Sex Chat


Couple Live Webcams


Instant Live Sex Cams


Live Sex Boys Cams


Free Webcam Sex Rooms


HD Gay Porn


Live Dolls TV


XXX Gay Porn Galls


XCamMix.com


Super Movies Gay


Superior HD Sex Cams


Camgirls Online


Free Sex Webcams


Teen Cam Vids


Bed Spy Cams


Cutest Cam Girls


Live sex cams


Teen Webcam Sex


My Hidden Cameras

Priya said...

The information you have deliver here is really useful to make my knowledge good. Thanks for your heavenly post. It is truly supportive for us and I have accumulated some essential data from this blog.
CAT coaching in chennai

Varun Reddy 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

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

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

Sharaf Mohamed 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

ltf Solution said...
This comment has been removed by the author.
ltf Solution 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

RC Furniture Store 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

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