淘米科技C++二面
来源：https://www.nowcoder.com/feed/main/detail/3bddc6d3ebb745be8d8690569d934dad
1、手撕：字符串的排列
问题描述：
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
思路：
- 首先，统计字符串 s1 中每个字符的出现次数，可以使用哈希表来实现，将字符作为键，出现次数作为值。
- 接下来，创建一个大小为 s1.length() 的滑动窗口，从 s2 的开头开始，依次向右滑动。
- 在滑动窗口中，也维护一个哈希表来统计当前窗口内的字符出现次数。
- 在滑动过程中，检查当前窗口的哈希表是否与 s1 的哈希表匹配，如果匹配，表示找到了 s1 的一个变位词。
- 滑动窗口一步一步地移动，直到窗口大小等于 s1 的长度。然后，每次移动窗口时，更新窗口内字符的统计信息。
- 如果找到一个变位词，返回 true，否则继续滑动窗口直到 s2 的末尾。
参考代码：
C++
#include <iostream>
#include <unordered_map>
bool checkInclusion(std::string s1, std::string s2) {
if (s1.length() > s2.length()) return false;
std::unordered_map<char, int> s1Count;
std::unordered_map<char, int> windowCount;
// 统计 s1 中每个字符的出现次数
for (char c : s1) {
s1Count[c]++;
}
int left = 0, right = 0;
int validCount = 0; // 记录窗口内匹配的字符数量
while (right < s2.length()) {
char c = s2[right];
right++;
// 更新窗口内字符的统计信息
if (s1Count.find(c) != s1Count.end()) {
windowCount[c]++;
if (windowCount[c] == s1Count[c]) {
validCount++;
}
}
// 当窗口大小等于 s1 长度时，检查窗口内字符是否匹配 s1
while (right - left >= s1.length()) {
if (validCount == s1Count.size()) {
return true;
}
char d = s2[left];
left++;
if (s1Count.find(d) != s1Count.end()) {
if (windowCount[d] == s1Count[d]) {
validCount--;
}
windowCount[d]--;
}
}
}
return false;
}
int main() {
std::string s1 = "abc";
std::string s2 = "eidbaooo";
if (checkInclusion(s1, s2)) {
std::cout << "s2 contains a permutation of s1." << std::endl;
} else {
std::cout << "s2 does not contain a permutation of s1." << std::endl;
}
return 0;
}2、手撕：数组只有0或1，最多改K个0为1，求最长连续1的长度 题目描述：
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
思路：
- 维护一个窗口，初始时窗口的左边界为 0，右边界为 0。
- 移动右边界以扩展窗口，直到窗口内的 0 的数量超过 k 为止。在这个过程中，你可以记录 0 的数量，并在右边界每次移动时更新窗口内的 0 的数量。
- 一旦窗口内的 0 的数量超过了 k，你需要移动左边界，缩小窗口，直到窗口内的 0 的数量不再超过 k。
- 在窗口扩展和收缩的过程中，记录窗口内连续 1 的最大个数。
参考代码：
C++
#include <iostream>
#include <vector>
int longestOnes(std::vector<int>& nums, int k) {
int left = 0; // 窗口左边界
int maxOnes = 0; // 记录最大的连续 1 的个数
int zeroCount = 0; // 记录窗口内 0 的数量
for (int right = 0; right < nums.size(); right++) {
if (nums[right] == 0) {
zeroCount++;
}
while (zeroCount > k) {
if (nums[left] == 0) {
zeroCount--;
}
left++;
}
maxOnes = std::max(maxOnes, right - left + 1);
}
return maxOnes;
}
int main() {
std::vector<int> nums = {1, 1, 0, 0, 1, 1, 1, 0, 1};
int k = 2;
int result = longestOnes(nums, k);
std::cout << "The maximum number of consecutive 1s after flipping at most " << k << " 0s is: " << result << std::endl;
return 0;
}3、redis响应慢怎么排查？
- 检查服务器负载： 首先，查看服务器的负载情况，包括 CPU 使用率、内存使用率、磁盘 I/O 等。高负载可能导致 Redis 响应变慢。
- 检查慢查询日志： 启用 Redis 的慢查询日志功能，检查是否有查询执行时间较长的命令。可以使用
SLOWLOG GET命令查看慢查询日志。如果发现慢查询，考虑优化这些查询。 - 监测内存使用： 使用
INFO命令或监控工具来监测 Redis 的内存使用情况。内存不足可能导致 Redis 响应变慢，需要考虑释放内存或增加内存。 - 检查持久化操作： 如果 Redis 在持久化操作（如 RDB 快照或 AOF 日志写入）时变慢，可以考虑调整持久化策略，减少持久化的频率。
- 网络问题： 检查网络连接是否正常，延迟是否较高。网络问题可能导致 Redis 响应时间增加。
- Redis 配置： 检查 Redis 配置文件，确保配置参数合理。可以尝试调整一些参数，如
maxmemory、maxclients、timeout等，以优化性能。 - 使用监控工具： 使用专业的 Redis 监控工具，如 Redis Sentinel、Redis Cluster、或第三方监控工具，来实时监测 Redis 的性能和状态。
- 使用客户端工具： 使用 Redis 客户端工具来测试 Redis 响应时间，以确定是整个 Redis 服务器慢还是特定操作慢。
- 缓存优化： 考虑是否需要更好的缓存策略，如增加缓存容量、采用 LRU（最近最少使用）算法、或使用更高效的数据结构。
4、根据4的回答反问，持久化开了另一个线程操作，主线程响应还是慢怎么排查，如何定位？
- 检查持久化操作是否阻塞主线程： 确保异步持久化线程没有因某些原因而阻塞或变慢。检查持久化线程的状态，确保它能够正常执行。
- 检查持久化任务的负载： 持久化操作本身可能会消耗系统资源。如果写入大量数据到磁盘，可能导致磁盘 I/O 压力增加。使用系统监控工具来查看持久化任务对系统资源的影响。
- 查看持久化配置： 检查 Redis 的持久化配置，包括 RDB 快照和 AOF 日志的策略、频率、文件路径等。合理配置这些参数，以平衡性能和数据安全。
- 监测持久化操作的执行时间： 使用 Redis 的
INFO命令或监控工具来监测持久化操作的执行时间。持久化操作的执行时间超过一定阈值可能会影响主线程的响应。 - 异步持久化的数据量： 如果异步持久化的数据量非常大，可能需要更快的磁盘和 I/O 子系统来处理它。磁盘性能不足可能导致持久化操作变慢。
- 系统资源监控： 使用系统监控工具来查看系统资源的使用情况，包括 CPU、内存、磁盘 I/O 等。高负载或资源瓶颈可能导致主线程响应变慢。
- 使用 Redis 专业工具： Redis 提供了一些工具来监测异步持久化的状态，例如
INFO PERSISTENCE命令。使用这些工具来查看异步持久化的进度和性能。 - 考虑优化持久化策略： 有时可以通过优化持久化策略来降低对主线程的影响。例如，减少 RDB 快照的频率或采用更高效的 AOF 编码模式。
5、再哈希，什么情况会发生，有什么用？
再哈希是指在哈希冲突发生时，通过另一种哈希函数重新计算哈希值的过程。哈希冲突是指多个不同的键映射到相同的哈希桶或槽位，这可能导致在散列表（哈希表）中的性能问题。
- 哈希冲突解决： 再哈希通常用于解决哈希表中的冲突。当两个或多个不同的键被映射到同一个桶时，再哈希可以通过使用另一个哈希函数对键进行重新哈希，然后将其放入新的桶中来解决冲突。
- 均匀分布： 通过再哈希，可以更好地分散键，以避免槽位的过度拥挤。这有助于减少冲突的频率，提高哈希表的性能。
- 性能优化： 通过再哈希，可以确保键的分布在哈希表中更加均匀，从而减少冲突的概率。这有助于保持常数时间的查询性能，避免性能下降。
- 哈希表扩容： 当哈希表需要扩容时，原始哈希函数可能不再适用。在这种情况下，可以使用再哈希来将原有的键重新映射到新的桶中，以适应更大的哈希表。
- 支持不同的哈希函数： 再哈希允许使用不同的哈希函数来处理特定的冲突，这可以根据键的特性来选择适当的哈希函数。
6、什么情况下导致用户态和内核态切换？
- 系统调用： 当用户程序需要执行需要特权的操作，例如文件读写、网络通信、进程创建等系统级操作时，它需要通过系统调用（syscall）请求内核执行这些操作。这时，用户态进程会触发一次用户态到内核态的切换，以便内核在特权模式下执行这些操作。完成后再切换回用户态。
- 中断： 中断是由外部硬件设备或时钟中断等引起的事件，它们需要被内核处理。当中断发生时，CPU需要立即切换到内核态来响应和处理中断请求。这是一种异步切换，例如硬件中断处理，和系统调用不同，它是由硬件事件触发的。
- 异常： 异常是一种错误或非法操作引起的事件，例如除零错误或内存访问冲突。这些异常需要由内核来处理，因此当它们发生时，CPU需要切换到内核态，以执行异常处理程序。
- 进程切换： 当操作系统需要切换当前运行的进程，或者在多任务系统中切换到另一个进程，会引发用户态到内核态的切换。这种切换包括保存当前进程的上下文，恢复下一个进程的上下文，并执行进程调度。
- 页面错误： 当程序访问的内存页不在物理内存中时，会发生页面错误。这时，内核需要将所需的页面从磁盘加载到内存，这会导致用户态到内核态的切换。
- 信号处理： 当进程接收到信号（例如Ctrl+C产生的中断信号）时，内核会中断当前进程的正常执行，切换到信号处理程序，然后再切换回用户态。
7、epoll原理，怎么实现的多路复用？
epoll 是一种 I/O 多路复用机制，主要用于在高并发网络服务器中有效管理大量的文件描述符（sockets）。epoll 基于事件驱动模型，能够监测多个文件描述符上的事件，以及在事件发生时通知应用程序。
epoll 的工作原理：
- 创建
epoll实例： 首先，应用程序需要创建一个epoll实例，通过epoll_create()系统调用来完成。 - 向
epoll中注册文件描述符： 应用程序将需要进行 I/O 监听的文件描述符注册到epoll实例中，通常使用epoll_ctl()系统调用来注册。 - 等待事件发生：
epoll提供了一个epoll_wait()系统调用，应用程序可以在这里等待事件的发生。epoll会监控注册的文件描述符，当文件描述符上发生读、写、异常等事件时，epoll会将这些事件通知应用程序。 - 事件通知： 当有文件描述符上的事件发生，
epoll_wait()会返回触发事件的文件描述符列表，应用程序可以通过这个列表来处理事件。
epoll 实现多路复用的优点：
- 高效的事件通知机制：
epoll只会通知那些发生了事件的文件描述符，而不是轮询所有的文件描述符。这减少了不必要的 CPU 负载。 - 支持大规模并发连接：
epoll可以有效地处理大量的并发连接，因为它不受限于打开文件描述符的数量，而是受系统资源限制。 - 快速的增删文件描述符： 应用程序可以随时增加或删除需要监控的文件描述符，而不会影响正在监听的文件描述符。
- 可跨平台性：
epoll在 Linux 系统上得到广泛支持，而其他系统可能使用不同的多路复用机制（如select或poll）。 - 支持水平触发和边缘触发：
epoll可以配置为水平触发（默认）或边缘触发。在边缘触发模式下，只在文件描述符上发生事件的瞬间才通知应用程序，而在水平触发模式下，只要文件描述符上仍有事件，就会持续通知。
8、epoll_wait组件数据结构？
struct epoll_event： 这是epoll事件的主要数据结构，用于存储事件信息。它包括以下主要字段：events：表示关注的事件类型，可以是EPOLLIN（可读事件）、EPOLLOUT（可写事件）、EPOLLERR（错误事件）等。data：用于存储与事件相关的数据。通常，这个字段会存储文件描述符，以便在事件发生时识别是哪个文件描述符发生了事件。
struct epoll_data： 这是epoll_event结构中的data字段的具体数据结构，它用于存储事件相关的数据。它可以是一个整数，一个指针，或者一个联合体，具体取决于应用程序的需要。
在使用 epoll 的过程中，应用程序通常会创建一个 epoll 实例，然后使用 epoll_ctl() 来注册需要监听的文件描述符，并指定关注的事件类型（如可读、可写、错误等）。当有事件发生时，epoll_wait() 函数会返回一个 struct epoll_event 数组，每个数组元素表示一个事件，应用程序可以遍历这个数组，根据 events 字段判断是哪种事件，然后通过 data 字段中存储的数据来识别是哪个文件描述符上发生了事件。
一个简单的例子：
C++
#include <sys/epoll.h>
int main() {
int epoll_fd = epoll_create(1); // 创建一个 epoll 实例
struct epoll_event event;
event.events = EPOLLIN; // 监听可读事件
event.data.fd = socket_fd; // 存储需要监听的文件描述符
epoll_ctl(epoll_fd, EPOLL_CTL_ADD, socket_fd, &event); // 注册监听
struct epoll_event events[10]; // 存储事件的数组
while (1) {
int num_events = epoll_wait(epoll_fd, events, 10, -1); // 等待事件发生
// 处理事件
for (int i = 0; i < num_events; i++) {
if (events[i].events & EPOLLIN) {
// 处理可读事件
int socket_fd = events[i].data.fd; // 获取文件描述符
// 处理读操作
}
}
}
close(epoll_fd); // 关闭 epoll 实例
return 0;
}9、epoll_wait是否阻塞？
epoll_wait 函数可以在不同的模式下进行阻塞和非阻塞的操作，具体取决于它的参数 timeout 的设置：
- 如果将
timeout参数设置为负数，如-1，epoll_wait会一直阻塞，直到有事件发生，或者发生错误，或者被信号中断。 - 如果将
timeout参数设置为0，epoll_wait会立即返回，如果没有任何事件发生，它将返回 0。这是一种纯粹的非阻塞方式，用于轮询是否有事件发生。 - 如果将
timeout参数设置为正整数，如1000，epoll_wait会等待指定的时间（以毫秒为单位），然后返回。如果在等待时间内有事件发生，它将返回发生事件的数量，如果超时仍然没有事件发生，它将返回 0。
10、epoll_wait为什么用红黑树不用hash？
epoll_wait 使用红黑树而不是哈希表的原因涉及到数据结构的特性和操作复杂度。红黑树和哈希表都有自己的优点和用途，但在 epoll_wait 的情境下，红黑树更适合。
原因：
- 顺序性：红黑树是有序数据结构，它可以帮助
epoll_wait返回已经准备好的文件描述符的有序列表。这对于某些应用程序非常重要，特别是需要按照事件发生的顺序进行处理的情况。 - 动态性：哈希表需要在初始化时选择合适的容量，而红黑树可以在运行时动态调整。
epoll_wait需要处理大量的文件描述符，这些文件描述符数量可能会动态变化，因此红黑树更适合用于管理这些描述符。 - 插入和删除操作的复杂度：红黑树的插入和删除操作的复杂度为 O(log n)，而哈希表的复杂度通常为 O(1)。尽管哈希表在单个操作上更快，但它在动态大小调整和范围查询方面可能不如红黑树高效。
- 冲突处理：哈希表在处理冲突时可能需要更多的工作，如链表或再哈希。红黑树不涉及这些问题。
- 稳定性：哈希表的遍历是无序的，这意味着
epoll_wait返回的文件描述符可能以无序方式出现。红黑树提供了有序性，能够以可控的顺序处理文件描述符。
11、根据红黑树方便范围查询，那epoll什么情况下用到范围查询？
epoll 主要用于 I/O 多路复用，通常情况下并不直接涉及范围查询。epoll 主要用于监控大量文件描述符，以确定哪些文件描述符已经就绪，可以进行读取或写入操作。
经典场景：
- 网络服务器：
epoll通常用于监控套接字文件描述符，以便异步地处理传入的网络连接和数据。 - 文件系统监控：
epoll也可以用于监控文件系统中文件或目录的变化。
在这些典型场景中，epoll 主要用于检测文件描述符的可用性，而不是进行范围查询。范围查询通常涉及到数据库或其他数据结构，而不是 epoll 的主要用途。
如果需要进行范围查询，通常会使用数据库管理系统或其他数据存储机制，这些系统具有专门的查询功能，可以根据范围查找数据。epoll 不是用于执行此类查询的工具，它的主要目的是高效处理文件描述符的 I/O 事件。
12、操作系统中，本机发送和远端发送有什么区别？
- 本机发送：
- 发送方和接收方位于同一台计算机上。
- 数据包或消息可以直接在操作系统内部进行传递，不需要离开计算机。
- 本机发送通常是在同一台计算机上的不同进程或线程之间进行通信。
- 远端发送：
- 发送方和接收方位于不同的计算机上，通常通过网络连接进行通信。
- 数据包或消息必须经过网络传输，以到达远程计算机。
- 远端发送通常是用于实现计算机之间的分布式通信，例如客户端与服务器之间的通信或不同计算机上的应用程序之间的通信。
区分本机发送和远端发送的主要目的是确定数据包或消息的传输路径和处理方式。对于本机发送，数据通常在操作系统内部传递，效率较高。而对于远端发送，数据需要通过网络传输，可能需要经过路由器和网络协议栈等组件，因此可能会引入一些延迟和网络通信的特殊处理。
13、mybatis连接池，用过什么数据源，了解他们之间性能的差距吗？
MyBatis是一个支持多种数据源的Java持久层框架，因此可以与不同种类的数据库连接池一起使用。
- HikariCP：HikariCP是一个高性能的轻量级数据库连接池，具有快速启动时间和低资源消耗。它通常被认为是性能最好的数据库连接池之一，因为它的实现专注于尽量减少锁定、线程争用和垃圾收集。与其他连接池相比，HikariCP在大多数情况下具有更好的性能。
- Apache Commons DBCP：Apache Commons DBCP是一个较早的数据库连接池，功能较为基本。在某些方面，性能不如HikariCP，特别是在高并发环境下。然而，对于小型应用程序或需要更广泛配置的场景，它仍然是一个合理的选择。
- C3P0：C3P0是另一个较早的数据库连接池，它提供了很多自定义配置选项。性能上与HikariCP相比差一些，但适用于某些特殊情况。
- Tomcat JDBC Pool：Tomcat JDBC Pool是Tomcat项目中的数据库连接池实现。它相对较新，性能不错。尤其适用于与Tomcat服务器一起使用的应用程序。
14、数据池性能从哪方面考虑，如何设计？
- 连接获取和释放的效率：连接池的主要目标是高效地获取和释放数据库连接。这包括在高负载情况下的连接获取、分配和回收速度。通常情况下，快速的连接获取和释放对性能至关重要。
- 连接池大小和连接生命周期：连接池的大小（最大连接数和最小连接数）需要根据应用程序的负载和数据库的吞吐能力来合理设置。不要设置太小，以防止资源不足，也不要设置太大，以防止资源浪费。此外，连接池应支持连接的自动重置或超时机制，以处理长时间闲置的连接。
- 连接状态检测：连接池需要能够检测连接的状态，以防止使用已经失效的连接。这可以通过定期发送心跳查询或使用数据库提供的健康检查功能来实现。
- 并发性能：连接池需要处理多个并发线程尝试获取和释放连接的情况。因此，在高并发负载下，连接池应该具备线程安全性，以避免竞态条件和死锁。
- 连接池参数调优：连接池通常允许设置多个参数，如连接超时、最大连接数、最小空闲连接数、连接生命周期等。这些参数需要根据应用程序的需求和数据库的性能来进行调优。
- 连接池类型：不同类型的连接池实现（如HikariCP、C3P0、Tomcat JDBC Pool等）在性能方面可能有所不同。进行性能测试和基准测试以确定哪个连接池最适合您的应用程序是重要的。
- 合适的数据库连接驱动程序：选择合适的数据库连接驱动程序对性能也有影响。某些驱动程序可能比其他驱动程序更高效。
- 资源管理：除了数据库连接外，还需要管理其他资源，如线程池、内存和CPU。确保整个应用程序堆栈的资源使用在合理范围内，以避免性能瓶颈。