面试复盘 | 字节提前批面试（已OC）

一面（20210726，17:00~18:00）

一、算法

1、二维矩二进制矩阵，0能构成的最大正方形

力扣：剑指 Offer II 040. 矩阵中最大的矩形

二、项目介绍

1、分库分表策略

使用用户uid进行映射，将用户的数据存储在映射到的库表中

2、热点数据并发读写

从业务考虑，当前分库分表策略能hold得住。随着后续访问量增加，拓展的话，需要进行数据迁移

三、网络

1、time_wait

TCP四挥手中，客户端最后一次发送消息之后，需要等待两个MSL时间，确保服务器能收到最后一个报文，期间客户端就是处于time_wait状态

2、网络拥塞

滑动窗口机制，慢开始、拥塞避免、快恢复、快重传

3、窗口的作用

网络拥堵时，限制发送到网络的报文数量

四、数据库

1、mysql分页查询和limit、offset原理和优化

讲了数据库底层原理，B+树，但是优化这个没有答出来

2、脏读和幻读

脏读：事务之间相互干扰，一个事务读取到另一个事务未提交的的数据；幻读：一个事务读取时，另一个事务添加了数据，造成前一个事务读取到新的数据、总数不一致（幻读针对的是一整批数据，不可重复读是针对一条数据）

3、MVCC

首先MVCC的作用是用于实现事务并发读写；然后介绍快照读和当前读；然后介绍实现原理是隐式字段，两种undolog日志，ReadView。

二面（20210806，17:00~18:00）

一、项目经历

1、没有自我介绍，直接就从实习的项目说起

2、项目中分库分表策略（答案同一面）

3、如何扩容，成本如何（答案同一面）

4、使用用户id分库分表，跨账号查询怎么解决

按照id去查询，然后合并结果

5、跨账号查询中实现分页查询算法

延伸到合并两个有序列表，再延伸到合并m个有序列表中分页的时空复杂度

6、合并有序列表，引申到数据结构根堆及其时空复杂度

二、算法题

1、给定一个数组，里面存储linux的目录，".."表示上一级，"."表示当前目录，统计不同路径的个数

时间关系，没有统计个数，仅对目录进行转换

import java.util.Stack;

public class Main {
    public static String solution(String str) {
        String[] strArr = str.split("/");
        Stack<String> stack = new Stack<>();
        for (String strItem : strArr) {
            if (strItem.equals(".") || strItem.equals("")) {
                continue;
            }
            if (strItem.equals("..")) {
                if (stack.isEmpty()) {
                    continue;
                } else {
                    stack.pop();
                }
            } else {
                stack.push(strItem);
            }
        }
        String result = "";
        while(!stack.isEmpty()) {
            result = stack.pop() + "/" + result;
        }
        return result;
    }
    public static void main(String[] args) {
        System.out.println(solution("/root/a/b/d/../c"));
    }
}

三、反问

1、电商系统的特点？

业务知识可能比较繁杂，特别是涉及金额的计算部分

三面（20210812，17:00~18:00）

一、自我介绍

1、教育背景+实习经历

2、着重介绍实习项目，设计分布式、数据库分库分表、数据筛选、并发

二、实习项目拓展

1、实习项目中数据量大小

从同步数据量聊到如何做数据筛选，如何减轻数据库压力、减少对当前业务的影响。

2、项目中分布式锁如何实现

利用Redis实现，加锁时在Redis中写入键值对，写入成功则获得锁；解锁时删除键值对。锁设置有效期为五分钟，数据同步平均耗时半分钟，考虑热点数据+数据库延迟，分布式锁有效期为5min。

3、数据库扩容怎么做？

首先要数据迁移，将新的数据迁移到新的库表，这个工作联合运维一起实施。当前程序支持数据库扩容，所有实例、库表信息都由配置文件引入，修改配置文件即可，无需更改业务代码。

4、并发考虑

考虑数据库实例级别开启多线程处理，不在数据库一级别开启线程，减少数据库压力

三、算法

1、 10个城市编号0~9，城市之间移动只能前后移动（比如5只能到4或者6），10个城市构成一个环，从0可以到9，从9也可以到0。从任意城市X出发，途径N个城市，问有多少途径？

public class Main {
    //dp + 递归
    static int solution(int X, int N){
        int result = recur(X, X + 1, N);
        return result * 2;
    }

    static int recur(int X, int Y, int N) {
        if (N == 0) {
            if (Y == X) {
                return 1;
            } else {
                return 0;
            }
        }
        //处理循环
        int pre = Y - 1;
        if (pre < 0) {
            pre = 9;
        }
        int next = Y + 1;
        if (next > 9) {
            next = 0;
        }
        return recur(X, pre, N-1) + recur(X, next, N-1);
    }
    public static void main(String[] args) {
        System.out.println(solution(0, 3));
    }
}