小公司数据库笔试题

1.

数组 A 和 B 都是已经排序的整数数组。

A 中的元素数量为 N，但 A 的总数组长度为 2N，元素在数组的前半部分

B 中的元素数量为 N，同时数组长度也是 N

现在，请把 B 中的元素合并到 A 中并保持合并后的 A 数组依然有序，请使用原地更新的代码

​

2.

在已排序的整数数组中，查找并计算给定数字的出现次数，要求最坏情况下的时间复杂度是 O(n)。

实现一个函数：

int Count(std::vector<int> arr, int target);

返回 arr 数组中，target 数值的总数量，注意 arr 是一个已经排序的递增数列。

注意，请不要使用数组遍历的方法实现

​

3.

在 C++ 编程中，在调用某一个函数的时候，通常会有如下需求：

- 如果函数调用正确，则返回要查询的目标值

- 如果函数出现错误，则返回错误状态信息

StatusOr<User> FindUserById(int user_id) {

    User user;

    bool user_found = FindUser(&user);

    if (user_found) {

        return user;

    }

    return Status::Error("User cannot be found");

}在上述函数中，如果找到了 `user` 则直接返回，否则返回错误信息。

现在，请你实现一个 `Status` 和 `StatusOr` 类，达到类似上面的效果，并提供对应的说明。

提示：需要使用模板

​

4. 现在有一个整数数组 a，我们已知它的总长度是 n，请实现一个函数，能够将数组 a 中的元素进行随机打乱，多次运行后的结果应该不同。实现后请描述时间复杂度和空间复杂度，可以使用必要的 C++ 函数库（如随机数生成等），但不能直接使用 shuffle 库函数。

5. 内存分配器的主要用途是提前批量的向系统申请一大片内存，然后根据业务的需要自己管理小片内存的使用和释放，以减少系统调用带来的性能抖动，同时，也能够根据我们对业务知识的理解，设计专用的内存分配策略，达到性能和利用率的最优化。现在，请你为以下特殊的需求场景设计一个内存分配器：

1. 用户每次进行内存申请的 size 有三种：小尺寸（100B 左右）、中尺寸（4KB 左右）、大尺寸（100KB 左右）

2. 每一种尺寸的申请数量不定，可能90%都是小尺寸的，只有小部分其他尺寸，也可能反过来

3. 内存申请后的释放时机不定，可以认为均匀分布

一个基本的内存分配器的定义如下所示：

class MemAllocator {

public:

    // Allocate a fixed size memory

    // maximum size is limited by `uint32_t`.

    void* Allocate(uint32_t size);

    int Free(void* ptr);

private:

    // low-level memory which was allocated from the kernel.

    void* arena_;

    // memory usage management

    MemoryManager manager_;

};其中，我们声明了 Allocate 和 Free 两个函数，而底层大片内存统一从系统分配，交给 arena_ 维护，最有用户每次的 Allocate 和 Free 交给 MemoryManager 维护，即这个类要维护哪些内存区域被用户占用了和释放了。

现在，请尝试回答以下问题：

1. 请描述 MemoryManager 的实现方案，它如何知道哪些内存片段是可以给用户用的，又是如何释放用户占用的内存的，并给出元数据开销预估

2. `Free` 函数并没有传递要释放的内存 size，它如何知道释放内存的尺寸？

3. 由于用户可能不同尺寸的内存片段穿插申请，MemoryManager 是否需要进行碎片整理，如果需要，如何做？

6..我们进行文件写操作的时候，有两种常见方法：

- 使用 MMAP 打开一个文件，然后对这个文件进行写操作

- 使用 DIRECTIO 模式打开一个文件，然后对文件进行写操作

假设我们使用的是 EXT4 文件系统，那么，请解释这两种方法写文件的优缺点，请从性能、数据一致性、API 限制等方面分别阐述。

7 请提供以下内容的答案：

1. 什么是协程？[2 分]

2. 什么情况下我们应该考虑使用协程？[3 分]

3. 请编写一段伪代码描述协程的使用方法 [5 分]

​

​8,1. 概述 LSM Tree 的工作原理以及主流的业界实现

2. 比较LSM Tree 和B+树优缺点