利用7个分片确定姓氏如何编排问题的思路与解答

tech2022-12-04  8

题目描述: 将中国的百家姓按一定规则进行存储, 1.存储容器为一个圆盘,将圆盘等量分为7份,每一个分片上存储若干个姓氏 2.随机指定某个姓氏,对7个分片逐个进行访问,每个分片都会返回true/false告诉你这个姓氏是否在这个分片上,7个分片全部询问结束后,你就可以知道指定的是哪个姓氏了 要求:对这些分片存储姓氏的规则进行合理编排以满足上诉两条规则

看到这个题目首先想到的是布隆过滤器,但是布隆过滤器只能判断给定姓氏一定不存在和可能存在,无法判断这个姓氏一定存在,所以这个方案pass了, 仔细研究下题目,发现它有个遍历询问的过程,然后给出最终确定答案,是不是感觉和「小白鼠试毒药」问题很像呢,简直是异曲同工之妙呀~ 话不多说,直接给思路吧

1.圆盘分区划分设定

将给定的大圆盘平均分为7份,排号为1-7 设定:

每一个分片上都可以存储1个或者若干个姓氏一个姓氏可以被存储多次
2.对每个姓氏进行初始化编码操作

对每个姓氏进行初始化编码,最简单的就是按照顺序排列,假定有100个姓氏,按照0-99给定编码,将每个编码转成7为的二进制数,高位用0补齐,因为2的7次方是128,所以完全可以满足条件 举例: 肖在百家姓排名中占第30位,那么 肖 姓的编号就是 30 转成7位二进制: 001 1110 二进制数与7个分片对照起来, 位置是1的对应分片存储这个字 (从左到右)

分片1分片2分片3分片4分片5分片6分片70011110❌❌存储存储存储存储❌

按照这个规则,将100个姓氏都进行编排存储

3.判断指定姓氏

对指定的某个姓氏进行判断的时候,只需要根据分片返回的true/false true: 1 false: 0 按照规则拼装出对应7二进制数字,再转回10进制编码,就可以确定这个姓氏是哪个啦 是不是很简单呢!!

[注1] 这道题和「小白鼠试毒药」的原理相同,面试时可能还会有其他场景的变形,只要确定用二进制位数确定唯一值的原理就都可以引刃而解啦 [注2] 中国的百家姓远不止100个这个多,这里只是用作举例说明,如果想要表示更多的姓氏,只需要增加分片的数量即可

最新回复(0)