一道刚遇到的面试题,面试官说答不出正常

程序员鱼皮

共 1889字,需浏览 4分钟

 ·

2022-11-18 10:44

大家周末愉快,今天分享一道很有意思的面试题目。

面试官问这道题之前还说:不用紧张,基本上没啥人可以答出来,你就发散着想想就行。

好了,废话不多说了,我们直接上题。

题目

现在有 10 只小白鼠和 1000 支药水,1000 支药水中有且仅有一支药水有毒,如果小白鼠喝下毒药,那么毒发的时间是两小时。

现在只给你两小时的时间,请问如何用这 10 只小白鼠测出哪支药水有毒?(忽略小白鼠喝药的时间)。

思考

当时听完这题,我第一反应是:这题是不是在逗我?

就 10 只小白鼠,喝 1000 支药水,那么一只小白鼠肯定要喝多支药水,假设某只小白鼠两小时后死了,我怎么确定它到底是因为喝了哪支药水死的?

我直接把我的这个想法跟面试官说了,我说这题目是不是有问题,面试官微微一笑,他说题目没问题,你再想想

再想想

看到这,不知道诸位是否有啥想法,期间面试官给了我一个提示:10 如何能代表 1000

这里建议先想个两分钟,各位再思考思考,没啥思路再看我下面的解答。

解答

不卖关子了,反正我当时没想出来,哈哈,一下子联想不到那里,但是这题听完答案之后又会豁然开朗。

10 如何能代表 1000?重点就是这个提示,其实就是二进制。

10 只小白鼠,我们分别给它们编号,从 0-9。

每只老鼠喝下药水,最终的结果要么是生,要么是死,所以有两种状态。

看到这是不是有点感觉了?

两种状态就是二进制的 0 和 1。

如下图所示:

所以,每只小白鼠有两种状态,那么 10 只小白鼠联合起来,2 的 10 次方是 1024,当然可以表示 1000 个数字了。

然后我们给每只药水编号,从 0-999。

好了,操作来了

0 二进制表示,是 0000000000 

1 二进制表示,是 0000000001 

2 二进制表示,是 0000000010 

3 二进制表示,是 0000000011

..........

999 二进制表示,是 1111100111

可以看到我把药水编号转成二进制,一共写了 10 位,每一位其实就表示对应一只小白鼠喝不喝这个药水

就是说第 0 个小白鼠,把药水编号第 0 位是 1 的药水都喝一遍。

第 1 个小白鼠,把药水编号第 1 位是 1 的药水都喝一遍。

第 2 个小白鼠,把药水编号第 2 位是 1 的药水都喝一遍。

...

第 9 个小白鼠,把药水编号第 9 位是 1 的药水都喝一遍。

这样设计之后,除了第 0 瓶药水,其它药水都有小白鼠喝了,所以如果没有小白鼠死亡,那么第 0 号药水有毒。

那么,如果有小白鼠死亡该怎么判断?

其实很好理解,假设现在是编号 3 的药水有毒,我们得知编号 3 的二进制是:0000000011

丛上面的规则我们知道,有且仅有第 0 个和第 1 个老鼠喝了编号 3 这个药水,所以如果别的老鼠都没死,只有这两个老鼠死了,那么我们可以断定编号 3 药水是毒药。

所以,我们让对应的老鼠喝对应的药水,然后两小时之后观察哪几只老鼠死亡,我们就可以从死亡的老鼠编号反推出毒药的编号。

假设现在第 0、1、3、5 老鼠死了,那么毒药水编号就是:2^0 + 2^1 + 2^3 + 2^5 = 1 + 2 + 8 + 32 = 43。

好了,解答完毕。(其实这个题干应该再补充下,每支药水量充足,足够每只小白鼠喝一口)

现在想想这个方式是不是有点巧妙?有点拓宽思路的感觉。

最后

这道题看起来好像是智力题,其实给了提示之后就是考察对二进制的掌握程度了。

二进制其实在很多场景都有比较深入的运用,其实就是位域的用法。

我举个距离我们比较近的例子,Java里面的读写锁即ReentrantReadWriteLock

AQS 里面用一个 int 变量 state 来表示锁的占有,那一个变量同时如何表示读锁和写锁呢

int 是 4 个字节,一共 32 位,于是乎李老爷子就把 32 位分为了两部分,高 16 位表示读锁的状态,低 16 位表示写锁的状态。

这就是二进制的一个简单应用,当然还有很多,包括刷算法题的时候,通过位来节省内存开销等等,这里就不多说了。

对了,不知道你们是否在路边遇到过摆摊的算命先生,说让你指着前面几张纸就能知道你的姓氏,其实用的就是二进制!

然后,你们在面试中有遇到什么比较有趣的面试题吗?欢迎留言分享下!



欢迎学编程的朋友们加入我的 编程知识星球 ,我会 1 对 1 解决你的问题,并且直播带大家开发完整项目(第三期项目进行中,本周日继续)。


往期推荐

项目启动失败?不用慌!

别担心,我们都一样!

有了这些 IDEA 插件,代码拿捏!

这几个程序员必备画图工具,很实用!

我的学习小圈子

浏览 16
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报