问题

国王有一百桶酒,比自己的生命还重要。结果有一天其中一桶被投了慢性毒药,喝了以后半个小时以后就会死掉。国王大怒,命令玩忽职守的侍卫去试毒。酒不能被混合,一个侍卫可以喝多桶酒,一桶酒也可以由多个侍卫喝,怎么样才能用最少的侍卫、在最短的时间知道哪桶是毒酒。侍卫可以理解为线程,即怎么样用最少的线程用最快的速度完成这个工作。

方案

此问题是我在面试时经常用的一道题目,主要考察的是候选人能不能以计算机的思维考虑问题。

最简单的方案肯定是找100个人,每个人试一桶酒,那么用时30分钟,就可以判断出哪一桶就有毒。

再进一步的,可以使用分段法,把酒分成n份,先找n个侍卫试酒,可以定位出哪一段的酒有毒,再接着分段试酒。但这种方案,分段数目越少,试出毒酒的平均耗时就越长。

如果用计算机的思维来分析这个问题,那么首先考虑如何存储这100桶酒。100桶酒可以用二进制7个bit来表示(27>100)。对应那一桶毒酒,其二进制表示中为1的位置如果能够可以定位出来,就可以定位出此桶毒酒。可以找7个侍卫编号1-7。对于每一桶酒的二进制表示(不足七位前面用0表示),从第一位到第七位,如果是1,则对应编号的侍卫喝此桶酒。这样,每个侍卫喝掉对应的酒。30分钟后,侍卫按照编号1-7,死掉的置为1,活着的置为0,如此,侍卫的一个序列如0000111就表示第七桶酒为毒酒。

总结

上述最后一种方案提现了在计算机中使用bit来解决问题的思路。当需要节省存储的时候,使用bit来做经常会有出其不易的效果。就比如最近很火的电影《天才枪手》中,主角们记忆选择题的答案A、B、C、D,完全可以使用位编码来表示四种答案:00-A 01-B 10-C 11-D,四个bit转换为一个十六进制数字,如此就可以节省一半的存储,记忆起来也会简单很多。此外,我们处理大数据去重/计数使用的Bitmap、BloomFilter,也都是一种使用bit节省存储的思路。