微软面试题:现有10只小白鼠和无限多的干净试管,怎么在1000个瓶子里找出1瓶毒药?

微软面试题:现有10只小白鼠和无限多的干净试管,怎么在1000个瓶子里找出1瓶毒药?

有1000个瓶子,其中999瓶是水,1瓶是毒药,外观无法区别。现有10只小白鼠和无限多的干净试管,你怎么找出那瓶毒药?

6f49ad51ly1gyfwmpcb7xj20e30m83zf.jpg

最近 | 62.8K人阅读
回答 | 24
默认排序
  • 按时间排序
  • 默认排序
  • 1000分10组,每组100个试管混合,然后分别喂10个小白鼠

    被毒死的那一组,100个再分10组,每组10个,分别喂给剩下的9只

    如果都没事,那就是最后一组有毒,如果毒死了,那就是毒死那组

    这个时候就只剩下10个试管需要确认了,还剩8或者9只老鼠

    直接挨个灌吧,懒得分组了,毒死了就确认了,毒不死就是剩下的那个

    28赞同
    2 收藏 8 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
    • 纯路人 | 最近
      回复
      不如1000瓶水 放一点点装1000个试管 让一个小白鼠喝1000次 其它小白鼠在旁边感恩
    • 小猪 | 最近
      回复
      回复 @鸡米太美 : 测试3次就可以出结果,你测试1000次,面试怎么过
    • 纯路人 | 最近
      回复
      也没限制测试次数吧
    • 产品新人成长中~ | 最近
      回复
      回复 @鸡米太美 : 你这方法太笨了...哈哈哈哈
    • 汪仔5965 | 最近
      回复
      回复 @鸡米太美 : 是没有限制,但是用人单位肯定选一个更聪明的人啊
    • 纯路人 | 最近
      回复
      回复 @不会秃头的烁子 : 格局小了 如何定义什么是聪明方法什么是笨方法?/滑稽
    • 最光阴 | 最近
      回复
      回复 @纯路人 : 你这个方法好
    • 汪仔7208 | 最近
      回复
      回复 @小猪 : 被毒死的组你试管都混合了100再分多少组不都是有毒的吗?9





  • 我自己喝,小老鼠不死,试管也不用,最大化节省公司财产。

    29赞同
    收藏 5 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
    • iced tea | 最近
      回复
      死*狗,我好喜欢~
    • 暴打椰椰 | 最近
      回复
      呲溜呲溜
    • 摇阿摇 | 最近
      回复
      哈哈哈哈哈哈哈哈哈哈哈哈哈哈笑不活了
    • 大乔 | 最近
      回复
      哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
    • Aiden | 最近
      回复
      回复 @暴打椰椰 : 哈哈哈哈哈哈哈
  • 看到题目,工程师们立刻开始研究算法,怎么解题,这很好。

    然而如果是产品经理的话就不能只为了解题,还要明白问题背后的含义,目的,就本题而言,既然确定了毒药在1000瓶水之间,那么必然有确定这个的依据,请问是谁,通过什么方法判定的?是不是投毒者?如果有判定依据可不可以继续缩小范围?费这个力找出毒药的目的是什么,为了让剩下的999瓶水重回市场吗?怎么确认不会有其它问题?为了产品的安全性以及口碑,可以建议,不用找,直接无害化处理这剩下的1000瓶水,将责任人移交公安机关。

    16赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 没有时间限制,也没有实验次数限制,难道就是为了考验面试者对问题条件的分析能力和思维拓展的广度?不明白。。。

    最少实验次数的话,我选择让小白鼠先繁殖,养着呗,养到1000只,再找1000个人,大家一起测,一次实验出结果。

    最少时间的话,分10组,每组1个人、1只小白鼠,同时依次喂水,直到一组小白鼠死了。

    最省人,最省小白鼠的话,一个人拿着1只小白鼠依次滴喂这1000瓶水。

    干净的试管就是干扰项,每只小白鼠可以重复饮水。

    5赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 以下为百度搜索


    ①决策树法:    可能有人觉得,这多简单啊,用0.2秒联想一下卡诺图(或者3-8译码器),打个响指,答案不就出来了吗?但是我想说,这是需要天才的。可我认为好的解题思路,是不需要天才便可解答的思路。换句话说,依赖于天才的解题方法不是个好的方法。再者,即便对于天才,我想剥清那灵机一闪的背后,意识的水面下庞大的无意识洪流,是以什么为根据运行的。再延伸下去就要到很多大师都谈到过的知识与灵感的大问题了,不展开了。说得简单点,我想回答的是,我没想到这个方法,凭什么他就想到。现在就来谈谈这个凭什么。    首先,题目做了个巧妙的障眼,把1024改成1000。但根据经验,还是不难想到,要用这么少的老鼠分出这么大的任务量,肯定有指数爆炸的功劳。或者说,把问题对数分解。从而不难想到2^10=1024这个数量关系。为了问题更容易理解,不妨把问题做一个变形:    问题2:把原问题中的1000个瓶子改成8个瓶子,10只老鼠改成3只老鼠。其它一样。这样,问题2肯定有了个解法。下面的问题是,这背后的数量关系的本质是什么?按照职业和个人知识背景的不同,不同的人可能有不同的联想。如果你学过算法,不难从原问题的2^10=1024数量关系中想到二分查找算法思想。问题是这里只有单步(一个单位时间,或一个指令周期)计算时间。没错,老鼠负责做测试,就是一个处理机,符合计算的本质。于是,为了问题易于理解,不妨进一步做一次变形:    问题3:把问题2中的3只老鼠改成1只老鼠,但是老鼠有3条命,并且时间限制从一个星期改成3个星期。其它一样。于是,成了一个典型的二分查找问题,2^10=1024这个数量关系依然适用。这是按照程序员的思维走到二分查找的。但如果你不是程序员呢?或者说,自然而然想到变换到二分查找,这和一步联想卡诺图(或3-8译码器)有什么区别呢?更甚,二分查找的本质又是什么?为什么不是三分?首先,因为老鼠只能通过活蹦乱跳,或死翘翘,来报出编码为0或1的实验结果,所以查找中的“二分”,可以说是直接的。再者,为什么不是三分?    二分的本质在于,每次处理,都把问题规模降解为原来的1/2,这才是问题得以解决的关键!为何不是1/3?    杨振宁说:“对称支配宇宙力量。”有一本科普书叫《可畏的对称》。有一种世界通行的说法叫“一枚硬币的两面”。有一种学说叫辩证法。再说,连阴阳和谐都要出来了,打住。暂时还不用这么玄乎。    为什么不是1/3?因为如果是1/3,那么在老鼠给出0或1的不同答案的时候,你如果幸运,就是把问题规模降为了1/3;如果不幸,就只降为了2/3。我们说,依赖于运气的方法不是足够理想的方法。如果可以依赖于幸运,那你为何不说原题的解法,靠纯蒙就能做到?在命运之神的全力狙击下,依然肯定能按期交付的方法,才是可控的方法,才是够理想的方法。如果你学过算法,可以知道这也是一种叫“随机化算法思想”的奥妙。而且和算法研究中,关注于“最坏情况运行时间”的研究原则一致。所以二分。    那么在二分查找的背后,又是怎样的规律?基于测试(比较)的查找背后,是决策树模型。如图:    二分查找是以时间迭代来下降到决策树的叶子;而在这里的原题中只有单步的运行时间,却有多个处理机,明显是以空间迭代的方式下降到决策树的叶子。学过算法的又要说“Aha”了,“时间换空间,或者空间换时间”。事实上,这也是并行计算的思想。可以把这个看作是二分查找的并行实现。如果你一开始想到的是逻辑门电路,那么我想提醒数字电路的运行方式就是并行的。数字电路某种程度上就是并行机。同时,这也是“量子计算机无法完成算法之外的任务,却可以把串行算法,并行地实现”的真谛所在。现在,问题2中,三只老鼠同时单步内吐出0或1的答案。解的组合便是2^3=8,正好解决问题。剩下的便是编码了。0或1各代表什么可以自定。因为只有0或1,二进制编码是自然的,也是直接的。吐出0或1的是老鼠,所以明显老鼠对应于一个二进制位(或称一个bit处理单元)。3只老鼠,3个二进制位。老鼠从低位到高位,编码为:0, 1, 2。3位二进制数够简单,所以先把所有数枚举出来再说:000=0001=1010=2011=3100=4101=5110=6111=7    然后我实在抑制不住直接下一步跳入3-8译码电路类比的冲动。但是我们再来问几个为什么。注意到每个位,0和1各占一半(这也是自然,穷举了3位二进制数嘛),这和为了均等吐出0和1的可能性,需要的对老鼠的输入是一致的。(先烂尾到这里,未完待续)    总之,10只老鼠就像10根地址线,可以寻址1024个瓶子(内存单元)。至于理由根据,笔者也暂时不清。笔者也无暇查看编址译址电路的早期思想萌芽,产生于哪些论文中。笔者也隐约觉得应用信息熵的理论, 就可以理想地、“无需想象力”地、坚实地,一步解决。但其实信息熵的理论是什么样的,我也不太清楚,只是猜想。你问我为什么不去学信息熵?也是因为懒啊。 


    ②网图法    从1000个瓶子跟10个老鼠这里直觉就是会跟2的10次方有关系    也学是学计算机的对二进制比较熟悉吧联想到要用10这个数字来构造1000种可能而 2的10次方=1024>1000,而且每条老鼠的结果就两种可能被毒死而没被毒死    这个问题就把十个老鼠当作十个二进制的位,十位二进制能表示的数字个数是1024个,所以即使瓶子数量是1024也是可以找出来结果的,具体办法就是把一千个瓶子标上序号(先拿出来一瓶,剩下的瓶子从1开始编号),假设 是编号为n的有毒 比如n是 512那么 写成二进制就是1000000000,现在让你找这个序号是多少,相当于让你确定这个十位的二进制数每一位的数字是什么,so 我们先来确定第一位,我们使用正向确定法,就是确定这位是不是1(反向推测就是确定这位是不是0),怎么确定呢,我们先找到这一位是1的所有的数值,然后把这些数值对应的瓶子里面的液体取出来混合,让第一个老鼠喝掉,然后第二位,第三位.....依次类推到最后一位。最后十个老鼠都喝了512个瓶子的液体,一周后,哪个老鼠死了那一位就是1,得到一个十位的二进制数字,转换成十进制就搞定了,比如我们之前举的例子是编号512这瓶,那么肯定就是只有第一个老鼠死了,得到结果是1000000000 


    ③数学归纳法备注:跟题解无关,不过证明了2^n次方之所以产生结果的严密数学论证    问题可以描述为:有2的n次方个瓶子和n只老鼠,瓶子里装的是水,有一个瓶子的水有毒,老鼠喝了后第7天会死,那么在第7天能识别出这瓶毒药吗?证明:    当n=1时,把其中一个瓶子的水给老鼠喝第7天能识别出毒药。假设当n=k时,第7天也能识别这瓶毒药。    当n=k+1时,假设瓶子的编号为1,2,3 ...直到 2的(k+1)次方。    将每两个瓶子分为一组,刚好可分为2的k次方个组(其中编号为 i 的瓶子和编号为 (2的k次方)+i 的瓶子是一组)。那么用k只老鼠第7天就能确定是那一组瓶子里有毒药。假设最后结果是第m组有毒(即编号为 m 和 (2的k次方)+m 的两个瓶子)。同时将编号从 2的k次方+1 到 2的(k+1)次方 的瓶子(共2的k次方个瓶子)的水给第 k+1只老鼠喝。(关键步骤)如果第7天第k+1只老鼠没死,可以得知毒药在编号为 1 到 2的k次方 的瓶子中,由此可知是编号为m的瓶子有毒。如果第7天第k+1只老鼠死了,可以得知毒药在编号为 2的k次方+1 到 2的(k+1)次方 的瓶子中,由此可知是编号为 (2的k次方)+m 的瓶子有毒。因此n为自然数时,都能识别出这瓶毒药。 


    ④化学法备注:此想法因时间限制,不对,不过想法独特       取每100瓶药水滴少许进1个瓶子,得10瓶混合药水分给10只老鼠,1只老鼠死;再将死老鼠这100瓶平均分成10组,取每10瓶药水滴少许进1个瓶子,得10瓶混合药水,其中9瓶给9只老鼠喝,能得到混有毒药的10瓶药水;然后这10瓶平均分成5组,取每2瓶药水滴少许进1个瓶子,得5瓶混合药水,分给5只老鼠喝,1只老鼠死,得到混有毒药的2瓶药水;再取出给2只老鼠喝,得到毒药。

    4赞同
    1 收藏 2 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
    • 㵘山遍野 | 最近
      回复
      我竟然一个都没看懂。。。。
    • 运营狂想家 | 最近
      回复
      这面试题,一定是出给程序员看的
  • 有三种方式:

    第一种:分组法,将1000瓶分10组,每组的100瓶取样放到同一个试管里,测试9组数据(只需要9只小白鼠,不需要10只),就可判断出有毒的那一组,再将100瓶分成10组,每组的10瓶取样放到同一个试管里,测试9组数据,就可以判断出有毒的那一组还剩10瓶,用同一只小鼠测试就好,最好的情况时小鼠一只不死,最差的情况时死三只;

    第二种:中分法,将1000瓶分2组,每组的500瓶取样放到同一个试管里,并喂一只小鼠,小鼠若死亡,则表示在该组中,再将500瓶分2组,每组250瓶取样放到同一个试管里,并喂一只小鼠,接着时125瓶,一组62,一组63,如此重复;最好的情况是小鼠一只不死,最差的情况是死9只

    第三种:一瓶一瓶的喂,死一只老鼠;

    还有一种是取巧的方式:将1000瓶液体倒在一个瓶子中,这瓶液体就是有毒的,小鼠一只不死


    4赞同
    收藏 5 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
    • linken | 最近
      回复
      第三种牛逼
    • 自来卷夏忆 | 最近
      回复
      从喝下药到毒发需要一段时间,这也是对照组存在的意义
    • Jose Wong | 最近
      回复
      老鼠表示:来不了了,再喝就多了,今天就到这吧。
    • 汪仔1370 | 最近
      回复
      有没有想过 小白鼠喝不下这么多水
    • Aiden | 最近
      回复
      回复 @Jose Wong : 哈哈哈哈哈哈哈
  • 1000对半分两个500个,全部放在在一个试管里,一只小白鼠测试,如果中毒则判断毒瓶在这500个里面,如果没中毒,就是在另外500个里面,以此类推,250个消耗一个小白鼠,或者不消耗,125又一次,62一次……最后能筛选到2个,10只小白鼠差不多够用了。

    3赞同
    收藏 2 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
    • 大鱼炖海棠 | 最近
      回复
      2^10=1024>1000,运气不好的话,10只小鼠刚刚够用,不过倒是省试管。
    • 阿么日记 | 最近
      回复
      果然大学生就是不一样,我都不会用公式的。
  • 我只有一个想法,小白鼠也是珍贵的生命,作为微软这样的企业,基本的社会责任感和正确的价值观是必备的,毒药我会全部倒掉,再把小白鼠放生,无限多的干净试管捐赠给医院或者研发机构。

    如果你们不认同我的做法,我也不屑在这样的企业就职。

    2赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 1000瓶分10组,每组的10瓶取样放到同一个试管里,并喂小鼠。

    毙鼠的那一组重复以上操作,直至筛选出来毒药。

    一共消耗试管30支,毙鼠3只,运气最烂的情况下需要喂鼠30次。

    2赞同
    收藏 3 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
    • 菠萝包同学 | 最近
      回复
      回复 @大鱼炖海棠 : 每组取样10瓶,要是没取到毒药咋办哈哈
    • 大鱼炖海棠 | 最近
      回复
      补充一个网上看到的类似的题目,大体条件一致,但多了条件“中毒的老鼠1h后才会被毒死,求最快的方法找出毒瓶”。

      这种情况肯定不能用我的法子。但是也有办法:
      将瓶子编号1~1000并转换成二进制(数位有10个)。
      将10只小鼠对应10个数位。
      将每个数位是1的瓶子取样品混合,喂给对应数位的小鼠。1h记录小鼠的状态,毒死则记录1,生还则记录0。
      把所有小鼠的状态对应的二进制数转换成十进制,即可找到毒瓶。

      共消耗试管10只,喂鼠10次,毙鼠最少1只,最多6只。
    • 大鱼炖海棠 | 最近
      回复
      回复 @菠萝包同学 : 总有一组是取到了毒药。没取到毒药的组说明小鼠在本轮命不该绝,可喜可贺,应该结一个婚以示冲喜。
  • 是什么岗位要面试这道题呢?
        如果是产品经理/助理岗位,面试官可能想考察需求分析能力
        如果是程序员岗位,面试官可能想考察逻辑能力
    .................

    1赞同
    收藏 1 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 首先,2的十次方是1024,所以肯定可以找到的。
    1000对半砍,500装一管,
    一喝就知道,毒药在哪半,

    500对半砍,125装一管,
    同理可知道,毒药在哪半,

    此理做循环,十次出答案。
    1赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 把1000个瓶子倒到一个盆里,处理了,这样岂不是还省一只小白鼠

    1赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 这问题不完整
    1、瓶子液体数量:是不是带滴管的瓶子?瓶子液体数量能最小化取多少次?

    2、毒效:老鼠如何中毒(喂食/注射)?多少浓度才中毒?毒药起效时间要多长?中毒的表现是什么?

    1赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 题目太简单了,应该换成干系人可能为了逃避责任说了谎,毒药数量为1到10瓶,如何确定那些是毒药。

    赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近

    • 1000个瓶子,其中有1瓶毒药。

    • 10只小白鼠可用于测试。

    • 目标是找出含有毒药的那一瓶。

    1. 问题转换:我们可以将这个问题看作是二进制编码问题。给每个瓶子编号,从0到999(总共1000个)。每个编号都可以转换为二进制数,最多需要10位(因为2^10 = 1024 > 1000)。例如,瓶子编号999可以转换为二进制数1111100111。

    2. 小白鼠与二进制位对应:我们可以使用10只小白鼠,每只对应二进制编号中的一位。每只小白鼠将喝下所有在其代表的二进制位上为1的瓶子中的液体。例如,小白鼠1将喝下所有二进制编号第1位为1的瓶子中的液体,小白鼠2将喝下所有二进制编号第2位为1的瓶子中的液体,以此类推。

    3. 实验结果分析:

    • 若某只小白鼠死亡,说明它喝下的液体中含有毒药,即毒药瓶的二进制编号在该小白鼠对应的位置上必定是1。

    • 若小白鼠存活,说明它没喝到毒药,毒药瓶的二进制编号在该小白鼠对应的位置上必定是0。

    1. 确定毒药瓶:通过组合10只小白鼠的实验结果,我们可以得到一个10位的二进制数,这个二进制数转换为十进制后,就是含有毒药的瓶子的编号。


    赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 这就是量化和拆解,确认问题的过程,先对样本进行细分,找到问题,再进行二次分解,,细化直到找到问题。但实际业务中并不会这样。
    赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 说他骗人,打乱试管,让他找

    赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 讲真的,人家这题目一没说让你用最快的办法,二没说让你用最秀的办法,只说要找出毒药。请注意目标是找到有毒的那瓶水。那就一瓶瓶的给老鼠喂水就行了啊。又是分组又是分析的。你这是面试还是来走秀哦。

    那些分组混合的,你怎么知道毒药稀释到何种程度会失效?如果混合失效的话,那你就找不出来有毒的,这和你要找出有毒的那一瓶是目标背离的啊。

    赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 把1000个试管分成2组,每组500个,500个在分10组,也就是50个倒在同一试管,如果老鼠没中毒则换第2组,如果老鼠中毒了,剩9只老鼠,那就在老鼠中毒的组再测试,50个试管分9组,6个试管倒入同一试管,老鼠中毒剩8只,中毒的组再用剩下的八只测试就能找到有毒的试管,最多测试4次,至少死3只老鼠就能知道答案

    赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 先是第一轮死掉的小鼠不能被replace的情况,小鼠有三种状态,第一轮死,第二轮死,和两轮都没死,那么三种状态可以类比为3进制,小鼠的量程为3^10即59049瓶,具体操作方式为对编码为2的位数,第二轮混合喂。然后是第一轮死掉的小鼠可以被replace的情况,将每1024瓶混合为1滴做第一轮,选定组别后第二轮确定瓶子编码,量程为2^10 * 2^10即1048576瓶。对不能replace的N轮,量程为(N+1)^10,能replace的N轮,量程为2^(10*N)。第二种变体,如果1000瓶里有2瓶毒药,需要多少只小鼠?1000瓶里1瓶毒药有1000种可能性,而1000瓶2瓶毒药则有C(1000,2),即499500种可能性,那么log2(499500) 为18.93,即需要19只小鼠。具体实现方式为以两两混合法将1000瓶拆成499500滴,并用题目1中的方法测得。那么对1000瓶中的N瓶毒药,则需要log2(C(1000,N))只小鼠,若N>=500,则取C(1000,1000-N)。第三种变体,有16瓶水1瓶有毒,用多少只小白鼠能测出14瓶无毒的水?将16瓶药水用二进制XXXX表示,取3只小白鼠来测,测出的状态为XXX,那么毒在XXX0或XXX1中,剩下14瓶无毒。

    赞同
    收藏 回复 分享

    微信扫码分享给好友

    or

    复制页面链接

    最近
  • 还有4个有趣回答,继续看^-^

暂时还没回答,等你发挥

发布回答,请先 登录 / 注册

面试题bot

一个没有感情,只会问面试题的bot
  • 干货文章
    优质课程
  • 行业大会
    线下沙龙
  • 热门问答
    精品专场

扫码即可下载app

内容举报

请慎重选择举报原因

垃圾广告营销

不友善内容

侮辱谩骂骚扰

淫秽色情信息

违法有害信息

涉嫌抄袭/盗用

其他

邀请回答

想要更快获得答案?试试邀请回答吧~ 今日已邀请0/5

x

问题还没有标签

给问题加标签后,可根据标签推荐更专业的用户来回答

微信扫码即可分享

确认删除

删除后将不会展示在回答列表中

你所查看的回答已被删除

你所查看的回复已被删除

沉底问题

沉底后问题将从推荐列表中移除,此为
智囊团成员特殊权限,请谨慎使用

温馨提示

问题已沉底
用户将无法在列表查看到该问题

温馨提示

沉底操作已达上限,建议联系天天问管理员
处理违规内容

操作失败

请重新尝试

©2016-2024 - 深圳聚力创想信息科技有限公司 - 粤ICP备14037330号  粤公网安备 44030502002255号

广播电视节目制作经营许可证(粤)字第03109号  增值电信业务经营许可证粤B2-20190788  版权所有 © 深圳聚力创想信息科技有限公司