A Thought Provoking Post From Past - Google & The Puzzle of Dropping Eggs Or What Makes Web 2.0 ClickOctober 5th, 2007 I wrote an article on a Google interview question in June, 2006 describing the problem and offering a simple solution. What makes this article interesting is that several people came up with better ideas and very thought provoking comments.
Explore A Journalists Life 24/7 Live on Camera, Can you identify him?August 27th, 2009 Imagine if you could see what a journalist (the guy with the camera) does all day (from his point of view), covering important events like the Presidents speech to mundane tasks like watching a beautiful skyline to waiting for someone or something special (Ted Kennedy related?). You can hear their idle chatter, name dropping their relationship with Kennedy family, and everything in between.
Google Down!January 8th, 2008 It has been several hours since Google search went down. Google services on google.com domain, including but not limited to GMail or Google Analytics, Google Adsense etc., are down too while blogsearch.google.com is up and running.
Google drops 'beta' from Gmail in move to woo business customersJuly 7th, 2009 Gmail drops 'beta' label to woo business customersNEW YORK — After more than five years officially in testing mode, Gmail is finally graduating from "beta."
Google Inc. says its e-mail service and three other applications in the Google Apps suite for businesses are now finished products in name as well as function.
Top New Features of Google Chrome 2.0May 22nd, 2009 It was dote on to see Google Chrome 2.0 dropping its beta tag. Surprisingly, Chrome was in beta for just three months whereas the Gmail launched four years back is still in its beta. It's semantics that rules Google.
SiteMap of GoogleJune 11th, 2005 I found something interesting: Google's SiteMap. This provides a handy reference to Google Tools which are increasing by the day.
Google Pages Introduced and WithdrawnFebruary 24th, 2006 Google seems to have developed a habit of introducing new services and then withdrawing them due to high demand and reintroducing them selectively later. Google Web Accelerator, Google Analytics and now Google Pages, all follow this overused pattern.
Google Loses Over 16 Billion in 1 DayJuly 20th, 2008 Just after announcing its quarterly results Google lost over 16 billion dollar on Friday. The last trade was at 481.32, down from its previous day high of 534.75.
Ghost DNS Lookup Puzzle on NIS ClientsMay 15th, 2007 I faced an extremely weird problem of ghost DNS lookups on machines configured as NFS clients. It took quite an effort to solve it.
After advertising blitz, Microsoft's new search site Bing lures curious Web surfersJune 9th, 2009 Bing swing: New search engine ups Redmond's share
SEATTLE — In the week since Microsoft Corp. launched Bing, its new search engine, the software maker's share of U.S.
Future Google ProductsJune 13th, 2006 Spencer Katt has an interesting (read funny) take on future Google products (and then there are mine). They are:
1.
Google.Com Banned in China?August 21st, 2006 A Chinese blogger finds Google.com inaccessible around 60% of the time whereas Google.cn is perfectly accessible. Is it coincidence or intetnional?
Is Google intentionally blocking Google.com in China and providing intermittent access instead of outright banning to prevent backlash from internet community & activists.
Is Bing Gobbling Up Google Share or Yahoo's?June 18th, 2009 Microsoft's rebranded search engine Bing is growing at a steady pace, according to the researches. Internet research firm comSource shows that the Bing has gained 12.1 percent of search results over the week from 8-12 June.
In Defence of Google Web SearchJuly 9th, 2006 Nowadays it is common to complain about the accuracy of Google web search results (not image search as I have done in my earlier post). Most of the people complaining about Google web search are SEO types and those who have been affected by sudden lack of Google love.
Google Venturing In Blogging? ... Hiring Bloggers?September 20th, 2006 I am not talking about providing blogging software / service like Blogger. It looks like Google (at least Google India) may actually venture into blogging themselves.
18 Comments | 
Email this Article
Loading ...
June 10th, 2006 at 12:24 pm
wouldn’t you drop it from the 51st instead of the 76th floor on the second round? if the first broke on 75, then it’s between 51 and 74 inclusive that you need to check now
June 10th, 2006 at 5:41 pm
I spent a long time typing a detailed explanation of a solution but I lost it in a browser mishap. But, here is my solution, without the explanation: drop egg #1 at every 10th (0, 10, 30, 50…) floor, and drop egg #2 at every 20th floor (20, 40, 60…), until one breaks. Then, drop one egg on every odd numbered floor and the other on every even numbered floor until one breaks. Then, you will have the answer to the question of “what is the lowest floor on which the egg will break?”
If you analyze the two solutions with respect to the number of drops, you will see that this alternative has the same best-case performance, and notably better worst-case performance, always wins when the answer is within (10,50) when, and often wins (but sometimes loses) when the answer is greather than 50.
If you analyze the two solutions with respect to travel time/effort going up/down the building, then I believe that the alternative’s advantage is even better. Your solution ignores travel time, but I imagine you’d do it the same way I did (travel up, drop one, travel up again, drop the other, then travel down to get both).
I don’t know if the alternative solution is optimal; I was just trying to show a better alternative. I too am interested in a better solution.
June 11th, 2006 at 7:17 am
@a
That depends on whether your floor numbering starts from 0 (ground floor) or 1 (first floor).
@Brian
I am sorry to hear your explanation got lost. I would love to hear it.
> Then, drop one egg on every odd numbered floor and the other on every even numbered floor until one breaks.
At this point one has already broken. If your second egg breaks too then you do not have any more eggs to find the exact floor.
Also why use two eggs at ood and even floors? Why not simply use one egg? We are limited by only two eggs. So shouldn’t we keep the second egg to pinpoint the exact floor?
June 12th, 2006 at 12:37 am
You are right; I copied my wording from the 10/20 part absent-mindedly. Once the first egg breaks, you should drop the second one from every floor, increasing the floor number by one, just as in your case.
However, my main point was that it is better to go every 10th floor then to try the “binary search” you described. Your search is highly optimized for when the answer is a floor over 75 and it performs very poorly for high floors less than 50.
The reason for the “every 10th floor / every 20th floor” logic is to minimize travel time. Let’s say that the answer is “22.” Then, I would drop egg #1 from floor 10, it would not break. Then, I can go up to floor 20 and drop egg #2 from floor 20, and it does not break. Then I need to go down and pick up both eggs, and take them both to floor 30. At this point I have traveled 10+10+20+30=70 flights of stairs.
If travel time is not an issue, then you could just go up to floor 10, drop egg #1, go down to pick it up, carry it up to floor 20, drop it again, go down to pick it up, go up to floor 30 etc. In this case you would just keep egg #2 in your pocket until egg #1 breaks. This method would require traveling 10+10+20+20+30=90 flights of stairs to get to floor 30. This is the kind of detail that interviewers would probably be interested in at least hearing about-they’d also probably like you to at least ask if the eggs will weaken structurally as you drop them.
Note also that I chose “10″ arbitrarily: I was just trying a better solution, not the optimal one.
June 22nd, 2006 at 4:35 am
What about N floors?
Is 10 a good choice since it’s the sqrt of 100?
What about using a binary search on floors i=1, 2, 4, 8, 16, 32, 64, … and then a linear search for the floors inbetween?
A solution for 36 floors is here:
http://mathforum.org/wagon/past_solns/s921.html
Using the fact that 36 is the 8th triangular number, i.e. 36 = 1 + 2 + … + 8
June 22nd, 2006 at 8:04 am
If you know the height of the building then I think the jump search is optimum using sqrt(h) as your jump size, but if the height of the building is unknown then I’m really not sure. Triangular numbers, fibonnaci, or binary. Binary search on floors i=1, 2, 4, 8, 16, 32, 64, … covers a lot of ground quickly with the first egg.
November 4th, 2006 at 4:02 am
hei…just a simple math problem
suppose we jump every N floors, and use second egg in the one step increasing pinpoint.
MaxNumbers = 100/N + (N-1)
To get the Max N we take a derivative:
-100/N^2 + 1 = 0 => N = 10
So we take 1st egg every 10 floors, then second egg one by one to pinpoint.
Worse case: 19
Average case: 10.
November 30th, 2006 at 1:43 am
Say X is the number we are looking for. Then, my choice will start with floor X first. This way, if the egg breaks, I start a linear search starting from 1 to X-1, guaranteeing a solution in Y attempts. Otherwise, I go to X + (X-1) floor…. Continuing in this way, with X attempts, I can cover sum(X + X-1 + X-2… 2 + 1) floors. Hence, we are looking for Min X such that X(X+1)/2 > 100.
I can do it in 14
October 4th, 2007 at 3:57 pm
I ran into this problem recently and am looking for a solution… it seems there are many
I don’t have a formal proof of this, but a gut feeling tells me my solution is good/pretty close to optimal (and it’s nice to have Jason Southgate’s agreement, I think he’s describing the same solution?).
Algorithm (assumes we know the number of floors):
* Number of floors = N
* Drop the first egg at floor 1 * sqrt(N), 2 * sqrt(N), … until you either reach N or it breaks. If you drop it from the top floor without it breaking you have your answer.
* If it breaks when dropped from k * sqrt(N) floor then drop the second egg, starting at the (k - 1) * sqrt(N) floor and going up one floor at a time until it breaks. By definition it must break sometime before k * sqrt(N)
I think this algorithm is O(N^0.5) - the maximum number of drops it can take is sqrt(N) + (sqrt(N) - 2). This would occur if it broke on the N-1′th floor.
Two interesting extensions of it would be: what if the number of floors doesn’t have an integer square root? E.g. if N = 378? It seems there are three alternatives for the size of the increment of the first egg drops - the floor, ceiling or round of sqrt(N). I’m not certain of my answer but I think using the round would be optimal?
The second extension is what to do in the case of an unknown number of floors, where N is just some integer (1…infinity). sqrt(infinity) just doesn’t make sense, and it seems to me that if any integer is equiprobable (sp?) then you want to leap up towards infinity as fast as possible, so you get a known upper bound and then just have a linear search. But I have no way of expressing this formally or in any convincing way, I’m just pumping intuitions madly!
All this fancy reasoning said though I think the triangle number solution linked to above is actually better. I’m just not sure how you would generalise it to situations where N is not a triangular number.
Binary search would be O(log N) though… hmmm, OK, now I’m confused and lack all certainty, but what the heck, other things to do this morning, I’ll post anyway
Christo
PS: A point I didn’t consider till now: if you’ve checked all but two possible floors and break the egg on the second to last possible floor then you still have your answer… Again, not sure and no time to see if this is important!
October 5th, 2007 at 5:13 pm
The original puzzle doesn’t say what they’re trying to optimize, so I assume the optimization variable is left to the solver.
Personally, I would optimize for minimal egg breaks by starting on floor 1 and going up one floor at a time until it breaks. In the end you’d be left with your answer and one unbroken egg. Any egg that can survive a drop from more than 1 story would be a very valuable egg indeed, and get you a lot of money on ebay!
October 6th, 2007 at 11:42 am
The optimization is for minimizing the number of drops.
October 16th, 2007 at 12:42 am
For goodness sake. The egg will break when dropped from the first floor because, well, it’s an egg.
I say cook the two eggs for breakfast and move onto the next question!
November 2nd, 2007 at 11:21 pm
@Christo Fogelberg execellent explanation and generalisation for optimizing the no of attempts.
but ofcourse you can match sqrt(n)(how did you find this?) from duduqin solution.
it is like :
no of steps = n
let us assume x = no of steps between two attempts
and y = total no of attempts with first egg (maximum)
so we get
x*y = n
and now no of attempt = y + x -1 (or y + x not sure)
so for min(y + x - 1)
derivative(y + x -1) = 0
so you get x = y = sqrt(n) from here.
Now we can go with your solution.
I dont know what to do when it is required to optimize not the no of attemps but the total no of steps travelled(going up to some floor and coming down to collect the egg(s) and in the same way).
Please put your views.
December 4th, 2007 at 4:24 am
Well because the questions is based upin eggs (fragile), we need to include the non-algorithmic parameters as well.
Looking at the question statement, nothing is mentioned about the material on which it is to be dropped & the place where it should be dropped. In those cases the egg could also be dropped on to the same floor from any height.
December 4th, 2007 at 9:20 pm
Obviously it is being dropped to the ground otherwise the question becomes meaningless. What non-algorithmic parameters are you talking about?
The task is to determine at which height (divisible by height of each floors which are of equal height) the egg breaks. The material of egg is unknown but obviously it is made of stronger material than your regular poultry egg.
December 14th, 2007 at 11:48 am
One idea is that you want to maintain a constant risk throughout the drops to guarantee an equal average- and worst-case.
With the strategy of skipping a constant number of floors \
January 18th, 2008 at 1:36 pm
I found this page again randomly while checking nothing too noxious was being attributed to me on Google, it sounds like the discussion has moved on so I figure I\’ll add to it again
@Dhananjay:
Yes, going back now and reading duduqin\’s reasoning I see it is a specific example for n=100 of the general case.
You are also right that I did not explain why sqrt(n) was optimal - and in fact, as I think I noted, I\’m still not sure that it is!
In any case, I don\’t think derivatives factor into it. Perhaps they do but I\’m not sure what you\’re deriving with respect to. I agree x = y and that the maximum number of attempts will be n=xy and that you can get sqrt(n) from that but I\’m still a little bit confused. Sorry! Also, what does the min function in min(x + y - 1) refer to or mean?
###########
@dkaminski:
I haven\’t thought about this much, but I think you\’re right - it would be interesting to look at the expectation distribution. Any further thoughts? (I have none right now:)
Actually, talking of expectation, a cute wee problem with plenty of off-by-1 and off-by-k chances that a friend and I ended up talking about over dinner recently goes something like this:
You have a bag with 50 lengths of string inside it.
You pull out one end of one piece of string, leaving the rest of that piece in the bag. You pull out a second end of string, possibly the end of a different piece of string and possibly the other end of the piece of string you\’re already holding. You tie the two ends together before dropping them back in the bag.
After all the ends have been tied to some other end, what is the expected number of loops in the bag?
OK, it\’s Friday night, there\’s jazz and cocktails on and if I\’m not going to go to that I should really be doing something more productive. Cheerio all!
xto