# 场景题
# 1.一个32位系统，dump结果有1G，但是用户申请512M却触发OOM了，有几种原因？
答案
1.内存被小的分配占用，导致没有足够大的连续空间分配给512M的请求
2.可能操作系统对单个进程可以使用的内存量有限制，即使系统内存足够，超出限制后也会出发OOM错误
3.可能有一部分内存是操作系统保留的内存，实际用户能使用的内存已经不足512M了
4.可能存在内存泄漏，即使系统报告有大量未使用的内存，但实际可用内存已经很少了
# 2.如何保证幂等性
答案
1.Token机制：客户端请求时，服务端发放一个Token，客户端提交请求时携带这个Token。服务器收到请求后，判断Token是否有效，有效则执行操作，并使Token失效，否则不执行任何操作。
2.悲观锁机制：在数据库中使用版本号或时间戳机制，尝试更新数据时检查版本号或时间戳，如果不匹配则不执行任何操作，否则执行操作并更新版本号或时间戳
3.使用唯一标识符：客户端为每个请求生成一个唯一标识符，服务端根据这个唯一标识符判断请求是否执行过，如果已经执行过不，则忽略，否则执行操作。
# 4.10亿个数，找出最大的10个
答案
堆/快速选择
# 5.10亿个数排序
答案
首先将数据进行分成n块，对每个块加载进内存进行排序，然后取出n个块中的第一个元素，放入堆中，然后弹出堆顶元素，然后根据弹出的元素去对应的块中取出一个元素放入，直到时堆被取空。
通过bitmap排序，将所有数字塞入bitmap,然后从小到大遍历一遍bitmap
# 6.如何把一个文件较快的发送到100w个服务器？
答案
首先将文件发送给1000个服务器，然后每一个服务器发送给另外1000个服务器
# 7.如何从大量的URL中找出相同的URL?
答案
背景:给定a,b两个文件，各存放50亿个URL,每个URL各占64B，内存限制是4G，请找出两个文件共同的URL
解法1：因为是URL，所以一般会有很多重复部分，我们可以使用Trie树即可
解法2：遍历文件a,b，对遍历到的URL求哈希值%1000，从而分成一共2000个文件，每个文件约300MB，不同文件的URL一定不同。然后遍历a的每一个小文件，写入hashset，然后遍历b对应的小文件，如果在hashset中存在，那么就是他们公共的URL
# 8.如何从大量数据中找到高频词？
答案
背景:有一个1GB大小的文件，文件每一行是一个词，每个词大小不超过16B，内存大小限制是1MB，要求返回频率前100的词
解法1:遍历该文件，对每个词求hash%1000，分成1000个小文件，使用Map统计出小文件中的每个词的出现次数，然后写入堆中，并只保留出现次数前100的词
解法2:使用外部归并排序对所有数据进行排序，然后按顺序遍历所有数据，并使用变量来统计数的出现次数，并插入堆中
# 9.如何在大量数据中找到不重复的整数
答案
背景:在2.5亿个整数中找到不重复的整数
解法1:首先遍历所有整数，将其哈希到若干个小文件中，然后遍历这些小文件，使用统计出现次数，然后将不重复的写入
解法2:使用位图法，遍历整数的时候，如果没出现过，对应的位就是00，如果出现过一次，对应的位就是01，如果出现过多次，对应的位就是10。总内存2^32*4=1GB。如果内存超过1GB就可以使用位图法
# 10.如何在大量数据中判断一个数是否存在
答案
解法1:使用位图法，遍历每一个整数，将其对应的位设置为1，如果要查询的位为1，那么就存在
# 11.点赞系统设计
答案
点赞系统分为接入层，应用层，异步任务，数据层。
接入层需要将流量进行划分，对于点赞系统使用同城多活来实现容灾，将写流量分到同一个机房，读流量均分到不同机房。当机房出现故障时将读写流量都切换到另一个机房
应用层需要将流量转发到异步任务中，在处理读请求时从数据层获取数据，并做限流和服务降级兜底策略
异步任务这里需要将数据进行聚合，然后更新数据和刷新缓存
数据层使用三级存储，Mysql + Redis + 本地缓存。Redis做缓存，本地缓存用于缓存热点数据，通过最小堆算法将热点数据加载到本地缓存。当缓存不可用时，通过对Mysql限流最大限度为用户提供服务，触发限流的请求使用兜底数据返回。在更新存储时一定要进行重试，直到写入成功为止，具有最终一致性。然后数据也应用多地备份，异步进行数据同步
在数据量较大时需要进行分库分表，对于水平分表而言，可通过按点赞者和被点赞者进行分库，保存两份数据，在写入时进行双写即可
# 12.分库分表策略
答案
对于水平分表时，通过选定分片键，可采用哈希或区间进行分段
通过对分片键进行哈希，问题是当需要进行扩容时需要进行rehash，但可以采用同步双写更新增量数据，然后使用脚本迁移旧库中的存量数据。但是每次扩容需要迁移全部的数据，迁移成本较大，可以使用一致性哈希算法，这样迁移的成本更小，但是会存在节点分配不均的问题，但是可以使用虚拟节点来解决分配不均的问题
通过对分片键的值域范围进行分段，问题是可能存在分配不均的问题，某些值域的访问比较频繁，某个值域的数据比较少。对于该问题可以进行哈希取模来解决
对于查询非分片键的记录时，可以通过建立映射表来查询，或者将数据冗余一份到ES中，通过ES进行查询。也可以通过基因法来实现，本质上是利用取模，要求表的数量必须是2的次幂，因此x%2^n等价于获取x二进制的后n位。因此我们对分片键求出%2^n的结果作为基因数，然后将基因数拼接到需要查询的键上，这样可以使得同一个分片键的所有非分片键都落在一个表上。查询的时候求后n位即可知道在哪个表上
分库主要是解决单数据库支持的连接数有上限并且磁盘空间有限，因此需要分库
分表主要是解决单表数据量过大时查询速度下降和热冷数据问题
# 13.短链系统设计
答案
方案1：通过哈希算法
将一个长链通过哈希算法生成短链，每次去数据库中查找是否存在相同的短链，如果存在则给当前的url添加上特殊字符，然后继续计算，直到不冲突为止。因为哈希冲突的概率特别低实际效率会很高。但如果请求量上来，我们可以通过布隆过滤器进行优化，对于不在布隆过滤器中的一定不存在于数据库中。然后我们还可以通过多级缓存来进行优化
方案2：通过自增ID实现
可以通过数据库自增ID来实现，当然这在并发量太大的情况下是扛不住的。但是我们可以实现多个发号器。
1.每个发号器负责一段ID。整体ID由多个发号器获取的ID组成
2.每个发号器负责不同的范围的ID，然后将请求负载均衡到每个发号器上
3.每个发号器有一个唯一前缀，通过唯一前缀和分配的ID来实现