快手一面，真细节！！

来源：

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

阿Q给出一些参考回答，希望大家可以借鉴借鉴~

1. 编程范式：

• C++：C++是一种多范式编程语言，支持面向过程、面向对象和泛型编程。这意味着你可以使用C++编写传统的过程式代码，也可以使用类和对象创建面向对象的程序，还可以使用模板进行泛型编程。
• C：C是一种面向过程的编程语言，它更注重以过程和函数为基础的编程方法。

1. 面向对象编程（OOP）：

• C++：C++支持面向对象编程（OOP），提供了类、继承、多态等概念，允许你以对象为基础组织代码，实现封装、继承和多态等OOP特性。
• C：C不直接支持面向对象编程。虽然可以模拟一些OOP概念，但没有直接的语言支持。

1. 标准模板库（STL）：

• C++：C++具有强大的标准模板库（STL），其中包含了各种容器（如向量、链表、映射等）、算法和函数模板，可用于高效地处理数据结构和算法问题。
• C：C没有类似STL的标准库，开发者需要自行实现各种数据结构和算法。

1. 异常处理：

• C++：C++具有异常处理机制，允许程序员编写可以捕获和处理异常的代码，以增加程序的健壮性。
• C：C不直接支持异常处理。在C中，错误通常通过函数的返回值或全局变量来处理。

1. 运算符重载：

• C++：C++允许运算符重载，这意味着你可以为类定义自定义的运算符行为。
• C：C不支持运算符重载。

1. 类型检查：

• C++：C++在编译时进行更严格的类型检查，有助于捕获潜在的类型错误。
• C：C的类型检查相对较弱，更容易出现类型错误。

1. 内存管理：

• C++：C++有更复杂的内存管理，包括构造函数、析构函数以及new和delete运算符，用于动态内存分配和释放。
• C：C的内存管理相对简单，主要使用malloc和free函数。

1. 标准库：

• C++：C++标准库在C标准库的基础上进行了扩展，包含了更多的容器、算法和其他功能。
• C：C标准库相对较小，包括一些基本的输入输出和字符串处理函数。

1. 编程风格：

• C++：C++通常用于大型、复杂的软件项目，特别适合需要面向对象设计的应用程序。
• C：C更适用于系统编程、嵌入式编程和一些需要更底层控制的任务。

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


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

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

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

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

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

1. 观察者角色：weak_ptr
   用于解决shared_ptr
   可能导致的循环引用问题。它允许你观察一个对象，但不会增加对象的引用计数。
2. 无法直接访问对象：weak_ptr
   不能直接访问共享对象的成员或方法。要访问对象，需要将weak_ptr
   转换为shared_ptr
   。
3. 提供.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;
}

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

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

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

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

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


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

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

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

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

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

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

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

#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;
}

#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;
}