首页 秋招复盘8.10：cpp、碎碎念
文章
取消

秋招复盘8.10：cpp、碎碎念

发表于 2023/09/25
作者 Olimi
阅读量: 18 分钟阅读
  1. 一个树的广义表达A(B(E,F,G)，C,D)怎么转换为二叉树。本来不是二叉树的，怎么转二叉树。

  2. 一个实参5，选择什么形参。short、long。

    error: call of overloaded ‘t(int)’ is ambiguous

    什么题目。。

  3. 排序算法复杂度。冒泡N2

  4. PreparedStatement的SetNString是啥。SetNString和SetString都行，前者设置NVARCHAR，后者VARCHAR。executeUpdate 返回影响的行数。

    返回值都考，查api文档呀。。

  5. python iter(dict)。for iter. 结果。

    返回键。

  6. FCFS适合I/O or CPU密集，长or短。

    错完了。思路完全反。

    FCFS（First-Come, First-Served）是一种简单的调度算法，它按照任务到达的顺序来处理任务。首先到达的任务首先被处理，以此类推。这种算法易于理解和实现，但在某些情况下可能不是最有效的策略。

    FCFS调度算法更适合于长任务和CPU密集型任务：

    1. 长任务：FCFS对长任务更友好，因为一旦任务开始，它就会一直运行，直到完成。这避免了频繁的上下文切换，这可能会在处理大量短任务时产生显著的开销。
    2. CPU密集型任务：CPU密集型任务（与I/O密集型任务相比）倾向于在开始后持续运行，而不是频繁地等待I/O操作。因此，FCFS可以有效地为这类任务服务，因为一旦任务开始，它们就不太可能被中断。

    然而，FCFS的一个主要问题是可能会导致“饥饿”现象，即短任务或I/O密集型任务可能在长任务或CPU密集型任务后面等待很长时间。此外，FCFS也不能很好地支持优先级调度，因为它只考虑了任务的到达顺序。

    因此，尽管FCFS在某些场景下可能有效，但在需要支持多种类型任务、优先级调度或高吞吐量的环境中，可能需要更复杂的调度算法，如最短作业优先（SJF）、优先级调度，或者轮转调度（Round Robin）。

  7. RIPV2是啥，有啥特点。

    RIP (Routing Information Protocol) 是一种基于距离向量的路由协议，用于在 IP 网络中交换路由信息。RIPv2 是 RIP 的第二个版本，增加了一些新功能，改进了一些原有的缺陷。

    RIPv2 的主要特性包括：

    1. CIDR（无类别域间路由）支持：RIPv1 只支持固定的子网划分，而 RIPv2 支持 CIDR，允许更灵活的 IP 地址分配和路由汇总。
    2. 下一跳地址：RIPv2 更新可以包括下一跳路由器的地址，这可以改善网络的路由效率。
    3. 认证机制：RIPv2 提供了简单的认证机制，可以增加网络的安全性。
    4. 多播：RIPv1 使用广播来发送路由更新，这可能会浪费网络资源。RIPv2 使用 IP 多播地址（224.0.0.9）发送路由更新，这可以减少不必要的网络流量。

    然而，尽管 RIPv2 有这些改进，但它依然受限于 RIP 协议的一些基本限制，比如最大跳数限制（15 跳），以及使用跳数作为唯一的路由度量标准。这使得 RIPv2 在大型网络或者复杂的网络环境中可能并不是最佳的路由协议。在这些情况下，可能需要使用更高级的路由协议，例如 OSPF 或者 BGP。

  8. UML用例 extends。指向者扩展被指向者。

    img

    img

  9. hash算法，α是啥，碰撞和n有没关系

    在计算机科学中，哈希（hash）算法是一种函数，它将任何大小的输入数据（通常是字符串）映射到固定大小的输出数据。哈希函数的一个重要属性是它的确定性，即给定相同的输入，它总是产生相同的输出。

    在哈希表的上下文中，α (alpha) 通常被用来表示负载因子（load factor），也就是满载度。负载因子是一个衡量哈希表满载程度的指标，通常被定义为哈希表中已经填充的槽位的数量（n）除以哈希表的总的槽位数量（m）。换句话说，α = n/m。

    哈希碰撞是指两个或者更多的输入数据经过哈希函数映射后得到相同的输出值。当你往哈希表中添加元素时，如果新元素与已有元素经过哈希函数映射后得到的哈希值相同，那么就会发生哈希碰撞。

    如果哈希表中的元素数量增加，那么发生哈希碰撞的概率也会相应地增加。这是因为哈希函数的输出空间（也就是哈希表的大小）是有限的，但输入空间可能是无限的。因此，当元素数量增加时，不同元素映射到同一哈希值的概率就会提高。

    例如，如果哈希函数的输出空间只有1000个槽位，但你有10000个不同的输入元素，那么至少有9000个元素会和其他元素发生哈希碰撞。

    为了减少哈希碰撞，通常会设计良好的哈希函数以尽可能均匀地分布哈希值，并且在哈希表的负载因子（即已填充的槽位数量和总槽位数量的比值）达到一定阈值时，会增大哈希表的大小。此外，还需要设计一种碰撞解决方案，比如链地址法（separate chaining）或者开放寻址（open addressing）。

  10. hash，线性探测再散列算法

    线性探测再散列是一种解决哈希表碰撞问题的技术，它属于开放地址（Open Addressing）的一种，也被称为线性探查（Linear Probing）。

    在哈希表中，当两个或者更多的键（key）经过哈希函数映射后得到相同的哈希值，就会发生碰撞。线性探测再散列的基本思想是，当发生碰撞时，尝试寻找下一个可用的槽位来存储新的键值对。

    具体的操作如下：

    1. 将键通过哈希函数映射到哈希表中的某个槽位。
    2. 如果该槽位已经被占用（即发生了碰撞），那么查看下一个槽位。
    3. 如果下一个槽位也被占用，那么继续查看下下一个槽位，以此类推，直到找到一个空闲的槽位。
    4. 将键值对存储在找到的空闲槽位中。

    这种方法的优点是实现简单，而且在哈希表的负载因子（已存储的键值对数和哈希表大小的比值）较低时，其性能较好。但是，当哈希表变得比较满时，可能需要探查很多个槽位才能找到空闲的位置，这会导致性能下降。并且，可能会出现聚集（clustering）现象，即连续的槽位都被占用，使得新的键值对必须存储在距离其哈希值较远的地方。

    为了解决这些问题，可以使用其他的开放寻址方法，如二次探查（Quadratic Probing）和双重哈希（Double Hashing），或者使用链地址法（Separate Chaining），在每个槽位上存储一个链表来处理碰撞。

  11. 算法。动规太菜了，必须专项加强一下，不要逃避问题。

  12. 结构化绑定

    就是解包啦，python经典。太高大上一时间有点想不起来。

    C++17 引入了一种新的语言特性，叫做 “结构化绑定”（Structured Binding）。这个特性允许你在单个声明中创建多个新的变量，这些变量可以用来接收从数组、元组或者结构体解构（destructure）出来的值。

    以下是一些使用结构化绑定的示例：

    1. 从元组中解构值：
    1
2
3

    std::tuple<int, std::string, float> getSomeData();
auto [a, b, c] = getSomeData();
std::cout << "Int: " << a << ", String: " << b << ", Float: " << c << std::endl;

    在这个示例中，getSomeData 函数返回一个元组，然后我们使用结构化绑定一次性创建了三个变量 a、b、c，并将元组中的值赋给了它们。

    1. 从数组中解构值：
    1
2
3

    int arr[] = {1, 2};
auto [x, y] = arr;
std::cout << "x: " << x << ", y: " << y << std::endl;

    在这个示例中，我们从数组 arr 中解构出两个值，并赋给了变量 x 和 y。

    1. 从结构体中解构值：
    1
2
3
4
5
6
7
8

    struct MyStruct {
    int id;
    std::string name;
};
    
MyStruct s = {1, "example"};
auto [id, name] = s;
std::cout << "id: " << id << ", name: " << name << std::endl;

    在这个示例中，我们从结构体 s 中解构出两个值，并赋给了变量 id 和 name。

    结构化绑定是一种非常方便的特性，它可以让你更简洁、更清晰地从复合数据类型中解构出值。

  13. unique_ptr独占的实现。

    说了拷贝构造和复制运算符重载删除，不过面试官好像不太满意。

    std::unique_ptr 的独占所有权是通过禁止复制操作并允许移动操作来实现的。具体来说，std::unique_ptr 的复制构造函数和复制赋值运算符被声明为删除的，这意味着你不能复制一个 std::unique_ptr。同时，它提供了移动构造函数和移动赋值运算符，允许你将一个 std::unique_ptr 的所有权转移给另一个 std::unique_ptr。

    以下是 std::unique_ptr 的简化实现，以便你可以理解其工作原理：

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

    template <typename T>
class unique_ptr {
public:
    explicit unique_ptr(T* ptr = nullptr) : ptr_(ptr) {}
    
    ~unique_ptr() { delete ptr_; }
    
    // 删除复制构造函数和复制赋值运算符
    unique_ptr(const unique_ptr&) = delete;
    unique_ptr& operator=(const unique_ptr&) = delete;
    
    // 提供移动构造函数和移动赋值运算符
    unique_ptr(unique_ptr&& other) noexcept : ptr_(other.ptr_) { other.ptr_ = nullptr; }
    unique_ptr& operator=(unique_ptr&& other) noexcept {
        if (this != &other) {
            delete ptr_;
            ptr_ = other.ptr_;
            other.ptr_ = nullptr;
        }
        return *this;
    }
    
    T* operator->() { return ptr_; }
    T& operator*() { return *ptr_; }
    
private:
    T* ptr_;
};

    在上述代码中，当我们尝试复制一个 unique_ptr 时，编译器会报错，因为复制构造函数和复制赋值运算符已被删除。当我们尝试移动一个 unique_ptr 时（例如，将其传递给另一个函数，或从另一个函数返回它），移动构造函数或移动赋值运算符会被调用，它们会从源 unique_ptr 中删除指针，并在目标 unique_ptr 中设置该指针。这就确保了每个 unique_ptr 都有其独占的对象，从而实现了独占所有权。

    注意，这只是一个简化版本的 unique_ptr，实际的 std::unique_ptr 还包括更多的功能，例如自定义删除器、数组支持等。

  14. new和malloc区别

    new 和 malloc 都是用于在 heap（堆）中分配内存的，但它们之间存在一些重要的区别：

    1. 来源：new 是 C++ 中的运算符，而 malloc 是 C 的函数。
    2. 构造和析构：new 不仅分配内存，还会调用对象的构造函数来初始化对象。当使用 delete 释放内存时，它还会调用对象的析构函数。而 malloc 只是简单地分配一块内存，不会调用任何构造函数或析构函数。
    3. 类型安全：new 会返回正确的类型，不需要类型转换。而 malloc 返回的是 void*，需要进行类型转换。
    4. 错误处理：如果 new 无法分配内存（例如，内存不足），它会抛出 std::bad_alloc 异常（除非你使用了 nothrow 版本的 new，那样的话它会返回 nullptr）。而 malloc 在无法分配内存时只会返回 NULL（或 nullptr 在 C++ 中）。
    5. 内存分配大小：new 会自动计算需要分配的内存大小，而 malloc 需要显式地提供字节数。

    以下是两者的使用示例：

    使用 new：

    1
2
3
4

    int* p = new int;
*p = 5;
// 使用完成后，需要使用 delete 来释放内存
delete p;

    使用 malloc：

    1
2
3
4

    int* p = (int*) malloc(sizeof(int));
*p = 5;
// 使用完成后，需要使用 free 来释放内存
free(p);
随笔
总结 招聘
本文由作者按照 CC BY 4.0 进行授权
最近更新

秋招复盘9.15：大厂的痛

秋招复盘8.3：C加加