面经 | 百度26届校招开奖！附后端一面20道八股 + 手撕算法题

原标题：百度今年的薪资来了

大家好，我是小林。面试刷题网站：xiaolincoding.com

之前有读者催着要看百度 26 届开发岗的薪资。

这不来了嘛！我特意攒了波百度的开奖数据，整理成表格放下面， 提醒下哈，表里的年总包是算上签字费的。

岗位类型	薪资结构	年总包（第一年）
后端开发	32k x 16 + 9w 签字费	60.2w
后端开发	30k x 16 + 6w 签字费	54.0w
后端开发	28k x 16	44.8w
客户端开发	28k x 16 + 6w 签字费	50.8w
C++ 开发	26k x 16 + 8w 签字费	49.6w
测试开发	26k x 16 + 8w 签字费	49.6w
测试开发	25k x 16 + 6w 签字费	46.0w
后端开发	24k x 16	38.4w
客户端开发	22k x 16	35.2w
C++ 开发	22k x 16	35.2w

大概分档是这样：22k-24k 是普通 offer，25k-28k 是 SP，30k 往上就是 SSP 了。说真的百度签字费给得挺大方，但这钱不是一次性到手的 ， 分 2 年发，第一年拿一半，剩下的第二年才给，相当于拴着你多干一年。

我翻了下去年 25 届的开奖数据，今年百度薪资基本没涨，属于「原地踏步」 型。

甚至有同学拒了百度的 SSP offer，放往年这绝对是香饽饽，但今年大厂薪资卷太狠了啊！字节、小红书这些，校招薪资比去年涨了不少，SSP 都能开到 35k+，这么一对比，百度的 SSP 突然就不香了。

百度秋招面试的时间还是蛮早的，8-9 月份就看到不少人已经百度面完三面了，但是等到了接近 12 月才开奖，就比如训练营有同学百度三面完之后，等了快两个月才开奖，不过好在泡出来了，开了是 SP offer，总包 40w+，也算没白等。

百度毕竟是老牌大厂，面试难度肯定不低。

这次给大家看份百度后端一面的面经 ，这题量是真的大，光八股就问了快 20 道，加上项目追问，没准备充分的话绝对招架不住。

考察的技术点也很全：Java 集合、并发、JVM、Spring、MySQL、Redis、数据结构、算法全涵盖了。从这也能看出来，大家准备大厂后端面试的时候，把这几块的八股往深了啃准没错，都是高频考点。

百度（秋招后端一面）

1. ArrayList 和 LinkedList 区别是什么？

ArrayList和LinkedList都是Java中常见的集合类，它们都实现了List接口。

底层数据结构不同：ArrayList使用数组实现，通过索引进行快速访问元素。LinkedList使用链表实现，通过节点之间的指针进行元素的访问和操作。

插入和删除操作的效率不同：ArrayList在尾部的插入和删除操作效率较高，但在中间或开头的插入和删除操作效率较低，需要移动元素。LinkedList在任意位置的插入和删除操作效率都比较高，因为只需要调整节点之间的指针。

随机访问的效率不同：ArrayList支持通过索引进行快速随机访问，时间复杂度为O(1)。LinkedList需要从头或尾开始遍历链表，时间复杂度为O(n)。

空间占用：ArrayList在创建时需要分配一段连续的内存空间，因此会占用较大的空间。LinkedList每个节点只需要存储元素和指针，因此相对较小。

使用场景：ArrayList适用于频繁随机访问和尾部的插入删除操作，而LinkedList适用于频繁的中间插入删除操作和不需要随机访问的场景。

线程安全：这两个集合都不是线程安全的，Vector是线程安全的

2. 聊一下ConcurrentHashMap原理

JDK 1.7 ConcurrentHashMap

在 JDK 1.7 中它使用的是数组加链表的形式实现的，而数组又分为：大数组 Segment 和小数组 HashEntry。

Segment 是一种可重入锁（ReentrantLock），在 ConcurrentHashMap 里扮演锁的角色；

HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素。

JDK 1.7 ConcurrentHashMap 分段锁技术将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

JDK 1.8 ConcurrentHashMap

在 JDK 1.7 中，ConcurrentHashMap 虽然是线程安全的，但因为它的底层实现是数组 + 链表的形式，所以在数据比较多的情况下访问是很慢的，因为要遍历整个链表，而 JDK 1.8 则使用了数组 + 链表/红黑树的方式优化了 ConcurrentHashMap 的实现，具体实现结构如下：

JDK 1.8 ConcurrentHashMap JDK 1.8 ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。添加元素时首先会判断容器是否为空：

如果为空则使用  volatile  加  CAS  来初始化

如果容器不为空，则根据存储的元素计算该位置是否为空。

如果根据存储的元素计算结果为空，则利用  CAS  设置该节点；

如果根据存储的元素计算结果不为空，则使用 synchronized  ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

如果把上面的执行用一句话归纳的话，就相当于是ConcurrentHashMap通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。

而且 JDK 1.8 使用的是红黑树优化了之前的固定链表，那么当数据量比较大的时候，查询性能也得到了很大的提升，从之前的 O(n) 优化到了 O(logn) 的时间复杂度。

3. CAS 是什么？

CAS核心思想就是乐观锁，不像synchronized那样悲观地直接加锁，而是乐观地认为不会发生冲突，先去尝试操作，如果失败了就重试。

具体来说，CAS涉及三个操作数，一个是内存地址V，一个是预期原值A，还有一个是新值B。操作过程就是先读取内存地址V的当前值，然后跟预期值A做比较，如果相等就说明没有别的线程修改过，那就把新值B写进去，如果不相等就说明有线程改过了，这次更新就失败，然后会重新读取再尝试，这个过程叫自旋。

CAS最大的优势是它是CPU层面的原子指令，比如Intel的cmpxchg指令，由硬件保证原子性，不需要加锁就能保证线程安全。

Java里是通过Unsafe类调用到底层的native方法来实现的，JDK1.5之后在concurrent包里大量使用，比如AtomicInteger、AtomicLong这些原子类，它们内部就是用CAS加上volatile来实现的无锁操作。

举个例子，AtomicInteger的自增操作，它会先读取当前值，然后用CAS尝试把值加1写回去,如果这期间有别的线程改了这个值，CAS就会失败，然后它会再次读取重新尝试，直到成功为止。

4. 创建线程的方式有哪些？

1.继承Thread类

这是最直接的一种方式，用户自定义类继承java.lang.Thread类，重写其run()方法，run()方法中定义了线程执行的具体任务。创建该类的实例后，通过调用start()方法启动线程。

classMyThreadextendsThread{
    @Override
    publicvoidrun(){
        // 线程执行的代码
    }
}

publicstaticvoidmain(String[] args){
    MyThread t = new MyThread();
    t.start();
}

采用继承Thread类方式

优点: 编写简单，如果需要访问当前线程，无需使用Thread.currentThread ()方法，直接使用this，即可获得当前线程缺点:因为线程类已经继承了Thread类，所以不能再继承其他的父类

2.实现Runnable接口

如果一个类已经继承了其他类，就不能再继承Thread类，此时可以实现java.lang.Runnable接口。实现Runnable接口需要重写run()方法，然后将此Runnable对象作为参数传递给Thread类的构造器，创建Thread对象后调用其start()方法启动线程。

classMyRunnableimplementsRunnable{
    @Override
    publicvoidrun(){
        // 线程执行的代码
    }
}

publicstaticvoidmain(String[] args){
    Thread t = new Thread(new MyRunnable());
    t.start();
}

采用实现Runnable接口方式：

优点：线程类只是实现了Runable接口，还可以继承其他的类。在这种方式下，可以多个线程共享同一个目标对象，所以非常适合多个相同线程来处理同一份资源的情况，从而可以将CPU代码和数据分开，形成清晰的模型，较好地体现了面向对象的思想。

缺点：编程稍微复杂，如果需要访问当前线程，必须使用Thread.currentThread()方法。

实现Callable接口与FutureTask

java.util.concurrent.Callable接口类似于Runnable，但Callable的call()方法可以有返回值并且可以抛出异常。要执行Callable任务，需将它包装进一个FutureTask，因为Thread类的构造器只接受Runnable参数，而FutureTask实现了Runnable接口。

classMyCallableimplementsCallable<Integer> {
    @Override
    public Integer call()throws Exception {
        // 线程执行的代码，这里返回一个整型结果
        return1;
    }
}

publicstaticvoidmain(String[] args){
    MyCallable task = new MyCallable();
    FutureTask<Integer> futureTask = new FutureTask<>(task);
    Thread t = new Thread(futureTask);
    t.start();

    try {
        Integer result = futureTask.get();  // 获取线程执行结果
        System.out.println("Result: " + result);
    } catch (InterruptedException | ExecutionException e) {
        e.printStackTrace();
    }
}

采用实现Callable接口方式：

缺点：编程稍微复杂，如果需要访问当前线程，必须调用Thread.currentThread()方法。

优点：线程只是实现Runnable或实现Callable接口，还可以继承其他类。这种方式下，多个线程可以共享一个target对象，非常适合多线程处理同一份资源的情形。

使用线程池（Executor框架）

从Java 5开始引入的java.util.concurrent.ExecutorService和相关类提供了线程池的支持，这是一种更高效的线程管理方式，避免了频繁创建和销毁线程的开销。可以通过Executors类的静态方法创建不同类型的线程池。

classTaskimplementsRunnable{
    @Override
    publicvoidrun(){
        // 线程执行的代码
    }
}

publicstaticvoidmain(String[] args){
    ExecutorService executor = Executors.newFixedThreadPool(10);  // 创建固定大小的线程池
    for (int i = 0; i < 100; i++) {
        executor.submit(new Task());  // 提交任务到线程池执行
    }
    executor.shutdown();  // 关闭线程池
}

采用线程池方式：

缺点：程池增加了程序的复杂度，特别是当涉及线程池参数调整和故障排查时。错误的配置可能导致死锁、资源耗尽等问题，这些问题的诊断和修复可能较为复杂。

优点：线程池可以重用预先创建的线程，避免了线程创建和销毁的开销，显著提高了程序的性能。对于需要快速响应的并发请求，线程池可以迅速提供线程来处理任务，减少等待时间。并且，线程池能够有效控制运行的线程数量，防止因创建过多线程导致的系统资源耗尽（如内存溢出）。通过合理配置线程池大小，可以最大化CPU利用率和系统吞吐量。

5. 线程池原理是怎样的？

线程在正常执行或者异常中断时会被销毁，如果频繁的创建很多线程，不仅会消耗系统资源，还会降低系统的稳定性，一不小心把系统搞崩了。

使用线程池可以带来以下几个好处：

线程池内部的线程数是可控的，可以灵活的设置参数；线程池内会保留部分线程，当提交新的任务可以直接运行；方便内部线程资源的管理，调优和监控；

所以，线程池是为了减少频繁的创建线程和销毁线程带来的性能损耗，线程池的工作原理如下图：

当用户提交了一个任务，接下来这个任务将如何执行都是由这个阶段决定的。首先，所有任务的调度都是由execute方法完成的，这部分完成的工作是：检查现在线程池的运行状态、运行线程数、运行策略，决定接下来执行的流程，是直接申请线程执行，或是缓冲到队列中执行，亦或是直接拒绝该任务。

其执行过程如下：

首先检测线程池运行状态，如果不是RUNNING，则直接拒绝，线程池要保证在RUNNING的状态下执行任务。

如果workerCount < corePoolSize，则创建并启动一个线程来执行新提交的任务。

如果workerCount >= corePoolSize，且线程池内的阻塞队列未满，则将任务添加到该阻塞队列中。

如果workerCount >= corePoolSize && workerCount < maximumPoolSize，且线程池内的阻塞队列已满，则创建并启动一个线程来执行新提交的任务。

如果workerCount >= maximumPoolSize，并且线程池内的阻塞队列已满, 则根据拒绝策略来处理该任务, 默认的处理方式是直接抛异常。

6. BIO 和 NIO 区别是什么？

BIO（blocking IO）：就是传统的 java.io 包，它是基于流模型实现的，交互的方式是同步、阻塞方式，也就是说在读入输入流或者输出流时，在读写动作完成之前，线程会一直阻塞在那里，它们之间的调用是可靠的线性顺序。优点是代码比较简单、直观；缺点是 IO 的效率和扩展性很低，容易成为应用性能瓶颈。

NIO（non-blocking IO） ：Java 1.4 引入的 java.nio 包，提供了 Channel、Selector、Buffer 等新的抽象，可以构建多路复用的、同步非阻塞 IO 程序，同时提供了更接近操作系统底层高性能的数据操作方式。

AIO（Asynchronous IO） ：是 Java 1.7 之后引入的包，是 NIO 的升级版本，提供了异步非堵塞的 IO 操作方式，所以人们叫它 AIO（Asynchronous IO），异步 IO 是基于事件和回调机制实现的，也就是应用操作之后会直接返回，不会堵塞在那里，当后台处理完成，操作系统会通知相应的线程进行后续的操作。

7. SpringBean的生命周期说一下？

Bean 的生命周期可以简单分成 4 个阶段，流程很清晰：

创建阶段：Spring 先找到需要管理的 Bean，实例化对象，然后给属性赋值（依赖注入）。

初始化阶段：

先调用各种 Aware 接口（比如 BeanNameAware、ApplicationContextAware），让 Bean 知道自己的 ID、上下文等信息。接着执行 BeanPostProcessor 的前置处理方法。然后调用 InitializingBean 的 afterPropertiesSet 方法，或者自定义的 init-method 初始化方法。最后执行 BeanPostProcessor 的后置处理方法，此时 Bean 才算初始化完成。

使用阶段：Bean 在容器中待命，随时被程序调用。

销毁阶段：容器关闭时，先调用 DisposableBean 的 destroy 方法，或者自定义的 destroy-method 销毁方法，完成资源清理。

8. Redis的持久化方式是怎样的？

Redis 的读写操作都是在内存中，所以 Redis 性能才会高，但是当 Redis 重启后，内存中的数据就会丢失，那为了保证内存中的数据不会丢失，Redis 实现了数据持久化的机制，这个机制会把数据存储到磁盘，这样在 Redis 重启就能够从磁盘中恢复原有的数据。Redis 共有三种数据持久化的方式：

AOF 日志：每执行一条写操作命令，就把该命令以追加的方式写入到一个文件里；

RDB 快照：将某一时刻的内存数据，以二进制的方式写入磁盘；

AOF 日志是如何实现的？

Redis 在执行完一条写操作命令后，就会把该命令以追加的方式写入到一个文件里，然后 Redis 重启时，会读取该文件记录的命令，然后逐一执行命令的方式来进行数据恢复。

我这里以「set name xiaolin」命令作为例子，Redis 执行了这条命令后，记录在 AOF 日志里的内容如下图：

Redis 提供了 3 种写回硬盘的策略， 在 Redis.conf 配置文件中的 appendfsync 配置项可以有以下 3 种参数可填：

Always，这个单词的意思是「总是」，所以它的意思是每次写操作命令执行完后，同步将 AOF 日志数据写回硬盘；

Everysec，这个单词的意思是「每秒」，所以它的意思是每次写操作命令执行完后，先将命令写入到 AOF 文件的内核缓冲区，然后每隔一秒将缓冲区里的内容写回到硬盘；

No，意味着不由 Redis 控制写回硬盘的时机，转交给操作系统控制写回的时机，也就是每次写操作命令执行完后，先将命令写入到 AOF 文件的内核缓冲区，再由操作系统决定何时将缓冲区内容写回硬盘。

我也把这 3 个写回策略的优缺点总结成了一张表格：

RDB 快照是如何实现的呢？

因为 AOF 日志记录的是操作命令，不是实际的数据，所以用 AOF 方法做故障恢复时，需要全量把日志都执行一遍，一旦 AOF 日志非常多，势必会造成 Redis 的恢复操作缓慢。为了解决这个问题，Redis 增加了 RDB 快照。

所谓的快照，就是记录某一个瞬间东西，比如当我们给风景拍照时，那一个瞬间的画面和信息就记录到了一张照片。所以，RDB 快照就是记录某一个瞬间的内存数据，记录的是实际数据，而 AOF 文件记录的是命令操作的日志，而不是实际的数据。因此在 Redis 恢复数据时， RDB 恢复数据的效率会比 AOF 高些，因为直接将 RDB 文件读入内存就可以，不需要像 AOF 那样还需要额外执行操作命令的步骤才能恢复数据。

Redis 提供了两个命令来生成 RDB 文件，分别是 save 和 bgsave，他们的区别就在于是否在「主线程」里执行：

执行了 save 命令，就会在主线程生成 RDB 文件，由于和执行操作命令在同一个线程，所以如果写入 RDB 文件的时间太长，会阻塞主线程；

执行了 bgsave 命令，会创建一个子进程来生成 RDB 文件，这样可以避免主线程的阻塞；

9. 你知道哪些Redis的数据结构？

Redis 提供了丰富的数据类型，常见的有五种数据类型：String（字符串），Hash（哈希），List（列表），Set（集合）、Zset（有序集合）。

随着 Redis 版本的更新，后面又支持了四种数据类型：BitMap（2.2 版新增）、HyperLogLog（2.8 版新增）、GEO（3.2 版新增）、Stream（5.0 版新增）。Redis 五种数据类型的应用场景：

String 类型的应用场景：缓存对象、常规计数、分布式锁、共享 session 信息等。

List 类型的应用场景：消息队列（但是有两个问题：1. 生产者需要自行实现全局唯一 ID；2. 不能以消费组形式消费数据）等。

Hash 类型：缓存对象、购物车等。Set 类型：聚合计算（并集、交集、差集）场景，比如点赞、共同关注、抽奖活动等。Zset 类型：排序场景，比如排行榜、电话和姓名排序等。

Redis 后续版本又支持四种数据类型，它们的应用场景如下：

BitMap（2.2 版新增）：二值状态统计的场景，比如签到、判断用户登陆状态、连续签到用户总数等；

HyperLogLog（2.8 版新增）：海量数据基数统计的场景，比如百万级网页 UV 计数等；

GEO（3.2 版新增）：存储地理位置信息的场景，比如滴滴叫车；

Stream（5.0 版新增）：消息队列，相比于基于 List 类型实现的消息队列，有这两个特有的特性：自动生成全局唯一消息ID，支持以消费组形式消费数据。

10. .MySQL的事务隔离级别有哪些？

读未提交（read uncommitted），指一个事务还没提交时，它做的变更就能被其他事务看到；

读提交（read committed），指一个事务提交之后，它做的变更才能被其他事务看到；

可重复读（repeatable read），指一个事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，MySQL InnoDB 引擎的默认隔离级别；

串行化（serializable）；会对记录加上读写锁，在多个事务对这条记录进行读写操作时，如果发生了读写冲突的时候，后访问的事务必须等前一个事务执行完成，才能继续执行；

11. MySQL 的  MVCC 是怎样实现的？

MVCC允许多个事务同时读取同一行数据，而不会彼此阻塞，每个事务看到的数据版本是该事务开始时的数据版本。这意味着，如果其他事务在此期间修改了数据，正在运行的事务仍然看到的是它开始时的数据状态，从而实现了非阻塞读操作。

对于「读提交」和「可重复读」隔离级别的事务来说，它们是通过 Read View 来实现的，它们的区别在于创建 Read View 的时机不同，大家可以把 Read View 理解成一个数据快照，就像相机拍照那样，定格某一时刻的风景。

「读提交」隔离级别是在「每个select语句执行前」都会重新生成一个 Read View；「可重复读」隔离级别是执行第一条select时，生成一个 Read View，然后整个事务期间都在用这个 Read View。

Read View 有四个重要的字段：

m_ids ：指的是在创建 Read View 时，当前数据库中「活跃事务」的事务 id 列表，注意是一个列表，“活跃事务”指的就是，启动了但还没提交的事务。

min_trx_id ：指的是在创建 Read View 时，当前数据库中「活跃事务」中事务 id 最小的事务，也就是 m_ids 的最小值。

max_trx_id ：这个并不是 m_ids 的最大值，而是创建 Read View 时当前数据库中应该给下一个事务的 id 值，也就是全局事务中最大的事务 id 值 + 1；

creator_trx_id ：指的是创建该 Read View 的事务的事务 id。

对于使用 InnoDB 存储引擎的数据库表，它的聚簇索引记录中都包含下面两个隐藏列：

trx_id，当一个事务对某条聚簇索引记录进行改动时，就会把该事务的事务 id 记录在 trx_id 隐藏列里；

roll_pointer，每次对某条聚簇索引记录进行改动时，都会把旧版本的记录写入到 undo 日志中，然后这个隐藏列是个指针，指向每一个旧版本记录，于是就可以通过它找到修改前的记录。

在创建 Read View 后，我们可以将记录中的 trx_id 划分这三种情况：

一个事务去访问记录的时候，除了自己的更新记录总是可见之外，还有这几种情况：

如果记录的 trx_id 值小于 Read View 中的 min_trx_id 值，表示这个版本的记录是在创建 Read View 前已经提交的事务生成的，所以该版本的记录对当前事务可见。

如果记录的 trx_id 值大于等于 Read View 中的 max_trx_id 值，表示这个版本的记录是在创建 Read View 后才启动的事务生成的，所以该版本的记录对当前事务不可见。

如果记录的 trx_id 值在 Read View 的 min_trx_id 和 max_trx_id 之间，需要判断 trx_id 是否在 m_ids 列表中：

如果记录的 trx_id 在 m_ids 列表中，表示生成该版本记录的活跃事务依然活跃着（还没提交事务），所以该版本的记录对当前事务不可见。

如果记录的 trx_id 不在 m_ids列表中，表示生成该版本记录的活跃事务已经被提交，所以该版本的记录对当前事务可见。

这种通过「版本链」来控制并发事务访问同一个记录时的行为就叫 MVCC（多版本并发控制）。

12. MySQL存储引擎的区别是什么？

InnoDB：InnoDB是MySQL的默认存储引擎，具有ACID事务支持、行级锁、外键约束等特性。它适用于高并发的读写操作，支持较好的数据完整性和并发控制。

MyISAM：MyISAM是MySQL的另一种常见的存储引擎，具有较低的存储空间和内存消耗，适用于大量读操作的场景。然而，MyISAM不支持事务、行级锁和外键约束，因此在并发写入和数据完整性方面有一定的限制。

Memory：Memory引擎将数据存储在内存中，适用于对性能要求较高的读操作，但是在服务器重启或崩溃时数据会丢失。它不支持事务、行级锁和外键约束。

13. 栈和队列的区别？

主要区别在于元素的插入和删除方式以及元素的访问顺序。

插入和删除方式：

队列：队列采用先进先出（FIFO）的方式，即新元素插入队尾，删除操作发生在队首。

栈：栈采用后进先出（LIFO）的方式，即新元素插入栈顶，删除操作也发生在栈顶。

元素的访问顺序：

队列：队列的元素按照插入的顺序进行访问，先插入的元素先被访问到。

栈：栈的元素按照插入的顺序进行访问，但是最后插入的元素先被访问到。

队列适用于需要按照插入顺序进行处理的场景，例如任务调度；

而栈适用于需要维护最近操作状态的场景，例如函数调用。

14. 二叉树的遍历方式有什么哪些？

二叉树的遍历方式主要分为两大类，一类是深度优先遍历，另一类是广度优先遍历。

深度优先遍历有三种，分别是前序遍历、中序遍历和后序遍历。它们的区别就是访问根节点的顺序不一样。

前序遍历是根左右，就是先访问根节点，再递归遍历左子树，最后右子树。中序遍历是左根右，先遍历左子树，再访问根节点，最后右子树，这种方式对二叉搜索树特别有用，因为能得到升序排列的结果。后序遍历是左右根，先遍历左右子树，最后才访问根节点，这种方式适合做一些需要先处理子节点的场景，比如计算树的高度或者删除节点。

这三种遍历既可以用递归实现，也可以用栈来做非递归实现。递归写起来简单直观，就是几行代码的事，但递归深度太大会栈溢出。非递归的话需要手动维护一个栈来模拟递归过程，代码稍微复杂一点，但能避免栈溢出问题。

广度优先遍历就是层序遍历，按照树的层次从上到下、从左到右一层一层访问节点。实现方式一般用队列，先把根节点放进队列，然后每次从队列取出一个节点访问，再把它的左右子节点依次放入队列，这样循环下去就能实现层序遍历。层序遍历在处理树的层级相关问题时特别好用，比如找每层的最大值、锯齿形遍历这些。

15. TCP 和 UDP 区别是什么？

连接：TCP 是面向连接的传输层协议，传输数据前先要建立连接；UDP 是不需要连接，即刻传输数据。

服务对象：TCP 是一对一的两点服务，即一条连接只有两个端点。UDP 支持一对一、一对多、多对多的交互通信可靠性：TCP 是可靠交付数据的，数据可以无差错、不丢失、不重复、按序到达。UDP 是尽最大努力交付，不保证可靠交付数据。但是我们可以基于 UDP 传输协议实现一个可靠的传输协议，比如 QUIC 协议拥塞控制、流量控制：TCP 有拥塞控制和流量控制机制，保证数据传输的安全性。UDP 则没有，即使网络非常拥堵了，也不会影响 UDP 的发送速率。首部开销：TCP 首部长度较长，会有一定的开销，首部在没有使用「选项」字段时是 20 个字节，如果使用了「选项」字段则会变长的。UDP 首部只有 8 个字节，并且是固定不变的，开销较小。传输方式：TCP 是流式传输，没有边界，但保证顺序和可靠。UDP 是一个包一个包的发送，是有边界的，但可能会丢包和乱序。

16. JVM内存结构是怎样的？

JVM的内存结构按照Java虚拟机规范，主要分为几个区域，我按照线程共享和线程私有来说会比较清楚。

先说线程共享的区域。

首先是堆，这是JVM里最大的一块内存区域，几乎所有的对象实例和数组都分配在这里。堆是垃圾回收的主要区域，可以细分为新生代和老年代，新生代又分为Eden区和两个Survivor区。新创建的对象一般在Eden区，经过几次GC还存活的会进入老年代。堆的大小可以通过-Xms和-Xmx来设置。

然后是方法区，也叫永久代或者元空间。JDK8之前叫永久代，在堆里面，JDK8之后改成元空间了，直接用本地内存。方法区主要存储类的结构信息，比如类的字段、方法、常量池、静态变量这些编译期生成的数据。还有运行时常量池也在这里，存放编译期的字面量和符号引用。

再说线程私有的区域。每个线程都有自己的虚拟机栈，栈里存的是一个个栈帧，每调用一个方法就会创建一个栈帧压入栈中，方法执行完就出栈。栈帧里包含局部变量表、操作数栈、动态链接和方法返回地址。局部变量表存的是方法的参数和局部变量，操作数栈用来存放方法执行过程中的操作数。栈的大小可以通过-Xss设置，如果递归太深或者方法调用层次太多，会抛StackOverflowError。

还有本地方法栈，它跟虚拟机栈类似，只不过服务的是Native方法，就是那些用C或C++写的本地方法。

最后是程序计数器，它是一块很小的内存空间，记录当前线程执行的字节码指令地址。如果执行的是Java方法，计数器记录的是字节码指令地址，如果是Native方法，计数器值就是空。程序计数器是唯一一个在Java虚拟机规范中没有规定任何OutOfMemoryError情况的区域。

除了这些运行时数据区，还有直接内存，它不是JVM运行时数据区的一部分，但也会被频繁使用。NIO引入了基于通道和缓冲区的IO方式，可以使用Native函数直接分配堆外内存，通过DirectByteBuffer来引用和操作。直接内存不受JVM堆大小限制，但受本机总内存限制，分配不当也会导致OutOfMemoryError。

所以简单说，JVM内存就是堆、方法区、虚拟机栈、本地方法栈、程序计数器这几块，前两个线程共享，后三个线程私有。堆放对象，方法区放类信息，栈放方法调用，程序计数器记录执行位置。

17. 你知道哪些垃圾回收算法？

标记-清除算法

• ：标记-清除算法分为“标记”和“清除”两个阶段，首先通过可达性分析，标记出所有需要回收的对象，然后统一回收所有被标记的对象。标记-清除算法有两个缺陷，一个是效率问题，标记和清除的过程效率都不高，另外一个就是，清除结束后会造成大量的碎片空间。有可能会造成在申请大块内存的时候因为没有足够的连续空间导致再次 GC。

复制算法

• ：为了解决碎片空间的问题，出现了“复制算法”。复制算法的原理是，将内存分成两块，每次申请内存时都使用其中的一块，当内存不够时，将这一块内存中所有存活的复制到另一块上。然后将然后再把已使用的内存整个清理掉。复制算法解决了空间碎片的问题。但是也带来了新的问题。因为每次在申请内存时，都只能使用一半的内存空间。内存利用率严重不足。

标记-整理算法

• ：复制算法在 GC 之后存活对象较少的情况下效率比较高，但如果存活对象比较多时，会执行较多的复制操作，效率就会下降。而老年代的对象在 GC 之后的存活率就比较高，所以就有人提出了“标记-整理算法”。标记-整理算法的“标记”过程与“标记-清除算法”的标记过程一致，但标记之后不会直接清理。而是将所有存活对象都移动到内存的一端。移动结束后直接清理掉剩余部分。

分代回收算法

：分代收集是将内存划分成了新生代和老年代。分配的依据是对象的生存周期，或者说经历过的 GC 次数。对象创建时，一般在新生代申请内存，当经历一次 GC 之后如果对还存活，那么对象的年龄 +1。当年龄超过一定值(默认是 15，可以通过参数 -XX:MaxTenuringThreshold 来设定)后，如果对象还存活，那么该对象会进入老年代。

18. 手撕算法

快速排序算法

面试突击资源推荐 ：
✅Java/Go/C++ 面试刷题： xiaolincoding.com
✅程序员 1 对 1 AI 模拟面试：niumianoffer.com
✅后端训练营：Java/Go 后端训练营，出大成果了！✅大模型训练营：又出成绩了，转行去做大模型开发了！