我的一个 friend 在面试时被问到这个问题，当时无法解决。以为我会分享同样的东西。
There are a thousand choco-chip cookies with one of them poisoned. You have access to 10 lab rats per day. Each rat can nibble on any number of cookies and each cookie can be nibbled by any number of rats. After a rat nibbles on a poisoned cookie, it takes a day to see the after effects on the rat if it were poisoned.
优化天数。我能够在 2 天内想出一种算法来找到有毒的 cookie，尽管我相信有一种方法可以在 1 天内完成此操作
最佳答案
这是三天内“简单”的解决方案:
- 首先，让每只老鼠啃 100 block cookies 。
- 一天后，让每只老鼠啃掉 10 block 死老鼠吃过的 cookies 。
- 两天后，让每只老鼠啃食第二只死老鼠吃掉的一 block cookies 。
- 三天后，你就会知道哪个 cookies 中毒了。
现在是一天内的“硬”解决方案:
- 用二进制对所有 cookie 进行编号。
- 每只老鼠要啃食那些二进制表示在老鼠的索引中有固定位的 cookies 。例如，老鼠 1 会啃掉所有奇数编号的 cookies 。
- 换句话说， cookies 37 将被老鼠 1、3 和 6 啃食。因此，如果第二天恰好有三只老鼠死了，您就知道 cookies 37 是中毒的那只。
关于algorithm - 优化找到有毒 cookie 的天数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11488009/