D
divya bisht
Hardest Google Interview Question
http://hardest-puzzle.blogspot.com/2011/10/google-interview-question.html
http://hardest-puzzle.blogspot.com/2011/10/google-interview-question.html
M
Malcolm McLean
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.
W
Willem
Malcolm McLean 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
)> 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
M
Malcolm McLean
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.
W
Willem
Malcolm McLean wrote:
)> Malcolm McLean 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
)> Malcolm McLean 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
R
Richard Damon
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.
J
James Kuyper
On 10/24/2011 01:23 PM, christian.bau wrote:
....
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.
....
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.
E
Edward A. Falk
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.
Question specifies that it could break anywhere from the first
to the last floor.
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.
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.
Question specifies that it could break anywhere from the first
to the last floor.
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.
A
arnuld
My best guess, interviewer is trying to check guy's algorithmic analysis
skills
B
Bill Reid
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...
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)?
M
Mark Bluemel
I never follow blogspot links, I understood them to be basically bait
for click farming.
for click farming.
P
Phil Carmody
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.)
Yup, definitely underspecified.
Perhaps; but not surprised.
Phil
S
Stephen Sprunk
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
N
northerntechie
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.
M
Malcolm McLean
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.
J
James Kuyper
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.
E
Edward A. Falk
Google finally cracked down on it a year or so ago; now most of
the blogspot blogs are legitimate. AFAIK, that is.
E
Edward A. Falk
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..."
S
Seebs
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
S
Stephen Sprunk
That reminds me of this urban legend:
http://www.snopes.com/college/exam/barometer.asp
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