1000个瓶子和10个小白鼠的算法题

  算法/数据结构/数据库 计算复杂度 空间复杂度    浏览次数:627        分享
1

现在有1000个看上去一模一样的瓶子,其中999瓶里装的是水,1瓶是毒药,只要喝下一滴,就会在一个星期之后死亡。

现在给你10只小白鼠和一星期的时间,如何检测出哪个瓶子装的是毒药?

一道面试,求解答,谢谢各位了!

 

古力夬   2019-07-28 14:09



   1个回答 
9

这是道编码题,而且$2^{10}=1024$,会想到二进制编码。先瓶子编号向量$X$为00_0000_0000到11_1110_0111。老鼠喝水操作的矩阵$A$,第一行$A_{1*}=$10_0000_0000,表示一号老鼠喝所有$X=$1x_xxxx_xxxx的水,x表示0和1都喝。$Y_1=A_{1*}X$用于标志从左到右的$X$第一位是0或1。第二行$A_{2*}=$01_0000_0000,表示一号老鼠喝所有$X=$x1_xxxx_xxxx的水。以此类推。

老鼠死掉的编码$Y$就是毒药瓶子的编码,因为$A=I$。比如0号瓶是毒药,$Y$=00_0000_0000;如果1号瓶是毒药,$Y$=00_0000_0001。1代表老鼠死掉。每个瓶子对应唯一的$Y$。

$Y=AX$

进一步,只要$A$是正交基,$X$通过$A$投影,有唯一$Y$对应。

SofaSofa数据科学社区DS面试题库 DS面经

Zealing   2019-07-28 17:37

厉害啊,很精妙 - zzzz   2019-07-30 22:14
多谢多谢,我感觉到是用二进制,但是没想到具体怎么对应 - 古力夬   2019-08-14 14:30


  相关主题

NP-hard是什么意思   1回答

beam search是什么意思?   1回答

在python中获取模型运行的时间   3回答

sql查询时count(*)、count(1)、count()哪个更快?   1回答

kNN进行预测时计算复杂度是多少?   1回答

朴素贝叶斯的训练/预测效率如何?快吗?   1回答

python中怎么获取cpu的个数?   1回答

python中如何合并两个dict   2回答

python中怎么对一组逻辑变量求“或”?   1回答

怎么在python中复制指定路径下的文件?   1回答

python中defaultdict的用法   2回答

python的set进行append操作?   2回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!