Hardest Google Interview Question

Discussion in 'C Programming' started by divya bisht, Oct 23, 2011.

  1. divya bisht

    divya bisht Guest

    divya bisht, Oct 23, 2011
    #1
    1. Advertising

  2. Malcolm McLean, Oct 23, 2011
    #2
    1. Advertising

  3. divya bisht

    Willem Guest

    Malcolm McLean wrote:
    ) On Oct 23, 8:39?am, divya bisht <> wrote:
    )> Hardest Google Interview Question
    )>
    )> http://hardest-puzzle.blogspot.com/2011/10/google-interview-question....
    )>
    ) Drop from first floor. If it doesn't break, pick up the egg, and try
    ) the second floor, and so on. When it breaks, you know the critical
    ) floor.

    If this is the puzzle I think it is, you're supposed to have two eggs, and
    the question is to determine the minimal number of drops which guarantees
    an answer.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
    Willem, Oct 23, 2011
    #3
  4. On Oct 23, 10:53 am, Willem <> wrote:
    > Malcolm McLean wrote:
    >
    > ) On Oct 23, 8:39?am, divya bisht <> wrote:
    > )> Hardest Google Interview Question
    > )>
    > )>http://hardest-puzzle.blogspot.com/2011/10/google-interview-question.....
    > )>
    > ) Drop from first floor. If it doesn't break, pick up the egg, and try
    > ) the second floor, and so on. When it breaks, you know the critical
    > ) floor.
    >
    > If this is the puzzle I think it is, you're supposed to have two eggs, and
    > the question is to determine the minimal number of drops which guarantees
    > an answer.
    >

    The obvious method is a binary search. However you are only allowed to
    break a maximum of two eggs, and you have 100 floors to search, so it
    won't work.
    Malcolm McLean, Oct 23, 2011
    #4
  5. divya bisht

    Willem Guest

    Malcolm McLean wrote:
    ) On Oct 23, 10:53?am, Willem <> wrote:
    )> Malcolm McLean wrote:
    )>
    )> ) On Oct 23, 8:39?am, divya bisht <> wrote:
    )> )> Hardest Google Interview Question
    )> )>
    )> )>http://hardest-puzzle.blogspot.com/2011/10/google-interview-question....
    )> )>
    )> ) Drop from first floor. If it doesn't break, pick up the egg, and try
    )> ) the second floor, and so on. When it breaks, you know the critical
    )> ) floor.
    )>
    )> If this is the puzzle I think it is, you're supposed to have two eggs, and
    )> the question is to determine the minimal number of drops which guarantees
    )> an answer.
    )>
    ) The obvious method is a binary search. However you are only allowed to
    ) break a maximum of two eggs, and you have 100 floors to search, so it
    ) won't work.

    The obvious method with 2 eggs is to use the first egg in increments of 10
    floors until it breaks, and then use the second on the 10-floor interval
    below the floor where the first one broke. 19 drops worst case, IICC.

    But you can do better than that.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
    Willem, Oct 23, 2011
    #5
  6. On 10/23/11 5:40 AM, Willem wrote:
    > Malcolm McLean wrote:
    > ) On Oct 23, 10:53?am, Willem<> wrote:
    > )> Malcolm McLean wrote:
    > )>
    > )> ) On Oct 23, 8:39?am, divya bisht<> wrote:
    > )> )> Hardest Google Interview Question
    > )> )>
    > )> )>http://hardest-puzzle.blogspot.com/2011/10/google-interview-question....
    > )> )>
    > )> ) Drop from first floor. If it doesn't break, pick up the egg, and try
    > )> ) the second floor, and so on. When it breaks, you know the critical
    > )> ) floor.
    > )>
    > )> If this is the puzzle I think it is, you're supposed to have two eggs, and
    > )> the question is to determine the minimal number of drops which guarantees
    > )> an answer.
    > )>
    > ) The obvious method is a binary search. However you are only allowed to
    > ) break a maximum of two eggs, and you have 100 floors to search, so it
    > ) won't work.
    >
    > The obvious method with 2 eggs is to use the first egg in increments of 10
    > floors until it breaks, and then use the second on the 10-floor interval
    > below the floor where the first one broke. 19 drops worst case, IICC.
    >
    > But you can do better than that.
    >
    >
    > SaSW, Willem


    These sort of questions aren't really all that great for interviews, as
    they are the sort of thing that if you have seen this particular one
    before, it becomes trivial, if not, it requires a bit of thought, and
    the pause to do that becomes unnatural in the interview. They much more
    test how the interviewee handles being flustered under pressure than
    problem solving. Unless you are interviewing for something like tech
    support where your expect them to be hit with weird questions as part of
    their line of work, they aren't that good of a measure.

    As to this particular one, the key is to turn the problem around a bit.
    If we ask how tall of a building can we measure with n drops and m
    broken eggs.

    If we are only allowed to break 1 egg, then the only way to solve it is
    to start at the lowest floor and keep moving up, until we break, and
    thus we can measure an n story building.

    If we are allowed to break 2 eggs, then we can say that for the first
    drop, assuming it breaks, we have n-1 drops left, so by above we could
    measure n-1 floor below, so if we drop from the n story, and it break,
    we can use our second allowed break to figure out which floor it would
    happen at. If it doesn't, then we have n-1 drop left, and by the same
    logic we can go up n-1 more stories, to floor n+(n-1) for this drop.
    Continuing on, we eventually get to the floor n+(n-1)(n-2)...+1 which is
    known to be floor n*(n+1)/2 (the formula for triangle numbers)

    we can then extend this to breaking 3 eggs, and we will end up
    sequencing on the pyramid numbers (the sum of triangle numbers), but
    this is beyond what we need to do for this problem.

    Since we have a 100 story building, this requires an n of at least 14.
    So we drop the first egg from floor 14, if it doesn't break the next
    from floor 27, then 35, 46, ... and when we break an egg, you start from
    the floor above which you last didn't break and move up.

    Of course, the real flaw with the problem is it assumes something that
    is unlikely, that both eggs would have broken from exactly the same
    height, and that drops from a lower height don't affect the height that
    the egg can stand before it does break. If you don't make these
    unwarranted assumptions I don't think it is possible to find a solution.
    Richard Damon, Oct 23, 2011
    #6
  7. divya bisht

    James Kuyper Guest

    On 10/24/2011 01:23 PM, christian.bau wrote:
    ....
    > distributions (starting by dropping an egg from the first floor is
    > very likely to give the correct answer very, very quickly),


    For an unprotected egg landing on a paved sidewalk, that's probably true.
    However, I've read anecdotes about bomber pilots in Britain during the
    50's or 60's who, for fun, started testing dropping eggs in containers
    (I'm not sure which kind - certainly not the modern styrofoam ones) from
    high altitudes onto grassy fields. The were flying for some other
    reason, they just dropped the eggs for fun (I think - maybe they were
    testing for the Berlin airlift?). They found that, on average, only a
    few eggs out of each dozen were broken.
    James Kuyper, Oct 24, 2011
    #7
  8. In article <>,
    christian.bau <> wrote:
    >On Oct 23, 7:39 am, divya bisht <> wrote:
    >> Hardest Google Interview Question
    >>
    >> http://hardest-puzzle.blogspot.com/2011/10/google-interview-question....


    I would be surprised if they're still asking that one; Google tends
    to ban questions that are too widely known.

    These questions are asked to test to see if you can work out problems
    and to get a look into your thought process. In my experience, the
    interviewer will generally coax you along rather than force you to
    flounder if you don't get it right away. Of course, if you *do*
    get it right away, that's even better.

    >That's their hardest question? Seriously? Apart from the problem that
    >the "question" in the end is a bit unclear. The number of drops needed
    >obviously depends on something you don't know, which is the lowest
    >height that will break the egg.


    Question specifies that it could break anywhere from the first
    to the last floor.

    >A clearer question would be "which
    >strategy gives the lowest expected number of drops", given some
    >distribution of probabilities, or "which strategy produces the
    >smallest maximum number of drops".


    We generally asked the interviewee to optimize the worst-case
    scenario for number of drops. If they got it easily enough,
    we'd ask what the expected number of drops was. You'd be
    depressed to know how few interviewees even understood that
    part of the question.

    Another variant was to ask the interviewee to give the general
    solution for N eggs and M stories.

    --
    -Ed Falk,
    http://thespamdiaries.blogspot.com/
    Edward A. Falk, Oct 24, 2011
    #8
  9. divya bisht

    arnuld Guest

    > On Sun, 23 Oct 2011 08:53:31 +0000, Willem wrote:

    > If this is the puzzle I think it is, you're supposed to have two eggs,
    > and the question is to determine the minimal number of drops which
    > guarantees an answer.


    My best guess, interviewer is trying to check guy's algorithmic analysis
    skills





    --
    arnuld
    http://LispMachine.Wordpress.com
    arnuld, Oct 25, 2011
    #9
  10. divya bisht

    Bill Reid Guest

    On Oct 24, 3:53 pm, (Edward A. Falk) wrote:
    > In article <..com>,
    >
    > christian.bau <> wrote:
    > >On Oct 23, 7:39 am, divya bisht <> wrote:
    > >> Hardest Google Interview Question

    >
    > >>http://hardest-puzzle.blogspot.com/2011/10/google-interview-question.....

    >
    > I would be surprised if they're still asking that one; Google tends
    > to ban questions that are too widely known.
    >
    > These questions are asked to test to see if you can work out problems
    > and to get a look into your thought process.  In my experience, the
    > interviewer will generally coax you along rather than force you to
    > flounder if you don't get it right away.  Of course, if you *do*
    > get it right away, that's even better.
    >
    > >That's their hardest question? Seriously? Apart from the problem that
    > >the "question" in the end is a bit unclear. The number of drops needed
    > >obviously depends on something you don't know, which is the lowest
    > >height that will break the egg.

    >
    > Question specifies that it could break anywhere from the first
    > to the last floor.
    >
    > >A clearer question would be "which
    > >strategy gives the lowest expected number of drops", given some
    > >distribution of probabilities, or "which strategy produces the
    > >smallest maximum number of drops".

    >
    > We generally asked the interviewee to optimize the worst-case
    > scenario for number of drops.  If they got it easily enough,
    > we'd ask what the expected number of drops was.  You'd be
    > depressed to know how few interviewees even understood that
    > part of the question.
    >

    I don't know if it's "depressing", but as usual I'm somewhat
    amazed at how few "professional" programmers here know the
    correct answer to the question, and all the irrelevant obfuscatory
    crap they spew out to vainly try to disguise their lack of
    critical thinking and knowledge of search algorithms...confusing
    them with a first-day college statistics class concept of
    "expectation"
    is just cruel and unusual...

    > Another variant was to ask the interviewee to give the general
    > solution for N eggs and M stories.
    >

    I'm not sure I saw that in this thread, but it IS pretty
    simple...but what does any of this have to do with ripping
    off Sun's Java(TM) and Apple's iPhone(TM)? I mean, wouldn't
    a better Google(TM) question be: what's the best way to
    shoplift liquor from Rite-Aid(TM)?

    ---
    William Ernest Reid
    Bill Reid, Oct 25, 2011
    #10
  11. divya bisht

    Mark Bluemel Guest

    Mark Bluemel, Oct 25, 2011
    #11
  12. divya bisht

    Phil Carmody Guest

    (Edward A. Falk) writes:
    > In article <>,
    > christian.bau <> wrote:
    > >On Oct 23, 7:39 am, divya bisht <> wrote:
    > >> Hardest Google Interview Question
    > >>
    > >> http://hardest-puzzle.blogspot.com/2011/10/google-interview-question....

    >
    > I would be surprised if they're still asking that one; Google tends
    > to ban questions that are too widely known.
    >
    > These questions are asked to test to see if you can work out problems
    > and to get a look into your thought process. In my experience, the
    > interviewer will generally coax you along rather than force you to
    > flounder if you don't get it right away. Of course, if you *do*
    > get it right away, that's even better.
    >
    > >That's their hardest question? Seriously? Apart from the problem that
    > >the "question" in the end is a bit unclear. The number of drops needed
    > >obviously depends on something you don't know, which is the lowest
    > >height that will break the egg.

    >
    > Question specifies that it could break anywhere from the first
    > to the last floor.
    >
    > >A clearer question would be "which
    > >strategy gives the lowest expected number of drops", given some
    > >distribution of probabilities, or "which strategy produces the
    > >smallest maximum number of drops".

    >
    > We generally asked the interviewee to optimize the worst-case
    > scenario for number of drops.


    Looks like you've under-specified the problem, currently.
    (Pop over to rec.puzzles, they're always good at both finding answers
    to, and pedantic flaws in, puzzles.)

    > If they got it easily enough,
    > we'd ask what the expected number of drops was.


    Yup, definitely underspecified.

    > You'd be
    > depressed to know how few interviewees even understood that
    > part of the question.


    Perhaps; but not surprised.

    Phil
    --
    Unix is simple. It just takes a genius to understand its simplicity
    -- Dennis Ritchie (1941-2011), Unix Co-Creator
    Phil Carmody, Oct 25, 2011
    #12
  13. On 24-Oct-11 17:53, Edward A. Falk wrote:
    > These questions are asked to test to see if you can work out problems
    > and to get a look into your thought process. In my experience, the
    > interviewer will generally coax you along rather than force you to
    > flounder if you don't get it right away. Of course, if you *do*
    > get it right away, that's even better.


    I use similar questions. The purpose is to learn how they go about
    _finding_ the answer; if they get it "right away", I learn nothing and
    have to come up with a harder one. OTOH, I don't hold it against them
    if they don't get the solution in the allotted time, even with liberal
    hints. The only way to _fail_ the question is to give up. Incorrect
    answers are fine as long as the reasoning behind them is sound.

    S

    --
    Stephen Sprunk "God does not play dice." --Albert Einstein
    CCIE #3723 "God is an inveterate gambler, and He throws the
    K5SSS dice at every possible opportunity." --Stephen Hawking
    Stephen Sprunk, Oct 25, 2011
    #13
  14. On Oct 23, 2:39 am, divya bisht <> wrote:
    > Hardest Google Interview Question
    >
    > http://hardest-puzzle.blogspot.com/2011/10/google-interview-question....


    The answer is a minimum of 2 drops, maximum of 50 drops. If there
    exists a floor that will crack an egg(there is the exceptional case
    where a floor may not exist), then both eggs will need to be cracked
    to find the floor. The average amount of drops is a summation of the
    binary search method, switching to an incremental linear search
    starting from the least floor in the most recent binary search area.
    northerntechie, Oct 25, 2011
    #14
  15. On Oct 25, 4:34 pm, northerntechie <> wrote:
    >
    > The answer is a minimum of 2 drops, maximum of 50 drops. If there
    > exists a floor that will crack an egg(there is the exceptional case
    > where a floor may not exist), then both eggs will need to be cracked
    > to find the floor.  The average amount of drops is a summation of the
    > binary search method, switching to an incremental linear search
    > starting from the least floor in the most recent binary search area.
    >

    No, this is wrong.

    By dropping the egg from floor 10, floor 20, and so, we can find the
    block of ten floors on which it breaks. If it breaks, say, on floor 30
    we know it didn't break on floor 20. So we try floor 21, floor 22, and
    so on with the second egg. If the second egg doesn't crack on floor
    29, we know the answer must be floor 30, and in this rare situation we
    save an egg.
    The first part of the problem is to get the general strategy. The next
    part is to find the sequence of floors which give the result in the
    fewest possible drops. If you assume that the prior probability is
    evenly distributed between floors 1 to 100, there is a solution.
    --
    Visit my website, lots of C programming resources
    http://www.malcolmmclean.site11.com/www
    Malcolm McLean, Oct 25, 2011
    #15
  16. divya bisht

    James Kuyper Guest

    On 10/25/2011 11:12 AM, Malcolm McLean wrote:
    > On Oct 25, 4:34 pm, northerntechie <> wrote:
    >>
    >> The answer is a minimum of 2 drops, maximum of 50 drops. If there
    >> exists a floor that will crack an egg(there is the exceptional case
    >> where a floor may not exist), then both eggs will need to be cracked
    >> to find the floor. The average amount of drops is a summation of the
    >> binary search method, switching to an incremental linear search
    >> starting from the least floor in the most recent binary search area.
    >>

    > No, this is wrong.
    >
    > By dropping the egg from floor 10, floor 20, and so, we can find the
    > block of ten floors on which it breaks. If it breaks, say, on floor 30
    > we know it didn't break on floor 20. So we try floor 21, floor 22, and
    > so on with the second egg. If the second egg doesn't crack on floor
    > 29, we know the answer must be floor 30, and in this rare situation we
    > save an egg.
    > The first part of the problem is to get the general strategy. The next
    > part is to find the sequence of floors which give the result in the
    > fewest possible drops. If you assume that the prior probability is
    > evenly distributed between floors 1 to 100, there is a solution.


    A better solution has already been posted at
    <http://hardest-puzzle.blogspot.com/2011/10/google-interview-question.html>,
    with a citation of an online source analyzing why it's the optimal solution.
    James Kuyper, Oct 25, 2011
    #16
  17. In article <j85q1v$sfc$>,
    Mark Bluemel <> wrote:
    >
    >I never follow blogspot links, I understood them to be basically bait
    >for click farming.


    Google finally cracked down on it a year or so ago; now most of
    the blogspot blogs are legitimate. AFAIK, that is.

    --
    -Ed Falk,
    http://thespamdiaries.blogspot.com/
    Edward A. Falk, Oct 25, 2011
    #17
  18. In article <j86dru$k7k$>,
    Stephen Sprunk <> wrote:
    >
    >I use similar questions. The purpose is to learn how they go about
    >_finding_ the answer; if they get it "right away", I learn nothing and
    >have to come up with a harder one. OTOH, I don't hold it against them
    >if they don't get the solution in the allotted time, even with liberal
    >hints. The only way to _fail_ the question is to give up. Incorrect
    >answers are fine as long as the reasoning behind them is sound.


    Yes, well said. Plus, if they get it right away, then you have to suspect
    they already know it. Failure to 'fess up and say "I've seen this one before"
    is a huge no-no in an interview.

    When they interviewed me, I got two puzzles I'd already heard before. My
    answer both times was "Well, that sounds like a case of X, which you
    traditionally solve by Y, but here's a solution maybe you haven't
    heard before..."

    --
    -Ed Falk,
    http://thespamdiaries.blogspot.com/
    Edward A. Falk, Oct 25, 2011
    #18
  19. divya bisht

    Seebs Guest

    On 2011-10-25, Stephen Sprunk <> wrote:
    > I use similar questions. The purpose is to learn how they go about
    > _finding_ the answer; if they get it "right away", I learn nothing and
    > have to come up with a harder one. OTOH, I don't hold it against them
    > if they don't get the solution in the allotted time, even with liberal
    > hints. The only way to _fail_ the question is to give up. Incorrect
    > answers are fine as long as the reasoning behind them is sound.


    I am spectacularly good at coming up with answers in which I solve the hard
    part fast enough that it's not obvious that I didn't know it already, and
    then get the easy part wrong.

    When I was a kid, they attempted to give me an IQ test. They got to the
    famous "5-quart and 3-quart jugs, get exactly 2 quarts" puzzle. I
    walked through things like "here is how I can measure the heights of the
    jars and subdivide them", stuff like that. They kept having to add
    qualifiers.

    Finally, the guy gave up and told me the official answer. I stared blankly
    for a few seconds, then said "oh, you can do anything from one to eight
    that way. neat!"

    I still have no clue whether they scored that as success or failure. :)

    -s
    --
    Copyright 2011, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
    Seebs, Oct 26, 2011
    #19
  20. On 25-Oct-11 19:00, Seebs wrote:
    > On 2011-10-25, Stephen Sprunk <> wrote:
    >> I use similar questions. The purpose is to learn how they go about
    >> _finding_ the answer; if they get it "right away", I learn nothing and
    >> have to come up with a harder one. OTOH, I don't hold it against them
    >> if they don't get the solution in the allotted time, even with liberal
    >> hints. The only way to _fail_ the question is to give up. Incorrect
    >> answers are fine as long as the reasoning behind them is sound.

    >
    > I am spectacularly good at coming up with answers in which I solve the hard
    > part fast enough that it's not obvious that I didn't know it already, and
    > then get the easy part wrong.
    >
    > When I was a kid, they attempted to give me an IQ test. They got to the
    > famous "5-quart and 3-quart jugs, get exactly 2 quarts" puzzle. I
    > walked through things like "here is how I can measure the heights of the
    > jars and subdivide them", stuff like that. They kept having to add
    > qualifiers.


    That reminds me of this urban legend:
    http://www.snopes.com/college/exam/barometer.asp

    > I still have no clue whether they scored that as success or failure.


    The IQ tests I remember from my childhood were timed multiple-choice
    tests (points added for correct answers but points deducted for each
    second elapsed) and therefore completely objective, though one could
    debate their accuracy given the problems some kids have taking tests.

    S

    --
    Stephen Sprunk "God does not play dice." --Albert Einstein
    CCIE #3723 "God is an inveterate gambler, and He throws the
    K5SSS dice at every possible opportunity." --Stephen Hawking
    Stephen Sprunk, Oct 26, 2011
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Lighter
    Replies:
    15
    Views:
    571
  2. dorayme
    Replies:
    12
    Views:
    664
    dorayme
    Aug 15, 2007
  3. Ramon F Herrera
    Replies:
    0
    Views:
    345
    Ramon F Herrera
    Oct 2, 2007
  4. Replies:
    7
    Views:
    1,144
    Thomas Stanka
    Jan 20, 2008
  5. Helmut Jarausch

    python3 - the hardest hello world ever ?

    Helmut Jarausch, Oct 14, 2008, in forum: Python
    Replies:
    23
    Views:
    809
Loading...

Share This Page