查看原文
其他

腾讯面试题:兔子试毒

The following article is from 牛牛码特 Author 牛牛码特

今天给大家分享一道有趣有料的算法题,希望能让大家开启周末的好心情。

01故事起源

有1000瓶药水,其中有一瓶是毒药,只要喝上一滴,一天之后就必死无疑。

现在提供一批兔子来试毒,那我们怎么花最少的兔子、最少的时间,找出这瓶毒药呢?


02条件分析


喝一滴就死掉,换句话说,那一瓶药水是可以给多只兔子喝的。要花最少的兔子,又要花最少的时间,看起来像是时间与空间的决策,不如我们先来简化问题:

1.只追求时间,最快速度找出药水。
2.只追求空间,节约兔子,时间可以慢慢来。

这样从简单角度辅助思考一下,也能为我们深入思考打下基础。

03花式试毒


追求时间

简单来说,就是堆兔子。直接拿1000只兔子试毒,一只兔子负责一瓶药水。结果自然是耗用1000只兔子,1天出结果。这样的优势比较明显,就是快;缺点也明显:使用的兔子太多,占资源,不环保。



追求空间

如果我们出于环保考虑,节约兔子,那么可以考虑用2分。第一轮就分为500瓶毒药为一组,先放一只兔子,每瓶药水喝一滴,这样可以排除500瓶。如果活着,就继续用这只兔子,如果死了,就补充兔子。我们按最坏情况来算:每次都要消耗掉一只兔子。

下一轮250瓶,这样循环迭代,1000->500->250->125->63->32->16->8->4->2->1

10个箭头,就是10次,也就是用了10天。这样我们只用了10只兔子,很节约,不过就是等得太心慌。


中庸之道

把前两种方式综合一下,我们可以不用1000只兔子,也可以不用等足足10天。

把2分,变成多分。比如,9只兔子的话,每次能分10份,每轮补充兔子到9只,这样试完1000瓶药水,只需要3天,1000->100->10->1。

2只兔子的话,就是3份,1000->333->111->37->(12,12,13)->(4,4,5)->(2,2,1) -> 1

规律也很明显,天数为d,分a份,则兔子是a-1只,药水N瓶,那么d等于以a为底N的对数(logaN)。比如,当耗用2只兔子时,a为3,算出来正好是7天,和我们刚才的推算是一样的。

计算机思维

还有没有更好的办法呢?时间短,效率高。

当然有,因为一次可以喝多瓶药水,那么我们可以用10只兔子,模拟出1024种情况。

给药水编号,从1-1000,兔子也编上号,1-10号,1000瓶药水编号,都转换为二进制编号,1就是000 000 0001,1000就是111 110 1000。


这种情况下,第几位为1,就让对应的兔子喝一滴药水。由于编号都是独一无二的,所以最后根据死掉的兔子,反过来组合一下,就是药水的编号。


如此一来,10只兔子,只花1天,就能试毒成功。无论空间,还是时间,都是最快的。

04兔兔复盘
如果你是使用1000只兔子试毒,那么说明你对时间很敏感;如果是二分法,那你一定是个节约成本的大师;如果使用多分法,说明你懂得在空间和时间上,取一个均衡,深谙中庸之道;如果你能很快想到二进制模拟,那么你一定是对计算机01存储非常熟悉!

是选择时间?或空间?或寻求平衡?亦或是有办法另辟蹊径,两者兼备?相信随着思维的循序渐进,你会有所感悟。

今天分享的这道题不光有趣,还是大厂热门面试题,看起来似乎很简单,但其实是有巧思在其中的,它考察了你的思维方式和逻辑能力,希望大家在阅读过程中有所收获!

- EOF -

推荐阅读  点击标题可跳转

1、腾讯面试题:青蛙跳跳跳

2、腾讯面试题:64匹马,8赛道,找出最快的4匹最少要几次?

3、腾讯面试题:熊出没


觉得本文有帮助?请分享给更多人

推荐关注「算法爱好者」,修炼编程内功

点赞和在看就是最大的支持❤️

: . Video Mini Program Like ,轻点两下取消赞 Wow ,轻点两下取消在看

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存