字节跳动，差点跪在一面！

前几天，字节跳动也开始春季校园招聘了，针对的是 24 届校招和 25 届实习的同学，经过这么一周的时间，感觉互联网大厂全部都启动春招了。

字节跳动

当然，春招 3 月份开始并不是3 月份就会结束，还没准备好的同学，也不用太着急。

春招实习其实跨越的周期还蛮长的，3-7 月份之间都有机会，甚至后面也会有日常实习的机会，所以还没准备好的同学，先把面试该学的内容准备好一点。

不然一问三，投的早，也是炮灰呀，特别是算法，得刷熟练，字节喜欢考算法，每一面必有一题算法，有时候 2-3 题也会有可能，没手撕出来，很容易就寄了。

今天分享一位同学的字节后端开发的面经，主要针对基础知识拷打了一波，算法在提示下写出来，差点跪了。

我罗列下这次面经考察的知识内容：

• 网络：键入网址、http、tcp、子网掩码
• 操作系统：进程线程、进程和线程间通信、虚拟内存、软链接与硬链接、死锁
• mysql：b+树
• redis：数据结构、延迟队列的实现、redis 切片集群
• jvm：内存结构、垃圾回收
• 算法：数组最大子串和

网络

浏览器键入网址全过程？

输入URL过程如下：

• DNS 解析：当用户输入一个网址并按下回车键的时候，浏览器获得一个域名，而在实际通信过程中，我们需要的是一个 IP 地址，因此我们需要先把域名转换成相应 IP 地址。
• TCP 连接：浏览器通过 DNS 获取到 Web 服务器真正的 IP 地址后，便向 Web 服务器发起 TCP 连接请求，通过 TCP 三次握手建立好连接。
• 建立TCP协议时，需要发送数据，发送数据在网络层使用IP协议， 通过IP协议将IP地址封装为IP数据报；然后此时会用到ARP协议，主机发送信息时将包含目标IP地址的ARP请求广播到网络上的所有主机，并接收返回消息，以此确定目标的物理地址，找到目的MAC地址；
• IP数据包在路由器之间，路由选择使用OPSF协议， 采用Dijkstra算法来计算最短路径树，抵达服务端。
• 发送 HTTP 请求：建立 TCP 连接之后，浏览器向 Web 服务器发起一个 HTTP 请求（如果是HTTPS协议，发送HTTP 请求之前还需要完成TLS四次握手）；
• 处理请求并返回：服务器获取到客户端的 HTTP 请求后，会根据 HTTP 请求中的内容来决定如何获取相应的文件，并将文件发送给浏览器。
• 浏览器渲染：浏览器根据响应开始显示页面，首先解析 HTML 文件构建 DOM 树，然后解析 CSS 文件构建渲染树，等到渲染树构建完成后，浏览器开始布局渲染树并将其绘制到屏幕上。

http为什么是无状态？

HTTP被称为无状态协议是因为每个HTTP请求之间是相互独立的，服务器不会在不同请求之间保留客户端的状态信息。这意味着每个HTTP请求都是独立的，服务器不会记住先前的请求或会话状态。

HTTP无状态的原因：

1. 简单性：无状态使得HTTP协议设计更加简单和灵活，每个请求都可以独立处理，不需要维护复杂的状态信息。
2. 可伸缩性：由于服务器不需要保留客户端状态信息，可以更容易地进行水平扩展，处理更多的并发请求。
3. 易于缓存：无状态使得缓存更加有效，可以缓存响应并在多个请求之间共享，提高性能和减少网络流量。

尽管HTTP是无状态的，但为了处理用户会话和状态管理，通常会使用一些机制来维护状态信息，比如使用Cookies、Session等技术来跟踪用户状态。

三次握手过程介绍一下

TCP 是面向连接的协议，所以使用 TCP 前必须先建立连接，而建立连接是通过三次握手来进行的。三次握手的过程如下图：

TCP 三次握手

• 一开始，客户端和服务端都处于 CLOSE 状态。先是服务端主动监听某个端口，处于 LISTEN 状态
• 客户端会随机初始化序号（client_isn），将此序号置于 TCP 首部的「序号」字段中，同时把 SYN 标志位置为 1，表示 SYN 报文。接着把第一个 SYN 报文发送给服务端，表示向服务端发起连接，该报文不包含应用层数据，之后客户端处于 SYN-SENT 状态。
• 服务端收到客户端的 SYN 报文后，首先服务端也随机初始化自己的序号（server_isn），将此序号填入 TCP 首部的「序号」字段中，其次把 TCP 首部的「确认应答号」字段填入 client_isn + 1, 接着把 SYN 和 ACK 标志位置为 1。最后把该报文发给客户端，该报文也不包含应用层数据，之后服务端处于 SYN-RCVD 状态。
• 客户端收到服务端报文后，还要向服务端回应最后一个应答报文，首先该应答报文 TCP 首部 ACK 标志位置为 1 ，其次「确认应答号」字段填入 server_isn + 1 ，最后把报文发送给服务端，这次报文可以携带客户到服务端的数据，之后客户端处于 ESTABLISHED 状态。
• 服务端收到客户端的应答报文后，也进入 ESTABLISHED 状态。

一旦完成三次握手，双方都处于 ESTABLISHED 状态，此时连接就已建立完成，客户端和服务端就可以相互发送数据了。

子网掩码的作用 是什么？

网掩码用于定义一个IP地址中哪部分是网络地址，哪部分是主机地址。其作用包括：

• 划分网络和主机：子网掩码通过指示IP地址中的网络部分和主机部分的划分，帮助路由器识别网络内部和网络间的通信。
• 确定网络范围：通过与IP地址进行逻辑与操作，子网掩码帮助确定一个IP地址所在的网络范围，以便正确路由数据包。

操作系统

进程和线程的区别

进程间通信有哪些？

进程间通信的方式有多种，包括：

1. 管道（Pipe）：单向通信，适用于有亲缘关系的进程（父子进程）之间通信。
   • 优点：简单易用，适用于单向通信。
   • 缺点：只能在有亲缘关系的进程之间使用，且只能实现单向通信。
2. 命名管道（Named Pipe）：允许无亲缘关系的进程间进行通信。
   • 优点：允许无亲缘关系的进程进行通信。
   • 缺点：只能实现单向通信。
3. 消息队列（Message Queue）：实现进程间的异步通信，通过消息缓冲区传递数据。
   • 优点：支持异步通信，可以实现多对多通信。
   • 缺点：复杂度较高，需要处理消息的发送和接收。
4. 共享内存（Shared Memory）：多个进程共享同一块内存区域，实现高效的数据交换。
   • 优点：高效，适合大数据量的共享。
   • 缺点：需要处理同步和互斥问题，可能引起数据一致性和安全性问题。
5. 信号量（Semaphore）：用于进程间的同步和互斥控制。
   • 优点：可以实现进程间的同步和互斥。
   • 缺点：复杂度较高，需要处理信号量的管理。
6. 套接字（Socket）：适用于不同主机间的进程通信，可实现网络通信。
   • 优点：跨主机通信，支持多种通信协议。
   • 缺点：相比于其他方式，套接字通信开销较大。

线程间通信知道哪些？

在Linux系统中，线程间通信的方式包括：

• 互斥锁（Mutex）：线程可以使用互斥锁来保护共享资源，确保同时只有一个线程可以访问该资源。
• 条件变量：线程可以使用条件变量来等待特定条件的发生，以实现线程间的协调和通知。
• 信号量：线程可以使用信号量来控制对共享资源的访问，实现线程间的同步和互斥。
• 读写锁：允许多个线程同时读取共享资源，但只允许一个线程写入共享资源。

虚拟内存是什么？有什么作用？

如果没有虚拟内存，程序读写的地址是物理地址的话，可能会出现物理地址冲突的问题，比如，第一个程序在 2000 的位置写入一个新的值，将会擦掉第二个程序存放在相同位置上的所有内容。

为了解决这个问题，就引出了虚拟内存，操作系统为每个进程分配独立的一套「虚拟地址」，人人都有，大家自己玩自己的地址就行，互不干涉。但是有个前提每个进程都不能访问物理地址，至于虚拟地址最终怎么落到物理内存里，对进程来说是透明的，操作系统已经把这些都安排的明明白白了。

进程的中间层

操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。

如果程序要访问虚拟地址的时候，由操作系统转换成不同的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，这样就不会冲突了。

最后，说下虚拟内存有什么作用？

• 第一，虚拟内存可以使得进程对运行内存超过物理内存大小，因为程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，我们可以把它换出到物理内存之外，比如硬盘上的 swap 区域。
• 第二，由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了多进程之间地址冲突的问题。

软连接和硬连接有什么区别？

软连接实际上是一个指向目标文件的路径的符号链接，类似于Windows系统中的快捷方式，创建软连接不会占用目标文件的inode节点，只是简单地指向目标文件的路径。删除原始文件后，软连接仍然存在，但指向的目标文件失效，称为"悬空链接"。软链接可以跨文件系统创建软连接。

硬连接是指多个文件实际上指向同一个inode节点，即多个文件共享同一块数据块。创建硬连接会增加目标文件的链接计数，删除任何一个硬连接并不会影响其他硬连接指向的文件数据。只能在同一文件系统内创建硬连接。

死锁条件是什么？

死锁只有同时满足以下四个条件才会发生：

• 互斥条件：是指多个线程不能同时使用同一个资源。
• 持有并等待条件：指当线程 A 已经持有了资源 1，又想申请资源 2，而资源 2 已经被线程 C 持有了，所以线程 A 就会处于等待状态，但是线程 A 在等待资源 2 的同时并不会释放自己已经持有的资源 1。
• 不可剥夺条件：指当线程已经持有了资源 ，在自己使用完之前不能被其他线程获取，线程 B 如果也想使用此资源，则只能在线程 A 使用完并释放后才能获取。
• 环路等待条件：指的是在死锁发生的时候，两个线程获取资源的顺序构成了环形链。

死锁的解决方法是什么？

产生死锁的四个必要条件是：互斥条件、持有并等待条件、不可剥夺条件、环路等待条件。

那么避免死锁问题就只需要破环其中一个条件就可以，最常见的并且可行的就是使用资源有序分配法，来破环环路等待条件。

那什么是资源有序分配法呢？

线程 A 和 线程 B 获取资源的顺序要一样，当线程 A 是先尝试获取资源 A，然后尝试获取资源 B 的时候，线程 B 同样也是先尝试获取资源 A，然后尝试获取资源 B。也就是说，线程 A 和 线程 B 总是以相同的顺序申请自己想要的资源。

我们使用资源有序分配法的方式来修改前面发生死锁的代码，我们可以不改动线程 A 的代码。

我们先要清楚线程 A 获取资源的顺序，它是先获取互斥锁 A，然后获取互斥锁 B。

所以我们只需将线程 B 改成以相同顺序的获取资源，就可以打破死锁了。

mysql

mysql 为什么用 b+树，而不是b树？

MySQL 默认的存储引擎 InnoDB 采用的是 B+ 作为索引的数据结构，原因有：

• B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少。
• B+ 树有大量的冗余节点（所有非叶子节点都是冗余索引），这些冗余索引让 B+ 树在插入、删除的效率都更高，比如删除根节点的时候，不会像 B 树那样会发生复杂的树的变化；
• B+ 树叶子节点之间用链表连接了起来，有利于范围查询，而 B 树要实现范围查询，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。

redis

redis数据结构有哪些？

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

• String 类型的应用场景：缓存对象、常规计数、分布式锁、共享 session 信息等。
• List 类型的应用场景：消息队列（但是有两个问题：1. 生产者需要自行实现全局唯一 ID；2. 不能以消费组形式消费数据）等。
• Hash 类型：缓存对象、购物车等。
• Set 类型：聚合计算（并集、交集、差集）场景，比如点赞、共同关注、抽奖活动等。
• Zset 类型：排序场景，比如排行榜、电话和姓名排序等。

用什么结构实现延迟消息队列？

延迟队列是指把当前要做的事情，往后推迟一段时间再做。延迟队列的常见使用场景有以下几种：

• 在淘宝、京东等购物平台上下单，超过一定时间未付款，订单会自动取消；
• 打车的时候，在规定时间没有车主接单，平台会取消你的单并提醒你暂时没有车主接单；
• 点外卖的时候，如果商家在10分钟还没接单，就会自动取消订单；

在 Redis 可以使用有序集合（ZSet）的方式来实现延迟消息队列的，ZSet 有一个 Score 属性可以用来存储延迟执行的时间。

使用 zadd score1 value1 命令就可以一直往内存中生产消息。再利用 zrangebysocre 查询符合条件的所有待处理的任务， 通过循环执行队列任务即可。

redis分片集群，如何分片的，有什么好处？

当 Redis 缓存数据量大到一台服务器无法缓存时，就需要使用 Redis 切片集群（Redis Cluster ）方案，它将数据分布在不同的服务器上，以此来降低系统对单主节点的依赖，从而提高 Redis 服务的读写性能。

Redis Cluster 方案采用哈希槽（Hash Slot），来处理数据和节点之间的映射关系。

在 Redis Cluster 方案中，一个切片集群共有 16384 个哈希槽，这些哈希槽类似于数据分区，每个键值对都会根据它的 key，被映射到一个哈希槽中，具体执行过程分为两大步：

• 根据键值对的 key，按照 CRC16 算法计算一个 16 bit 的值。
• 再用 16bit 值对 16384 取模，得到 0~16383 范围内的模数，每个模数代表一个相应编号的哈希槽

也就是：CRC16(key1)%16384，就能得到 key 对应的哈希槽编号，然后在通过编号找到对应的节点。

我通过一张图来解释数据、哈希槽，以及节点三者的映射分布关系。

上图中的切片集群一共有 2 个节点，假设有 4 个哈希槽（Slot 0～Slot 3）时，我们就可以通过命令手动分配哈希槽，比如节点 1 保存哈希槽 0 和 1，节点 2 保存哈希槽 2 和 3。

redis-cli -h 192.168.1.10 –p 6379 cluster addslots 0,1
redis-cli -h 192.168.1.11 –p 6379 cluster addslots 2,3

然后在集群运行的过程中，key1 和 key2 计算完 CRC16 值后，对哈希槽总个数 4 进行取模，再根据各自的模数结果，就可以被映射到哈希槽 1（对应节点1） 和 哈希槽 2（对应节点2）。

jvm

jvm内存分布说一下

图片

JVM的内存结构主要分为以下几个部分：

• 程序计数器（Program Counter Register）：每个线程都有一个程序计数器。当线程执行 Java 方法时，程序计数器保存当前执行指令的地址，以便在 JVM 调用其他方法或恢复线程执行时重新回到正确的位置。
• Java 虚拟机栈（Java Virtual Machine Stacks）：每个线程都有一个虚拟机栈。虚拟机栈保存着方法执行期间的局部变量、操作数栈、方法出口等信息。线程每调用一个 Java 方法时，会创建一个栈帧（Stack Frame），栈帧包含着该方法的局部变量、操作数栈、方法返回地址等信息。栈帧在方法执行结束后会被弹出。
• 本地方法栈（Native Method Stack）：与 Java 虚拟机栈类似，但是为本地方法服务。
• Java 堆（Java Heap）：Java 堆是 Java 虚拟机中最大的一块内存区域，用于存储各种类型的对象实例，也是垃圾收集器的主要工作区域，Java 堆根据对象存活时间的不同，Java 堆还被分为年轻代、老年代两个区域，年轻代还被进一步划分为 Eden 区、From Survivor 0、To Survivor 1 区。
• 方法区（Method Area）：方法区也是所有线程共享的部分，它用于存储类的加载信息、静态变量、常量池、方法字节码等数据。在 Java 8 及以前的版本中，方法区被实现为永久代（Permanent Generation），在 Java 8 中被改为元空间（Metaspace）。

有垃圾回收的是哪些地方？

垃圾回收主要是针对堆内存中的对象进行的，包括以下几个方面：

• 堆内存：垃圾回收主要针对堆内存中不再被引用的对象进行回收，包括新生代和老年代中的对象。
• 永久代/元空间：虚拟机中存放类的元数据信息的区域，也会进行垃圾回收，即对不再使用的类信息进行清理。
• 字符串常量池：存放字符串常量的区域，也会进行垃圾回收，对不再被引用的字符串进行清理。

手撕

• 算法：数组最大子串和