it面试题去哪刷（烧脑的科技公司面试题）

据说是某科技公司面试题：1000个瓶子，其中只有1瓶是毒药，其他都是水，外观无法区别，现在有10只小白鼠和无限多干净试管，怎样找出那瓶毒药。

（一）

最直接的办法，挨个试。但是问题呢，很明显，就是效率低下。因为你不能连续喂，需要观察时间，要不然不成了于谦吃蘑菇了...

假定每次喂水间隔半小时观察时间，每次可以试10个，最好的结果是第一次就试出来了，最差的结果就是第100次才试出来，期望就是50次，需要25小时，啥也不干，4天的时间，效率非常底下。

（二）

有人说，这题就是二进制的问题。正好10只小白鼠，2的10次方等于1024，大于1000，刚刚好能解出。此解法的核心思路就是分组。

我们推演一下，第一次，1000瓶子平均分为两组，每组的500瓶每瓶取一滴混合，喂小白鼠，小白鼠中毒，看是否中毒；第二次，把500再平均分为两组，重复以上操作；第三次分每组125，第四次分向上取整63，第五次分向上取整32，第六次16，第七次8，第八次4，第九次2，第十次，2选1，完美！

是真完美了吗？不见得吧！存在的问题，还是效率！10次需要5个小时，而且小白鼠全军覆没，消耗高！

（三）

如何才能提高效率呢？我先分析一下二进制的问题，最大的缺陷就是，每次只试验一组，是一维的，扩展维度是不是就可以有效提高效率了？那么维度扩展到多少？对，小白鼠有10只，那就扩展到10维。

推演一下。第一步，分10组每组100个，每瓶取一滴混合，喂小白鼠，筛选出1组100瓶；第二步，100瓶分为9组，筛选出1组向上取整12瓶；第三步，12瓶分8组，筛选出1组向上取整2瓶，第四步，筛选出毒药。

只需要4步4只小白鼠，完美！

（四）

真完美了吗？有人说，上面第三种方法还可以优化一下。第二步不能整分，我们可以整分为10组，9只小白鼠去试其中9组，能试到最好，如果小白鼠都没中毒，说明没试那组有问题！逻辑很严密，perfect！第三步，10瓶分8组筛选出1组向上取整还是2瓶，虽然还得需要第四步，但是，我们仔细分析一下，还是有八成以上的概率在三步之内完成！

（五）

完美了吗？三步完成的概率能不能再提高？

从上面的优化我们看到，维度还可以再扩展！就是优化关键的第一步，从原来的10维扩展为11维，逻辑上没问题，perfect！

推演一下。第一步，1000瓶分为11组筛选出一组向上取整为91瓶；第二步，91瓶分10组，这一步需要展开分析，9组9瓶，1组10瓶，9只小白鼠试验9瓶的9组，如果中毒，则第三步9瓶8只小白鼠；如果没中毒，那么第三步是剩余的一组10瓶9只小白鼠，可见第三步一定能完成确认！

真完美了吗？没有！因为考虑概率的的影响后，我们不一定非得等分，实际上我可以适当减小需要喂小白鼠的样本组的样本数量，例如上面第一步，我们分成90瓶10组和100瓶1组，这样分组的结果就是，小白鼠中毒，那么下一步是9只小白鼠验证90瓶子，如果没有中毒，那么下一步是10只小白鼠验证100瓶子，这种优化在样本空间增大时效果才能显现出来，就我们此时需求，效果不明显。

通过上面分析，经过不断的优化，方案越来越来完美，然而，这是科技公司的面试题，我们应该从代码实现的角度再看看上面的问题，随着不断优化，需要的逻辑越来越复杂，代码实现的难度反而也越来越大，纵观这五步的逻辑，第三步实现起来最简单。因此我们在编程的时候，不要一味追求完美，允许缺憾存在才是解脱，或许，世间万事亦如此吧！