腾讯C++三面

来源：https://www.nowcoder.com/feed/main/detail/dda07ecc2bb54ecb9704c6de6907bd47

1、怎么确保接收端合法？

确保接收端合法通常涉及对输入进行验证和过滤，以确保它符合预期的格式和要求。在网络通信中，特别是涉及用户输入或外部数据的情况下，确保接收端合法非常重要，以防止恶意输入或错误数据导致安全漏洞或系统故障。

一些确保接收端合法的方法：

输入验证：对输入数据进行验证，包括格式、长度、类型等方面。例如，如果接收到的是一个整数，可以验证它是否是有效的整数并且是否在预期的范围内。
过滤输入：对输入数据进行过滤，去除不必要的字符或格式，确保只有符合要求的数据被传递给后续处理步骤。例如，在接收到用户提交的表单数据时，可以过滤掉 HTML 标签和特殊字符，以防止 XSS 攻击。
安全性检查：对输入数据进行安全性检查，以防止恶意输入。例如，对于接收到的用户输入，可以检查是否包含恶意脚本或 SQL 注入攻击的内容。
错误处理：在接收端对输入数据进行错误处理，包括边界情况和异常情况的处理。例如，如果接收到的数据为空或格式不正确，需要能够进行适当的错误处理并返回合适的错误信息。
日志记录：记录接收到的数据和处理过程中的重要步骤，以便在出现问题时进行排查和分析。这有助于追踪数据来源和处理流程，发现潜在的问题。
数据加密：如果涉及敏感数据，应该对接收到的数据进行加密处理，以确保数据在传输和存储过程中的安全性。

2、秘钥安全性？

秘钥安全性是指在加密通信或数据存储中，用于加密和解密的秘钥（密钥）的保密和安全性。

为什么秘钥安全性很重要？

保密性：秘钥用于加密和解密数据，如果秘钥泄露，攻击者可以轻易地解密通信内容或存储的数据，导致信息泄露。
完整性：秘钥的完整性需要得到保护，以防止被篡改或损坏，从而导致加密数据无法正确解密或者被篡改。
身份验证：在某些情况下，秘钥也用于身份验证，比如数字签名。如果秘钥被篡改或泄露，可能会导致身份伪造或者认证失败。

如何确保秘钥安全？

生成安全的秘钥：使用安全的随机数生成算法生成秘钥，确保秘钥具有足够的随机性和复杂性，使其难以被猜测或穷举破解。
秘钥传输安全：在秘钥的传输过程中使用安全的通信渠道，比如使用 SSL/TLS 加密的网络连接，或者使用安全的文件传输协议。避免在不安全的网络环境中传输明文秘钥。
秘钥存储安全：在存储秘钥时，应该采取措施保护秘钥不被未经授权的访问或泄露。可以使用加密算法对秘钥进行加密存储，或者将秘钥存储在安全的硬件设备中，如安全模块（HSM）。
访问控制：对秘钥的访问应该进行严格的控制和权限管理，确保只有授权的人员才能访问秘钥。
周期性更换：定期更换秘钥可以降低秘钥被猜测或者泄露的风险。同时，及时撤销或废弃不再使用的秘钥也是保证秘钥安全性的重要措施。
监控和审计：对秘钥的使用情况进行监控和审计，及时发现异常活动或者潜在的威胁，并采取相应的应对措施。

3、异步有什么好处？

它的核心思想是将任务分解成更小的部分，并在任务完成之前不阻塞主线程，从而提高程序的并发性和性能。

好处：

提高程序的并发性：异步编程允许程序同时执行多个任务，而不需要等待某个任务完成后才能开始下一个任务，从而提高了程序的并发性。
提高程序的响应性：异步编程可以使程序在执行耗时任务时不会阻塞主线程，这样可以保持程序的响应性，用户在执行耗时操作时仍然可以进行其他操作，提高了用户体验。
提高系统的吞吐量：异步编程可以使系统更有效地利用资源，从而提高系统的吞吐量。通过并发执行多个任务，系统可以更快地处理大量请求。
节省资源：异步编程可以减少线程或进程的创建和销毁，节省了系统资源。相比于同步编程中为每个任务创建一个线程或进程，异步编程可以通过少量的线程或进程来处理大量的任务。
适应IO密集型任务：异步编程特别适用于IO密集型任务，如网络请求、文件读写等。在这些任务中，大部分时间都花费在等待IO操作完成上，异步编程可以在等待IO操作的同时执行其他任务，提高了系统的效率。
支持高并发：异步编程可以更好地支持高并发的场景，例如服务器端的网络通信和请求处理，能够更有效地处理大量并发请求。

4、看过windows底层源码吗，异步怎么实现的？

Windows 下的异步编程通常使用 I/O Completion Port（I/OCP）来实现。

实现的流程：

创建 I/OCP 对象：首先需要创建一个 I/OCP 对象，这可以通过调用 CreateIoCompletionPort 函数来完成。I/OCP 对象是一个与系统内核通信的对象，用于接收异步 I/O 完成的通知。
将文件句柄关联到 I/OCP 对象：对于需要进行异步 I/O 的文件句柄，需要将其关联到之前创建的 I/OCP 对象上，这可以通过调用 CreateIoCompletionPort 函数来实现。
发起异步 I/O 操作：要发起异步 I/O 操作，可以使用诸如 ReadFileEx、WriteFileEx 等带有 Overlapped 结构的函数，它们允许传入一个 Overlapped 结构作为参数，用于指定异步 I/O 操作的回调函数等信息。
等待异步 I/O 完成事件：一旦异步 I/O 操作被发起，程序可以调用 GetQueuedCompletionStatus 函数等待 I/O 操作完成的通知。当 I/O 操作完成时，系统会将完成结果放入 I/OCP 对象的队列中，然后 GetQueuedCompletionStatus 函数会返回完成结果，并可以获取到完成的相关信息。
处理异步 I/O 完成事件：在获取到异步 I/O 操作完成的通知后，程序可以根据完成的结果进行相应的处理，比如读取完成的数据，继续发起下一个异步 I/O 操作等。

5、讲一下EPOLL？

epoll 是 Linux 中用于高效处理大量文件描述符的机制，主要用于实现高性能的 I/O 多路复用。它是在 Linux 2.5.44 内核中引入的，取代了之前的 select 和 poll 等机制，在处理大量并发连接时性能更好。

基本概念： epoll 是一个事件通知机制，它允许程序监视多个文件描述符上的 I/O 事件，并在这些文件描述符就绪时得到通知。通过 epoll，程序可以同时监视大量的文件描述符，而不需要像 select 和 poll 那样限制监视的文件描述符数量。
工作模式：
- 水平触发模式（Level-Triggered，简称LT）：
  - 在水平触发模式下，当文件描述符就绪时，epoll_wait会立即返回，并且每次调用epoll_wait时都会通知一次已就绪的文件描述符。即使文件描述符仍然处于就绪状态，下次调用epoll_wait时仍然会通知。
  - 对于非阻塞IO，水平触发模式下需要循环读取直到返回EAGAIN。
  - 优点是实现相对简单，不易丢失事件。
- 边缘触发模式（Edge-Triggered，简称ET）：
  - 在边缘触发模式下，epoll_wait只会在文件描述符状态发生变化时才会通知，即从未就绪变为就绪时通知一次。如果文件描述符一直处于就绪状态，下次调用epoll_wait时不会再次通知。
  - 对于非阻塞IO，边缘触发模式下只需要读取一次，直到返回EAGAIN或EWOULDBLOCK为止。
  - 优点是能够最大程度地减少事件通知次数，提高效率，但也需要更加精细地处理事件，防止事件丢失。
使用方式：使用 epoll 需要经过以下步骤：
- 创建 epoll 实例：使用 epoll_create 函数创建一个 epoll 实例。
- 添加文件描述符：使用 epoll_ctl 函数将要监视的文件描述符添加到 epoll 实例中。
- 等待事件发生：使用 epoll_wait 函数等待文件描述符上的事件就绪，并获取就绪的文件描述符列表。
优势：相比于 select 和 poll，epoll 具有更高的性能和扩展性。它使用红黑树来存储文件描述符，可以快速地检索就绪的文件描述符，并且能够处理大量的并发连接。

6、红黑树讲一下？

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个额外的属性来存储节点的颜色，可以是红色或黑色。

红黑树满足以下几个性质：

每个节点要么是红色，要么是黑色。
根节点是黑色的。
每个叶子节点（NIL节点，空节点）是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的（不能有两个连续的红色节点）。
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些性质确保了红黑树的平衡性和搜索效率。

红黑树的插入和删除操作都会影响树的结构，但通过一系列的旋转和颜色调整，可以保持红黑树的性质不变。在插入操作中，插入新节点后可能会破坏红黑树的性质，此时需要进行旋转和颜色调整来修复。在删除操作中，删除节点后也可能破坏性质，同样需要进行调整。

红黑树的平衡性保证了其在最坏情况下的时间复杂度为O(log n)，使得它在实际应用中被广泛使用，例如在C++ STL中的std::map和std::set等容器中就是使用红黑树来实现的。

7、为什么高效？

平衡性：红黑树是一种自平衡的二叉搜索树，保持了树的平衡性。在插入和删除节点时，通过旋转和颜色调整等操作，能够保持树的高度平衡，使得整棵树的高度不会过高，从而保证了查找、插入和删除操作的时间复杂度为 O(log n)。
二叉搜索树性质：红黑树本质上还是一棵二叉搜索树，具有二叉搜索树的特性。在红黑树中，左子节点的值小于父节点的值，右子节点的值大于父节点的值，这种有序性质使得在红黑树中进行查找操作更加高效。
良好的平均性能：虽然红黑树在最坏情况下的时间复杂度也是 O(log n)，但它的平均性能较好。在大多数情况下，红黑树的插入、删除和查找操作都能在较短的时间内完成。
应用广泛：由于红黑树具有上述优秀的性能特性，它被广泛应用在各种需要高效搜索、插入和删除的场景中。例如，C++ STL中的std::map和std::set等容器就是使用红黑树来实现的，这些容器在实际应用中能够提供高效的数据操作。

8、左旋右旋的代价？

左旋和右旋是红黑树中用于保持树的平衡性的操作，它们的代价主要体现在修改指针和颜色上。

左旋操作：
- 左旋操作是将当前节点的右子节点提升为新的父节点，原父节点成为新父节点的左子节点，原右子节点的左子节点成为原父节点的右子节点。
- 左旋操作需要修改多个节点的指针，包括当前节点的父节点、右子节点的左子节点、当前节点的右子节点等。
- 左旋操作的时间复杂度为 O(1)，因为它只涉及固定数量的节点指针修改。
右旋操作：
- 右旋操作是左旋操作的对称操作，将当前节点的左子节点提升为新的父节点，原父节点成为新父节点的右子节点，原左子节点的右子节点成为原父节点的左子节点。
- 右旋操作同样需要修改多个节点的指针，包括当前节点的父节点、左子节点的右子节点、当前节点的左子节点等。
- 右旋操作的时间复杂度也为 O(1)，因为它同样只涉及固定数量的节点指针修改。

总的来说，左旋和右旋操作的代价主要在于修改节点的指针，由于它们只涉及固定数量的节点指针修改，并且操作过程中不需要遍历整棵树，因此时间复杂度为 O(1)，代价相对较小。在红黑树中，通过左旋和右旋操作可以在保持树的平衡性的同时，保持了较高的插入、删除和查找效率。

9、内核和用户态？

内核态：
- 内核态是操作系统运行的特权级别，具有最高的权限和访问权力。在内核态下，操作系统可以执行任何指令并访问所有的系统资源，如内存、硬件设备等。
- 内核态通常用于执行操作系统内核代码，处理系统中断、异常和系统调用等关键操作，以及对系统资源进行管理和控制。
- 进入内核态的方式通常是通过系统调用、中断或异常等机制，用户程序需要请求操作系统提供特权操作或访问受保护资源时会进入内核态。
用户态：
- 用户态是用户程序运行的一种非特权级别，具有较低的权限和访问权力。在用户态下，用户程序只能执行受限的指令集，并且对系统资源的访问受到限制。
- 用户态通常用于执行用户编写的应用程序，这些程序不能直接访问系统资源，而是通过系统调用等方式请求操作系统提供服务。
- 在用户态下，用户程序可以执行一般的计算、IO 操作等任务，但无法直接对系统进行管理或访问受保护资源。

切换：

从用户态切换到内核态通常需要一定的开销，因为需要保存用户程序的状态并切换到内核模式执行。
从内核态返回到用户态也需要一定的开销，因为需要恢复用户程序的状态并切换回用户模式执行。

10、高效进程通信？

管道（Pipe）：管道是一种单向通信机制，常用于父子进程之间或者具有亲缘关系的进程之间的通信。管道通过操作系统提供的内核缓冲区进行数据传输，性能较高，但只能用于具有亲缘关系的进程之间。
命名管道（Named Pipe）：命名管道是一种具有名称的管道，允许不具有亲缘关系的进程之间进行通信。它通过文件系统提供的特殊文件实现通信，可以在文件系统中创建，提供了一种高效的进程间通信方式。
信号量（Semaphore）：信号量是一种用于进程间同步和互斥的机制，可以用于控制多个进程对共享资源的访问。信号量通常用于实现进程之间的互斥访问和同步操作，保证多个进程之间的数据一致性和安全性。
消息队列（Message Queue）：消息队列是一种可以实现进程间通信的机制，允许进程通过消息传递进行通信。消息队列可以实现进程之间的异步通信，适用于需要高效传递大量数据的场景。
共享内存（Shared Memory）：共享内存是一种进程间通信的方式，允许多个进程共享同一块内存区域，可以实现高效的数据共享和传输。共享内存通常用于需要频繁读写大量数据的场景，能够提供较高的性能和效率。
套接字（Socket）：套接字是一种网络通信的接口，也可以用于进程间通信。套接字通常用于网络编程，但也可以在本地进程间进行通信，提供了一种灵活而高效的进程通信方式。

11、如何减少加锁、使用信号量？

粒度控制：合理控制加锁的粒度，避免过多地对共享资源进行加锁。如果可能，可以将共享资源分成多个部分，每个部分使用不同的锁或信号量进行控制，以提高并发性能。
使用读写锁：读写锁是一种特殊的锁机制，允许多个线程同时读取共享资源，但只允许一个线程写入共享资源。这种锁适用于读操作频繁、写操作较少的场景，可以提高并发性能。
使用无锁数据结构：一些特定的数据结构，如无锁队列、无锁栈等，可以在不使用锁的情况下实现并发访问。这些数据结构通常基于原子操作或者比较交换指令实现，并发性能较高。
使用信号量：信号量是一种广泛用于进程间同步和互斥的机制，也可以用于线程间的同步和互斥。通过合理使用信号量，可以控制多个线程对共享资源的访问，避免竞态条件和死锁等问题。
避免长时间持有锁：尽量避免长时间持有锁，可以通过将锁的粒度调整得更小，或者采用非阻塞的锁机制，减少锁的持有时间，提高并发性能。
使用乐观并发控制：乐观并发控制是一种基于版本号或者时间戳的并发控制机制，允许多个线程同时访问共享资源，只在写入时进行互斥控制。这种机制适用于读操作远远多于写操作的场景，可以提高并发性能。

12、环形队列问题？环形队列是一种特殊的队列数据结构，它通过循环利用固定大小的数组来实现队列的功能。环形队列通常由一个固定大小的数组和两个指针（front 和 rear）组成，其中 front 指向队列的第一个元素，rear 指向队列最后一个元素的下一个位置。

环形队列的特点包括：

循环利用空间：当队列满时，rear 指针可以继续向后移动，从而利用数组中未使用的空间，实现循环利用。
固定大小：由于环形队列使用固定大小的数组实现，因此其大小在创建时就被确定，并且在运行过程中不会改变。
判空和判满：由于队列是循环的，因此判断队列为空和队列满的条件需要特别处理。一般来说，可以通过 front 和 rear 指针的位置关系来判断队列的状态。
入队和出队操作：入队操作将元素插入到 rear 指针所指向的位置，并将 rear 指针向后移动；出队操作将元素从 front 指针所指向的位置移除，并将 front 指针向后移动。
遍历操作：由于环形队列是循环的，因此在遍历队列时需要特别处理 rear 指针超过数组末尾的情况。
性能优化：环形队列通常在空间和时间上都有较好的性能表现，因为它可以循环利用数组空间，而且在入队和出队操作中不需要频繁地移动元素。

13、项目？

三面项目问的比较多，这里就不介绍了。

14、算法：两个字符串求最长公共子串？

问题描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

c++

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

c++

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

c++

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

思路

定义状态：定义一个二维数组 dp，其中 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。
初始化状态：初始化动态规划表 dp 的第一行和第一列，使其值均为0。这是因为当其中一个字符串为空时，它们的最长公共子序列长度为0。
状态转移方程：对于 dp[i][j]，如果 text1[i - 1] 和 text2[j - 1] 相等，则 dp[i][j] 应该等于 dp[i - 1][j - 1] + 1，表示当前字符是两个字符串的公共字符，最长公共子序列的长度应该在前一个位置的基础上加1；如果不相等，则 dp[i][j] 应该等于 max(dp[i - 1][j], dp[i][j - 1])，表示当前字符不是两个字符串的公共字符，最长公共子序列的长度应该取左边或上边的较大值。
返回结果：最终返回 dp[m][n]，即为 text1 和 text2 的最长公共子序列的长度。

参考代码

c++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
    int longestCommonSubsequence(std::string text1, std::string text2) {
        int m = text1.size(); // 第一个字符串的长度
        int n = text2.size(); // 第二个字符串的长度
        std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0)); // 创建动态规划表，初始化为0

        // 动态规划求解最长公共子序列的长度
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1; // 如果当前字符相同，则在前一个位置的基础上加1
                } else {
                    dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]); // 如果当前字符不同，则取左边和上边的最大值
                }
            }
        }

        return dp[m][n]; // 返回最长公共子序列的长度
    }
};

int main() {
    Solution solution;
    std::string text1 = "abcde";
    std::string text2 = "ace";
    int result = solution.longestCommonSubsequence(text1, text2);
    std::cout << "最长公共子序列的长度为：" << result << std::endl;
    return 0;
}

微服务

文档

基础

腾讯C++三面 ​

1、怎么确保接收端合法？ ​

2、秘钥安全性？ ​

3、异步有什么好处？ ​

4、看过windows底层源码吗，异步怎么实现的？ ​

5、讲一下EPOLL？ ​

6、红黑树讲一下？ ​

7、为什么高效？ ​

8、左旋右旋的代价？ ​

9、内核和用户态？ ​

10、高效进程通信？ ​

11、如何减少加锁、使用信号量？ ​

13、项目？ ​

14、 算法：两个字符串求最长公共子串？ ​

问题描述 ​

思路 ​

参考代码 ​