A Googlish puzzle

It’s probably getting to the point where everyone’s a bit tired of hearing about Google’s interview process but recently heard a nice one someone was given to solve – one of those “Can you think like a programmer?” type questions. It goes like this…

You have two eggs. These are special eggs – they can take much more punishment than you average chicken egg. But the question is just how much punishment can they take?

Using a 100 storey building and only the two eggs, how would you find out which is the highest floor of the building you can drop the eggs from, before they break?

It could be the 1st floor but it could also be the 99th floor – you don’t know but to test, you need to try dropping the eggs from different floors and see what happens.

Technically there isn’t a “right” answer as such, although what was expected is an approach that requires the least number of tests, irrespective of where the result lies – an efficient search algorithm which offers consistent performance no matter what the result is. If you’re struggling for inspiration, try here – doesn’t help directly but might prompt some lateral thought.

To some extent questions like this are a little unfair these days, if it wasn’t Google doing the asking. Picking a random number, I’d guess 95% of programming today has nothing to do with solving these kind of problems any more – it’s all hidden behind APIs (or in DBs) offering “good enough” performance 99+% of the time. Most employers will be less-than-impressed if your answer to “Is it finished yet?” is “No, but my latest search algorithm is kicking”.

Anyway – something not-too-heavy to ponder over while waiting for the whistle.

Free book: Jump Start HTML5 Basics

Grab a free copy of one our latest ebooks! Packed with hints and tips on HTML5's most powerful new features.

  • http://www.deanclatworthy.com Dean C

    Very interesting. I’m sure I’m wrong but I’d increment in two’s. Drop it from the 1st floor. If it doesn’t break then drop it from the 3rd floor, if it breaks i’d drop the second egg from the second floor, else try dropping from the 5th floor, and so on :p

  • Scott Mattocks

    Dean,

    I think you are on the right track but you forget that you have two eggs. You can jump by four until the first egg breaks. Then you drop the second egg from two floors below that. If the second egg breaks, the barrier is one floor below. If it doesn’t, go up one floor and drop again. At that point you should have a definitive answer in at most (highestfloor / 4) + 2 drops.

    Scott Mattocks

  • Richard@Home

    …or do it one at a time and save an egg.

  • Yogler

    But that would take more tests, Richard. The goal was the minimum number of tests. :)

  • Fenrir2

    Scott, that won’t work. Assume you are on the 4th floor, and you have two eggs. You drop one, it doesn’t break. You go up 4 floors (8th), and drop the other egg. It breaks. You get the egg on the ground, and drop it from the 8 – 2 = 6th floor. It breaks.

    Now you don’t know if the “breaking floor” is the 5th or the 6th.

  • http://scottyearton.com scottyearton

    actually, shouldn’t you start at the second floor? that way, if it breaks, then the forst sloor is the safe drop and you’re done, because the puzzle assumes you can drop it from some floor without it breaking.

  • Anonymous

    With the 2nd egg you can only afford to try one floor at a time, but that doesn’t mean you can’t take a good bit more risk with the first, so you can do a lot better than every other floor.

    How about trying every 10 floors with that? That will narrow it down nicely. :)

    Maximum: 19 tries needed (floor 98 or 99):
    Egg one: floor 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 (breaks)
    Egg two: floor 91, 92, 93, 94, 95, 96, 97, 98, 99
    If egg two breaks at 99 your safe height is 98, otherwise it is 99.

  • http://scottyearton.com scottyearton

    *forst sloor = first floor. :)

  • http://www.vodkafish.com VodkaFish

    Well, one approach I might take is “what’s the maximum amount of drops I want to make?” This is thinking that the break floor could be anywhere and I simply want to mimimize my drops, no matter where it is. You go every 10 floors with one egg until it breaks, then you go up 1 by 1 from the last safe floor. 18 possible drops at the most with that method. In math terms I guess it’s the squareroot of 99 * 2.

    However, that doesn’t ensure you’re going to still drop it less than anyone else. Let’s say you take the safe route and go every three floors (so if 4 is safe, you go to 7, if it breaks, go back to 5 and start that as your new base number – you’ll never miss the exact break floor that way). If the break floor is very low, you’ll drop less than the first method.

    I’d go with the first method if I had to do it real world.

  • http://www.vodkafish.com VodkaFish

    Looks like I write too slow :)

    The anonymous post is what I was getting at – I also said 18 instead of 19 since I was thinking this was a 99, not 100 storey building (need more coffee… or maybe less).

  • Wim Heemskerk

    Sorry about the completely anonymous post. That was me. I’d been wondering about even better tactics for a while, so I refreshed the page before hitting submit to check if no one else had posted the same meanwhile but forgot to put my name (back) in.

  • Jens

    It is not a Googlish puzzle but simply a modification of The Monk and the Riddle ISBN 1-57851-644-7 (pbk)

  • Fenrir2

    I created a Ruby script to test an algorithm. It works like this:

    test "Simple algorithm" do
    next_floor = 0
    while eggs_in_hands?
    walk :to => next_floor
    next_floor = floor + 1
    drop_egg!
    if egg_broken?
    report_solution! floor
    elsif no_eggs_in_hands?
    pick_up_eggs!
    end
    end
    end

    This defines a simple algorithm: you just go up one floor at a time, and drop an egg. If you don’t have any eggs in your hands, you go down to pick the eggs from the ground, and then you continue the drop, go up cycle.

    This algorithm isn’t very good, but it’s easy to understand. The Ruby script tries this algorithm 99 times, each time with a different breaking floor, ie the max height before the eggs break. It logs the number of floors you go up and down. So if you go up one floor, drop an egg, go up another, drop, go 2 floors down to pick the eggs, and go to floor 3 to continue the test, that counts as 7 “walks”. The script also logs the number of times you drop an egg.

    "Simple algorithm" solved 99 of 99 puzzles. It took 166650 walks and 5049 drops

    I hope my script counts correctly, if it does, this is the algorithm that requires the least number of “walks”, and uses a skip method:

    test "Skip 7 algorithm" do
    n = 6
    next_floor = n + 1
    while eggs != 0
    if no_eggs_in_hands?
    pick_up_eggs!
    elsif eggs == 1
    walk :to => next_floor
    next_floor = floor + 1 if floor != 99
    drop_egg!
    if egg_broken?
    report_solution! floor
    end
    else
    walk :to => next_floor
    drop_egg!
    if egg_broken?
    next_floor = floor - n
    else
    if floor + n + 1 > 99
    next_floor = floor + 1
    else
    next_floor = floor + n + 1
    end
    end
    end
    end
    end

    The algorithm goes like this:

    You go 7 floors up, and drop an egg.

    - If the egg breaks, you go 6 floors down, and drop an egg. If the egg breaks, that it the max + 1 th floor. If it doesn’t, you pick the egg up, go up 1 floor, and try again.

    - If it doesn’t break, go 7 floors up again, and drop the remaining egg, and loop.

    This algorithm produces this result:

    "Skip 7 algorithm" solved 99 of 99 puzzles. It took 63242 walks and 1149 drops

    The library to execute this:

    $verbosity = 0
    @tests = []

    def report(msg)
    puts msg if $verbosity == 2
    end

    def setup!(bf)
    @highest_floor = 99
    @break_floor = bf
    @eggs_in_hands = 2
    @eggs_on_ground = 0
    @floor, @walks, @drops = 0,0,0
    @solution = false
    end

    def walk(arg)
    if arg.is_a? Symbol
    walk arg => 1
    elsif arg[:to]
    if arg[:to] @highest_floor
    puts "Cannot go to floor #{arg[:to]}"
    return false
    end
    @walks += (@floor - arg[:to]).abs
    @floor = arg[:to]
    report "Walk to #{@floor}"
    true
    elsif arg[:up]
    walk :to => (@floor + arg[:up])
    elsif arg[:down]
    walk :to => (@floor - arg[:down])
    end
    end

    def drop_egg!
    @egg_broken = false
    @drops += 1
    if @eggs_in_hands floor
    @eggs_on_ground += 1
    report "Dropped egg! -- Didn't break"
    else
    @egg_broken = true
    report "Dropped egg! -- Whoa, broken!"
    end
    end

    def egg_broken?
    @egg_broken
    end

    def eggs_in_hands?
    eggs_in_hands > 0
    end

    def no_eggs_in_hands?
    !eggs_in_hands?
    end

    def eggs_in_hands
    @eggs_in_hands
    end

    def eggs
    @eggs_in_hands + @eggs_on_ground
    end

    def pick_up_eggs!
    report "Picking up eggs -- found #{@eggs_on_ground}"
    verb = $verbose
    $verbose = false
    walk :to => 0
    $verbose = verb
    @eggs_in_hands += @eggs_on_ground
    @eggs_on_ground = 0
    end

    def floor
    @floor
    end

    def highest_floor
    @highest_floor
    end

    def report_solution!(floor)
    @solution = floor
    throw :finished
    end

    def test(algorithm, &alg_proc)
    @tests alg[0], :walks => @walks, :drops => @drops, :solved => @solution == @break_floor, :solution => @solution}
    end

    def run_tests!
    results = []

    for alg in @tests
    for n in (1..99)
    results

    Can you come up with a better algorithm?

  • Fenrir2

    Somehow the last bit of code didn’t get posted, so here it is:

    results

    The code looks really ugly without indenting :S.

  • Fenrir2

    OK, sitepoint doesn’t like that bit of code.

  • Fenrir2
  • http://www.phppatterns.com HarryF

    It is not a Googlish puzzle but simply a modification of The Monk and the Riddle ISBN 1-57851-644-7 (pbk)

    Thanks for the reference. Interesting looking book.

    Wim (as anon) got the answer they were looking for BTW. There is one further optimisation (but would require calculation) which is reducing the increment of the first egg the further you go up, which can reduce the number of attempts below 18, if the answer is on floor 99.

  • Piku

    You can also do something like a binary search.
    Drop it from 50 floor, if it breaks then drop it from 25 floor and cutting in half every time. I haven’t calculated, but it should be pretty efficient.

  • Anonymous

    That is not possible because you have a chance that you break both eggs.

  • DevonWright

    Wait until both eggs hatch. Mate the creatures that are in the eggs.

    Use 100 eggs and drop from each floor (be sure to number them)

    :D

  • didimo

    picu has the best search algorithm for this case ;)

  • Anon

    the first thing to mention is that every process has variation – so we have to document our assumptions.

    1. that the eggs will break on the same floor. there is variation in everything, so on eegg could break on the 50th floor and the other oculd break on the 53rd floor.

    2. that the strength of the eggs doesn’t change with each marginal drop.

    3. that you know nothing about the strength of the eggs to approximate a probability distribution regarding where the eggs will break. if you have some significan tforknowledge, the process to zone in the exact floor can differ. iow, if you were pretty sure the eggs can’t survive a 20th floor drop, you procedure would change.

    all in all, good question and good answer – especially with the nuance of reducing the increment to possibly reduce the number of tests.

    a friend interviewed at motorola:

    given:

    1. two rooms (one with 3 switches (A, B, C), one with 3 lightbulbs (1, 2, 3).
    2. the room sare separated – when you flick a switch you can’t see in the other room.
    3. each switch matches one, and one only, light.
    4. you enter the switch room and can only leav eit to enter the light room a single time.

    what do you do to mate up each of the three switches to their corresponding lights?

    this question is easy if you are able to think out of the box… errr, bulb.

    good luck.

  • Anon

    okay, another… from motorola again…

    you have 9 marbles and a balance scale. one marble weigh slightly more than the other eight.

    what is the minimum amount of measurements required to accurately identify the heavier marble?

    btw, my friend didn’t answer either of these questions and still got the job. ;-)

    he didn’t give me enough time to ponder for an answer before he told me – so i don’t know if i would’ve gotten it or not.

  • Ryan Wray

    I don’t know if someone had already posted this one but this is what I am thinking, in pseduo-code:

    low = 1, high = 100;
    egg1, egg2;

    story = floor(high/2)
    egg1.dropFromFloor(story)

    if egg1.isSmashed() == true:
    high = story
    else if egg1.isShamed() == false:
    low = story
    end if

    while egg2.isSmashed() == false AND low high:
    print "Egg does not smash"
    else:
    print "Egg smashes on floor "+ low

  • http://www.assemblysys.com mniessen

    Anon,

    I would say 5…

    1) weigh 3 marbles
    2) weigh 3 others
    3) weigh the last 3

    You’ll then know with certainty which set contains the heavier. Divide the weight of that set by 3 to get the average.

    4) weigh the first marble in that set
    5) weigh a second one.

    The one that is heavier than the average you calculated before is the one. If both are of equal weight, it’s the third one.

  • Anonymous

    For the balance puzzle, you need two meausurements.

  • Anonymous

    Take any 6 marbles and put 3 on each side of the scale.

    If any side is “heavier” that set of three contains the marble.
    Take it and put 2 marbles with one on each side. If any side is
    “heavier” then that’s your marble.

    If at any time, both sides weight the same, then the heavy marble
    must be in the group which you didn’t weigh.

  • http://www.assemblysys.com mniessen

    Anon,
    In fact, it could even be 4 steps only, because if the 2 first sets of 3 marbles weigh the exact same, you’ll know that the third one is contains the heaviest, and you’ll know the weight of a “normal” marble (average of any of those 3 marble sets).
    If one of the first sets is heavier, it’s the one containing the heaviest marble.
    So definitely, 4 steps are enough…

  • Anonymous

    mniessen,

    You only need two measurements to deduce which is the heavy marble.

  • http://www.deanclatworthy.com Dean C

    [quote]
    picu has the best search algorithm for this case ;)
    [/quote]

    Wrong, binary search won’t work in this instance. What if it breaks on the 2nd floor, and you have already wasted your eggs doing the first 2 intersections.

  • Ryan Wray

    No, actually, I had a more better alogorithm in mind but I got sidetracked eventing a suitable pseudo-language. Here is what I have in mind in untested PHP (this the language I decided to use :p):


    isSmashed() == false || $story == $high) {
    $low = $story;
    $story = floor(($high/2) + $low);
    $egg1->dropFrom($story);
    }

    if ($story == $high) {
    echo "Egg does not break on a ". $high ." story high building.";
    }
    else {
    $high = $story;
    while ($egg2->isSmashed() == false && $low dropFrom($low);
    $low++;
    }
    echo "Egg drops from the ". $low ." story";
    }
    ?>

  • http://www.assemblysys.com mniessen

    Oops… I missed it was a “balance” scale…

  • Ryan Wray

    The concept of binary search works in this case (that is what I did). Use the first egg for the binary search, and as soon as the first egg smashed, use the second egg and drop it from the last known safest story and increment your way up till you either stumble on a lower floor where an egg smashes then your egg1 or you reach the same floor as egg1. That seems to be a valid algorithm to me.

  • http://www.deanclatworthy.com Dean C

    To answer the marble question.

    Weigh any two marbles. If they are equal you have removed 2 options and are left with 7. But if they are not equal in weight you know that one or the other is the lighter, hence by taking one of the marbles out of the scales and replacing it you either find the new two marbles of equal weight, meaning the one you took out is the lighter, or they are of different weight, meaning the one you didn’t take out is the lighter.

    However, if this is not the case then you are left with 7 marbles, and place another 2 marbles in the scales, and proceed as before until you find your marble :)

    That’s how I would do it. You either have a minimum of 2 times that you have to weight the marbles, or a maximum of 4 times (I think ;))

  • Ryan Wray

    This system doesn’t like code, does it. :p

  • Ryan Wray

    I have heard the light bulb one before, though I think variation. What you do is turn on 2 switches, and wait atleast few minutes. Then, turn off 1 of the switches.

    Now you enter the lightbulb room. The lightbulb that is still on is matched to the switch you left on. To find the lightbulb you turned on for a while before turning off you find the lightbulb between the 2 that are off which is the warmest. The one which is cold was never turned on, and so is easy to match.

    This question, in my opinion, is stupid one to ask a programmer. I mean, it is possible that a programmer might not even consider the fact that lightbulb let off heat he may have never handled a lit lightbulb let alone a lightbulb at all.

  • Anonymous

    For the egg drop puzzle, instead of thinking about binary search, think about how to best balance a possible low-breaking floor search with a possible high-breaking floor search to determing your floor skip size.

    For example, if I chose to skip the first 20 floors and test on this floor; I then have to test each floor up to this point to determine the actual floor. Thus, in low worst case, I test 20 times, (once for the 19 floor, and 19 times to check for floor 1 through 18). If the possible floor is very high (say 99), then I just add 4 additional tests onto the algorithm, for worstcase test of 24 times.

    Now, ask yourself, is this skip value of 20 the best given you have 100 floors (ground is a floor)? Is some smaller value better?

    With a 10 floor stride, you have min test count of 10, worst case test count of 20.

    With a 15 floor stride, you have min test count of 15, worst case test count of 20.

    Thus, the optimial solution will be where the min and max test count approach one another.

  • aneitlich

    This is why I stick to marketing. Now the question becomes:

    How do you market eggs that are stronger than the usual eggs to make a fortune?

    Much more fun.

  • http://www.sitepoint.com Matthew Magain

    By the way, if you really enjoy these types of algorithm-solving problems you should definitely check out the regular Ruby Quiz. Some are seemingly simple, like this one, others quite involved, but always guaranteed to teach you something.

  • Pests

    The light switch problem:

    Turn on the first switch for a few minutes. Turn it off. Turn on the second switch and leave it on. Go inside the room with the lights. The light that is on belongs to the second switch. The one that is hot belongs to the first, and the remaining to the third.

  • shea

    For the switch and lightbulb question:
    There needs to be 3 distinct states to be able to verify which switch belongs to which lightbulb. On and off are two states and heat can be used for the third.
    I would flick a switch and leave it on until the light has heated up. Then by turning that light off, and turning any other light on, you can enter the light room and be able to match the switches with the light bulbs.

  • shea

    Hah should check the responses before posting eh? ;)

  • http://www.pcbunk.net XtrEM3

    if i understand the question right, you are dropping 2 eggs (not one) of the same strength. so you can drop two at once and that is considered one test, am i right? (why else would we get 2 eggs?) if this is true, i would modify the binary search, and instead of dividing by 2, i would divide by three…so drop the eggs at 66 and 33 as test 1, 11 and 22 as test 2, etc.

    as far as i can tell, any type of linear search (going up through the list — generally in order) will not be CONSISTANTLY efficient with this scenario. looking at it logically, worst case scenario for a basic linear search is n tests, and worst case scenario for a basic binary search is log2(n). so with 100 stories, worst case for linear is 100 tests (average case of 50 tests), and worst case for binary is 7 tests. improving the linear search by skipping a few will cut down on the tests, but i don’t see how you can get under 7 tests. lastly, if you drop 2 eggs per test (as i mentioned in the last paragraph), you can increase the worst case efficiency to log3(n)…which comes out to a maximum of 5 tests. i’d really love to see another method find the answer in less than 5 tests.

    my 2 cents

  • Fenrir2

    If you drop two eggs, that’s two tests. You have 2 eggs because you can break one. Also, if you drop your first two eggs at 66 and 33 there is a chance you break both. So your method will not work.

    A skip 9 algorithm is most test efficient, and a skip 7 algorithm is most walk efficient.

    With skip 9, you go to floor 9, drop, if it doesn’t break, you go to floor 18, drop, etc. If you do 99 tests, with test 1: breaks on floor 1 … test 99: breaks on floor 99, this algorithm requires a total of 1089 tests, so that’s 11 tests on average. But you can do better by decreasing the number of floors you go up as you go higher.

  • http://www.phpism.net Maarten Manders

    Little variation: What if the building had infinite floors and you had an infinite amount of eggs?

  • http://nedthunkit.blogspot.com/ ikarys

    Speaking from experience with eggs, an adequate algorithm for this can be

    egg_break_floor = 1;

    If anyone has eggs that are capable of surviving a drop from the first floor of a building, I suggest you return them ASAP.

  • Andre

    From a mathematical point of view, the function how many drops are needed when a delta (e.g. 10) is given, is:

    f(x) = 100/x + x – 1

    The formula is based on the assumption that you need for a given stepping a maximum of 100/x droppings plus maximum x – 1 tries after the first egg has broken.

    The function differentiated:

    f’(x) = -100/x^2 + 1 == 0

    an solved gives:
    x = +-10

    So this function has a minimum at x = 10. So is this the best stepping for 100 floors.

    For 1000 floors it would be x^2 = 1000 -> which gives x = 31.6

    So for 1000 floors the stepping 32 or 31 would be best.

    What do you think?

    PS: Sorry for my poor english.

  • Foo

    For the marble question, I can think of two answers depending on the semantics of the question. The absolute minimum number of weighs to find the heavy marble is one weigh, if you’re lucky. All you do is weigh eight marbles, four on each side, with one left off. If the scale is balanced with those eight, then the one you left off is the heavy one. But that’s probably not the answer they want.

    You can always find the heavy one in two weighs like this:

    Divide the marbles into three groups of three (A, B, and C). Weigh two of them (say, A and B). You now know which group of three has the heavier marble: if A and B weigh the same, C has the heavy one; otherwise, the heavier of A and B has the heavy one.

    Take the three marbles in the heavy group (call them X, Y and Z) and do the exact same thing: weigh X and Y and leave Z off. If X and Y weigh the same, Z is the heavy one. Otherwise, the heavier of X and Y is the heavy one.

    If you had 27 marbles with one heavy marble, you could find the heavy one in three weighs. 81, four weighs, etc.

  • Richard@Home

    But that would take more tests, Richard. The goal was the minimum number of tests. :)

    meh, google can afford it ;-)

  • ronanmagee

    Has anyone asked Humpty Dumpty – he only fell off a wall and went to pieces – whats that about 6 feet high?

  • JC

    I go with Andrés mathematical approach.

    I would say

    f/ d + (d-1) = s

    where
    f= number of floors
    d= drop rhythm (each x floors you will drop an egg)
    s=number of drops neaded

    If you calculate from this function on, you will find

    d= sq (f)
    s = 2d -1

    So given 100 floors, you should drop an egg each 10th floor.
    If you have 25 floors, you should drop it each 5th floor.

  • missing

    i assume giving Google’s track record with this sort of thing, if they asked this question, then they would be looking for an approximation algorithim involving an inverted log.

    That is, that the egg is more likely to break on the lower floors than on the upper floors, and as such using this equation for the first egg:

    floor(n) = floor(max) – log n

    there would be more drops in the lower floors.
    Once n has been found (when it breaks), this equation for the second egg:

    floor(m) = floor(max) – log n.m

    incrementing m by 1 each time, startign at 0.

    The base used is a choice based on speed versus accuracy. Base 10 would give the fastest (largest gaps) and as such would be beest for the first egg, whereas base 1.7 or base e would be best for the second egg (conversion requird).

  • SKJ

    What if we drop it by 13 floor ..

    if break floor is say 99 it will take 100/13+8=15 tests better than 10 floor gap which take 100/10+9=19 drops.
    Same with if break floor is 27.

  • Will

    How can one be sure that the eggs will land in the same manner? Egg shell strength isn’t uniform due to its errr… egg shape!

    Am I going off on too much of a tangent?! :)

  • skeeterbug

    you guys are pretty good!

    the answer for the marbles is two weighs…

    divide marbles into 3 sets of 3, put two sets on the balance and then you can determine which of the 3 sets has the heavier marble (the side of the balance that drops or the marbles on the sideline if the balance is even. repeat for the three remaining marbles.

    the lightbulb question is easy when you think outside the light… yes, heat is an identifier, too. if you use heat and light, you can figure out which is which.

    as for asking these questions to a programmer, the position was more of an engineering / technician type position. it might have some programming, but it isn’t all programming.

  • Tim

    I remember doing something similar to this in real life when I was in about prep. We had to take a hard boiled egg, create some kind of container around it and then drop it from about one story up straight on to solid concrete. Whoever’s egg lasted the longest won. I remember people rocking up with eggs in modified bear cans packed with polystyrene and all sorts of modified egg carton contraptions. I showed up with an egg wrapped in a beach towel and won :) Simple is good.

  • http://www.deanclatworthy.com Dean C

    Does anyone know of any good books with puzzles like this that are programming based. It’s fascinated me :)

  • Steve

    Uh. Yeah.

    function dropegg() {
    if (dropfirsteggfromfloor(50).breaks)
    if (dropsecondeggfromfloor(25).breaks)
    return "the max is about the 12th floor"
    else
    return "the max is about the 37th floor"
    else
    if (dropsecondeggfromfloor(75).breaks)
    return "the max is about the 62nd floor"
    else
    return "the max is about the 87th floor"
    }

    That would get you “close enough”, eh?

    -Steve.

  • http://www.ctinc.ca rommi

    Drop it from the roof first. If it does not break you are done.

  • http://www.ctinc.ca rommi

    Or drop an egg from every 10 floor – 10 drops max.

    Then when and if it breaks go the previous X1 floor and start with the second egg.

    This whay you will have a maximum of 19 drops to figure it out.

  • RobR

    easy.

    use a binary chop. this is a technique for locating an item in a list quickly and with a consistent and predictable elapsed time.

    for 100 floors, this finds the correct floor with a maximum of 7 attempts.

    increase the number of floors to 1000 and it will find the correct floor with a maximum of 17 attempts.

    this is the correct answer and i claim my $5! :)

  • Jason

    Doesn’t sqrt(n) give you a good delta size??
    What about going up in a triangular number series 1,3,6,10,15.. with the first egg and using a linear search with the second egg?

  • Dev T

    - Drop the first egg at floors 14,27,39,50,60,69,77,84,90,95,99,100

    - when the first egg breaks, drop second egg in the range of floors underneath the floor between the previously tested floor and the floor
    at which the first egg breaks.

    eg. if first egg breaks at 77 then test range of floors 70 to 76

    When the second egg breaks, the floor beneath is the highest floor you can drop the eggs safely without the egg breaking.

    The maximum number of drops is 14 with this method.

    Why begin at 14? 14 is the last number in the arithmetic progression
    1+2+3+4+5+6+7+8+9+10+11+12+13+14 which just exceeds 100.
    The next floor is 14 + 13 = 27
    The next floor is 27 + 12 = 39
    The next floor is 39 + 11 = 50
    ,etc,etc,etc

    Dev T
    TTCS OSSWIN CD at http://www.ttcsweb.org/osswin-cd/

  • dionsiseire

    i assume on the 14 model that if the first breaks on 77, you then drop from 71 73 75 to find the exact floor.

    if it breaks on 75 you know 74 is the highest

    but without physically testing 74 cant you be sure it wont break

  • http://nexusfx.net/ krt

    “i assume on the 14 model that if the first breaks on 77, you then drop from 71 73 75 to find the exact floor.”

    No, eg: if the highest floor you can drop from is 73, the egg would survive from floor 73 and break on 75. How do you know if the highest floor you can drop from is 73 or 74?

    Dev T, good job on beating me to it, that is very close to the best answer. I think my numbers were a bit different towards the end.

  • Smart

    Don’t the eggshells get weaker with each drop?

  • Cs

    Binary gives the best average amount of drops

  • Zhivko

    the reaason questions like these are important is that companies like Google/ Microsoft are the ones that write the API. While a majority of the programming community is just using these API the Googles and Microsofts need to be really carefully with what kind of programmers they select. Hence such mind testing questions.

  • Gili

    Thanks Zjivko! Now I understand why the MS API looks like it does…