2024面试复盘11

编程随想面经

字数统计: 6.8k阅读时长: 24 min

 2024/08/12   Share

前言

一周没写复盘了。上周主要是滴滴的一面，一个小公司的一面，还有个网易的线下面试。网易那个其实都在问简历的东西，方向不是很匹配，大概是凉了。今天是小公司的二面，可能面试官觉得之前做的东西不是业务开发，所以感觉机会也小。这次把两次面试一起复盘了。

复盘

TCP和UDP

TCP	UDP
是否面向连接	是	否
是否可靠	是	否
是否有状态	是	否
传输效率	较慢	较快
传输形式	字节流	数据报文段
首部开销	20 ～ 60 bytes	8 bytes
是否提供广播或多播服务	否	是

UDP 一般用于即时通信，比如：语音、视频、直播等等。这些场景对传输数据的准确性要求不是特别高，比如你看视频即使少个一两帧，实际给人的感觉区别也不大。

TCP 用于对传输准确性要求特别高的场景，比如文件传输、发送和接收邮件、远程登录等等。

ES作用？为什么不用mysql？mysql模糊查询？

ElasticSearch 是一个开源的分布式、RESTful 搜索和分析引擎，可以用来解决使用数据库进行模糊搜索时存在的性能问题，适用于所有类型的数据，包括文本、数字、地理空间、结构化和非结构化数据。

Elasticsearch 使用倒排索引来支持快速的全文搜索和复杂的查询操作。这使得 ES 能够高效地处理大量的非结构化数据（如日志）。ES 能够对多个字段进行模糊搜索、词语匹配、词干提取等复杂查询，并且性能优越。

MySQL 的主要索引结构是 B-Tree 索引，适合处理结构化数据和简单查询。但对于全文搜索、复杂查询和模糊匹配，性能较差。

虽然 MySQL 也支持全文索引（如 InnoDB 和 MyISAM 引擎），但其搜索功能和性能不如 Elasticsearch 强大，特别是在处理大量日志数据时。

mysql模糊查询有三种情况：

前缀匹配 (LIKE 'keyword%')：查找以 keyword 开头的记录，这种情况下如果 column_name 有索引，MySQL 可以有效利用索引。

后缀匹配 (LIKE '%keyword')：查找以 keyword 结尾的记录，通常索引无法生效。

全匹配 (LIKE '%keyword%')：查找包含 keyword 的记录，索引也通常无法生效。

对于 MySQL 的 InnoDB 或 MyISAM 引擎，如果要进行更高效的模糊查询，尤其是针对大文本数据，可以使用全文索引。全文索引适用于自然语言文本的查找，但它主要适用于针对整词的搜索，而不是部分匹配。

1	SELECT * FROM my_table WHERE MATCH(column_name) AGAINST('keyword');

字典树，KMP，AC自动机

聊到mysql搜索的时候面试官突然说到这个，好久了，这里复习一下。

字典树（Trie），也称为前缀树或单词查找树，是一种用于存储字符串集的数据结构，特别适合处理字符串前缀相关的问题。字典树的结构类似于一棵多叉树，每个节点代表字符串中的一个字符，通过节点之间的链接表示字符串的前缀关系。

字典树的基本特性

根节点不包含字符，它仅用于表示一个空字符串。
每个节点都表示一个字符，通过路径从根节点到某个节点，可以组成一个字符串。
每个节点的所有子节点表示不同的字符，即所有子节点不重复。
路径上的每个节点都对应一个前缀，从根节点到某个节点的路径表示一个字符串的前缀或完整字符串。

假设我们有一组单词集：["cat", "cap", "bat", "bad"]，它的字典树可能是这样的：

     root
     /  \
    c    b
   / \   / \
  a   a a   a
 /   /   \   \
t   p     d   t

字典树的优缺点

优点：
- 高效的前缀查找：对于前缀匹配和字符串查找，字典树可以在 O(m) 时间复杂度内完成操作，其中 m 是字符串的长度。
- 结构清晰：字典树的结构非常直观，特别适合处理字符串。
缺点：
- 空间消耗大：由于每个节点都需要存储多个子节点的引用，字典树的空间消耗较大，尤其在字符集较大的情况下。
- 不适合处理变长字符串：对于非常长的字符串，字典树的深度会很大，导致操作效率下降。

KMP

Knuth-Morris-Pratt 算法，用于在一个字符串中快速查找另一个字符串（即模式匹配问题）。查找单个模式的时间复杂度是 O(n)，其中 n 是主字符串的长度。

KMP算法：主要用于单个模式字符串在一个主字符串中的查找，适用于模式匹配问题。

字典树：用于存储和快速查询多个字符串，特别适合处理前缀查询、多模式匹配、自动补全等问题。

AC自动机

AC自动机，全称 Aho-Corasick 自动机，是一种多模式字符串匹配算法。它结合了 字典树（Trie） 和 KMP算法 的思想，用于在一个文本中同时查找多个模式字符串。AC自动机在网络安全、文本检索、DNA序列分析等领域有广泛应用。

AC自动机的构建和使用分为以下几个步骤：

构建字典树（Trie）把所有模式字符串插入到字典树中，构建一棵多叉树。
构建失败指针（Failure Pointer）在字典树的基础上，构建每个节点的失败指针。失败指针指向当前匹配失败时，应该转移到的下一个状态（即节点）。如果某个状态下的字符匹配失败，则通过失败指针跳转到另一个状态继续匹配，直到匹配成功或回到根节点。
匹配过程。在文本中进行匹配时，从根节点开始，逐个字符遍历文本。如果当前字符匹配成功，则进入下一个状态。如果匹配失败，则通过失败指针进行状态转移，继续匹配。

说实话这次面试官是个算法工程师，所以对算法比较在行。说实话我对算法不是很熟悉。

HTTP和RPC

HTTP （超文本传输协议）是一种应用层协议。

使用场景：

Web 浏览器与服务器之间的通信：加载网页、提交表单、下载文件等。
RESTful API：使用 HTTP 协议进行跨平台、跨语言的服务调用。

RPC 是一种分布式计算协议，它使得一个程序可以像调用本地函数一样，调用位于远程服务器上的函数或过程。RPC 的目的是隐藏网络通信的细节，让开发者可以专注于业务逻辑。

特性	HTTP	RPC
层次	应用层协议	分布式计算协议
通信模型	请求-响应	请求-响应（远程调用）
数据格式	通常为纯文本（如 JSON、HTML）	通常为二进制或自定义协议格式
状态性	无状态	通常有状态
透明性	明显的请求和响应分离	远程调用看起来像本地调用
适用场景	Web 开发、API 调用	微服务通信、分布式系统

HTTP 更适合于 Web 应用和简单的 API 调用，而 RPC 更适用于复杂的分布式系统和微服务架构。

redis作用

这个不再多说了。之前复习过好几次了。

其他问题都是项目介绍，就不展开了。

MongoDB用过吗？存什么数据？

MongoDB 是一个基于 分布式文件存储 的开源 NoSQL 数据库系统，由 C++ 编写的。MongoDB 提供了 面向文档 的存储方式，操作起来比较简单和容易，支持“无模式”的数据建模，可以存储比较复杂的数据类型，是一款非常流行的 文档类型数据库 。

适合存储的数据类型

非结构化数据：MongoDB 使用 BSON（Binary JSON）格式来存储数据，能够处理复杂的嵌套结构和多样化的数据类型，包括文档、数组、嵌套对象等。
动态模式的数据：对于数据模型经常变化的应用，MongoDB 允许文档之间的字段不一致，使得模式可以灵活调整。
大规模的数据：MongoDB 支持水平扩展（sharding），能够处理大规模的数据存储需求。

例如存储和管理不同类型的内容（如文章、评论、用户信息）以及内容的元数据。

灵活的数据模型：不同的内容可能有不同的字段和结构，如文章有标题、正文、作者等字段，评论有评论者、内容、时间等字段。MongoDB 的文档模型允许每个内容类型有不同的结构。

嵌套文档：可以在一个文档中嵌套评论，避免了复杂的联接操作。

{
  "_id": "article_123",
  "title": "Introduction to MongoDB",
  "author": "John Doe",
  "content": "MongoDB is a NoSQL database...",
  "comments": [
    {
      "user": "Alice",
      "comment": "Great article!",
      "date": "2024-08-10"
    },
    {
      "user": "Bob",
      "comment": "Very informative.",
      "date": "2024-08-11"
    }
  ]
}

又比如存储和处理来自大量设备的数据，如传感器数据、设备状态和日志。

高吞吐量和可扩展性：支持大规模数据写入，适合物联网场景中的实时数据采集。

时间序列数据：能够处理时间序列数据，支持高效的插入和查询操作。

mysql数据结构

BTree 索引：MySQL 里默认和最常用的索引类型。只有叶子节点存储 value，非叶子节点只有指针和 key。存储引擎 MyISAM 和 InnoDB 实现 BTree 索引都是使用 B+Tree，但二者实现方式不一样（前面已经介绍了）。

哈希索引：类似键值对的形式，一次即可定位。

RTree 索引：一般不会使用，仅支持 geometry 数据类型，优势在于范围查找，效率较低，通常使用搜索引擎如 ElasticSearch 代替。

全文索引：对文本的内容进行分词，进行搜索。目前只有 CHAR、VARCHAR ，TEXT 列上可以创建全文索引。一般不会使用，效率较低，通常使用搜索引擎如 ElasticSearch 代替。

B 树& B+树两者有何异同呢？

B 树的所有节点既存放键(key) 也存放数据(data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。
在 B 树中进行范围查询时，首先找到要查找的下限，然后对 B 树进行中序遍历，直到找到查找的上限；而 B+树的范围查询，只需要对链表进行遍历即可。

B+树与 B 树相比，具备更少的 IO 次数、更稳定的查询效率和更适于范围查询这些优势。

B+树为什么快

树的高度较低。B+树是一种自平衡的多路查找树，所有的叶子节点都在同一层。这意味着从根节点到任一叶子节点的路径长度（即树的高度）是相同的。
顺序存储叶子节点。B+树的所有数据都存储在叶子节点中，且所有叶子节点通过指针连接在一起形成一个有序链表。当需要进行范围查询（如查找某个区间内的所有数据）时，B+树可以从找到的起始叶子节点开始，顺序扫描后续的叶子节点，大大提高了查询效率。
分裂与合并减少磁盘I/O。在B+树中，节点分裂和合并的操作次数相对较少，因为每个节点可以包含多个元素。当插入或删除元素时，不会频繁触发树的重平衡操作，这减少了磁盘I/O操作的频率。由于树的高度较低，搜索过程中的磁盘I/O次数较少，而磁盘I/O通常是数据库系统中的瓶颈，因此 B+ 树能够显著提高查找速度。
所有键值在叶子节点上。在 B+ 树中，所有实际数据（键值对）都存储在叶子节点上，中间节点只存储键值用于指引搜索路径。这意味着每次查找最终都会访问到叶子节点，避免了不必要的键值访问，简化了搜索路径。

前缀查找与全文检索

前缀查找和全文检索是两种不同的查询方式。前缀查找通常是基于B+树索引（如 BTREE 索引）的查询方式，通过匹配字符串的前缀来进行快速定位。例如，WHERE column LIKE 'abc%' 这样的查询就是典型的前缀查找。

全文检索（Full-Text Search）是一种基于全文索引的查询方式，专门用于查找大文本中的关键词。MySQL 提供的 FULLTEXT 索引可以支持自然语言模式和布尔模式下的全文检索。

前缀查找通常比全文检索快，因为它只需在索引中定位前缀即可，而全文检索需要更复杂的计算和匹配操作。不过，这也取决于数据的规模和具体的查询条件。

全文检索更灵活，可以查找文本中的任意位置，而前缀查找只能匹配字符串的开头部分。

如果你只需要匹配字符串的前缀（如用户名查找），前缀查找更合适且更快；但如果你需要在大文本中查找关键词（如文章搜索），全文检索则更适合，尽管速度可能略慢。

mysql调优

这个其实需要具体问题具体分析，前面也有一些复盘提过这个。

Redis线程模型

对于读写命令来说，Redis 一直是单线程模型。不过，在 Redis 4.0 版本之后引入了多线程来执行一些大键值对的异步删除操作， Redis 6.0 版本之后引入了多线程来处理网络请求（提高网络 IO 读写性能）。

Redis 基于 Reactor 模式设计开发了一套高效的事件处理模型 （Netty 的线程模型也基于 Reactor 模式，Reactor 模式不愧是高性能 IO 的基石），这套事件处理模型对应的是 Redis 中的文件事件处理器（file event handler）。由于文件事件处理器（file event handler）是单线程方式运行的，所以我们一般都说 Redis 是单线程模型。

既然是单线程，那怎么监听大量的客户端连接呢？

Redis 通过 IO 多路复用程序 来监听来自客户端的大量连接（或者说是监听多个 socket），它会将感兴趣的事件及类型（读、写）注册到内核中并监听每个事件是否发生。

这样的好处非常明显：I/O 多路复用技术的使用让 Redis 不需要额外创建多余的线程来监听客户端的大量连接，降低了资源的消耗（和 NIO 中的 Selector 组件很像）。

虽然说 Redis 是单线程模型，但实际上，Redis 在 4.0 之后的版本中就已经加入了对多线程的支持。

不过，Redis 4.0 增加的多线程主要是针对一些大键值对的删除操作的命令，使用这些命令就会使用主线程之外的其他线程来“异步处理”，从而减少对主线程的影响。

为此，Redis 4.0 之后新增了几个异步命令：

UNLINK：可以看作是 DEL 命令的异步版本。
FLUSHALL ASYNC：用于清空所有数据库的所有键，不限于当前 SELECT 的数据库。
FLUSHDB ASYNC：用于清空当前 SELECT 数据库中的所有键。

Redis6.0 引入多线程主要是为了提高网络 IO 读写性能，因为这个算是 Redis 中的一个性能瓶颈（Redis 的瓶颈主要受限于内存和网络）。

虽然，Redis6.0 引入了多线程，但是 Redis 的多线程只是在网络数据的读写这类耗时操作上使用了，执行命令仍然是单线程顺序执行。

Redis如何做主从同步

当从节点启动并配置为从主节点复制数据时，从节点会向主节点发送 PSYNC 命令，表示希望与主节点同步。
如果从节点是第一次与主节点同步，主节点会执行全量同步。如果从节点曾经同步过，但与主节点的连接中断了一段时间，主节点会尝试进行增量同步（如果从节点的复制偏移量与主节点匹配）。
主节点生成当前内存数据的快照（RDB 文件），并将该快照发送给从节点。从节点接收快照文件并将其加载到内存中，完成数据同步。在快照传输的同时，主节点会继续记录新的写操作，并在快照传输完成后将这些增量操作也发送给从节点。
当主节点判断从节点可以进行增量同步时，主节点只将从节点缺失的那部分命令发送给从节点。从节点执行这些命令，从而使自身的数据与主节点保持一致。
从节点与主节点保持长连接，主节点会实时将所有写命令传播给从节点，使得从节点的数据保持与主节点同步。

mq的选型

首先要明确业务需求，包括但不限于以下几点：

消息的吞吐量：预估系统每秒钟需要处理的消息数量。
消息的延迟要求：消息传递的实时性要求如何，是否可以容忍延迟。
消息持久化：是否需要消息的持久化存储，以便系统故障时能够恢复。
消息的顺序性：消息是否需要保证严格的顺序性。
消息的可靠性：是否需要确保消息不丢失、不重复。
可扩展性：系统未来可能需要的扩展能力。
与现有技术栈的兼容性：是否与现有的技术栈兼容，或者团队是否擅长使用。

Apache Kafka

特点：

高吞吐量，支持大规模数据传输。
适合处理流式数据，如日志、事件数据的实时处理。
数据持久化存储，支持消息重放。
强大的分区机制，支持消息的水平扩展。
有时会存在消息延迟，尤其是在高吞吐场景下。

适用场景：

实时数据处理、日志收集和分析、事件驱动架构、流处理等。
大数据相关的应用场景。

RabbitMQ

特点：

支持丰富的消息路由规则（如发布/订阅、点对点、路由键）。
高可靠性，支持消息确认机制、持久化、镜像队列等。
支持复杂的消息路由和协议（如 AMQP、STOMP、MQTT）。
吞吐量较 Kafka 低，但延迟较低。

适用场景：

金融系统、订单处理、需要复杂路由逻辑的场景。
高可靠性、高一致性要求的应用。

kafka如何实现负载均衡

这个我可能理解错了，我以为说的是部署如何实现负载均衡。其实应该是使用上的消息负载均衡。

主题（Topic）与分区（Partition）

分区的概念：Kafka 将每个主题（Topic）分成多个分区（Partition），每个分区都是一个有序的消息队列。消息会被分发到不同的分区中，每个分区只能被一个消费者组中的一个消费者消费。
负载均衡的基础：分区是实现负载均衡的基本单位。Kafka 通过将消息分配到不同的分区来实现消息的分布，而消费者组内的消费者则通过消费不同的分区来实现负载均衡。

生产者端的负载均衡

分区选择策略：生产者在发送消息时，需要决定消息发送到哪个分区。Kafka 提供了几种分区选择策略：
- 轮询策略（Round-Robin）：消息被轮询地发送到每一个分区。这种方式简单而均匀。
- 基于键的分区策略：如果消息携带了一个键，Kafka 会根据这个键的哈希值来选择分区。这样可以保证相同键的消息总是被发送到相同的分区，实现消息的有序性。
- 自定义分区器：用户可以实现自己的分区器逻辑，控制消息如何分布到不同的分区。

消费者端的负载均衡

消费者组：Kafka 通过消费者组实现消费负载的自动均衡。每个消费者组由多个消费者实例组成，每个消费者实例负责消费一部分分区。
- 消费者组的分区分配：Kafka 会自动将分区分配给消费者组中的消费者。默认的分配策略是均匀分配（Range Assignor）或轮询分配（RoundRobin Assignor）。如果消费者的数量发生变化（如新消费者加入或消费者退出），Kafka 会重新平衡分区分配，以确保每个消费者分配到的分区数量大致相等。
再平衡（Rebalance）：当消费者组中的消费者发生变化时（如新增消费者、消费者故障退出等），Kafka 会触发再平衡操作。再平衡过程会重新分配分区，以确保新的消费者组中的每个消费者都能公平地消费分区。再平衡过程中，消费者可能会暂停消费一段时间，直到新的分配完成。

kafka场景题

同一个topic，两个不同的消费者组，一个消费到5，第二个消费者组没有消费者，此时第二个消费者组进来一个消费者，此时应该消费什么？

没遇到过这种场景，蒙了一下，还蒙错了。不同消费者组其实是相互独立的。

不同消费者组的消费行为

相互独立：不同的消费者组是相互独立的，每个消费者组都会消费主题中的所有消息。也就是说，Kafka 会为每个消费者组维护独立的消费偏移量（offset），每个消费者组会从自己的偏移量开始消费消息。
重复消费：由于不同的消费者组独立消费消息，每个消费者组中的消费者实例都会消费主题中的全部消息。因此，同一个主题的不同消费者组会重复消费这些消息。

假设有一个主题 TopicA，它有 2 个分区，存在两个消费者组 Group1 和 Group2，每个消费者组中各有 2 个消费者实例。

Group1 的两个消费者实例分别消费 TopicA 的两个分区中的消息。
Group2 的两个消费者实例也会分别消费 TopicA 的两个分区中的消息。

算法1：topK问题

之前写过文章。就回答了三种算法。

排序

快排时间复杂度O(nlogn)

堆

使用一个大小为 K 的最小堆来维护当前遇到的前 K 个最大元素。

时间复杂度O(N log K)。其中 N 是元素的总数，K 是需要找出的最大元素数量。

快速选择法

基于快速排序的思想，使用分治法找到前 K 个元素。使用快速排序的分区（partition）方法，每次将集合划分成两部分，一部分比基准元素小，另一部分比基准元素大。判断基准元素的位置是否为第 K 大元素的位置，如果是，则前 K 个元素已经找到，否则继续递归处理相应的部分。

平均 O(N)，最坏 O(N^2)，平均情况下，快速选择法可以在线性时间内找到前 K 个元素，但在极端情况下，时间复杂度会退化为 O(N^2)。

桶排序法

将元素分到不同的桶中，根据需要的 K 值只处理最靠近的几个桶。

确定桶的数量和范围。
将元素分配到相应的桶中。
对包含最大元素的桶进行排序，然后找出前 K 大的元素。

O(N)（分配到桶的操作）+ O(K log K)（在目标桶中排序）。

算法2：两个栈实现队列

主要思路：

将元素推入栈 stack1 中；
当需要出队列时，如果 stack2 为空，就将 stack1 中的所有元素逐个弹出，并推入 stack2，这样 stack2 中的元素顺序就是先进先出的顺序；
从 stack2 中弹出的元素就是队列的出队元素。

import java.util.Stack;

public class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    // 入队操作
    public void push(int x) {
        stack1.push(x);
    }

    // 出队操作
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    // 获取队列头部元素
    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    // 判断队列是否为空
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}