在滴滴一面，被拷打了

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

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

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

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

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

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

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

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

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

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

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

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

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 preorderTraversal(TreeNode root) {List result = new ArrayList();
        traversePreOrder(root, result);
        return result;
    }

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

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

public class PreorderTraversalIterative {public List preorderTraversal(TreeNode root) {List result = new ArrayList();
        Deque 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 长连接的实现

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

TCP 短连接的实现

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

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 值后，就会被发送到死信队列中去。

步骤如下：

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

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

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

步骤如下：

1. 安装插件 ：在 RabbitMQ 服务器上安装rabbitmq_delayed_message_exchange 插件。

2. 创建延迟消息交换机 ：创建一个类型为x-delayed-message 的交换机。

3. 创建队列并绑定到延迟交换机：创建队列并将其绑定到延迟消息交换机上。

4. 发送带有延迟属性的消息 ：在发送消息时，可以设置x-delay 头来指定延迟的时间，单位是毫秒。

RabbitMQ 做延迟消息时有哪些注意事项

• 对于大量延迟消息，使用 rabbitmq_delayed_message_exchange 插件可能更优，因为它可以避免死信队列带来的额外复杂性和潜在的性能问题。
• 在使用死信队列方法时，确保 队列和消息的 TTL设置得当，以避免不必要的内存消耗。
• 在使用延迟消息插件时，确保 RabbitMQ 版本支持该插件，并且插件已经正确安装和启用。

以上，点亮【赞 与在看】让我们总能披荆斩棘，挑战自我。