Hardest Google Interview Question

[Seebs]

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.

It's possible that this was one of the other tests; they did a ton of
different tests. At least one, the guy giving the test could answer
questions, and for instance, one of the quests involved a baseball diamond,
and I had no clue what it was.

Apparently, a memorable highlight of the testing process was the point at
which I commented that he was looking the answers up, meaning that he didn't
know them either.

-s

 

[Seebs]

By now, I suppose everyone who cares knows and understands the
intended solution. The question I have is: Is there a practical use
for this class of algorithm? We have all manner of examples of
O(log(n)) algorithms, e.g. binary search. However what about
O(sqrt(n)) algorithms? Are there applications that use the same kind
of reasoning that is used in the 2-egg puzzle?

Interesting question. I think no, because in general you don't have a hard
cap of N failed tests allowed. Usually, tests don't care whether they're
"positive" or "negative", but maybe there are to be exceptions later.

-s

 

[Sjouke Burry]

I never follow blogspot links, I understood them to be basically bait
for click farming.

Hear, hear!!!.nl

 

[Richard Damon]

Interesting question. I think no, because in general you don't have a hard
cap of N failed tests allowed. Usually, tests don't care whether they're
"positive" or "negative", but maybe there are to be exceptions later.

-s

I can certainly see cases where the test tends to go one way fairly
fast, but to prove that it isn't going to go that way can take a long
time, because you can guess a solution which works most of the time, but
to prove there isn't one could take a lot of exhaustive searching. To
find the first point where there isn't a solution could involve
something similar to this.

There are also situations where your testing something, and failure will
be expensive, so management is giving you a limited budget for how many
failures, but you also don't have time for a linear search to find the
failure point.