7.27 字节跳动提前批二面-风控部门-后端

一面面经 https://www.nowcoder.com/discuss/457745?source_id=profile_create&channel=1009

1.乐观锁和悲观锁分别的应用场景，为什么竞争不大的时候乐观锁比较好

2.乐观锁的ABA问题

3.乐观锁还有什么其他问题

乐观锁只能锁一个变量

4.乐观锁为什么只可以控制一个变量

扯到了数据库MVCC也是这种实现

5.MVCC和乐观锁有什么关系

乐观锁是一种锁算法思想，而CAS和MVCC是一种实现

6.多版本跟普通的锁有什么区别

多版本是乐观锁，普通的锁是悲观锁

7.项目问题，问我如何做的IP限流

我的实现思路是放在缓存，每次IP进来都去缓存里访问看看有没有存在此IP，如果存在且还没过期那就不放行，如果不存在或者已经到期就放行，这里其实是针对某一特定IP的频率限制。

8.如果要实现更加广义上的，比如一秒钟放行1k请求，怎么做

这题我会，我说可以用桶算法去处理，但是具体的桶算法原理就不敢再扯了。

算法题1：实现一个栈，要求如下：

(a) 提供基本的push和pop方法，时间复杂度O(1)；

(b) 提供一个queryMaxValue方法用于查询栈里的最大值，时间复杂度O(1)。

这题没有做出来，面试官也没有给我提示，感觉没了呜呜呜。。。。

这道题的正解是用两个栈来做，一个当做正常的栈来操作，一个用来保留最大值，例子如下

dataStack： 3 4 5 1 2 1

算法题2：给定一个n * m的矩阵a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

这题第一眼以为要用DP来做，一想到要用DP我都想直接放弃了，但是这样给面试官印象太差了，就硬着头皮上，发现可以用BFS（误，应该是DFS）做，直接code。

public class Main {
    private static int n = 5;
    private static int m = 5;
    private static int[][]a = new int[n][m];
    private static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        a = new int[][]{{1,2,3,4,5},
                   {4,5,5,9,9},
                   {2,1,1,9,9},
                   {2,1,1,9,9},
                   {2,1,1,1,1}};
        bfs(0,0,0);
        System.out.println(min);
    }
    public static void bfs(int i,int j,int value){
            //目前为止的路径值
            value += a[i][j];
        if(i<m-1){
                //发现右边可以走就走右边
               bfs(i+1,j,value);
        }
        if(j<n-1){   //发现下边可以走就走下边     
                bfs(i,j+1,value);  
        }
        if(i==m-1 && j==n-1){
                  //最后所有路都会到右下角的点，比较出最小值
                  if(min>value){
                      min = value;
            }
        }
    }
}

这里面试官说我的算法看起来怪怪的可能会有问题，然后就写了case测试发现没有问题哈哈哈哈哈哈哈，面试官虽然不想服输但是两个case都通过了就没问题了哈哈哈哈哈哈哈。

9.操作系统进程调度算法

10.进程的状态有哪些

11.进程之间同步的机制

提到了锁

12.那么进程之间的锁放在哪

我说锁作为一种资源，应该不属于任何一个进程，而是单独的一个内存区域

13.那么我进程怎么去获取这个锁呢

它在内存区域就会有地址啊，作为一个资源进行调度是要提交给内核的，那么内核肯定知道你的地址。

这里被面试官打断了。。而且上面的其实是我乱吹的哈哈哈哈，所以我不知道是不是我吹错了。

14.TCP的粘(niān?zhān?)包

大概就是一个TCP包里面包含着两个进程（或者说上层应用）的数据

15.为什么要这么设计

为了提高带宽利用率，数据从应用层到数据链路层的过程中会封装上一层又一层的协议头信息（http、tcp、ip），那么你有效信息其实比例并不大，当你使用粘包而不是分包的时候就相当于少掉了一次头部信息，提高带宽利用率。

18.索引有什么数据结构