Re:Google Interview Questions
by xhuang on Wednesday February 17, 2010 @07:24AM
(#1131368)
just wondering for this question("how strong is an egg"), i think binary search will be the minimum tries, so its quite useful.
[ Parent
| on HN ]
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.
For N balls, the other balls can/should be binary searched. It's just a little tricky when it comes to the last two..
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.