关于作者：程序猿石头(ID: tangleithu)，从十八县贫困农村一路逆袭上清华（点这里查看我的逆袭之路），BAT某厂P7，是前大疆（无人机）技术主管。
本文首发于微信公众号，原文链接，转载请全文保留。后台回复关键字 “1024” 获取程序员大厂面试指南。
背景
大家好，我是石头哥。
估计大家都有做过核酸检测吧？我也做过好多次。
我参加到的检测流程基本是这样：
医院挂号缴费，然后排队，领个管儿，再排队，然后到“全副武装”的护士那里，用棉签捅一捅喉咙，放到你领的管儿里面。
然后等结果，完事儿……
我都是做的咽拭子，一般还有一种鼻拭子，估计会难受一点儿？（你做过么？）
这种，基本上都是一个人采样（所谓的“单采单检”），用一份核酸检测的试剂进行检查。
全员核酸
不知道你有没有参与过大规模的核算检测。
大规模核算是这样的吗？比如全员核酸？
如果，都按照“单采单检”的标准进行，成本是一回事，耗时也不少啊。
要知道在疫情的关键时刻，早一点筛查出目标，就能尽早减少扩散，多一份安全。
因此，会采用 “多人混检”的方式。
例如“十合一混检”：
即：每组10人，采集10个标本，全混入一个容器，然后统一送检。
其中只要有一位中招了，那就10人全部召回复检。
复检再回到前文提到的“单采单检”模式进行，确定10人中的哪一个（或多个）中招。
这样做，速度大大提高了。
有更好的方法吗？
不过，能否有方法能省掉上文中的复检流程呢？
在初次检测中知道某组10人中，有一人中招了，不需要再通过复检，就能确定出到底是谁中招呢？
直接就想到了这样一道面试题。
类似的场景设计题目，我多年前面试某个大厂的时候，就遇到了！
老鼠试毒
这道题目是这样的：
有8瓶药，其中只有一瓶是毒药，我们有三只老鼠，能被毒药很快毒死。请问如何设计，能尽快把毒药试出来？假设药水可以混合且不影响毒性。
这个题目比较好的解法是利用二进制思想。
如下所示，三只老鼠编号 A、B、C，0-7对应8瓶药编号：
ABC //三只老鼠编号ABC |
对应位为1，表示对应老鼠需要吃对应药水，按照如下的方案进行分配：
- 将1、3、5、7号药水混合，喂给C号老鼠；
- 将2、3、6、7号药水混合，喂给B号老鼠；
- 将4、5、6、7号药水混合，喂给A号老鼠；
老鼠喝完后，该挂的也就挂了。ABC对应挂了的标记为1，活着的标记为0，得到一个数字。
假设结果为：A、B 挂了，C 活着，即为110=6，就得到6号药水有毒。
充分必要性证明
110=6 不假，但 A、B 挂了，C 活着，就能得到6号药水有毒？？
确实是的！
回到前面的混合方案：
- 将1、3、5、7号药水混合，喂给C号老鼠；
- 将2、3、6、7号药水混合，喂给B号老鼠；
- 将4、5、6、7号药水混合，喂给A号老鼠；
6号有毒，确实能正向推导结果：C活着，A、B 挂了。
反过来呢？
C活着，必然1、3、5、7号药水无毒。即相当于：
- 将2、6号药水混合，喂给B号老鼠，挂了！
- 将4、6号药水混合，喂给A号老鼠，挂了！
又因为只有 1 瓶有毒：
- 假设2号有毒的话，那4、6无毒，A 死不了。
- 同理假设4号有毒的话，那2、6无毒，B 就死不了。
所以只能是6号有毒。
核算检测场景适用吗？
这个“老鼠试毒”的场景能直接“照搬”到核算检测吗？
假设不考虑核酸检测实操过程中的困难，比如每人采样后，可以直接将标本进行拆分（不考虑采样标本被稀释，从而影响结果等等），标号分组等工序。
是否能设计一种类似的方案，排列组合一下，拆分，尽量用较少的核酸检测试剂，较少的次数，来确定到底谁中招？
我脑袋不够用了，评论区等你来回答~
后记
数据结构和算法是重中之重，这里我跟大家推荐一本 Leetcode 算法指南，质量还挺不错的，推荐给大家参考。获取方式，在公众号后台回复 leetcode01 即可获取。
最后，求关注、求星标，本号会定期分享一些技术干货、职场经验等，如果大家对阿里或者其他大厂感兴趣，也可以找我内推，我可以帮忙提供简历 review 等，希望能和大家积极交流讨论，一起学习、共同进步。
关于作者：程序猿石头(ID: tangleithu)，从十八县贫困农村一路逆袭上清华（点击这里查看我的逆袭之路），目前在BAT某厂打工，是前大疆（无人机）技术主管。
欢迎扫码加入互联网大厂内推群 & 技术交流群，一起学习、共同进步。后台回复关键字 “0” 送阿里技术大礼包。
