Google And The Puzzle of Dropping Eggs

15 Responses to “Google And The Puzzle of Dropping Eggs”

1. a Says:
   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

2. Brian Says:
   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.

3. Angsuman Chakraborty Says:
   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?

4. Brian Says:
   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.

5. Jason Southgate Says:
   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

6. Jason Southgate Says:
   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.

7. duduqin Says:
   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.

8. Vikram Gupta Says:
   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

9. Christo Fogelberg Says:
   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!

10. Michael Thomas Says:
    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!

11. Angsuman Chakraborty Says:
    October 6th, 2007 at 11:42 am

    The optimization is for minimizing the number of drops.

12. Rob Says:
    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!

13. Dhananjay Says:
    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.

14. Correct Says:
    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.

15. Angsuman Chakraborty Says:
    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.

16. dkaminski Says:
    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 \

17. Christo Fogelberg Says:
    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

Looking forward to hear your thoughts.