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

  算法/数据结构/数据库 计算复杂度 空间复杂度    浏览次数:3189        分享
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


  相关讨论

树的inorder traversal是什么意思?

如果让你付费提问一个IT问题,你会问什么?

NP-hard是什么意思

beam search是什么意思?

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

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

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

python里list的remove和pop方法的时间复杂度是多少?

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

GMM和KMeans哪个快一点?

  随便看看

VGG16和VGG19的区别?

python sklearn模型中random_state参数的意义

python里怎么计算曼哈顿距离?

如何复制一个pandas DataFrame

怎么把pandas dataframe中一列英文文本全部转成小写?