微软面试题:红帽子与黑帽子

Java技术迷

共 1353字,需浏览 3分钟

 ·

2021-04-27 23:47








01
故事起源

一群人开舞会,每人都戴着一顶帽子。帽子只有红和黑两种,其中黑的至少有一顶。每个人能看到其它人的帽子颜色,但看不到自己的。

大家先一起做一个游戏,规则如下:
所有人先看别人头上戴的是什么帽子,然后关灯,如果有人认为自己戴的黑帽子,就打自己一个耳光。

游戏开始:

第一次关灯,没有声音。

于是打开灯再看一遍,第二次关灯,依然鸦雀无声。
一直到第三次关灯,才有声音响起。

问:有多少人戴着黑帽子?



02

分析

假设有5个红帽子,和5个黑帽子。
对于红帽子的人,他看到的是有4个红帽子,和5个黑帽子。
对于黑帽子的人,他看到的是有5个红帽子,和4个黑帽子。
那么第一次关灯,对于任何一个人,只能得到上面的信息,他是无法判断自己的帽子颜色的,所以肯定啥也不发生。


03

寻找突破口

题目是问戴黑帽子的有几个人,跟具体人数相关。但我们再回到题目描述,并没有给总共多少人,也没有说红帽子有多少人,只有一个跟数字相关的条件,就是戴黑帽子的至少有一人,这就是突破口。
所以这类的问题都可以从题目的信息量上面寻找突破口。
没有说红帽子有多少人,说明解题的思路肯定跟红帽子没什么关系,有多少都无所谓,那就从黑帽子开始思考。


04

小规模简单场景

4.1
假设只有1个黑帽子
对于每一个红帽子,他看到的场景是这样的。第一次关灯他们都无法确定自己帽子的颜色。
对于唯一的一个黑帽子,他看到的场景是这样的。因为至少有一个黑帽子,他没有看到,所以推出自己一定是黑帽子,第一次关灯声音响起。

4.2
假设有2个黑帽子
对于每一个红帽子,他看到的场景是这样的。第一次关灯他们是无法判断的。
对于2个黑帽子,他看到的场景是这样的。
第一次关灯,他们都在等对方打耳光,所以什么也不会发生。
因为第一次没有声音,这时他俩都知道,第一次对方在等自己打耳光。所以这时他们都可以判断自己是黑帽子,第二次关灯声音响起。

4.3
假设有3个黑帽子
对于红帽子的人来说,一定比黑帽子的人后得到信息,所以不考虑。
对于其中的每一个黑帽子,他们认为2次之后对方可以发现,结果两次之后因为都在等,不会有声音,那第三次都可以判断自己是黑帽子了。

4.4
假设有N个黑帽子
根据上面分析,可以推论第N次声音响起。所以题目第3次有声音,也就意味着有3个黑帽子。


05

总结

对于所有的红帽子,他们的地位是相同的,也就是视角永远一样,对黑帽子也同样成立,所以如果有信息就会是同时得到,而不是一些人先发现。那这个问题就分红黑两类来考虑就行了。这也是属于博弈论相关的问题,可以先考虑小数据的简单场景。


1、最牛逼的 Java 日志框架,性能无敌,横扫所有对手!
2、把Redis当作队列来用,真的合适吗?
3、惊呆了,Spring Boot居然这么耗内存!你知道吗?
4、牛逼哄哄的 BitMap,到底牛逼在哪?
5、全网最全 Java 日志框架适配方案!还有谁不会?
6、30个IDEA插件总有一款适合你
7、Spring中毒太深,离开Spring我居然连最基本的接口都不会写了

点分享

点收藏

点点赞

点在看

浏览 43
点赞
评论
收藏
分享

手机扫一扫分享

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

手机扫一扫分享

分享
举报