字节-商业化-后端开发-日常实习-一面
八股
删除掉了部分项目相关
- 讲讲IO多路复用？select/poll/epoll的差别?
- 动态线程池技术？如果让你来实现一个线程池，会考虑哪几部分？
- Kafka的使用场景？如果出现了消息堆积如何优化？
算法
1. 八皇后
总结
问的问题很少。算法折腾了半小时。
八股答的很糊，说的很多但是可能术语不够精确。
简历上写了埋点监控，但是被问起来场景，为什么要用这个方法，数据落下来怎么用，如果重新设计怎么设计，被问懵了。
复盘
IO多路复用
什么是IO多路复用？
多路：指的是多个socket网络连接；
复用：指的是使用一个线程来检查多个网络连接（或者说文件描述符）的就绪状态。
好处是：解决了单线程处理多个IO操作时的阻塞问题。在需要处理大量并发IO的情况下，可以提升程序性能和响应速度。
常用的多路复用技术？
select -> poll -> epoll
select:
提供了一种单线程处理多个IO操作的方式。
流程如下：
- 应用程序调用select函数，参数中传递待监听的文件描述符集合，进入阻塞。
- 内核将这些文件描述符加入到内核维护的等待队列，监听其IO状态。
- 当有文件描述符准备好IO操作，内核将其标记为可读或可写。
- 内核将这些准备好的文件描述符信息返回给应用程序，select返回。
- 应用程序接受返回后，遍历文件描述符，检查哪些文件描述符准备好了IO操作。
- 应用程序根据文件描述符状态进行IO操作，完成后调用select等待下一次IO事件。
存在的问题：
问题一：首先是用户态和内核态之间拷贝的开销，两次copy，从用户态->内核态，因为需要告知内核态需要管理哪些文件描述符，这个无法省。但是内核态->用户态，明显只有部分fds（文件描述符）发生了事件，却做了一次整体拷贝。并且，用户态只知道发生了事件，但是不知道是哪些fds，所以还要重新遍历，时间复杂度是O(n)。
问题二：单个进程/线程能监听的最大连接数，在内核中写死了，32位：1024；64位：2048。
poll
解决了问题二，在调用时，可以指定数组大小，而非select中固定大小的bitmap，该数组的大小仅受限于系统资源。但这个并非关键问题。
epoll
有几点改进：
1.IO事件发生后放入就绪链表，避免了用户态需要遍历来确定事件的处理；
2.只有在用户态主动调用epoll_wait时才执行拷贝，而非一旦发生IO事件即拷贝，减少了用户态和内核态的切换次数，提高了效率。
另外， 红黑树的结构，便于查询、插入、删除，时间复杂度都是O(logn)。、
MQ中的消息堆积问题
出现消息堆积的原因
1.生产端数据激增
2.消费端消费能力不足或挂掉
3.kafka中数据倾斜
解决方法：
1.从生产端入手：如果是过时无效的数据直接清空，拉到latest；如果有效，但是不要求消费顺序，可以直接消费最新的数据，lag部分的数据用离线补偿。
2.从消费端入手：
- 增加消费者的数量。
- 增加分区的数量。（增加分组时，同步要增加一组内的消费者的数量）
- 加强消费者的消费能力：优化消费逻辑，批量消费，异步消费
3.数据倾斜问题解决：根据业务重新设置key，使其均匀。
八皇后
非优解，写的麻烦，仅为理思路
不考虑输出的形式，现在需要使用回溯去遍历所有的可能。
主干函数如下：
/**
tmp: 用于记录每行所选定的y轴坐标的index，x轴坐标隐藏在数组下标中了
x：当前在处理第几行
n：处理的是几皇后问题
**/
public void backtrack(List<Integer> tmp, int x, int n){
if（tmp.size() == n){
//当tmp中元素数量为n时，说明每行的皇后都找到了合适的位置。
//res是一个全局变量，用于记录结果，先不考虑他。
res.add(new ArrayList<>(tmp);
return;
}
//对于当前第x行的皇后，要考虑0~n-1的所有可能的y轴坐标
for (int y = 0;y < n;y++){
//尝试坐标(x,y),如果是个合法位置，则考虑x+1的摆放
if (isValid(tmp, y){
tmp.add(y);
backtrack(tmp, x+1, n); //进入下一行
tmp.remove(tmp.size()-1);
}
}
}
其中有些问题，比如如何判断当前皇后位置是否合法？
public boolean isValid(List<Integer> tmp, int y2){
//当前的坐标实际上是（tmp.size(), y2），点还没放进tmp，所以不用-1
int x2 = tmp.size();
for (int x1 = 0; x1 < tmp.size(); x1++){
int y1 = tmp.get(x1);
//肯定不会同行的，同列或者斜线即为不合法，斜线可以看x,y轴增量是否一致
if (y1 == y2 || Math.abs(x1 - x2) == Math.abs(y1 - y2)){
return false;
}
return true;
}
}
现在问题已经解决了，收个尾。
目前给出的结果实际上是 [[0,1,2,3,4],[1,0,4,2,3],...],即给出y轴的坐标，题目要求给出的形式是
[ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]
写个函数改改
public List<List<String>> visualize(int n){
List<List<String>> finalRes = new ArrayList<>();
for(List<Integer> item : res){
List<String> tmp = new ArrayList<>();
for (int y : item){ //第y个为Q
tmp.add(".".repeat(y) + "Q" + ".".repeat(n-y-1));
}
finalRes.append(tmp);
}
}
整体流程如下：
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
backtrack(new ArrayList<>(), 0 , n);
return visualize(n);
}
public void backtrack(List<Integer> tmp, int x, int n){
}
public boolean isValid(List<Integer> tmp, int y2){
}
public List<List<String>> visualize(int n){
}
}
#面经#
