微信支付面试题:如何用最少的老鼠试出有毒的牛奶?

业余杂谈 herman 434浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:codedq,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:codedq,之前的微信号好友位已满,备注:返现
饿了么大量招人,我内推!Java 方向!薪资不设上限,工作年龄不限!工作地点限魔都,可电话面试!简历,发我微信:codedq
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

面试题

有 n 桶牛奶,其中有 1 桶有问题,老鼠喝了后第二天会死掉。如何用最少的老鼠测出有问题的那瓶牛奶?

答案

把 n 转换成二进制,二进制的长度就是对应老鼠的个数

操作方案

为了方便演示假设 n = 8,转换成二进制位 1000,可知需要最少的老鼠是 4 只

第一步

给 8 桶牛奶用二进制编号
第 1 桶牛奶 0001
第 2 桶牛奶 0010
第 3 桶牛奶 0011
第 4 桶牛奶 0100
第 5 桶牛奶 0101
第 6 桶牛奶 0110
第 7 桶牛奶 0111
第 8 桶牛奶 1000

第二步

4 只老鼠按顺序排好,面对着牛奶对应的二进制编号,每桶二进制编号为 1 对应的老鼠喝牛奶

老鼠 1 喝第 8 桶的牛奶
老鼠 2 喝第 4、5、6、7 桶的牛奶
老鼠 3 喝第 2、3、6、7 桶的牛奶
老鼠 4 喝第 1、3、5、7 桶的牛奶

第三步

第二天后把这 4 只老鼠还按昨天的顺序排好,死了的老鼠标记为 1,没有死的老鼠标记为 0,这这样 4 只老鼠就组成了一个二进制的数,与之对应的牛奶编号就是有毒的那桶。比如老鼠 2 和老鼠 3 死了,对应的二进制编号为 0110,那就说明第 6 桶牛奶有毒

后记

这种题考查了对二进制的应用,也有很多变种面试题,但万变不离其宗,掌握了方法方可以不变应万变

这是一位网友的微信支付一面中遇到的题,我看到后,一点思路都没有,但有的朋友直接就把方案说出来了,可见平时积累的重要性

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号1:xmtxtt(5000人已满),微信号2:xttblog(5000人已满),微信号3:codedq(超3800)。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » 微信支付面试题:如何用最少的老鼠试出有毒的牛奶?