腾讯面试出的一道题:兔子试毒飞天小牛肉关注共 1648字,需浏览 4分钟 ·2021-09-30 12:07 大家好,我是牛牛,经过了忙碌的一周,终于盼来了周五。今天给大家分享一道有趣有料的算法题,希望能让大家开启周末的好心情。01故事起源有1000瓶药水,其中有一瓶是毒药,只要喝上一滴,一天之后就必死无疑。现在提供一批兔子来试毒,那我们怎么花最少的兔子、最少的时间,找出这瓶毒药呢?02条件分析喝一滴就死掉,换句话说,那一瓶药水是可以给多只兔子喝的。要花最少的兔子,又要花最少的时间,看起来像是时间与空间的决策,不如我们先来简化问题:1.只追求时间,最快速度找出药水。2.只追求空间,节约兔子,时间可以慢慢来。这样从简单角度辅助思考一下,也能为我们深入思考打下基础。03花式试毒追求时间简单来说,就是堆兔子。直接拿1000只兔子试毒,一只兔子负责一瓶药水。结果自然是耗用1000只兔子,1天出结果。这样的优势比较明显,就是快;缺点也明显:使用的兔子太多,占资源,不环保。追求空间如果我们出于环保考虑,节约兔子,那么可以考虑用2分。第一轮就分为500瓶毒药为一组,先放一只兔子,每瓶药水喝一滴,这样可以排除500瓶。如果活着,就继续用这只兔子,如果死了,就补充兔子。我们按最坏情况来算:每次都要消耗掉一只兔子。下一轮250瓶,这样循环迭代,1000->500->250->125->63->32->16->8->4->2->110个箭头,就是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存储非常熟悉!是选择时间?或空间?或寻求平衡?亦或是有办法另辟蹊径,两者兼备?相信随着思维的循序渐进,你会有所感悟。今天分享的这道题不光有趣,还是大厂热门面试题,看起来似乎很简单,但其实是有巧思在其中的,它考察了你的思维方式和逻辑能力,希望大家在阅读过程中有所收获!END关注公众号,免费领取学习资料你好,我是牛牛,普通二本毕业。本科进腾讯,去过外企,肝过头条。目前回腾讯担任高级工程师。想来腾讯的朋友,可以找我内推哦!点个“赞”和“在看”鼓励一下嘛~ 浏览 23点赞 评论 收藏 分享 手机扫一扫分享分享 举报 评论图片表情视频评价全部评论推荐 【腾讯面试题】兔子试毒苦逼的码农0【腾讯面试题】兔子试毒月伴飞鱼0御试䇿一道御试䇿一道 盖闻道之大原出于天,超乎无极大极之妙,而实不离乎日用事物之常,根乎隂阳五行之?,而实不外腾讯二面算法题来了~JavaEdge0试馆职䇿一道试馆职䇿一道 对:天下有常势,非人之?能为也。自古恢复大业之君,虽其慿藉积累之基有厚有薄,祖宗徳泽之一道腾讯产品面试题产品刘0记一道有趣的“签到”题白帽子社区0一道SQL题的7种解法数据管道0兔子面美食城本店特色美食。鱼香肉丝炒饭,香辣大虾,木耳炒肉片,龙眼肉,清炒苦瓜,凉拌粉丝,番茄煎蛋汤,豌豆饭,坨子肉,盐菜肉,杂酱兔子面,鲜茶酥菇炒腊肉,尖椒吵拱嘴,血旺牛柳,干锅肥肠头,蒜泥白肉,糖醋里脊,四椒我试毒回来了!大家好,我是小林。 每年过春节,我都会带家里人去看春节档的电影,今年也不例外,跟大家聊聊观影感受。 初一和初二先后带家里人看了《红毯先生》、《飞驰人生 2》,豆瓣现在也开分了,《红毯先生》豆瓣 6.9 分,《...点赞 评论 收藏 分享 手机扫一扫分享分享 举报