Java开发

九、客观题

1、100亿黑名单URL，每个64B，问这个黑名单要怎么存？判断一个URL是否在黑名单中

​ 散列表：

​ 如果把黑名单看成一个集合，将其存在 hashmap 中，貌似太大了，需要 640G，明显不科学。

​ 布隆过滤器：

​ 它实际上是一个很长的二进制矢量和一系列随机映射函数。

​ 它可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。对于布隆过滤器而言，它的本质是一个位数组：位数组就是数组的每个元素都只占用 1 bit ，并且每个元素只能是 0 或者 1。

​ 在数组中的每一位都是二进制位。布隆过滤器除了一个位数组，还有 K 个哈希函数。当一个元素加入布隆过滤器中的时候，会进行如下操作：

• 使用 K 个哈希函数对元素值进行 K 次计算，得到 K 个哈希值。
• 根据得到的哈希值，在位数组中把对应下标的值置为 1。

2、2GB内存在20亿整数中找到出现次数最多的数

​ 通常做法是使用哈希表对 出现的每一个数做词频统计，哈希表的key是某个整数，value记录整数出现的次数。本题的数据量是20亿，有可能一个数出现20亿次，则为了避免溢出，哈希表的key是32位（4B）,value也是 32位（4B），那么一条哈希表的记录就需要占用8B。

​ 当哈希表记录数为2亿个时，需要16亿个字节数（8*2亿），需要至少1.6GB内存(16亿/2^30,1GB== 2 ^30个字节 == 10亿)。则20亿个记录，至少需要16GB的内存，不符合题目要求。

​ 解决办法是将20亿个数的大文件利用哈希函数分成16个小文件，根据哈希函数可以把20亿条数据均匀分布到16个文件上，同一种数不可能被哈希函数分到不同的小文件上，假设哈希函数够好。然后对每一个小文件用哈希函数来统计其中每种数出现的次数，这样我们就得到16个文件中出现次数最多的数，接着从16个数中选出次数最大的那个key即可。

3、40亿个非负整数中找到没有出现的数

​ 对于原问题，如果使用哈希表来保存出现过的数，那么最坏情况下是40亿个数都不相同，那么哈希表则需要保存40亿条数据，一个32位整数需要4B，那么40亿*4B = 160亿个字节，一般大概10亿个字节的数据需要1G的空间，那么大概需要16G的空间，这不符合要求。

我们换一种方式，申请一个bit数组，数组大小为4294967295，大概为40亿bit，40亿/8 = 5亿字节，那么需要0.5G空间， bit数组的每个位置有两种状态0和1，那么怎么使用这个bit数组呢？呵呵，数组的长度刚好满足我们整数的个数范围，那么数组的每个下标值对应4294967295中的一个数，逐个遍历40亿个无符号数，例如，遇到20，则bitArray[20] = 1；遇到666，则bitArray[666] = 1,遍历完所有的数，将数组相应位置变为1。

4、40亿个非负整数中找到一个没有出现的数，内存限制10MB

​ 本题将内存空间缩小为10MB，对于40亿个数据来说那是明显不够用的，那么我们只有将数据分块处理，分块应该怎么分，分多少块合理呢？根据我做过的题经验来看，10亿个字节的数据大概需要1GB空间处理(如果这个结论不正确欢迎读者指出)，那么10MB内存换算过来就是可以处理1千万字节的数据，也就是8千万bit，对于40亿非负整数如果申请bit数组的话，40亿bit / 0.8亿bit = 50，那么这样最少也得分50块来处理，处理每块数据的时候几乎用完了内存空间，这样也不太好。看书上解说是分成了64块，至于为什么是64我目前也不是很了解，我只知道最少50块。所以下面就以64块来进行分析解答吧。

首先，将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进制为sBc。

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

（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 跑的性能。

读写分离

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

ElasticSearch

​ Elasticsearch，简称 es。es 是分布式的，可以随便扩容，分布式天然就可以支 撑高并发，因为动不动就可以扩容加机器来扛更高的并发。那么一些比较简单的 查询、统计类的操作，可以考虑用 es 来承载，还有一些全文搜索类的操作，也 可以考虑用 es 来承载。

11、假设有这么一个场景，有一条新闻，新闻的评论量可能很大，如何设计评论的读和写

可以进行读写分离、加载到缓存

12、显示网站的用户在线数的解决思路

1. 维护在线用户表

2. 使用Redis统计

十、个人项目

秒杀项目：

项目架构介绍：

​ 系统主要通过缓存，异步，限流来保证系统的高并发和高可用。

​ https://blog.csdn.net/awake_lqh/article/details/83306983

​ https://www.baidu.com/link (opens new window)

1、秒杀的流程

用户发起请求——秒杀接口——访问内存标记库存——访问redis预减库存——判断是否重复下单——压入消息队列——客户端通过ajax请求轮询访问下单结果接口，直到响应状态成功或者失败

2、库存预减用的是哪个redis方法

redisService.decr(GoodsKey.getSeckillGoodsStock, "" + goodsId);

3、如果项目中的redis服务挂掉，如何减轻数据库的压力

redis当做二级缓存使用，ehcache作为一级缓存，当redis挂掉，还有一级缓存减轻数据库的压力。

4、如何避免消息队列的消费方重复消费消息

消费者每次执行查询前，首先在DB上查询任务的执行状态，若处于「取消/失败/成功」则表示已经由其它消费者消费过，那么直接返回ACK状态码给MQ，将消息从MQ中移除；

5、说一下如何解决超卖的

更改数据库时，判断库存是否大于0

redis预减库存：redis库存不足时直接返回失败

Mysql乐观锁：给每个商品库存一个版本号version字段，在实际减库存的SQL操作中，首先判断version是否是我们查询库存时候的version，如果是，扣减库存，成功抢购。如果发现version变了，则不更新数据库，返回抢购失败。

6、你说你用到了redis，redis有哪些数据结构，你为什么要用redis，哪里用到了，为什么说redis快，多路io复用详细原理可以说说嘛？

String、List、Set、ZSet、Map

redis是内存型数据库，访问、存储都非常快，通常用来缓存一些热点数据，比如秒杀商品、用户状态信息等，减轻数据库访问的压力

快是由于redis基于单线程，减少了线程的上下文切换；内存型数据库，访问快；基于多路io复用；

多路-指的是多个socket连接，复用-指的是复用一个线程。多路复用主要有三种技术：select，poll，epoll。epoll是最新的也是目前最好的多路复用技术。

这里“多路”指的是多个网络连接，“复用”指的是复用同一个线程。采用多路 I/O 复用技术可以让单个线程高效的处理多个连接请求（尽量减少网络IO的时间消耗），且Redis在内存中操作数据的速度非常快（内存内的操作不会成为这里的性能瓶颈），主要以上两点造就了Redis具有很高的吞吐量。

7、说一下redis的应用场景

计数器

​ 可以对 String 进行自增自减运算，从而实现计数器功能。Redis 这种内存型数据库的读写性能非常高，很适合存储频繁读写的计数量。

缓存

​ 将热点数据放到内存中，设置内存的最大使用量以及淘汰策略来保证缓存的命中率。

会话缓存

​ 可以使用 Redis 来统一存储多台应用服务器的会话信息。当应用服务器不再存储用户的会话信息，也就不再具有状态，一个用户可以请求任意一个应用服务器，从而更容易实现高可用性以及可伸缩性。

其它

​ Set 可以实现交集、并集等操作，从而实现共同好友等功能。ZSet 可以实现有序性操作，从而实现排行榜等功能。

8、秒杀系统怎么做的，架构图画了一下

10.秒杀模块怎么设计的，如何压测，抗压手段，如何保证数据库与redis缓存一致的,消息队列怎么用的 11.秒杀系统服务器抗压思路，从哪些方面去优化 12.如何解决超卖 13.讲讲你做的秒杀项目 14.你的秒杀项目，别说你里面的优化，你还有什么优化策略吗？多服务器负载均衡，把秒杀商品平均分给服务器。 15.秒杀项目部分实现怎么做的 16.秒杀系统的前端设计怎么做？ 17.说说秒杀如何实现的？（用redis预库存的减少，然后方式异步消息队列rabbitMQ中） 18.如何解决商城中超卖问题？秒杀场景呢？ 19.秒杀过程中怎么保证redis缓存和数据库的一致性 20.具体的秒杀细节怎么做的？秒杀的核心技术在哪儿？你怎么保证的？ 21.秒杀商品的库存放在哪里，如何保证redis和DB的一致性 22.设计秒杀方案（从高并发、快速响应、高可用三方面回答，高并发（增加网络带宽、DNS域名解析分发多台服务器、使用前置代理服务器ngnix、CDN内容分发、数据库查询优化（读写分离、分库分表）），快速响应（缓存服务器（memcached、redis）、能使用静态页面就用静态页面，减少容器解析、把常访问的图片等内容缓存）、高可用（热备，如数据库服务器的热备、集群监控（如使用zabbix，重点关注IO、内存、带宽和机器load））） 23.秒杀时如果机器资源有限怎么办 24.秒杀接口防刷怎么做 25.如何防止超卖和少卖 26.秒杀系统场景下怎么防止超卖，redis和数据库数据不一致怎么办，以什么为准 27.秒杀流程图 如何保证不超卖 以及对应SQL

1、如何解决超卖？

mysql乐观锁+redis预减库存+redis缓存卖完标记

2、如何解决重复下单？

mysql唯一索引+分布式锁

3、如何防刷？

IP限流+验证码

4、热key问题如何解决？

redis集群+本地缓存+限流+key加随机值分布在多个实例中

5、消息队列的作用？如何保证消息的不丢失？

异步削峰；发送方开启confirm+消息队列持久化+消费方关闭自动ACK,确保消费成功之后自动调用API进行确认。

6、缓存和数据库数据一致性如何保证？

秒杀项目不用 保证，其他项目就用延时双删或者先更新数据再是缓存失效，为防缓存失效这一信息丢失，可用消息队列确保。

10