观棋不语

02-28 22:56 已编辑上海交通大学 Java

关注

字节-商业化-后端开发-日常实习-一面

八股

删除掉了部分项目相关

讲讲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){
	}
}

#面经#