一道刚遇到的面试题,面试官说答不出正常
共 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 解决你的问题,并且直播带大家开发完整项目(第三期项目进行中,本周日继续)。
往期推荐