笔试和面试总结

前言这几个基本都是奔着刷题去的

某友实习面试

去除重复的关键字是？

Distinct

如何实现多线程？

#include <iostream>
#include <vector>
#include <queue>
#include <thread>
#include <mutex>
#include <condition_variable>

class ThreadPool {
private:
    std::vector<std::thread> workers;
    std::queue<std::function<void()>> tasks;
    std::mutex queueMutex;
    std::condition_variable condition;
    bool stop;

    void workerFunction() {
        while (true) {
            std::unique_lock<std::mutex> lock(queueMutex);
            condition.wait(lock, [this] { return stop ||!tasks.empty(); });
            if (stop && tasks.empty()) {
                return;
            }
            std::function<void()> task = tasks.front();
            tasks.pop();
            lock.unlock();
            task();
        }
    }

public:
    ThreadPool(size_t threadCount) : stop(false) {
        for (size_t i = 0; i < threadCount; ++i) {
            workers.emplace_back([this] { workerFunction(); });
        }
    }

    ~ThreadPool() {
        {
            std::unique_lock<std::mutex> lock(queueMutex);
            stop = true;
        }
        condition.notify_all();
        for (std::thread& worker : workers) {
            worker.join();
        }
    }

    template<typename FunctionType>
    void enqueue(FunctionType&& task) {
        {
            std::unique_lock<std::mutex> lock(queueMutex);
            tasks.emplace(std::forward<FunctionType>(task));
        }
        condition.notify_one();
    }
};

void task(int id) {
    std::cout << "Task " << id << " is running" << std::endl;
}

int main() {
    ThreadPool pool(4);

    for (int i = 1; i <= 10; ++i) {
        pool.enqueue([i] { task(i); });
    }

    return 0;
}

ThreadPool 类包含工作线程的向量、任务队列、互斥锁、条件变量和停止标志。
workerFunction 是每个工作线程的执行函数，它等待任务并执行。
构造函数创建指定数量的工作线程。
enqueue 方法用于向任务队列添加任务。
在 main 函数中创建线程池并添加任务。

某小公司实习

什么是字节对齐？int ,char,short占多少字节？

某益网络笔试

贪心算法有哪些？

迪杰斯特拉算法，prim算法，Floyd warshall算法，ford fulkerson

第三个不是贪心算法，其余是的，最后一个是求最大流的图算法

下列哪些是平衡树？

替罪羊树，基数树，伸展树

替罪羊树

替罪羊树（Scapegoat Tree）是计算机科学中一种基于部分重建的自平衡二叉搜索树。

替罪羊树的主要思想是将不平衡的树压成一个序列，然后暴力重构成一棵平衡的树。这里的平衡指的是：对于某个0.5 <= α <= 1（α 一般取 0.75），满足 size(lson(x)) <= α * size(x) 并且 size(rson(x)) <= α * size(x)，即这个节点的两棵子树的大小都不超过以该节点为根的子树的大小，那么就称这个子树（或节点）是平衡的。

在非平衡的二叉搜索树中，每次操作以后检查操作路径，找到最高的满足 max(size(son_l), size(son_r)) > α * size(this) 的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为替罪羊节点。

与其他一些平衡树（如通过旋转操作来保持平衡的树）相比，替罪羊树具有一些优点：

思维难度相对较小，和其他平衡树的思维难度差不多；
代码量少，思路清晰，实现简单，容易调试；
速度不慢；
不依赖于旋转机制。

替罪羊树的基本操作包括插入、删除、重构和查询等，以下是这些操作的简要介绍：

插入：与二叉搜索树的插入操作类似。直接找到合适的位置插入新节点，如果插入后导致某个子树不平衡，则对该子树进行重构。
删除：不是真正地删除节点，而是标记节点不存在，并在计算其所在子树大小时将实际大小减 1。如果删除后子树不平衡，也需要进行重构。
重构：先通过中序遍历将子树“拍扁”，把所有节点存入一个数组，保证数组元素有序；然后以数组中间的节点为新的根，重新构建平衡的二叉树。
查询：例如查询值为 v 的数的排名和排名为 rk 的数的值，查询过程与二叉搜索树类似，但要多判断一些节点不存在的情况。

虽然替罪羊树在重构时看起来比较暴力，但由于平衡的限制，其插入、删除和查询等操作的均摊时间复杂度仍然是 O(log n)。在实际应用中，替罪羊树适用于需要维护平衡二叉搜索树结构，且对代码简洁性和调试方便性有一定要求的场景。然而，它的时间复杂度可能不如一些其他更高效的平衡树结构，例如红黑树等。在选择数据结构时，需要根据具体的应用场景和性能要求进行综合考虑。

哪些是私有网段？

UDP在哪些协议中有使用？

DNS,SNMP，SFTP，SNMP

UDP（User Datagram Protocol，用户数据报协议）通常在以下协议中被使用：

DNS（Domain Name System，域名系统）：用于将域名转换为 IP 地址。DNS 查询通常使用 UDP 协议，因为请求和响应的数据量较小，并且对实时性要求较高，不需要建立连接的开销。
SNMP（Simple Network Management Protocol，简单网络管理协议）：用于网络设备的管理和监控。
TFTP（Trivial File Transfer Protocol，简单文件传输协议）：适用于小型文件的传输，例如在启动过程中传输引导文件。
RIP（Routing Information Protocol，路由信息协议）：一种内部网关协议，用于在自治系统内交换路由信息。
NTP（Network Time Protocol，网络时间协议）：用于在计算机网络中同步时钟。
DHCP（Dynamic Host Configuration Protocol，动态主机配置协议）：用于为网络中的设备动态分配 IP 地址等网络配置信息。

这些协议选择使用 UDP 主要是因为它们的数据量相对较小，对实时性要求较高，或者可以容忍一定程度的数据包丢失。UDP 的无连接特性和较低的开销使得它在这些场景中具有优势。

例如，在 DNS 中，当用户在浏览器中输入一个域名时，客户端会向 DNS 服务器发送一个 UDP 数据包请求域名对应的 IP 地址。DNS 服务器收到请求后，会尽快返回一个包含 IP 地址的 UDP 数据包给客户端。由于 DNS 查询通常较短，使用 UDP 可以快速完成交互，减少建立连接的时间和资源消耗。

SFTP是什么协议?

不使用UDP，因为他要求可靠的文件传输，通常用于大文件的传输

SFTP（Secure File Transfer Protocol，安全文件传输协议）是一种基于 SSH（Secure Shell）协议提供安全文件传输服务的网络协议。

SFTP 提供了以下主要特点和优势：

加密和安全性：对传输的数据进行加密，包括用户名、密码、文件内容等，确保数据在传输过程中的保密性和完整性。提供身份验证机制，确保只有授权的用户能够进行文件传输操作。
可靠的文件传输：支持文件的上传、下载、删除、重命名等常见操作。能够处理大文件的传输，并保证数据的准确性。
跨平台支持：可以在多种操作系统上运行，包括 Windows、Linux、Mac 等。

与传统的 FTP（File Transfer Protocol）协议相比，SFTP 提供了更高的安全性，适用于对数据安全要求较高的场景，如企业内部敏感数据的传输、金融交易数据的交换等。

例如，一家金融公司在不同分支机构之间传输财务报表时，可能会使用 SFTP 来确保这些重要数据不会被窃取或篡改。又如，软件开发团队在向服务器上传或下载代码文件时，为了保护知识产权和代码的安全性，也会采用 SFTP 协议。