写点什么

不是吧阿 sir,你这业务太熟了吧,震惊面试官第八年,献给真心想学 Java 的打工人

用户头像
极客good
关注
发布于: 刚刚

首先,将 0 - 4294967259 这个范围平均分成 64 个区间,每个区间是 67108864 个数,为了定位更加准确一些,我们先开辟一个大小为 64 的整型数组 intArray,将 40 亿个数进行区间划分,第 0 区间(0-67108863)、第一区间(67108864-134217728)、第 i 区间(67108864i-67108864(i+1)-1),…,第 63 区间(4227858432 - 4294967259)。intArray 分别记录每个区间出现的数的个数,肯定至少有一个区间上的计数少于 67108864.利用这一点可以快速找出一个没有出现过的数。


? 第一次遍历时,先申请长度为 64 的整型数组 countArr[0…63],countArr[i]用来统计区间 i 上的数有多少。遍历 40 亿个数,根据当前数是多少来决定哪一个区间上的计数增加。例如,如果当前数是 3422552090,3422552090/67108864=51,所以第 51 区间上的计数增加 countArr[51]++。遍历完 40 亿个数之后,遍历 countArr,必然会有某一个位置上的值(countArr[i])小于 67108864,表示第 i 区间上至少有一个数没出现过。我们肯定会至少找到一个这样的区间。此时使用的内存就是 countArr 的大小(64×4B),是非常小的。


假设我们找到第 37 区间上的计数小于 67108864,以下为第二次遍历的过程:


1.申请长度为 67108864 的 bit map,这占用大约 8MB 的空间,记为 bitArr[0…67108863];


2.再遍历一次 40 亿个数,此时的遍历只关注落在第 37 区间上的数,记为 num(num/67108864==37),其他区间的数全部忽略。


3.如果步骤 2 的 num 在第 37 区间上,将 bitArr[num - 67108864*37]的值设置为 1,也就是只做第 37 区间上的数的 bitArr 映射。


4.遍历完 40 亿个数之后,在 bitArr 上必然存在没被设置成 1 的位置,假设第 i 个位置上的值没设置成 1,那么 67108864×37+i 这个数就是一个没出现过的数。


总结一下进阶的解法:


1.根据 10MB 的内存限制,确定统计区间的大小,就是第二次遍历时的 bitArr 大小。


2.利用区间计数的方式,找到那个计数不足的区间,这个区间上肯定有没出现的数。


3.对这个区间上的数做 bit map 映射,再遍历 bit map,找到一个没出现的数即可。

[](

)5、找到 100 亿个 URL 中重复的 URL


[白嫖资料](


)


? 原问题的解法使用解决大数据问题的一种常规方法:把大文件通过哈希函数分配到机器,或者通过哈希函数把大文件拆成小文件。一直进行这种划分,直到划分的结果满足资源限制的要求。首先,你要向面试官询问在资源上的限制有哪些,包括内存、计算时间等要求。在明确了限制要求之后,可以将每条 URL 通过哈希函数分配到若干机器或者拆分成若干小文件,这里的“若干”由具体的资源限制来计算出精确的数量。


? 例如,将 100 亿字节的大文件通过哈希函数分配到 100 台机器上,然后每一台机器分别统计分给自己的 URL 中是否有重复的 URL,**同时哈希函数的性质决定了同一条 URL 不可能分给不同的机器;**或者在单机上将大文件通过哈希函数拆成 1000 个小文件,对每一个小文件再利用哈希表遍历,找出重复的 URL;或者在分给机器或拆完文件之后,进行排序,排序过后再看是否有重复的 URL 出现。总之,牢记一点,很多大数据问题都离不开分流,要么是哈希函数把大文件的内容分配给不同的机器,要么是哈希函数把大文件拆成小文件,然后处理每一个小数量的集合。

[](

)6、海量搜索词汇,找到最热 TOP100 词汇的方法


? 最开始还是用哈希分流的思路来处理,把包含百亿数据量的词汇文件分流到不同的机器上,具体多少台机器由面试官规定或者由更多的限制来决定。对每一台机器来说,如果分到的数据量依然很大,比如,内存不够或其他问题,可以再用哈希函数把每台机器的分流文件拆成更小的文件处理。


? 处理每一个小文件的时候,哈希表统计每种词及其词频,哈希表记录建立完成后,再遍历哈希表,遍历哈希表的过程中使用大小为 100 的小根堆来选出每一个小文件的 top 100(整体未排序的 top 100)。每一个小文件都有自己词频的小根堆(整体未排序的 top 100),将小根堆里的词按照词频排序,就得到了每个小文件的排序后 top 100。然后把各个小文件排序后的 top 100 进行外排序或者继续利用小根堆,就可以选出每台机器上的 top 100。不同机器之间的 top100 再进行外排序或者继续利用小根堆,最终求出整个百亿数据量中的 top 100。对于 top K 的问题,除哈希函数分流和用哈希表做词频统计之外,还经常用堆结构和外排序的手段进行处理。

[](

)7、40 亿个无符号整数,1GB 内存,找到所有出现两次的数


? 对于原问题,可以用 bit map 的方式来表示数出现的情况。具体地说,是申请一个长度为 4294967295×2 的 bit 类型的数组 bitArr,用 2 个位置表示一个数出现的词频,1B 占用 8 个 bit,所以长度为 4294967295×2 的 bit 类型的数组占用 1GB 空间。怎么使用这个 bitArr 数组呢?遍历这 40 亿个无符号数,如果初次遇到 num,就把 bitArr[num2 + 1]和 bitArr[num2]设置为 01,如果第二次遇到 num,就把 bitArr[num2+1]和 bitArr[num2]设置为 10,如果第三次遇到 num,就把 bitArr[num2+1]和 bitArr[num2]设置为 11。以后再遇到 num,发现此时 bitArr[num2+1]和 bitArr[num2]已经被设置为 11,就不再做任何设置。遍历完成后,再依次遍历 bitArr,如果发现 bitArr[i2+1]和 bitArr[i2]设置为 10,那么 i 就是出现了两次的数。


[白嫖资料](


)

[](

)8、10MB 内存,找到 40 亿整数的中位数


①内存够:内存够还慌什么啊,直接把 100 亿个全部排序了,你用冒泡都可以…然后找到中间那个就可以了。但是你以为面试官会给你内存??


②内存不够:题目说是整数,我们认为是带符号的 int,所以 4 字节,占 32 位。


假设 100 亿个数字保存在一个大文件中,依次读一部分文件到内存(不超过内存的限制),将每个数字用二进制表示,比较二进制的最高位(第 32 位,符号位,0 是正,1 是负),如果数字的最高位为 0,则将这个数字写入 file_0 文件中;如果最高位为 1,则将该数字写入 file_1 文件中。


从而将 100 亿个数字分成了两个文件,假设 file_0 文件中有 60 亿 个数字,file_1 文件中有 40 亿 个数字。那么中位数就在 file_0 文件中,并且是 file_0 文件中所有数字排序之后的第 10 亿 个数字。(file_1 中的数都是负数,file_0 中的数都是正数,也即这里一共只有 40 亿个负数,那么排序之后的第 50 亿个数一定位于 file_0 中)


现在,我们只需要处理 file_0 文件了(不需要再考虑 file_1 文件)。对于 file_0 文件,同样采取上面的措施处理:将 file_0 文件依次读一部分到内存(不超内存限制),将每个数字用二进制表示,比较二进制的 次高位(第 31 位),如果数字的次高位为 0,写入 file_0_0 文件中;如果次高位为 1,写入 file_0_1 文件 中。


现假设 file_0_0 文件中有 30 亿个数字,file_0_1 中也有 30 亿个数字,则中位数就是:file_0_0 文件中的数字从小到大排序之后的第 10 亿个数字。


抛弃 file_0_1 文件,继续对 file_0_0 文件 根据 次次高位(第 30 位) 划分,假设此次划分的两个文件为:file_0_0_0 中有 5 亿个数字,file_0_0_1 中有 25 亿个数字,那么中位数就是 file_0_0_1 文件中的所有数字排序之后的 第 5 亿 个数。


按照上述思路,直到划分的文件可直接加载进内存时,就可以直接对数字进行快速排序,找出中位数了。

[](

)9、设计短域名系统,将长 URL 转化成短的 URL.


(1)利用放号器,初始值为 0,对于每一个短链接生成请求,都递增放号器的值,再将此值转换为 62 进制(a-zA-Z0-9),比如第一次请求时放号器的值为 0,对应 62 进制为 a,第二次请求时放号器的值为 1,对应 62 进制为 b,第 10001 次请求时放号器的值为 10000,对应 62 进


【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


制为 sBc。


(2)将短链接服务器域名与放号器的 62 进制值进行字符串连接,即为短链接的 URL,比如:t.cn/sBc。


(3)重定向过程:生成短链接之后,需要存储短链接到长链接的映射关系,即 sBc -> URL,浏览器访问短链接服务器时,根据 URL Path 取到原始的链接,然后进行 302 重定向。映射关系可使用 K-V 存储,比如 Redis 或 Memcache。


[白嫖资料](


)

[](

)10、让你系统的设计一个高并发的架构,你会从哪几个方面考虑?


系统拆分


? 将一个系统拆分为多个子系统,用 dubbo 来搞。然后每个系统连一个数据库, 这样本来就一个库,现在多个数据库,不也可以扛高并发么。


缓存


? 缓存,必须得用缓存。大部分的高并发场景,都是读多写少,那你完全可以在数 据库和缓存里都写一份,然后读的时候大量走缓存不就得了。毕竟人家 redis 轻 轻松松单机几万的并发。所以你可以考虑考虑你的项目里,那些承载主要请求的 读场景,怎么用缓存来抗高并发。


MQ


? MQ,必须得用 MQ。可能你还是会出现高并发写的场景,比如说一个业务操作 里要频繁搞数据库几十次,增删改增删改,疯了。那高并发绝对搞挂你的系统, 你要是用 redis 来承载写那肯定不行,人家是缓存,数据随时就被 LRU 了,数 据格式还无比简单,没有事务支持。所以该用 mysql 还得用 mysql 啊。那你 咋办?用 MQ 吧,大量的写请求灌入 MQ 里,排队慢慢玩儿,后边系统消费 后慢慢写,控制在 mysql 承载范围之内。所以你得考虑考虑你的项目里,那些 承载复杂写业务逻辑的场景里,如何用 MQ 来异步写,提升并发性。MQ 单机 抗几万并发也是 ok 的,这个之前还特意说过。


分库分表


? 分库分表,可能到了最后数据库层面还是免不了抗高并发的要求,好吧,那么就 将一个数据库拆分为多个库,多个库来扛更高的并发;然后将一个表拆分为多个 表,每个表的数据量保持少一点,提高 sql 跑的性能。


读写分离


? 读写分离,这个就是说大部分时候数据库可能也是读多写少,没必要所有请求都 集中在一个库上吧,可以搞个主从架构,主库写入,从库读取,搞一个读写分离。 读流量太多的时候,还可以加更多的从库。

用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
不是吧阿sir,你这业务太熟了吧,震惊面试官第八年,献给真心想学Java的打工人