酒香也怕巷子深。

大家好，我是皇子。

前面一篇文章罗列了百度的面经，也顺便介绍了下百度的萝卜快跑。

没想到针对无人驾驶车辆运营的问题，收到了很多留言，有些比较全面客观分析无人驾驶对就业情况分析的、有反对利用科技手段让底层人民就业难上加难的、还有一些留言因为涉及敏感话题被平台自动屏蔽的。

下面这位网友的点评还是很全面和客观的。

我的观点：科技的进步与发展必然会对当前现阶段的某些行业、岗位带来挑战，但随着政策层面的不断完善之后，也会催生出很多新的机会和岗位。

就如当时的滴滴刚跑出来的网约车模式的时候，对传统出租车行业和司机带来了很大的影响，首先是接单减少和价格下降。所以同样受到了很多人的抵制。

但是随着网约车的监管问题不断得到解决，这种模式也逐渐被民众所认可，也提高了大家的出行效率，不是吗？

另外百度的萝卜快跑项目同样会对滴滴出行的业务产生多方面的影响，包括在成本、价格和技术创新方面。

不过我相信一个公司或者平台只要他不断与时俱进，敢于创新总能在夹缝中生存。

况且滴滴就算面对无人驾驶运营目前阶段还是有很多优势的，如：成熟的运营模式、广泛的用户基础、丰富的交通环境路线规划以及突发情况处理的经验上。

好了，下面开始介绍一位滴滴的后端一面实习面经，可以说涉及的范围很多，特别是在网络这里，被拷打了。

有些问题思索了很久才做出了解答，虽然有些问题回答得不好，但是这位同学发现很多知识点他都可以慢慢串起来了，而且一面还顺利通过了。

下面稍微罗列一下，希望能帮助大家。

Java

接口与抽象类的区别

在Java中，接口（Interface）和抽象类（Abstract Class）都是用于实现抽象和多态性的工具，但它们之间存在一些关键的区别，这些区别主要体现在以下几个方面：

1、实现与继承：

接口：类通过implements关键字来实现接口。一个类可以实现多个接口，这意味着接口支持多重继承。
抽象类：类通过extends关键字来继承抽象类。一个类只能继承一个抽象类，这意味着抽象类仅支持单一继承。

2、方法定义

接口：在Java 8之前，接口中的所有方法都必须是抽象的（没有方法体），但从Java 8开始，接口可以包含默认方法（有方法体，使用default关键字）和静态方法。
抽象类：可以包含抽象方法（没有方法体）和具体方法（有方法体）。

3、访问修饰符

接口：接口中的方法默认是public的，变量默认是public static final的。
抽象类：抽象类中的方法和变量可以具有任何访问级别（public, protected, private）。

4、构造器和状态

接口：接口不能有构造器，不能保存状态（没有实例变量，除了static final的常量）。
抽象类：可以有构造器，可以保存状态（有实例变量）。

5、设计意图

接口：通常用于定义行为规范，即一个类“能够做什么”。
抽象类：用于定义共享的行为和状态，即一个类“是什么”。

6、实现要求

接口：实现接口的类必须实现接口中所有的抽象方法，除非该类本身也是抽象的。
抽象类：继承抽象类的子类可以选择性地实现抽象方法，或者保持抽象而不实现。

如何选择使用接口还是抽象类

接口主要用于定义一组方法的契约，而抽象类则用于提供部分实现以及共享的状态。

选择使用哪一种取决于你是否需要共享行为和状态（抽象类），还是仅仅需要定义一个行为的规范（接口）。

算法

手撕前序遍历二叉树

前序遍历的顺序是：先访问根节点，然后遍历左子树，最后遍历右子树

解法一：递归实现

递归方法是最直观的实现方式，它直接遵循前序遍历的顺序：

public class PreorderTraversal {

    // 前序遍历递归函数
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traversePreOrder(root, result);
        return result;
    }

    private void traversePreOrder(TreeNode node, List<Integer> list) {
        if (node == null) {
            return; // 如果节点为空，则返回
        }
        list.add(node.val); // 访问当前节点
        traversePreOrder(node.left, list); // 遍历左子树
        traversePreOrder(node.right, list); // 遍历右子树
    }
}

解法二：迭代方法通常使用栈来辅助实现前序遍历：

public class PreorderTraversalIterative {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>(); // 使用双端队列作为栈
        if (root != null) {
            stack.push(root); // 将根节点压入栈中
        }

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop(); // 弹出栈顶元素
            result.add(node.val); // 访问当前节点

            // 注意：右节点先入栈，左节点后入栈，这样弹出时会先处理左节点
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }
}

前序或者中序是否能确定二叉树，如何确定

要通过序列（如前序或中序序列）来确定是否能构成一棵二叉树，实际上并不足够。因为单凭前序或中序序列之一，无法唯一确定一棵二叉树的结构。

但是，如果提供了前序和中序序列，那么就可以唯一确定一棵二叉树的结构。

这是因为前序序列提供了根节点的信息，而中序序列提供了左子树和右子树节点的相对位置信息。

首先，从前序序列中获取根节点。
在中序序列中找到根节点的位置，这将中序序列划分为左子树和右子树的序列。
根据中序序列中的划分，从前序序列中分别提取出左子树和右子树的前序序列。
递归地应用上述过程，直到所有节点都被处理。
如果在任何步骤中发现冲突（比如前序序列和中序序列的分割不符合二叉树的规则），则不能构成一棵二叉树。

例如

给定前序序列 [1, 2, 4, 5, 3, 6] 和中序序列 [4, 2, 5, 1, 6, 3]，我们可以按照上述步骤来构建二叉树。

1、根节点是前序序列的第一个元素 1，在中序序列中找到 1，它左边的是左子树的中序序列 [4, 2, 5]，右边的是右子树的中序序列 [6, 3]。

2、接着，我们可以在前序序列中找到对应的左子树和右子树的前序序列，以此类推，直至构建完整棵树。

需要注意的是，以上过程假设序列中没有重复的元素，否则需要额外的逻辑来处理重复元素的情况。

网络

TCP的首部格式包含哪些重要数据

源端口/目标端口：源端口字段包含了发送数据的设备（通常是客户端或服务器）上应用程序的端口号；目标端口字段包含了接收数据的设备（通常是另一台服务器或客户端）上应用程序的端口号。
序号：用于对字节流进行编号，例如序号为 301，表示第一个字节的编号为 301，如果携带的数据长度为 100 字节，那么下一个报文段的序号应为 401。
确认号：期望收到的下一个报文段的序号。例如 B 正确收到 A 发送来的一个报文段，序号为 501，携带的数据长度为 200 字节，因此 B 期望下一个报文段的序号为 701，B 发送给 A 的确认报文段中确认号就为 701。
数据偏移 ：指的是数据部分距离报文段起始处的偏移量，实际上指的是首部的长度。
标记位 ACK（Acknowledgment）：确认标志位，用于确认收到的数据包序号。当 ACK=1 时确认号字段有效，否则无效。TCP 规定，在连接建立后所有传送的报文段都必须把 ACK 置 1。
标记位同步 SYN（Synchronize）：同步标志位，用于建立TCP连接。在建立连接时，客户端发送一个SYN包，服务器回复一个SYN+ACK，客户端再回复一个ACK包，完成三次握手。当 SYN=1，ACK=0 时表示这是一个连接请求报文段。若对方同意建立连接，则响应报文中 SYN=1，ACK=1。
标记位PSH（Push）：推送标志位，用于告诉接收方立即将数据交给应用层处理，而不是等待缓冲区满了再交付。
标记位RST（Reset）：重置标志位，用于强制关闭TCP连接。当收到一个无效的数据包时，可以发送一个RST包，强制关闭连接。
标记位URG（Urgent）：紧急标志位，用于表示TCP数据包中有紧急数据需要尽快处理。
标记位 FIN（Finish）：结束标志位，用于关闭TCP连接。在关闭连接时，一方发送一个FIN包，另一方回复一个ACK包，然后再发送一个FIN包，对方再回复一个ACK包，完成四次挥手。当 FIN=1 时，表示此报文段的发送方的数据已发送完毕，并要求释放连接。
窗口：窗口值作为接收方让发送方设置其发送窗口的依据。之所以要有这个限制，是因为接收方的数据缓存空间是有限的。

在TCP协议中，TCP首部中ACK、SYN、PSH、FIN、RST、URG标志位，用于控制TCP连接的建立、维护和关闭。

这些标志位可以组合使用，例如SYN+ACK表示建立连接的确认包，FIN+ACK表示关闭连接的确认包等等。

TCP的三次握手过程

假设 A 为客户端，B 为服务器端。

首先 B 处于 LISTEN（监听）状态，等待客户的连接请求。
A 向 B 发送连接请求报文，SYN=1，ACK=0，选择一个初始的序号 x。
B 收到连接请求报文，如果同意建立连接，则向 A 发送连接确认报文，SYN=1，ACK=1，确认号为 x+1(x+数据长度。因为tcp建立连接三次握手中的固定的数据长度，所以是x+1)，同时也选择一个初始的序号 y。
A 收到 B 的连接确认报文后，还要向 B 发出确认，确认号为 y+1，序号为 x+1。
B 收到 A 的确认后，连接建立。

TCP三次握手的原因

第三次握手是为了防止失效的连接请求到达服务器，让服务器错误打开连接。

客户端发送的连接请求如果在网络中滞留，那么就会隔很长一段时间才能收到服务器端发回的连接确认。客户端等待一个超时重传时间之后，就会重新请求连接。但是这个滞留的连接请求最后还是会到达服务器。

如果不进行三次握手，那么服务器就会打开两个连接。

如果有第三次握手，客户端会忽略服务器之后发送的对滞留连接请求的连接确认，不进行第三次握手，因此就不会再次打开连接。

TCP的四次挥手

以下描述不讨论序号和确认号，因为序号和确认号的规则比较简单。并且不讨论 ACK，因为 ACK 在连接建立之后都为 1。

A 发送连接释放报文，FIN=1。
B 收到之后发出确认，此时 TCP 属于半关闭状态，进入CLOSE-WAIT状态，B 能向 A 发送数据但是 A 不能向 B 发送数据。
当 B 不再需要连接（B在处理的请求全部发送给了A）时，发送连接释放报文，FIN=1。
A 收到后发出确认，进入 TIME-WAIT 状态，等待 2 MSL（最大报文存活时间）后释放连接。
B 收到 A 的确认后释放连接。

2MSL是什么

MSL（Maximum Segment Lifetime）是TCP协议中的一个参数，它指的是一个分段在网络中最长的生存时间。

MSL的具体取值通常是由操作系统决定的，并且通常在几十秒到几分钟之间。

2MSL是MSL的两倍，即2倍的最大分段生存期时间。

在TCP连接关闭过程中，主动关闭连接的一方发送最后一个ACK报文后，需要等待2MSL的时间，才能认为连接已经彻底关闭。

TCP四次挥手的原因

客户端发送了 FIN 连接释放报文之后，服务器收到了这个报文，就进入了 CLOSE-WAIT 状态。这个状态是为了让服务器端发送还未传送完毕的数据，传送完毕之后，服务器会发送 FIN 连接释放报文。

TCP的长连接和短连接是如何实现的

TCP的长连接和短连接主要是指TCP连接的生命周期以及连接管理策略，它们的实现涉及到TCP连接的建立、数据传输和关闭过程。

TCP长连接的实现

建立连接：通过TCP的三次握手建立连接。这是所有TCP连接的开始，无论长连接还是短连接。
数据传输：一旦连接建立，就可以在这条连接上进行多次的数据传输。在长连接中，连接建立后不会立即关闭，而是保持开放状态，等待后续的数据发送。
维持连接：为了防止连接因空闲过久而被中间的路由器或防火墙断开，TCP协议中包含了保活机制（Keepalive）。当连接处于空闲状态超过一定时间后，会自动发送保活探测包来检测连接是否仍然有效。
关闭连接：当不再需要这条连接时，通过四次挥手（或三次挥手，取决于主动关闭方是否还有数据发送）来优雅地关闭连接。在长连接中，这个关闭动作通常发生在通信双方完成所有数据交换之后。

TCP短连接的实现

建立连接：同样通过TCP的三次握手建立连接。
数据传输：短连接中，连接建立后，进行一次或几次数据传输后就会立即关闭连接。这意味着每次数据交互都需要重新建立和关闭连接。
关闭连接：在数据传输完成后，立即执行四次挥手来关闭连接。由于连接在每次数据交换后都会被关闭，所以不存在维持连接的阶段。

TCP的长连接和短连接如何选择

长连接：长连接减少了频繁建立和关闭连接带来的性能损耗，适合于需要频繁交互的应用场景，如数据库连接、持续的聊天服务等。但是，长连接也会占用更多的系统资源（如文件描述符），因此需要适当管理，避免资源耗尽。
短连接：短连接适合于数据交互不频繁的场景，如普通的HTTP请求（尽管现代HTTP/1.1通常使用长连接）。短连接的优点在于管理简单，存在的连接都是活跃的，没有维护空闲连接的开销。

长连接接占用的文件描述符超过了限制需要如何做

当长连接占用的文件描述符超过系统限制时，这通常会导致新的连接请求无法被接受，因为没有可用的文件描述符来分配给新的套接字。

所以当长连接接占用的文件描述符超过了限制，需要考虑如下做法：

1、调整系统级文件描述符限制

可以通过编辑/etc/security/limits.conf文件来永久增加每个用户进程的文件描述符限制。
编辑/etc/sysctl.conf来增加整个系统的文件描述符限制，例如：
```
fs.file-max = 1000000
```

2、调整进程级文件描述符限制

使用ulimit命令临时增加当前shell及其子进程的文件描述符限制：
```
ulimit -n 100000
```
或者在脚本中添加：
```
ulimit -SHn 100000
```
这将在脚本运行时增加限制，并在脚本结束时恢复原始限制。

3、优化应用程序

使用连接池：如果你的应用程序需要与数据库或其他服务建立大量连接，考虑使用连接池来复用现有的连接，减少文件描述符的使用。
合理管理长连接：确保长连接在不使用时被及时关闭，避免不必要的空闲连接占用资源。
使用事件驱动模型：如使用epoll或kqueue等I/O多路复用技术，这些技术可以让一个进程同时监听多个套接字，从而减少每个连接所需的资源，进而可以打开的更多的文件描述符。

4、监控和诊断

使用lsof命令来查看哪些进程占用了多少文件描述符。
使用strace命令来追踪系统调用，找出哪些操作导致了文件描述符的使用。
定期检查系统日志，查找与文件描述符相关的错误信息。

5、分布式负载均衡

如果单个服务器的文件描述符限制已经达到瓶颈，考虑使用分布式系统或负载均衡器来分散连接请求，减少单一服务器的负担。

此处有个需要注意的是：

分布式系统中的负载均衡器一般都会具有更好的配置，以及采用了前面4个阶段的优化手段。

MySQL

说说 MySQL 的基础架构

客户端：最上层的服务并不是MySQL所独有的，大多数基于网络的客户端/服务器的工具或者服务都有类似的架构。比如连接处理、授权认证、安全等等。
Server层：大多数MySQL的核心服务功能都在这一层，包括查询解析、分析、优化、缓存以及所有的内置函数（例如，日期、时间、数学和加密函数），所有跨存储引擎的功能都在这一层实现：存储过程、触发器、视图等。
存储引擎层：第三层包含了存储引擎。存储引擎负责MySQL中数据的存储和提取。Server层通过API与存储引擎进行通信。这些接口屏蔽了不同存储引擎之间的差异，使得这些差异对上层的查询过程透明。

MySQL怎么存储emoji

MySQL可以直接使用字符串存储emoji。

但是需要注意的，utf8 编码是不行的，MySQL中的utf8是阉割版的 utf8，它最多只用 3 个字节存储字符，所以存储不了表情。那该怎么办？

需要使用utf8mb4编码。

alter table blogs modify content text CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci not null;

为什么使用索引会加快查询？

传统的查询方法，是按照表的顺序遍历的，不论查询几条数据，MySQL需要将表的数据从头到尾遍历一遍。

在我们添加完索引之后，MySQL一般通过BTREE算法生成一个索引文件，在查询数据库时，找到索引文件进行遍历，在比较小的索引数据里查找，然后映射到对应的数据，能大幅提升查找的效率。

和我们通过书的目录，去查找对应的内容，一样的道理。

索引是不是建的越多越好呢？

当然不是。

索引会占据磁盘空间。
索引虽然会提高查询效率，但是会降低更新表的效率。比如每次对表进行增删改操作，MySQL不仅要保存数据，还有保存或者更新对应的索引文件。

消息队列

RabbitMQ如何做延迟消息

RabbitMQ 支持两种主要的方式来实现延迟消息：

使用死信队列 (Dead Letter Exchanges)
使用延迟消息交换机插件 (rabbitmq_delayed_message_exchange)

1、使用死信队列 (Dead Letter Exchanges)

这种方法涉及创建一个死信队列和一个死信交换机。

当消息的TTL（Time To Live）到期时，消息会变成死信并被发送到死信交换机，最终到达死信队列。在原队列中，你可以设置一个TTL属性，这样消息在队列中停留的时间超过这个TTL值后，就会被发送到死信队列中去。

步骤如下：

创建死信交换机：这是一个专门用来接收和处理死信的交换机。
创建死信队列：用来接收从死信交换机转发过来的消息。
创建常规队列：这个队列将包含延迟消息，且需要设置TTL属性。
将常规队列与死信交换机绑定：通过设置队列的x-dead-letter-exchange参数为死信交换机的名字，以及x-dead-letter-routing-key为死信队列的路由键，这样当消息过期时，它会被转发到死信队列。

2、使用延迟消息交换机插件 (rabbitmq_delayed_message_exchange)

这个方法更为直接，它使用一个特殊的插件来将消息延迟到未来某个时间点再投递。此插件需要在RabbitMQ中安装和启用。