[TOC]

全部写的是技术面试，hr面就没写了

## 1. 字节跳动
字节面试提前和内推人沟通好了，给安排6.23下午2点到5点面完技术面

### 1.1 一面（60分钟）
面试时间：6.23 14:00 - 15:00
**1. 自我介绍**
这一部分提前要准备好，主要是讲自己擅长什么技术，负责过哪些项目，抓住重点，什么平时的兴趣爱好就不要说了，面试官不会care的

**2. 用过哪些Java容器**

**3. ArrayList和LinkedList特点及各自应用场景**

**4. 说下TreeMap和LinkedHashMap**

**5. TreeMap怎么按照自己想要的顺序排序**

**6. 说下HashMap**

**7. ConcurrentHashMap怎么实现的，1.7和1.8分别说下**

**8. ConcurrentHashMap怎么取的size值**

**9. 一个非常多元素的HashMap，rehash非常耗时，所以需要在它rehash过程中还能get、put，你有什么解决方案或者思路，谈谈你的理解**
这题我一开始没了解面试官说的什么意思，然后扯了很多相关的东西，比如：
针对大容量，带参初始化，避免频繁扩容
ConcurrentHashMap是fail-safe容器，遍历时会在副本上遍历，后续的写操作对当前遍历不可见

然后面试官又说那这个数据量特别大，rehash很耗时怎么办，还在rehash后面的get、put怎么办呢？
我说可以借鉴Redis的渐进式hash，hash操作分摊开

然后面试官说正在rehash，这时get元素怎么取值、put元素怎么插入？
我说在ConcurrentHashMap中当另一个线程put元素时，发现当前状态为扩容时会协助其扩容，这样提高性能

面试官说你不一定要去想已有的实现，可以自己想想有什么方案
我说由于正在rehash，比如正在从16扩容到32，那么对输入key进行两次hash，分别定位扩容前和扩容后的table索引位置，然后再在链表上遍历

**10. 怎么防止恶意请求刷接口**

**11. 说下ES的倒排索引**

**12. 那ES怎么切词的呢，有写过切词插件吗**

**13. 你在项目中用Redis的场景**

**14. 说下Redis有哪些数据类型**

**15. 说说你在项目中怎么用的这些数据类型**

**16. 一次请求拿出来所有的数据有什么问题，那怎么改进**
Redis单线程阻塞后面请求，类似线上服务不要执行keys *，可以分批取数据

**17. Redis怎么分片的**

**18. Redis的删除策略**

**19. 写代码，很简单的斐波那契数列**
面试官后面跟我说一般前面回答的好，算法题就不会为难你的，如果你前面答的一般，就需要难的算法题来找你的亮点了
遇到这些简单的算法题一定不能大意，这种写出瑕疵了会非常的减分，各种边界比如传的参数小于0可以抛异常，还有注意命名规范
面试写算法题要多和面试官交流，有的面试官故意不把题目说清楚，等着你去问，考察你的沟通交流能力，不要上来不交流就蒙头写代码

**20. 手撕代码，leetcode98验证二叉搜索树**
```
private List<Integer> res = new ArrayList<>();

public boolean isValidBST(TreeNode root) {
    inorder(root);
    for (int i = 1; i < res.size(); i++) {
        if (res.get(i) <= res.get(i - 1)) return false;
    }
    return true;
}

private void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    res.add(root.val);
    inorder(root.right);
}
```
写完和面试官聊了聊优化点，其实可以不用全部中序遍历完再判断，不然树比较大的话性能不够好

**21. 写SQL**
一个video表，里面有三个字段user_id、video_id、start_time
表里面的一行记录表示的是某个user在在某个time看了某个video
要求：今天看不同视频数量超过100个的用户id的前三名
```
SELECT user_id, count(distinct(video_id)) as c
FROM video
WHERE start_time = '2020-6-23'
GROUP BY user_id
HAVING c > 100
ORDER BY c DESC
LIMIT 0, 3
```
SQL渣渣，自己很虚也不知道写的对不对，面试官说没什么问题

**22. 你有什么想问我的吗**

面试官夸我基础扎实，挺开心，这些天的复习刷lc总算没有白费

### 1.2 二面（60分钟）
面试时间：6.23 15:00 - 16:00
**1. 自我介绍**

**2. 为什么还不到一年就出来看机会了**
得不到成长，有一些重复性的工作，注意不要说前东家的坏话

**3. 你希望你处于一个什么样的工作环境**
做的事有挑战性，周围都是优秀的人push自己更快的成长

**4. 你的职业规划**
计划赶不上变化，短期三年内主要是稳扎稳打学技术，提高实战能力，提升快速把业务抽象成代码的能力，拓宽技术广度，部分技术深度达到top

**5. 怎么根据0-5随机函数得到0-8随机函数**

**6. 缓存和DB之间怎么保证数据一致性**
缓存预留模式
读操作：先读缓存，缓存没有的话读DB，然后取出数据放入缓存，最后响应数据
写操作：先更新DB，再删除缓存
为什么是删除而不是更新呢？
原因很简单，复杂场景下缓存不单单是DB中直接取出来的值，此外更新缓存的代价是很高的，频繁更新的缓存到底会不会被频繁访问到？可能更新到缓存里面的数据都是冷数据，频繁失效，所以一般用到再去加载缓存，lazy加载的思想

先更新DB，再删除缓存的问题，如果更新DB成功，删除缓存失败会导致数据不一致
所以一般是先删除缓存，再更新DB

还是有问题，A先删除了缓存，但还没更新DB，这时B过来请求数据，发现缓存没有，去请求DB拿到旧数据，然后再写到缓存，等A更新完了DB之后就会出现缓存和DB数据不一致的情况了

解决方案：
更新数据时，根据数据的唯一标识路由到队列中，读取数据时，如果发现数据不再缓存中，那么把读取数据+更新缓存的操作，根据唯一标识路由之后，也发送到相应队列中。一个队列对应一个工作线程，线程串行拿到队列里的操作一一执行

带来的新问题：
可能数据更新频繁，导致队列中积压了大量的更新操作，读请求长时间阻塞，所以要压测

**7. 延时消息队列怎么设计**
Redis的zset

**8. zset做延时队列会有什么问题**
死循环轮询耗时

**9. zset区间查询怎么做的，时间复杂度多少**
底层跳表，lgN的查询，定位到起始位置顺序遍历即可

**10. 你最擅长的技术有哪些**
Java的集合、并发、虚拟机
MySQL和Redis的底层原理

**11. 说下索引**
二八原理、提升读性能牺牲写性能的数据结构
一个索引对应一颗B+树
哈希、有序数组、二叉树查询的优缺点
那为什么不用跳表呢？

回表、索引覆盖

最左前缀
哪些字段适合建索引、索引缺点

**12. 为什么疫情期间要展示健康码，别人又不看，又不扫描这个健康码，那展示出来有什么用呢**
还有就是为什么你最近去了疫情多发区，再扫健康码就是红色的了

其实就是拿出健康码时你的位置信息会push上去

**13. 火车票区间查询怎么设计数据结构**
比如上海去武汉，途经南京、合肥
现在要快速查询出两点之间票的库存

我说借鉴跳表的思路可以实现

**14. 手撕代码，leetcode54螺旋矩阵**
```
public List<Integer> func(int[][] matrix) {
    List<Integer> res = new ArrayList<>();
    int row = matrix.length;
    if (row == 0) return res;
    int col = matrix[0].length;
    int k = (Math.min(row, col) + 1) / 2;

    for (int i = 0; i < k; i++) {
        for (int a = i; a < col - i; a++) res.add(matrix[i][a]);
        for (int b = i + 1; b < row - i; b++) res.add(matrix[b][col - 1 - i]);
        for (int c = col - 2 - i; (c >= i) && (row - i - 1 != i); c--) res.add(matrix[row - 1 - i][c]);
        for (int d = row - 2 - i; (d > i) && (col - i - 1 != i); d--) res.add(matrix[d][i]);
    }

    return res;
}
```

**15. 你有什么想问我的吗**

### 1.3 三面（60分钟）
面试时间：6.23 16:00 - 17:00
**1. 手撕代码，模拟微信群随机红包，输入金额、人数，返回金额数组；注意最小单位分；**
```
private static final float MIN_COUNT = 0.01f;

public List<Float> func(float total, int k) {
    List<Float> res = new ArrayList<>(k);
    if (total <= 0 || k <= 0 || k * MIN_COUNT > total) return res;

    Random random = new Random();
    while (k != 0) {
        if (k == 1) {
            res.add(total);
        } else {
            float cur = MIN_COUNT + random.nextFloat(total - k * MIN_COUNT);
            res.add(cur);
            total -= cur;
        }
        k--;
    }

    return res;
}
```
nextFloat好像不能传参数，不过这种白板写代码主要也是看思路

**2. 写SQL**
找出所有语文考及格但是数学没有考及格的学生
```
SELECT sno
FROM student s1, student s2
WHERE s1.sno = s2.sno
AND s1.subject = '语文'
AND s1.score = 
```
这题我写了一半，面试官说思路对的就不用写了

**3. 聊项目，项目中的难点、模块**
然后还问了一些依赖模块的底层实现

**4. 项目的数据量以及QPS能达到多少**

**5. 你最近主要学了什么，怎么学的**

**6. 看过哪些MySQL书，名字叫什么**

**7. 说下RPC，与HTTP的区别**

**8. 你来字节最想得到什么**
我说希望技术能突飞猛进，面试官说你别说的太虚，实实在在的说...

**9. 你有什么想问我的吗**

## 2. Paypal
### 2.1 一面（60分钟）
这一轮面我的面试官临时有事情，让他同事来面的
面试时间：6.17 9:30 - 10:30
**1. 自我介绍**

**2. 聊项目，说项目中的模块、技术难点**

**3. 聊下ES内部的一些机制**

**4. ForkPoolJoin相对于线程池的优点，及底层实现**

**5. 你最熟悉的技术有哪些**

**6. 详细说下CMS和G1收集器**

**7. CMS怎么处理垃圾碎片的**

**8. GC Root有哪些**

**9. String的intern方法有什么用**

**10. 说下公平锁、非公平锁，为什么非公平锁性能更高**

**11. 说下乐观锁、悲观锁**

**12. CAS的三个问题及解决方案**

**13. 手撕代码，字符串反转**
这面试官是临时客串的，所以就给了个很简单的题
```
public String reverse(String str) {
    if (str == null || str.length() == 0) return str;
    char[] chars = str.toCharArray();

    for (int i = 0, j = str.length() - 1; i < j; i++, j--) {
        char ch = chars[i];
        chars[i] = chars[j];
        chars[j] = ch;
    }

    return new String(chars);
}
```

**14. 你有什么想问我的吗**

### 2.2 二面（60分钟）
面试时间：6.18 14:30 - 15:30
**1. 自我介绍**

**2. 说下项目中的难点**

**3. 说下多线程中有哪些锁**

**4. volatile关键字原理**
无法保证原子性，对于i++这种读改写操作无法保证线程安全，可用Atomic

保证可见性，什么是可见性？
Java内存模型
内存屏障，读取前插入load指令，拉取主内存最新值到工作内存
写入后插入store指令，把工作内存最新值更新到主内存

保证有序性，禁止指令重排序
比如单例的双检锁模式
new对象分三步：分配内存、初始化对象、引用指向分配的内存
禁止第2步第3步重排序，保证单例正确

**5. 说下ES的底层实现**

**6. 大数据Spark、Hadoop、MapReduce有了解吗**

**7. 100万的数组怎么求最小的100个数字和最大的100个数字**
最大堆和最小堆
或者用快排的partition

**8. 手撕代码，leetcode378有序矩阵中第K小的元素**
```
public int kthSmallest(int[][] matrix, int k) {
    // 边界判断
    if (matrix == null || matrix.length == 0
            || k < 1 || k > matrix.length * matrix[0].length) return -1;

    // 容量为K的最大堆
    Queue<Integer> maxHeap = new PriorityQueue<>(k, Comparator.reverseOrder());

    for (int i = 0; i < matrix.length && i < k; i++) {
        for (int j = 0; j < matrix[0].length && j < k; j++) {
            if ((i + 1) * (j + 1) > k) break; // 根据数组特性剪枝

            if (maxHeap.size() != k) { // 堆没放满直接放进去
                maxHeap.offer(matrix[i][j]);
            } else if (maxHeap.peek() > matrix[i][j]) { // 堆放满了则比较插入元素与堆顶元素
                maxHeap.poll();
                maxHeap.offer(matrix[i][j]);
            }
        }
    }

    return maxHeap.peek(); // 最后堆里面的元素就是前k小的元素，堆顶元素为第k小
}
```

### 2.3 三面（60分钟）
面试时间：6.18 15:30 - 16:30
**1. 自我介绍**

**2. 手撕代码，leetcode15三数之和**
```
public List<List<Integer>> threeSum(int[] arr) {
    List<List<Integer>> res = new ArrayList<>();
    if (arr == null || arr.length == 0) return res;
    Arrays.sort(arr);

    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > 0) break; // 最小的数字都大于0直接break
        if (i > 0 && arr[i] == arr[i - 1]) continue; // 重复的数字跳过
        int l = i + 1;
        int r = arr.length - 1;

        while (l < r) {
            int sum = arr[i] + arr[l] + arr[r];
            if (sum == 0) { // 如果等于0 接着l++ r--找可能解
                res.add(Arrays.asList(arr[i], arr[l], arr[r]));
                while (l < r && arr[l] == arr[l + 1]) l++;
                while (l < r && arr[r] == arr[r - 1]) r--;
                l++;
                r--;
            } else if (sum < 0) l++; // 三数和小于0，左指针右移
            else r--; // 三数和大于0，右指针左移
        }
    }

    return res;
}
```

**3. leetcode121买卖股票的最佳时机**
三数之和写的比较快，这题就没让写了直接让说思路
数据作差预处理后和leetcode53最大子序和就是一道题

**4. JVM调优**
总体思路：不同的场景选择不同的参数（貌似是句废话，但就是这样）
比如线程竞争激烈的场景禁用偏向锁可以提高性能
CMS收集器可以根据需要调节触发GC的阈值

**5. 详细说说偏向锁、轻量级锁、重量级锁**
问：这几个锁是在什么地方有这样的概念
答：synchronized的锁升级过程
问：轻量级锁是怎么实现的
答：CAS实现的
问：CAS的什么
答：类似AQS的CAS state状态的过程
问：Mark Word的00、01、10、11放在什么地方
答：对象的对象头
问：什么对象
答：线程抢锁的对象
对于方法，抢占的是调用方法的对象的锁；
对于静态方法，抢占的是类锁，也就是JVM方法区中class对象对应的锁；
对于代码块，抢占的是synchronized括号里面对象的锁；
问：轻量级锁一般都是在线程竞争不激烈时用，那怎么判断线程竞争不激烈呢
答：...
问：锁怎么知道被哪个线程抢占的呢
答：owner区域，wait set区域
问：那偏向锁是怎么实现的
答：完全没有线程竞争的情况下，连CAS也不用了
问：你说偏向锁和轻量级锁线程ID都是在对象头的Mark Word中，那他们之间有什么区别呢
答：...

**6. 新生代配合CMS收集器用的什么收集器**

**7. CMS垃圾收集可以进行内存的整理，那内存整理的过程中对象地址发生了变动，JVM不可能去通知所有的引用这些对象的线程地址变了，那是通过什么方式保证了引用对象的线程还能找到这些对象的呢**
面试官说你不要局限于JVM是怎么实现的，就假设你遇到这个问题，你怎么解决
JVM里面有一张表，这张表记录了所有对象引用的地址和他被引用的地址，内存整理时会更新这张表，和操作系统里面的内存页，地址映射类似

**8. JVM里面会有几个栈**
几个线程就有几个栈，栈是线程私有的
问：栈里面存放了什么
答：栈帧
问：什么时间入栈，什么时间出栈
答：方法调用入栈，方法返回出栈
问：除了返回还有什么情况会出栈
答：抛出异常

面试官说我记得不错那个轻量级锁里面存放的锁的标记位其实是在栈里面，有个引用从对象头里面到栈里面

**9. 为什么synchronized演变成重量级锁后性能会下降**
偏向锁和轻量级锁都是在用户态
重量级锁实现
synchronized——monitorenter/monitorexit——lock/unlock——mutex lock
重量级锁需要到OS的内核态，很耗性能

问：那为什么要到内核态
答：保护OS，有的指令不能让用户执行
问：计算机通过什么来区分什么是高优先级的，或者说需要在内核态执行的
答：指令会分级，Intel的x86会有R0、R1、R2、R3指令等级

**10. 说说volatile关键字**
没办法保证线程安全
线程安全主要体现在三个方面：原子性、可见性、有序性
volatile只能保证可见性和有序性，保证不了原子性
比如i++，典型的读改写操作，volatile无法保证i的原子性，如果想要保证可以用Atomic代替
volatile主要保证可见性，可见性就是多个线程在同时修改一个变量时，A线程对变量的修改，B线程马上就能知道，有点像数据库里面脏读的那种感觉
底层实现：加入内存屏障，JVM的内存模型，线程有自己的工作内存，然后有主内存，被volatile修饰的变量被读取时，在读取前插入load指令，把主内存中的最新值拉到工作内存中，被写入时，在写入后插入store指令，把工作内存中的最新值刷新到主内存中
还可以保证有序性，也就是volatile修饰的变量会禁止指令重排序，典型的应用就是单例模式的DCL，singleton变量是需要被volatile修饰的，具体过程：
先判断singleton变量是不是等于null，然后synchronized锁住类锁，然后接着判断singleton变量是不是等于null，等于null则new出对象，但是new出对象是需要三个步骤的
第一，为对象分配内存
第二，对象初始化
第三，对象引用指向第一步分配好的内存
那其实不加入volatile关键字修饰的话，第二步和第三步是可以重排序的，可以乱序执行
那如果这样第一个线程过来时只执行到第二步，就是说还没有初始化对象就已经引用上了，第二个线程再过来时，因为已经有了引用，所以直接返回对象，但对象还没有初始化，所以用起来会报错

问：那指令为什么会重排序呢
为了执行指令更快，指令间没有相互依赖（读后写、写后写、写后读）的话，可以乱序执行

问：从硬件架构来说，CPU为什么会重排序
答：前面指令如果依赖的数据发生缓存缺失，那么需要去内存磁盘读取数据，这个过程很耗时，如果不乱序执行的话，后面所有的指令都会被block住，这样CPU的吞吐量上不去，所有会有乱序执行机制，让后面没有数据依赖关系的指令可以不用等前面指令执行完了再执行（IPC，指令级并发）

**11. kafka有没有用过**

**12. Redis怎么保证高可用**
主从机制，哨兵机制

**13. 你有什么想问我的吗**

### 2.4 四面（60分钟）
面试时间：6.18 16:30 - 17:30
**1. 为什么在百度不到一年就出来看机会**
所在的组加班多，没时间思考

**2. 如果你来了pp发现这边太闲了，学不到东西怎么办**
成长是个人的事情

**3. 那要是你来了发现这边加班也很严重怎么办**
可能外企对加班严重有误解，八点就算加班严重了

**4. 你这会都面了哪些公司**
我说字节、微信、蚂蚁
他说那看来加班还不算是个问题(手动狗头.jpg

**5. 面试官接着问我为什么想来我们公司**

**6. 面试官跟我说了不少他这么多年的工作体会**
工作要超出预期，面对简单无聊的需求也要保持热情
保持对技术的追求，三四年之后再后头看自己的竞争力在哪
有的人不知道怎么去提高
有的人只完成手头上的事情，不愿意去了解系统上下游各个模块的细节，不愿意去突破
在任何公司都不可能让你只做自己喜欢的事情
在所有公司，你想要做有价值的事情而不是修修补补的工作，都是要靠你自己挣的，你作为新人来到一个公司，必须要学会给自己挣信用分，不然凭什么一个好的事情会交给你做
必须足够专业，比如接触到k8s，那这块知识你都要熟悉，不能有什么含糊不清的地方，当然也不要走的太偏，需要学习的东西很多
要有野心，要有长期的计划和短期的执行
不管在哪都要抽出时间留给自己去学习去思考，哪怕你时间少点，慢点，但必须走在这条路上
多分享，多向别人学习

**7. 问我机器学习和大数据这块熟不熟悉**
答不会
面试官说那我问你些java相关的问题

**8. Spring Boot内部怎么实现像tomcat那样直接把war包扔到某个目录然后运行起来整个项目的**

**9. Spring Boot很大的jar包里面比如说有个lib目录，那这个lib如果让你去加载，怎么加载**

**10. 你平时在开发中怎么解决遇到的问题的**

**11. 你怎么深入的去学习JVM的**

**12. 你怎么去看的虚拟机的内存**

**13. Jconsole和VisualVM会拿到内存占用的一个趋势，那你觉得什么样的趋势才是合理的**

**14. Full GC和OOM时，我怎么知道是哪一段代码引起的内存溢出和泄漏**

**15. G1收集器有没有Full GC**
线上服务GC日志有没有看过，G1 GC会有什么关键词

**16. 你有什么想问我的吗**

## 3. 微信支付
### 3.1 一面（75分钟）
面试时间：6.15 19:00 - 20:15
**1. 自我介绍**

**2. 操作系统中的大端和小端**

**3. 哈希和红黑树的特点和应用场景**
哈希：查找插入删除在没有哈希碰撞的情况下都是O(1)，性能高，以空间换时间
红黑树：BST树 -> 更新操作导致树左右不平衡，影响性能 -> 引入AVL树 -> 维护成本高 -> 引入红黑树
红黑树O(lgN)的查找性能

红黑树的五个性质保证左右高度不超过2倍
所有节点到叶子节点具有相同的黑节点，
红节点的子节点是黑节点，根节点和叶子节点都是黑节点
所以红节点数一定小于黑节点数，所以一定不超过2倍

**4. 排序**
快排：最优平均时间复杂度O(lgN)，最差时间复杂度O(N)，最差出现在基本有序时，空间复杂度可以说是O(1)，也可以说是O(N)，不稳定排序
堆排：最优最差平均时间复杂度都是O(lgN)，适合处理相对有序的数据，快排适合处理相对无序的数据，不稳定排序，空间复杂度O(1)
归并：额外开个数组，空间复杂度O(N)，最优最差平均时间复杂度都是O(lgN)，稳定排序

**5. 说下三次握手**

**6. 说下time wait，出现在哪一端，什么原因会导致time wait过多，怎么解决**

**7. TCP和UDP的区别**

**8. TCP收发包的方式，粘包拆包怎么解决**

**9. 网络socket连接的过程**

**10. 说下Netty**

**11. select、poll、epoll区别**

**12. 说下Java的线程池，为什么要有线程池**

**13. 线程池内部有什么数据结构，ForkJoinPoll工作窃取怎么保证任务只被一个线程消费**

**14. 用过什么微服务的框架**

**15. 项目中怎么实现负载均衡的**
Nginx
F5

**16. 为什么一年不到就出来看机会**

**17. 说下项目中的难点、各个模块功能**

**18. 你最擅长的技术有哪些**

**19. 项目用到了哪些存储**

**20. MySQL怎么保证主从同步**

**21. 为什么不用MySQL的分库分表，直接用ES**

**22. 项目的数据量多大，设计指标呢**

**23. ES索引里面都存储了哪些字段**

**24. ES部署了几个节点，怎么保证高可用**

**25. 调度平台模块是怎么调度的，什么时间调度，让你设计怎么实现**

**26. 项目中的超时机制**

**27. 任务处理失败怎么处理**

**28. 手撕代码，堆排**
微信这边是要求自己共享屏幕，在本地的IDEA里面写，自己写case跑通
并且写完之后是需要把所有的代码在腾讯会议上发送给面试官的
```
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 4, 7, 5};
        new HeapSort().sort(arr);
        for (int i : arr) { // 1 2 3 4 5 7
            System.out.print(i + " ");
        }
    }

    public void sort(int[] arr) {
        int n = arr.length;

        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        for (int i = n - 1; i >= 0; i--) {
            int tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;

            heapify(arr, i, 0);
        }
    }

    private void heapify(int[] arr, int n, int i) {
        int max = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[max]) max = left;
        if (right < n && arr[right] > arr[max]) max = right;

        if (max != i) {
            int tmp = arr[max];
            arr[max] = arr[i];
            arr[i] = tmp;

            heapify(arr, n, max);
        }
    }
}
```

**29. 手撕代码，实现HashMap**
```
public class MyHashMap {

    public static void main(String[] args) {
        MyHashMap hm = new MyHashMap();
        hm.put(1, 1);
        hm.put(2, 2);
        System.out.println(hm.get(1)); // 1
        hm.remove(1);
        System.out.println(hm.get(1)); // -1
    }

    private final int N = 100000; // 静态数组长度100000

    private Node[] arr;

    public MyHashMap() {
        arr = new Node[N];
    }

    public void put(int key, int value) {
        int idx = hash(key);

        if (arr[idx] == null) { // 没有发生哈希碰撞
            arr[idx] = new Node(-1, -1); // 虚拟头节点
            arr[idx].next = new Node(key, value); // 实际头节点
        } else {
            Node prev = arr[idx]; // 从虚拟头开始遍历

            while (prev.next != null) {
                if (prev.next.key == key) {
                    prev.next.value = value; // 直接覆盖value
                    return;
                }
                prev = prev.next;
            }
            prev.next = new Node(key, value); // 没有键则插入节点
        }
    }

    public int get(int key) {
        int idx = hash(key);

        if (arr[idx] != null) {
            Node cur = arr[idx].next; // 从实际头节点开始寻找

            while (cur != null) {
                if (cur.key == key) {
                    return cur.value; // 找到
                }
                cur = cur.next;
            }
        }
        return -1; // 没有找到
    }

    public void remove(int key) {
        int idx = hash(key);

        if (arr[idx] != null) {
            Node prev = arr[idx];

            while (prev.next != null) {
                if (prev.next.key == key) { // 删除节点
                    Node delNode = prev.next;
                    prev.next = delNode.next;
                    delNode.next = null;
                    return;
                }
                prev = prev.next;
            }
        }
    }

    // 哈希函数
    private int hash(int key) {
        return key % N;
    }

    // 链表节点
    private class Node {
        int key;
        int value;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}
```

### 3.2 二面（60分钟）
面试时间：6.17 19:00 - 20:00
**1. 自我介绍**

**2. 为什么不到一年就出来看机会**

**3. 一年工作对你来说最大的收获是什么**
非科班
之前学习没有目的性，效果可能不好
工作后可以理论结合实践

**4. ES和Solr的区别**

**5. ES的倒排索引**

**6. 说下Java的反射**

**7. 了解分布式事务吗**
确实没用过

**8. 最近学了哪些技术**

**9. 这边CPP你能接受吗**
当然可以接受了(手动狗头.jpg

**10. MySQL的事务隔离级别**

**11. MySQL的主从备份机制**

**12. 数据库的表结构设计有哪些经验**

**13. 数据库的分库分表**

**14. 说下项目中的某个功能怎么实现的**

**15. 手撕代码，leetcode199二叉树的右视图**
```
public class Main {

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;

        List<Integer> res = rightSideView(t1);
        for (Integer t : res) {
            System.out.print(t + " "); // 1 3 5
        }
    }

    public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int cur = 1;
        int next = 0;
        List<Integer> in = new ArrayList<>();

        while (!queue.isEmpty()) {
            TreeNode t = queue.poll();
            in.add(t.val);
            cur--;

            if (t.left != null) {
                queue.offer(t.left);
                next++;
            }
            if (t.right != null) {
                queue.offer(t.right);
                next++;
            }
            if (cur == 0) {
                res.add(in.get(in.size() - 1));
                in = new ArrayList<>();
                cur = next;
                next = 0;
            }
        }

        return res;
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }
}
```

**16. 说下项目中的难点**

**17. 关键帧提取的原理**

**18. 限流怎么实现的**

**19. Redis分布式锁**

**20. DB和缓存怎么保证数据的一致性**

**21. 平时怎么学习这些知识的**

**22. 你有什么想问我的吗**

**23. 你家哪里的，来深圳有问题吗**

### 3.3 三面（40分钟）
面试时间：6.23 11:20 - 12:00
**1. 为什么一年出来看机会**

**2. 手撕代码，二分查找，共享屏幕，自己写case**
```
public class Main {

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        System.out.println(binarySearch(arr, 1) == 0);
        System.out.println(binarySearch(arr, 3) == 1);
        System.out.println(binarySearch(arr, 7) == 3);
        System.out.println(binarySearch(arr, 9) == 4);
        System.out.println(binarySearch(arr, 2) == -1);
    }

    public static int binarySearch(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;

            if (arr[mid] == target) return mid;
            else if (arr[mid] > target) hi = mid - 1;
            else lo = mid + 1;
        }

        return -1;
    }
}
```

**3. 手撕代码，leetcode226翻转二叉树**
```
public class Main {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;

        List<List<Integer>> res = printTree(t1);
        for (List<Integer> t : res) {
            System.out.println(t);
        }

        System.out.println("树翻转之后---");

        res = printTree(reverseTree(t1));
        for (List<Integer> t : res) {
            System.out.println(t);
        }
    }

    public static List<List<Integer>> printTree(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int cur = 1;
        int next = 0;

        List<Integer> in = new ArrayList<>();

        while (!queue.isEmpty()) {
            TreeNode t = queue.poll();
            cur--;
            in.add(t.val);

            if (t.left != null) {
                queue.offer(t.left);
                next++;
            }

            if (t.right != null) {
                queue.offer(t.right);
                next++;
            }

            if (cur == 0) {
                res.add(new ArrayList<>(in));
                in.clear();
                cur = next;
                next = 0;
            }
        }

        return res;
    }

    public static TreeNode reverseTree(TreeNode root) {
        if (root == null) return null;
        TreeNode right = reverseTree(root.left);
        TreeNode left = reverseTree(root.right);
        root.left = left;
        root.right = right;
        return root;
    }
}
```

**4. 怎么保证缓存和DB之间的数据一致性**

**5. 缓存穿透、缓存击穿、缓存雪崩区别及解决方案**

**6. 怎么预估热点key，怎么解决热点key问题**

**7. 缓存的淘汰策略**

**8. CPP会吗**
不会...

**9. 为什么在百度还要自己写搜索的项目，没有搜索中台提供服务调用吗**

**10. 你们组都有什么业务**

**11. 你有什么想问我的吗**

### 3.4 四面（170分钟）
面试时间：6.28 19:00 - 21:50
这一轮是交叉面
**1. CPP熟悉吗**

**2. 面试官共享他的屏幕让我写试卷**
试卷上面基本都是选择题，让我选答案
包括编程语言、数据结构、网络、汇编、密码学、正则表达式等知识

**3. 手撕代码，字符串移位**
```
public class Main {

    public static void main(String[] args) {
        System.out.println(func2("abcdef", 2)); // "efabcd"
    }

    public static String func(String str, int m) {
        if (str == null || str.length() == 0 || m < 1) return str;
        int len = str.length();
        m = m % len;

        return new StringBuilder(str).append(str).substring(m, m + str.length());
    }

    public static String func2(String str, int m) {
        if (str == null || str.length() == 0 || m < 1) return str;
        int len = str.length();
        m = m % len;

        char[] chars = str.toCharArray();
        swap(chars, 0, len - 1);
        swap(chars, 0, m - 1);
        swap(chars, m, len - 1);
        return String.valueOf(chars);
    }

    private static void swap(char[] chars, int a, int b) {
        for (int i = a, j = b; i < j; i++, j--) {
            char ch = chars[i];
            chars[i] = chars[j];
            chars[j] = ch;
        }
    }
}
```
一开始我是用了额外的O(N)空间，写完面试官又要求O(N)时间复杂度，O(1)空间复杂度完成

**4. 手撕代码**
给定字符串str，返回第一个括号不匹配的索引，若没有返回-1
```
public class Main {

    public static void main(String[] args) {
        System.out.println(isBalance("aa(dss)") == -1);
        System.out.println(isBalance("aa(dss))") == 7);
        System.out.println(isBalance("aa((dss)") == 2);
        System.out.println(isBalance("aa(d(s)s)(") == 9);
        System.out.println(isBalance("aaaaaa") == -1);
    }

    public static int isBalance(String str) {
        if (str == null || str.length() == 0) return -1;
        int len = str.length();
        char[] chars = str.toCharArray();

        Stack<Character> stack = new Stack<>(); // 存放括号
        List<Integer> index = new ArrayList<>(); // 存放括号的索引位置

        for (int i = 0; i < len; i++) {
            if (!Arrays.asList('(', ')').contains(chars[i])) continue; // 遇到不是括号的字符直接跳过
            if (chars[i] == '(') { // 遇到左括号压入栈中，并记录索引
                stack.push('(');
                index.add(i);
            } else if (chars[i] == ')') {
                if (stack.isEmpty() || stack.peek() != '(') { // 遇到右括号，判断栈顶是不是左括号，如果不是直接return
                    return i;
                } else { // 否则弹出栈顶元素并移除index最后一个元素
                    stack.pop();
                    index.remove(index.size() - 1);
                }
            }
        }

        return stack.isEmpty() ? -1 : index.get(index.size() - 1);
    }
}
```

**5. 求两个数组的交集**
这题没让写，直接说思路
直接HashSet或者用bitmap

**6. 哈希存在的问题**

**7. Redis有序集合底层实现**

**8. 为什么用跳表不用红黑树**
实现简单
区间查询

**9. MySQL索引为什么用B+树不用红黑树**

**10. zset有什么应用场景**

**11. ES的倒排索引**

**12. 项目中的难点**

**13. 为什么用ES不用MySQL**

**14. 项目的数据规模**

**15. 为什么ES和MySQL都是基于磁盘，ES的查询性能要高**

**16. 面试官让我共享屏幕讲项目，边讲边问**
因为在简历中写了项目的文档链接，所以让共享屏幕讲

**17. 你有什么想问我的吗**

### 3.5 五面（0分钟）
第一轮面试结束时，面试官加了微信
四面结束后，一面的面试官微信跟我说五面是微信支付的大Boss面，还给了我一个ppt模板
说面试形式是自己提前写好ppt然后给面试官讲ppt（果然ppt是最好的语言啊），主要是项目中的难点
面试官和我说微信支付这边主要的技术面都面完了，五面以及后面的部门经理面、hr面基本不会卡人
但考虑到微信支付在深圳要换城市换语言，再加上家里有些事情，自己硕士毕业也不小了
就放弃了接下来的面试，可惜了微信完美的面试发挥

## 4. 蚂蚁金服
### 4.1 一面（60分钟）
面试时间：6.19 19:00 - 20:00
**1. 自我介绍**

**2. 挑个你印象最深的项目**

**3. 项目包含哪些模块**

**4. 项目中最大的难点是什么**

**5. 任务在多个模块间异步回调，如果某个模块挂了怎么处理**

**6. 失败任务怎么处理**

**7. ES的倒排索引是怎么建的**

**8. HashMap与ConcurrentHashMap的区别**
典型的Java八股文，都问烂了

**9. 说下MySQL的索引结构**

**10. 微信抢红包怎么设计系统**

**11. 怎么切分红包金额**

**12. 手撕代码**
问题：定义一个链表结构如下：

struct ListNode {
int value;
struct ListNode *next;
};
请写一个程序，实现链表中重复节点的删除（同一值的节点只保留一个），且链表顺序保持不变。如，
初始链表：3 -> 2 -> 3 -> 4 -> 4 -> 1 -> 7 -> 8
节点去重后的链表：3 -> 2 -> 4 -> 1 -> 7 -> 8

注意：初始链表是非排序的链表。
```
class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public ListNode func(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode dummy = new ListNode(-1);
    dummy.next = head;

    ListNode pre = head;
    ListNode cur = head.next;
    Set<Integer> exist = new HashSet<>();
    exist.add(head.val);

    while (cur != null) {
        if (exist.contains(cur.val)) {
            ListNode nxt = cur.next;
            cur.next = null;
            pre.next = nxt;
            cur = nxt;
        } else {
            exist.add(cur.val);
            pre = cur;
            cur = cur.next;
        }
    }

    return dummy.next;
}
```

**13. 你有什么想问我的吗**

### 4.2 二面（40分钟）
面试时间：7.1 20:00 - 20:40
因为二面基本都问的项目，所以也写一下
**1. 自我介绍**

**2. 项目的应用场景**

**3. 视频搜视频业务处理逻辑**

**4. 图搜图响应时间**

**5. 项目存在的问题及改进**

**6. 技术上有哪些需要优化的点**

**7. 图谱构建是全量还是增量的**

**8. 切词是每天都需要重新去切吗**

**9. 性能瓶颈是在依赖的服务模块上吗**

**10. 一年出来看机会的考虑是什么**

**11. 这会还面了哪些公司，你会怎么选offer**

**12. 你对工作地和出差是怎么考虑的**

**13. 你有什么想问我的吗**

### 4.3 三面（30分钟）
面试时间：7.4 10:50 - 11:20
**1. 自我介绍**

**2. 项目有没有什么性能方面的优化**

**3. 项目比较有挑战性的点**

**4. 项目中学到了什么，之后还需要学什么**

**5. 最近在学什么技术**

**6. 有没有什么收获可以分享一下**

**7. 知识图谱详细说下**

**8. 你在百度一年就想出来看机会的原因是什么**

**9. 晋升对你当前来说是最重要的吗**
送命题，那当然是成长最重要了(手动狗头.jpg

**10. 你有考虑过来杭州吗**

**11. 你有什么想问我的吗**

## 5. 总结
1. **面试本质是一个自我优势展示的过程，不要把面试变成面试官问一句自己回答一句**，主动抛出一些可能的点等面试官来问，比如我基本都被问到了DB和缓存之间怎么保证数据的一致性，其实都是我自己刻意往上引的，比如面试官说，你用过Redis吗，你可以说，用过，一般用来作为缓存配合MySQL提高性能，需要注意它们之间数据的一致性问题（不要太刻意，自己把握分寸），面试官大概率会接着问你那怎么保证的
2. **刷leetcode，刷leetcode，刷leetcode！**重要的事情说三遍，作为一个程序员，代码写的烂就是原罪，面试时前面答得再天花乱坠算法写的捉急也没用，只会让面试官产生你是背面经的感觉，所以写算法题还是要快准狠，快速无bug写出最优解在面试官那里是非常亮眼的，这个是没有捷径的，我自己这次面试leetcode高频300题刷了好几遍，面试算法很顺利，当然最主要的还是刷中等难度的题，hard题性价比太低，反正我没怎么刷...
3. **不要眼高手低**，不少小伙伴看面经觉得自己啥都会，但是**自己会与面试过程中能清晰有层次的说出来是两回事**，并且自己会到什么程度，有个说法很好，判断你是不是真的掌握一个知识的一个点在于你能不能通过通俗易懂的语言教会一个完全没有相关知识背景的人，如果这可以做到，那对知识的掌握一定是融会贯通的，面试过程中一定可以信手拈来。比如volatile关键字的原理，能不能说出点面试官眼前一亮的东西，和别的同学蜻蜓点水不一样的感觉，这还是不容易的
4. 面试得自信，声音自信，给面试官一种你啥都会稳如狗得感觉（时机内心慌得不行...），然后表达流畅，吐字清晰，不卑不亢，说话要有逻辑性，不能吞吞吐吐半天说不明白
5. 得总结自己的面经，**形成自己的知识体系**，别人的面经写的再好也是别人的，自己刷面经总结自己不会的点整理出来才是最有用的