快手一面

1、C++和C的区别？

编程范式：
- C++： C++是一种多范式编程语言，支持面向过程、面向对象和泛型编程。这意味着你可以使用C++编写传统的过程式代码，也可以使用类和对象创建面向对象的程序，还可以使用模板进行泛型编程。
- C： C是一种面向过程的编程语言，它更注重以过程和函数为基础的编程方法。
面向对象编程（OOP）：
- C++： C++支持面向对象编程（OOP），提供了类、继承、多态等概念，允许你以对象为基础组织代码，实现封装、继承和多态等OOP特性。
- C： C不直接支持面向对象编程。虽然可以模拟一些OOP概念，但没有直接的语言支持。
标准模板库（STL）：
- C++： C++具有强大的标准模板库（STL），其中包含了各种容器（如向量、链表、映射等）、算法和函数模板，可用于高效地处理数据结构和算法问题。
- C： C没有类似STL的标准库，开发者需要自行实现各种数据结构和算法。
异常处理：
- C++： C++具有异常处理机制，允许程序员编写可以捕获和处理异常的代码，以增加程序的健壮性。
- C： C不直接支持异常处理。在C中，错误通常通过函数的返回值或全局变量来处理。
运算符重载：
- C++： C++允许运算符重载，这意味着你可以为类定义自定义的运算符行为。
- C： C不支持运算符重载。
类型检查：
- C++： C++在编译时进行更严格的类型检查，有助于捕获潜在的类型错误。
- C： C的类型检查相对较弱，更容易出现类型错误。
内存管理：
- C++： C++有更复杂的内存管理，包括构造函数、析构函数以及new和delete运算符，用于动态内存分配和释放。
- C： C的内存管理相对简单，主要使用malloc和free函数。
标准库：
- C++： C++标准库在C标准库的基础上进行了扩展，包含了更多的容器、算法和其他功能。
- C： C标准库相对较小，包括一些基本的输入输出和字符串处理函数。
编程风格：
- C++： C++通常用于大型、复杂的软件项目，特别适合需要面向对象设计的应用程序。
- C： C更适用于系统编程、嵌入式编程和一些需要更底层控制的任务。

2、纯虚函数和虚函数？

虚函数（Virtual Function）：

虚函数是什么？

虚函数是在基类（父类）中声明为virtual的函数，它可以在派生类（子类）中被重写。通过使用虚函数，你可以实现运行时多态性，这意味着在程序运行时，根据对象的实际类型来调用适当的函数版本。

虚函数的声明和使用：

class Base {
public:
    virtual void foo() {
        // 基类中的虚函数实现
    }
};

class Derived : public Base {
public:
    void foo() override {
        // 派生类中的虚函数重写
    }
};

foo 是一个虚函数，它可以在派生类 Derived 中重写。

虚函数的特点：

虚函数可以有默认实现，但它们也可以在派生类中被覆盖（重写）。
如果一个类包含虚函数，它会有一个虚函数表（vtable），用于在运行时查找正确的函数版本。
调用虚函数时，实际调用的是对象的实际类型的函数版本。

纯虚函数（Pure Virtual Function）：

纯虚函数是什么？

纯虚函数是在基类中声明为纯虚拟的函数，它没有实际的实现。纯虚函数的目的是强制派生类提供其自己的实现。一个类如果包含纯虚函数，它就成为抽象类，不能被实例化。

纯虚函数的声明和使用：

class AbstractBase {
public:
    virtual void pureVirtualFunction() = 0; // 纯虚函数声明
};

pureVirtualFunction 是一个纯虚函数，没有实际的实现。这个类不能被实例化，只能用作基类。

纯虚函数的特点：

纯虚函数没有实际的函数体，它们只有声明。
任何派生类都必须提供纯虚函数的实现，否则它们也将变为抽象类，不能被实例化。
纯虚函数为实现多态性提供了强制性的规则，确保派生类提供适当的实现。

总结：

虚函数和纯虚函数都允许你在派生类中重写基类的函数，以实现多态性。虚函数有默认实现，而纯虚函数没有实际的实现，必须在派生类中提供。使用虚函数可以创建可实例化的类，而包含纯虚函数的类将变为抽象类，不能被实例化，只能用作基类。纯虚函数为面向对象编程中的抽象基类提供了一种机制。

3、共享指针和弱指针（shared_ptr与weak_ptr）？

shared_ptr（共享指针）：

共享拥有权： shared_ptr 允许多个智能指针共享同一个对象的所有权。每当你将一个shared_ptr指向一个对象时，它会增加该对象的引用计数。
引用计数：引用计数表示有多少个shared_ptr指向相同的对象。当引用计数降为零时，对象的内存将被自动释放，这有助于避免内存泄漏。
循环引用：尽管shared_ptr可以解决内存泄漏问题，但如果存在循环引用（两个或多个对象相互引用），可能会导致内存泄漏。为了解决这个问题，可以使用weak_ptr。

weak_ptr（弱指针）：

观察者角色： weak_ptr用于解决shared_ptr可能导致的循环引用问题。它允许你观察一个对象，但不会增加对象的引用计数。
无法直接访问对象： weak_ptr不能直接访问共享对象的成员或方法。要访问对象，需要将weak_ptr转换为shared_ptr。
提供.lock()方法：通过调用lock()方法，可以将weak_ptr转换为shared_ptr，如果共享对象仍然存在，就可以安全地使用它。

可参考如下代码使用以上两个指针：

#include <iostream>
#include <memory>

class MyClass {
public:
    MyClass(int value) : data(value) {
        std::cout << "MyClass constructor called" << std::endl;
    }

    ~MyClass() {
        std::cout << "MyClass destructor called" << std::endl;
    }

    void printData() {
        std::cout << "Data: " << data << std::endl;
    }

private:
    int data;
};

int main() {
    std::shared_ptr<MyClass> sharedPtr = std::make_shared<MyClass>(42);
    std::weak_ptr<MyClass> weakPtr = sharedPtr;

    // 使用 weak_ptr 转换为 shared_ptr 来访问对象
    if (auto lockedPtr = weakPtr.lock()) {
        lockedPtr->printData();
    } else {
        std::cout << "Object no longer exists" << std::endl;
    }

    // sharedPtr 在离开作用域时会自动销毁对象
    return 0;
}

shared_ptr和weak_ptr共享同一个对象。shared_ptr负责管理对象的生命周期，而weak_ptr用于安全地观察对象。当shared_ptr离开作用域时，对象会被销毁，但weak_ptr仍然可以检查对象是否存在。这有助于防止循环引用和内存泄漏。

4、什么叫同步io和异步io？

同步 I/O：

阻塞式：在同步 I/O 中，当程序发出一个 I/O 操作（比如读取文件或发送网络请求）时，程序会被阻塞，直到这个 I/O 操作完成。阻塞意味着程序会停止执行，等待 I/O 操作完成，然后继续执行。
顺序执行：在同步 I/O 中，I/O 操作通常是按照它们的顺序执行的。一个操作完成后，程序才能继续执行下一个操作。
简单易懂：同步 I/O 通常比较容易理解和编写，因为程序的流程是线性的，按顺序执行。
资源利用率低：由于程序在等待 I/O 完成时被阻塞，这可能导致系统的资源利用率较低，因为 CPU 时间被浪费在等待上。

异步 I/O：

非阻塞式：在异步 I/O 中，程序发出一个 I/O 操作后不会被阻塞，而是可以继续执行其他任务。程序会注册一个回调函数，当 I/O 操作完成后，系统会调用这个回调函数来处理结果。
并发执行：异步 I/O 允许多个 I/O 操作同时进行，无需等待前一个操作完成。这可以提高程序的并发性和性能。
复杂性：异步编程通常比同步编程更复杂，因为程序必须处理异步回调、状态管理和竞态条件等问题。
资源利用率高：由于程序可以继续执行其他任务而不必等待 I/O，异步 I/O 可以提高系统资源的利用率。

适用场景：

同步 I/O：
- 适用于简单的、顺序执行的程序，不需要高度的并发性。
- 适用于需要简单、易懂的代码的情况，例如小型命令行工具或脚本。
异步 I/O：
- 适用于需要高度并发性和响应性的应用程序，如网络服务器、图形界面应用程序等。
- 适用于需要处理大量并发连接或请求的情况，以便能够同时处理多个任务。
- 适用于需要提高系统资源利用率的情况，以充分利用多核处理器。

5、什么是回调异步？

回调异步是一种处理异步操作的编程模型，它基于回调函数的概念，用于处理异步任务的完成通知和结果处理。在回调异步模型中，当一个异步操作完成时，会调用事先注册的回调函数来处理操作的结果或执行特定的操作。

异步操作的触发：在回调异步模型中，异步操作通常是由非阻塞的 I/O 操作、计时器、事件通知等触发的。程序执行异步操作时，不会等待操作完成，而是立即继续执行其他任务。
回调函数的注册：在执行异步操作之前，程序会注册一个回调函数（也称为回调或回调处理程序）。这个回调函数是一个指向特定函数或方法的指针或引用，表示在异步操作完成时应该调用的代码。
异步操作的执行：异步操作在后台执行，不会阻塞程序的主线程。当操作完成时，系统会自动调用注册的回调函数，并将操作的结果作为参数传递给回调函数。
结果处理：在回调函数中，程序员可以访问操作的结果并执行适当的操作，例如处理返回的数据、更新用户界面、触发其他事件等。回调函数充当了异步操作的完成通知和结果处理的角色。
处理错误：回调函数还可以处理异步操作可能引发的错误或异常情况。程序员可以在回调函数中检查错误状态并采取适当的措施。

示例伪代码：

void onAsyncOperationComplete(ResultType result) {
    // 处理异步操作的结果
    if (result.success) {
        // 执行成功的逻辑
    } else {
        // 处理错误情况
    }
}

// 注册回调函数并执行异步操作
asyncOperationAsync(onAsyncOperationComplete);

回调异步模型适用于处理需要非阻塞和高并发性质的应用程序，例如网络通信、图形界面应用程序和事件驱动的系统。它允许程序在执行异步操作时继续执行其他任务，提高了程序的响应性和资源利用率。然而，使用回调函数来处理异步操作也可能导致回调地狱（callback hell）的问题，代码可读性下降，因此一些现代编程语言和框架提供了更高级的异步编程模型，如Promise和async/await。

6、设计题：100w个用户访问服务器，要求：读写互斥、不能用锁和信号量、不能等待。

阿Q给出一点思路：使用无锁队列和原子操作来实现读写互斥。

无锁队列可以允许多个线程同时进行读取和写入操作，而不需要显式的锁定或等待。原子操作用于确保对队列的操作是原子的，从而避免竞争条件。

具体步骤：

设计一个请求队列：创建一个请求队列，用于存储用户请求。这个队列可以是一个无锁队列，例如使用C++的std::queue，并通过原子操作确保队列操作的原子性。
读操作：
- 用户发起读请求时，将读请求放入请求队列中。
- 服务器通过原子操作从队列中取出请求并处理读操作。
- 原子操作保证了多个用户可以同时将读请求放入队列，并且服务器只会处理一个请求。
写操作：
- 用户发起写请求时，将写请求放入请求队列中。
- 服务器通过原子操作从队列中取出请求并处理写操作。
- 原子操作保证了多个用户可以同时将写请求放入队列，并且服务器只会处理一个请求。

这个设计的话基于无锁队列，允许多个用户同时发起读写请求而不需要锁定或等待。队列的原子操作确保了读写请求的互斥性，服务器能够按顺序处理请求。

要注意的是，无锁编程需要仔细处理竞争条件和原子操作的正确性。此外，性能和吞吐量也可能是一个挑战，因此需要根据实际需求进行优化。这个设计的关键在于使用无锁队列来管理请求，以确保互斥性和高并发性。

7、tcp怎么保证可靠性？

确认和序号： TCP使用序号（Sequence Number）来对数据进行编号，每个数据段都有一个唯一的序号。接收端使用这些序号来确认已经接收到的数据。如果发送方未收到确认，它会重传数据。
确认机制：接收端会向发送端发送确认（ACK）消息，以通知发送端已成功接收数据。如果发送端未收到确认，它会认为数据可能丢失，因此会重传。
超时和重传： TCP引入了超时机制。如果发送端在一定时间内未收到确认，它会认为数据丢失，然后重新发送数据。这确保了即使数据包在传输过程中丢失，也可以重新发送。
流量控制： TCP使用窗口控制机制来管理数据的流量。接收端可以通知发送端其可接受的数据窗口大小，以确保发送端不会发送过多的数据。这有助于防止数据拥塞和丢失。
拥塞控制： TCP引入了拥塞控制机制，用于监测网络拥塞并调整发送速率，以避免过多的数据堆积在网络中。这有助于防止丢失和延迟。
顺序保证： TCP确保数据在接收端按照正确的顺序交付。如果数据包到达顺序不正确，接收端会将其重新排序。
重复消除： TCP通过使用序号和确认机制来防止数据的重复传输。
滑动窗口： TCP使用滑动窗口来管理数据的流动。发送方和接收方都有一个窗口大小，用于控制数据的发送和接收速率。

8、tcp怎么判断丢包了？

TCP（Transmission Control Protocol）使用序号（Sequence Number）和确认（ACK）机制来判断是否发生了数据包丢失。

判断丢包的过程：

数据包发送：当发送端通过TCP发送数据时，每个数据包都会被分配一个唯一的序号。这个序号用于标识数据包在传输中的顺序。
数据包接收：在接收端，TCP接收到数据包后，会将数据包的序号与期望的下一个序号进行比较。
判断丢包：如果接收端收到的数据包的序号与期望的下一个序号不匹配，TCP会认为发生了丢包。这是因为数据包的到达顺序不正确，可能是之前的数据包丢失了或乱序到达。
发送ACK：如果接收端检测到丢包，它会发送一个ACK消息，其中包含期望的下一个序号。这告知发送端它需要重新发送丢失的数据包。
发送端重传：一旦发送端收到接收端的ACK消息，它会重新发送丢失的数据包。这确保了数据包能够按正确的顺序到达接收端。

9、超时时间怎么计算的？

RTT的测量： RTT是指数据包从发送端到接收端的往返时间，通常以毫秒为单位。TCP使用RTT来估计数据包的传输时间和网络延迟。RTT的测量通常包括以下步骤：
- 发送端发送数据包并记录发送时间戳。
- 接收端接收到数据包后，记录接收时间戳。
- 发送端收到接收端的确认时，计算RTT：RTT = 接收时间戳 - 发送时间戳。
平均RTT的计算： TCP维护一个RTT样本的历史记录，通常使用指数加权移动平均（Exponential Weighted Moving Average，EWMA）来计算平均RTT。这样做的目的是平滑RTT的波动，使其更稳定。
平均RTT = α * 当前RTT + (1 - α) * 上一次平均RTT
这里，α是一个介于0和1之间的权重系数，通常较小，以使平均值对较新的RTT更敏感。
RTT偏差的计算：除了平均RTT，TCP还维护一个RTT偏差，用于考虑RTT的变化。RTT偏差通常也使用指数加权移动平均来计算，以平滑偏差的波动。
偏差 = α * |当前RTT - 平均RTT| + (1 - α) * 上一次偏差
超时时间的计算：一旦有了平均RTT和偏差的估计，发送端可以计算超时时间。超时时间的计算通常使用以下公式：
超时时间 = 平均RTT + 4 * 偏差
这个公式中的4是一个经验性的倍数，用于提供一定的安全裕量，以应对RTT的变化和网络拥塞等情况。因此，超时时间会比估计的RTT和偏差更长，以确保数据包在合理的时间内得到重传。
超时时间的动态调整：超时时间不是固定的，而是根据网络环境的变化进行动态调整。如果数据包成功传输并且RTT保持稳定，超时时间会逐渐增长，以提高效率。如果发生数据包丢失或RTT波动较大，超时时间会相应地缩短，以更快地检测和处理丢失。

10、拥塞控制？

TCP拥塞控制的原理可以分为四个主要部分：慢启动、拥塞避免、拥塞检测、和快速恢复。

慢启动（Slow Start）：
- 初始阶段：当TCP连接建立时，发送方的拥塞窗口（Congestion Window，cwnd）被初始化为一个较小的值（通常为1或一些其他小值）。此时，发送方只能发送一个数据段来测试网络的拥塞状况。
- 指数增长：每当发送方成功发送并接收到一个数据段的确认（ACK），它将增加拥塞窗口的大小，将其翻倍。这导致了指数级增长，数据发送速率迅速增加。
- 慢开始门限：当拥塞窗口大小达到某个阈值（慢开始门限，ssthresh）时，发送方将进入拥塞避免阶段。
拥塞避免（Congestion Avoidance）：
- 阈值和线性增长：在拥塞避免阶段，发送方将拥塞窗口的增长改为线性增长，即每收到一个确认时，拥塞窗口增加一个固定大小的值。这减缓了数据发送速率的增长，以更稳定的方式来探测网络的容量。
- 拥塞发生：如果网络出现拥塞，即网络中的路由器或链路无法容纳当前的数据流量，就可能出现数据包丢失。当发送方检测到数据包丢失时，它会认为网络存在拥塞，并将慢开始门限（ssthresh）设置为当前拥塞窗口大小的一半，然后进入快速重传和快速恢复阶段。
快速重传和快速恢复：
- 发送方迅速重传：如果发送方在拥塞避免阶段收到三个相同的重复确认（对同一个数据包的确认），则发送方认为这是一个网络中的数据包丢失，立即重传该数据包，而不等待超时。这减少了恢复时间。
- 快速恢复：发送方将慢开始门限设置为当前拥塞窗口大小的一半，将拥塞窗口大小设置为慢开始门限加3。这样，发送方可以迅速恢复到之前的拥塞窗口大小，并继续线性增加拥塞窗口。
拥塞检测（Congestion Detection）：
- 丢包检测：发送方通过观察重复确认或超时来检测数据包的丢失，从而推断网络中的拥塞情况。
- 超时处理：如果发送方在合理的时间内没有收到对某个数据包的确认，它会认为这个数据包已经丢失，并减小拥塞窗口大小，然后重新开始慢启动。

11、窗口阈值怎么确定的？

用于控制拥塞窗口的大小以及拥塞避免算法的行为。

窗口阈值的确定通常遵循以下原则：

初始值：在TCP连接建立时，拥塞窗口的初始值通常设置为一个较小的值，例如1或一些其他小值。这是为了防止在连接刚开始时发送大量数据，以便在网络拥塞的情况下快速检测并响应。
阈值减小：当网络出现拥塞时，拥塞窗口的阈值（Threshold）会被设置为当前拥塞窗口大小的一半。这是一个通用的规则，旨在迅速减小数据流量，以便缓解拥塞。
阈值增加：在拥塞避免阶段，拥塞窗口的阈值会根据具体算法逐渐增加。通常情况下，阈值会在每个往返时间（RTT）内按某种方式增加。这可以是一个固定值，也可以是某种动态计算的值。
阈值的影响：阈值的设置对TCP拥塞控制的行为具有重要影响。较小的阈值会导致更快的进入快速重传和快速恢复阶段，而较大的阈值会导致更长时间的拥塞避免阶段。
阈值的动态性：一些TCP实现和拥塞控制算法可能会动态地调整阈值，以便更好地适应网络的条件。例如，TCP Reno算法根据拥塞事件的发生情况动态调整阈值。
平滑和稳定性：阈值的确定通常考虑到平滑和稳定性的因素，以防止频繁的阈值变化，因为这可能导致不稳定的拥塞控制行为。

12、算法：非递归前序遍历树（自建树，用栈依次放入根、右、左）

#include <iostream>
#include <stack>

using namespace std;

// 二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void iterativePreorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    stack<TreeNode*> nodeStack;
    nodeStack.push(root);

    while (!nodeStack.empty()) {
        TreeNode* currentNode = nodeStack.top();
        cout << currentNode->val << " "; // 打印当前节点的值
        nodeStack.pop();

        // 先将右子树入栈，再将左子树入栈，这样可以保证左子树在栈中处于顶部
        if (currentNode->right) {
            nodeStack.push(currentNode->right);
        }
        if (currentNode->left) {
            nodeStack.push(currentNode->left);
        }
    }
}

int main() {
    // 创建二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    cout << "非递归前序遍历结果: ";
    iterativePreorder(root);

    return 0;
}

结果输出：

13、找硬币，有1、3、5、7、9分的无限硬币，找到n分，要求二维数组实现和一维数组实现

一维数组：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

vector<int> findCoins(int n) {
    vector<int> coins = {1, 3, 5, 7, 9};
    vector<int> dp(n + 1, INT_MAX); // 用于存储最少硬币数量
    vector<int> prev(n + 1, -1);    // 用于记录硬币组合

    dp[0] = 0; // 0分不需要硬币

    for (int i = 1; i <= n; ++i) {
        for (int coin : coins) {
            if (i >= coin && dp[i - coin] != INT_MAX && dp[i - coin] + 1 < dp[i]) {
                dp[i] = dp[i - coin] + 1;
                prev[i] = coin;
            }
        }
    }

    // 构造硬币组合
    vector<int> result;
    while (n > 0) {
        result.push_back(prev[n]);
        n -= prev[n];
    }

    return result;
}

int main() {
    int n = 14;
    vector<int> result = findCoins(n);
    
    if (result.empty()) {
        cout << "无法找零" << endl;
    } else {
        cout << "找零" << n << "分的硬币组合为: ";
        for (int coin : result) {
            cout << coin << " ";
        }
        cout << endl;
    }

    return 0;
}

二维数组：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

vector<int> findCoins(int n) {
    vector<int> coins = {1, 3, 5, 7, 9};
    vector<vector<int>> dp(coins.size() + 1, vector<int>(n + 1, INT_MAX)); // 用于存储最少硬币数量
    vector<vector<int>> prev(coins.size() + 1, vector<int>(n + 1, -1));    // 用于记录硬币组合

    for (int i = 0; i <= coins.size(); ++i) {
        dp[i][0] = 0; // 0分不需要硬币
    }

    for (int i = 1; i <= coins.size(); ++i) {
        for (int j = 1; j <= n; ++j) {
            if (j >= coins[i - 1] && dp[i][j - coins[i - 1]] != INT_MAX && dp[i][j - coins[i - 1]] + 1 < dp[i - 1][j]) {
                dp[i][j] = dp[i][j - coins[i - 1]] + 1;
                prev[i][j] = coins[i - 1];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    // 构造硬币组合
    vector<int> result;
    int i = coins.size();
    int j = n;
    while (i > 0 && j > 0) {
        if (prev[i][j] != -1) {
            result.push_back(prev[i][j]);
            j -= prev[i][j];
        } else {
            --i;
        }
    }

    return result;
}

int main() {
    int n = 14;
    vector<int> result = findCoins(n);
    
    if (result.empty()) {
        cout << "无法找零" << endl;
    } else {
        cout << "找零" << n << "分的硬币组合为: ";
        for (int coin : result) {
            cout << coin << " ";
        }
        cout << endl;
    }

    return 0;
}

来源：https://www.nowcoder.com/discuss/523589743813128192?sourceSSR=users

微服务

文档

基础

快手一面 ​

1、C++和C的区别？ ​

2、纯虚函数和虚函数？ ​

3、共享指针和弱指针（shared_ptr与weak_ptr）？ ​

4、什么叫同步io和异步io？ ​

5、什么是回调异步？ ​

6、设计题：100w个用户访问服务器，要求：读写互斥、不能用锁和信号量、不能等待。 ​

7、tcp怎么保证可靠性？ ​

8、tcp怎么判断丢包了？ ​

9、超时时间怎么计算的？ ​

10、拥塞控制？ ​

11、窗口阈值怎么确定的？ ​

12、算法：非递归前序遍历树（自建树，用栈依次放入根、右、左） ​

13、找硬币，有1、3、5、7、9分的无限硬币，找到n分，要求二维数组实现和一维数组实现 ​