当前位置：首页 > news >正文

JAVA后端面经总结——应用类

news 2024/5/14 13:04:04

JAVA后端开发知识总结（持续更新…）

JAVA后端面经总结——应用类

文章目录

JAVA后端面经总结——应用类
一、方法总结
- 1.1 限流算法
- 1.2 亿万级别数据的处理
二、应用类
三、概率论
四、智力题
参考文档

一、方法总结

1.1 限流算法

固定窗口（计数器）：Redis的k-v，incr命令。常用于QPS限流和统计总访问量。
滑动窗口：TCP思想（左右指针固定边界，point指针确定当前的流量）。将时间周期分为N个小周期，分别记录每个小周期内访问次数，并且根据时间滑动删除过期的小周期，即每过一个小周期，它会右移一个小格。
漏桶（可以队列实现）：
令牌桶：可以较好地应对瞬时流量，流量也可以瞬时传输，面对突发流量可以应用。

限流算法与设计思路
【算法设计】限流算法
常用4种限流算法介绍及比较
面试必备：4种经典限流算法讲解——解决临界并发问题

计数器的问题——临界值的并发

一秒只允许四个请求，前10ms两个请求，第二个10ms两个请求，此时按理，第三个10ms来的一个请求，要等这一秒结束。但是对于滚动的时间窗口，第五个请求在第一个10ms后，变成了第三个请求，可以执行了，怎么本质上解决？

利用滑动窗口解决。

有多个 IP 请求过来，如果某个 IP 超过了 10次调用/5秒，就限流。使用 MySQL/Redis 实现，使用内存来实现，分别给两个解决方案。

内存实现：
每个 IP 对应一个大小为 10 的循环队列，队列里面存储请求的时间。比如现在队列满了 10 个，第 11 个请求来了，就拿第 11 个请求的时间减去第一个请求的时间，如果小于等于 5 秒，就拒绝第 11 个请求，如果大于5秒，就删掉第一个请求，再把第11个请求加入循环队列。
用个 HashMap 来存令牌，key 就是 ip，value 就是对应的令牌，每次放的时候就放所有 ip 的令牌，频率为 10次调用/5秒。
滑动窗口，一个 ip 对应一个滑动窗口类
一个 IP 对应一个令牌桶线程

Redis 实现：
使用 zset 实现滑动窗口，key 是 ip，value 是请求次数，score 是时间，可以使用 zrangebyscore key startScore endScore 查看局部分数范围内的值，可以用来统计滑动窗口中的请求次数。
直接redis incr命令：固定窗口。

QQ在5分钟内接收几百万的登录请求，QQ用户好几亿，怎么保证每个用户在5分钟内只能登录一次，用内存实现

1.2 亿万级别数据的处理

亿万级数据处理的高效解决方案
海量数据处理 - 10亿个数中找出最大的10000个数（top K问题）

时间

Hash统计
堆/快速/归并/桶排序
堆(Heap)：海量数据前n大，并且n比较小，堆可以放入内存
Trie树
外排序
Bit-Map
Bloom Filter
双层桶划分：第k大，中位数，不重复或重复的数字，只分不治
数据库索引
倒排索引（Inverted Index）

空间

分治
Hash映射：把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。

外排序

所谓内排序就是可以在内存中完成的排序，比如快速排序，堆排序，归并排序等。
外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换。
多路归并排序：将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序，然后，对已经排序的子文件进行归并排序。对于两两归并排序，磁盘IO太多，需要优化。
多路归并——堆：将每一个小文件的第一个数取出，即每一个小文件里的最小数，对这些数进行归并排序，将这些数里的最小数字写入大文件的第一行，此即整个大文件里的最小数字。继续前面的循环，直到所有小文件都遍历完成。

如何从一天的超过10G的记录IP地址的日志中，较快地找出登录次数最多的一个IP？

分而治之/hash映射 + hash统计 + 堆/快速/归并/桶排序：先映射，后统计，最后排序。
内存受限，只能把大文件化成(取模映射)小文件；
采用常规的HashMap(ip，value)进行频率统计；
统计完了之后，只需对n个进行排序(可采取堆排序)，得到次数最多的IP。

如何在10GB 的日志中找到一个出现两次的日志记录

如何读取多个文件，并统计单词出现的频率

分治 + Hash映射 + HashMap

给定一个2亿数字的数组，如何判定某个数是否在集合中，假设数组中没有重复元素，且数字大小在5亿以内。

HashSet可以，还有一种方法
0\1表示每个数字有或没有 + 查找：32b一组桶排序
具体答案

一个日志文件，十亿个账户，及其上线下线时间，求每秒在线人数

数组：24*3600；
位图，x&(x-1)

5.9 亿个 IP 地址，都为白名单，判断某个 IP 是否在该白名单中，内存管够

HashMap、布隆过滤器、桶排序，看在哪个桶的范围内，桶内二分查找；

如果白名单是动态的呢，怎么维护布隆过滤器?

一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。

A,B两个文件，各存放50亿条URL，每条URL占用64B，内存限制4G，求A,B文件URL交集。如果是三个乃至n个文件呢？

布隆过滤器，但是有误差。
对A分而治之/hash映射，然后根据所取得的值将url分别存储到1000个小文件；对B同等操作；
所有可能相同的url都在对应的小文件，不对应的小文件不可能有相同的url，只要求出1000对小文件中相同的url即可。

给定一天的订单。每个订单两个属性，下单时间和送达时间，单位是秒，计算下单的高峰期？

桶排序的思想，只要把当天订单的下单时间全部转成时间戳，然后创建一个24x3600s的数组，然后再对应的位置上进行计数。最后遍历数组找出最大的值。

100w个数中找最大的前100个数——topK问题

数据量太大，先分治为n个小文件，分别找出100个；
再用堆选取，避免了大量的磁盘IO。
Hash映射可以去重。

100w个数中找最大的前100个频率——topK问题

数据量太大，先分治为n个小文件，分别找出100个；
Trie树或Hash统计每个小数据集中的query词频；
再用堆选取，避免了大量的磁盘IO。

寻找热门查询，假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，查询字符串中统计最热门的10个查询，要求使用的内存不能超过1G。

考虑去重后一次性存入内存进行处理
直接上hash统计，然后排序：HashMap + 堆

有一个1G的文件，每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词

分而治之/hash映射 + HashMap统计 + 堆/归并排

10个文件，每个1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复，即可能不同文件有相同query,要求按照query的频度排序.

Hash映射：按照hash(query)%10将query写到另外10个文件保证相同query在同一个文件中。
分而治之/hash映射 + HashMap统计 + 堆/归并排

1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？

1.去重也可以用Trie树。

2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数

先分：整数个数为2^32，可将其划分为2 ^8个区域，比如用单个文件代表一个区域；
然后将数据分离到不同的区域，然后不同的区域利用bitmap就可以直接解决了；
将bitmap扩展一下，用2bit表示一个数，0表示未出现，1表示出现一次，2表示出现2次及以上；
在遍历这些数的时候，如果对应位置的值是0，则将其置为1，如果是1，将其置为2，如果是2，则保持不变。

有一个IP地址库，假设有几十万条ip，如何判断某个ip地址是否在这个库中？

分治法，将ip地址根据前三位分成256份，然后看这个ip地址对应的网段，只比对这个网段里面是否有这个ip，当然还可以继续分下去，根据数据量来决定分成多少份。
位图，将每一条ip对应位图中的一个位，2^32次方(42亿多)个数据只需要512M空间。可以实现O(1)的时间搜索，O(n)的时间存储。

5亿个int找它们的中位数

桶排序：将int划分为2^16个区域（如果5亿个数全等，则一个桶需要表示数5亿），然后读取数据统计落到各个区域里的数的个数，之后根据统计结果就可以判断中位数落到哪个区域，同时知道这个区域中的第几大数刚好是中位数。
然后第二次扫描只统计落在这个区域中的那些数就可以了。

在一个文件中有 10G 个整数，乱序排列，要求找出中位数，内存限制为 2G

整数用32bit，要表示10G个整数，最少需要一个64位的数据空间（10G = 5 * 2^31 > 2^32 )。
2G的内存，能够表示多少个64bit，就能分多少个区间（一个区间就表示一个64bit的数据空间），区间数位：2G / 64bit = 256M 个区间。
求区间表示范围：32bit的整数最大值为2^{32-1,所以区间的范围是2}32 / 256M = 16，即0 ~ 15 ，16 ~ 31，32 ~ 47，…（总共256M个)。
遍历10G个整数，每读取一个整数就将此整数对应的区间+1。
找出中位数所在的区间，统计每个区间中整数的值，然后从第一个区间的整数值开始累加，当累加到5G时，停止。
再次遍历10G个整数，统计出现在区间[a,a+15]中每个值的计数，有16个数值，按照a到a+15排序。

有一个0-30000的随机数生成器。请根据这个随机数生成器，设计一个抽奖范围是0-350000彩票中奖号码列表，其中要包含20000个中奖号码。

将0-35万的区间分成35/3=12个区间，然后每个区间的长度都小于等于3万。
可以用题目给的随机数生成器来生成了，然后再加上该区间的基数。

已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数

每个数字对应一个bit位，用bitmap。

几亿条数据往数据库里面插入，比如日志信息该如何处理？面试官又说，如果同时插入大量的数据还是会插入到同一张表里面，如何避免？

分库分表，基于数据库更新 + 内存分配
？？？日志信息用消息队列

1亿个正整数,范围是0-42亿。求出现次数是2的数字，空间复杂度。

将bitmap扩展一下，用2bit表示一个数，0表示未出现，1表示出现一次，2表示出现2次及以上，3表示出现3次及以上。

一个5T的文件，里面全是id，1-10^9 ，如何计算不同id的个数？

思路一：哈希到不同的文件，再逐个文件内找不同的。
思路二：使用redis的HyperLoglog可以大致估算出不同id的个数。

二、应用类

Word单词拼写检错怎么实现

hashmap存储所有单词然后比较
前缀树

Redis主从部署，在写请求特别多的场景下，如何保证在从节点读到的数据不是脏数据？

给数据加上时间戳，然后在代码层面进行时间戳的比较，总之就是有点MVCC的味道。

短链接网址设计

《如何设计一个短网址系统》

短链接主要用来为长链接生成更短的别名，用户点击短链接会重定向到原来的长链接。
用户可以选择为其 URL 选择自定义格式的短链接，链接将在默认时间间隔后过期。
读任务比写任务繁重，也就是说重定向的请求次数要远多于生成短网址的请求次数。
api_dev_key (字符串)：注册帐户的 API 开发人员密钥，可以根据分配的配额限制用户，防止恶意请求。
一方面要存储大量的数据，另一方面，数据对象之间的关系非常简单，使用非关系型数据库是更好的选择。
算法设计：发号策略，给每一个过来的长地址，发一个号即可，小型系统直接用mysql的自增索引就搞定了。如果是大型应用，可以考虑各种分布式key-value系统做发号器，不停自增就行了。第一个使用这个服务的人得到的短地址是http://xx.xx/0 第二个是 http://xx.xx/1 第11个是 http://xx.xx/a 第依次往后，相当于实现了一个62进制的自增字段即可。
《短 URL 系统是怎么设计的？》

设计题：设计一个图书馆借书系统。

主要问的是数据库表和 Java 类的设计，首先想了下有什么需求，再根据需求设计表即可

设计题：登录系统设计

主要说了 cookie/token 方式识别用户，密码 hash 并加盐后存储等等

设计一个用户登录页面, 保证用户长时间保存登录状态需要做哪些

洗牌程序的合法性判断

《洗牌程序》
元素洗牌后的位置与洗牌前无关，第一点是第二点的充分条件，因此测试函数只需要测第一点就够了。
测试方法为重复执行洗牌函数，统计每个位置每个元素出现的次数。
这样测试函数会输出一个矩阵，如果不考虑针对性捣乱情况的话，测试函数可以简化为计算每个位置的值的和，这个和的方差能够近似体现洗牌函数的正确性。

洗牌程序

Knuth-Durstenfeld Shuffle算法
每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字。

《浅谈洗牌算法（面试题）》
保证每个数出现在任意一个位置的概率相同，也就是说在n!个的排列中，每一个排列出现的概率相同。

如果想在整个项目启动之前，初始化一个全局的线程池，或者打印日志，要怎么实现

？？启动过程中实现 Aware 接口（ApplicationAware提前获得bean?）
@Configuration + @Bean；@ConfigurationProperties +@Component
BeanFactoryPostProcessor

分布式多个机器生成id，如何保证不重复?

用Redis生成ID，因为Redis是单线程的，也可以用来生成全局唯一ID。
可以用Redis的原子操作INCR和INCRBY来实现。
此外，可以使用Redis集群来获取更高的吞吐量，假如一个集群中有5台Redis，可以初始化每台Redis的值分别是1,2,3,4,5，步长都是5。
比较适合使用Redis来生成每天从0开始的流水号，如订单号=日期+当日自增长号，可以每天在Redis中生成一个Key，使用INCR进行累加。

数据库连接池怎么设计?

模拟线程池
限制连接池中最多、可以容纳的连接数目；
无空闲连接时，让客户一直等待，直到有空闲连接，或者为客户分配一个新的临时连接；
当客户不再使用连接，需要把连接重新放回连接池；
分core和max。

三、概率论

设计题：主要的问题是根据已知的概率分布每次随机选择一个/多个数。

解决思路是在区间 [0，1) 上，根据已知的概率分布确定每个点的位置，每次在 [0,1) 中随机出一个数，看这个数在哪两个点之间即可。

带权重抽奖：100万个人，100个奖品，每个人中奖倍率不同，抽完为止，每人最多中奖一次。

古典概型：基础中奖几率*中奖倍率，但是这样做对前面的人有优势.
几何概型：List表示线段，List中存对应人的id。

给定一个 0-4随机数生成器如何生成0-6随机数并验证？

核心是保证每个数的出现概率一致
采用n进制计数法
rand6() = {rand4() * 5 + rand4() }<=20 ? x/3 : loop

class Main{public static void main(String[] args) {int[] result = new int[7];for (int i = 0; i < 50000; i++) {int r = rand6();result[r]++;}for (int i = 0; i < result.length; i++) {System.out.println("num:" + i + " times: " + result[i]);}}public static int rand4() {// 大于等于 0.0 且小于 1.0double rand = Math.random() * 5;return (int) rand;}// 0 ~ 6 实际 7 个数字public static int rand6() {int result = rand4() * 5 + rand4();do {result = rand4() * 5 + rand4();} while (result > 20);return result / 3;}
}

四、智力题

一个由7个金砖组成的金条，有一个工人每天需要给他一块金砖，大金条最少需要切多少次？（雇1个人工作7天，有1根金条可以分成7份，只能切2刀，如何保证每天都得到1份金条）

答案解析
2刀 —> 1：2：4
可以向工人要回

只有两个无刻度的水桶，一个可以装6L水，一个可以装5L水，如何在桶里装入3L的水?

先将5L的桶装满，将5L的桶的水倒入6L的桶中。这时5L的桶是空的，6L的桶中有5L的水。
再将5L的桶装满，倒入6L的桶中。这时5L的桶有4L的水，6L的桶是满的。
将6L的桶中的水倒掉，5L的桶的水倒入6L的桶中。这时5L的桶是空的，6L的桶中有4L的水。
将5L的桶装满，倒入6L的桶中。这时5L的桶还有3L的水，6L的桶是满的。

1000瓶药水里面只有1瓶是有毒的，毒发时间为24个小时，问需要多少只老鼠才能在24小时后试出那瓶有毒。

log2 1000，最少10只，因为10位二进制足够表示1000
老鼠的编号，就相当于一个二进制bit位. 喝和不喝代表1喝0
对于二进制占位，死亡和存活的排列组合就是唯一的
从左到右，死了的小白鼠贴上标签1，没死的贴上0，最后得到一个序号，把这个序号换成10进制的数字，就是有毒的那瓶水的编号。

家里有两个孩子，一个是女孩，另一个也是女孩的概率是多少？

二分之一
已知家里有两个孩子Ａ和Ｂ，其中一个是女孩，关键问题就在其中一个是女孩这句话上。
如果理解为这个是指定了一个孩子为女孩，例如Ａ为女孩，那么Ｂ也是女孩的概率显然为二分之一。
如果理解为Ａ或Ｂ有一个孩子是女孩，问另一个孩子也是女孩的概率，这就是三分之一了。因为两个孩子的性别只有男男、男女、女男、女女四种组合，男男被排除了，剩下三种组合均符合题意，所以是三分之一。

一共12个一样的小球，其中只有一个重量与其它不一样(未知轻重)，给你一个天平，找出那个不同重量的球？

分治
将12个小球分为三组（因为分成两组不能找到重量不一样的球在哪组），为A组、B组、C组。
将三组球分别两两称重，找到重量和另外两组不同的那一组（只要有两组可以使天平平衡，重量不一致的球必然在第三组）。假设坏的球在C组。
将C组的球分成两组C1和C2，每组两个球，这时从A组和B组里找到两个正常的球，分别和C1和C2去称，天平不能平衡说明重量不一致的球就在哪组。假设在C1。
将C1组的球分别和正常的球去称，天平不平衡时就能找到重量与其他不一致的球。