Google Interview Questions

Re:Google Interview Questions by RiderOfGiraffes on Wednesday February 17, 2010 @08:21AM (#1131441)

That turns out not to be the case. Binary search doesn't help, binary doubling doesn't help, even though these are often thought to be the best. Indeed, the solution given on this site used binary doubling and claimed it to be optimal. It was wrong. It was posted here some time ago.

The solution, once found, is simple to prove optimal, but most people don't seem to know how to do that.

Most people don't find it.

[ Parent | on HN ]

Re:Google Interview Questions by OmniLarry on Wednesday February 17, 2010 @09:43AM (#1131583)

For N balls, the other balls can/should be binary searched. It's just a little tricky when it comes to the last two..

[ Parent | on HN ]

Re:Google Interview Questions by RiderOfGiraffes on Wednesday February 17, 2010 @10:14AM (#1131635)

  > For N balls, the other balls can/should be binary searched.

Interesting assertion. Can you prove that? Can you give a provably minimal search pattern?

  > It's just a little tricky when it comes to the last two.

Another interesting assertion. It seems to me that the case of exactly two balls is trivial, once the solution is found.

[ Parent | on HN ]

Re:Google Interview Questions by OmniLarry on Wednesday February 17, 2010 @11:22AM (#1131782)

Sorry, can't find the link, but it was a Topcoder problem at least 5 years ago.

Well, it is trivial with two balls, once you get it, but it's tricky with respect to "just binary search".

[ Parent | on HN ]