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

maxStack： 3 x x 1 x 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包里面包含着两个进程（或者说上层应用）的数据