八股文/智力题整理¶

记录一些，八股文和智力题。

C++ 相关¶

C++ 虚函数¶

一般定义虚函数时是为了多态，允许基类的虚函数指针调用不同子类对该虚函数实现的不同功能。虚函数分为了虚函数和纯虚函数，虚函数是有默认的功能实现的，纯虚函数是没有实现的，要求子类必须实现这个函数。

纯虚函数的定义方式是在定义的语句后面加=0，例如：virtual void funtion1()=0

vector 中 push_back 和 emplace_back 的区别¶

emplace_back 在某些情况下要更快一些。

push_back:

如果传入的是左值: push_back 会首先调用构造函数构造出右值，然后调用 copy 将这个右值拷贝到 vector 空间内，然后在结束时调用这个右值的析构函数。
如果传入的是右值: push_back 首先会调用构造函数构造出右值，然后调用 move 将这个右值移动到 vector 空间内，然后在结束时调用这个右值的析构函数。

emplace_back:

如果传入的是右指，那么 emplace_back 会直接在 vector 的指定位置的内存创建对应的数据，少了一次 move。其他情况与 push_back 相同。

move 底层是怎么实现的¶

假设要将 A 中的数据移动到 B 中，move 底层会将 B 指向 A 的数据地址，然后将 A 的数据地址置为 nullptr。也就是说将数据的所有权转移到了 B 中。

std::move 的作用是将左值引用转换为右值引用，这样使用 a = std::move(b) 时就可以自动调用移动构造函数来进行移动。

完美转发的原理¶

在 C++17 中，完美转发的实现原理是：

如果参数是左值引用，那么转发时也使用左值引用，即std::forward(t)返回的是左值引用；
如果参数是右值引用或者折叠表达式右值引用，那么转发时也使用右值引用，即std::forward(t)返回的是右值引用。

关键函数 std::forward，如果传入的是左值引用就会返回左值引用，传入的是右值引用的话就会返回右值引用。例如

template <typename T>
void foo(T&& arg) {
    // 使用 std::forward 完美转发 arg 参数给 bar 函数
    bar(std::forward<T>(arg));
}

Python 相关¶

Python 可变对象与不可变对象¶

不可变对象是不可变的，当修改这类对象时实际上是创建了一个新的对象并修改引用，并且对原来的不可变对象进行回收。可变对象是可变的，修改的话就是直接修改这个对象。

不可变对象：int, float, str, tuple
可变对象：list, dict, set

智力/算法题¶

如何在 1T 的数据中寻找中位数¶

快速选择：每次找中间点，然后遍历一遍，将小于中间点的放左边，大于中间点的放右边，然后递归。

如何在大批量数据中寻找重复数据¶

给定 a,b 两个文件，各存放 \(50\) 亿的数据，每个数据大小 64B, 内存限制 4GB，如何找出 a,b 两个文件的重复数据？

分治 + 哈希来做。首先通过计算算出数据的大致大小 \(50 \times 10^8 \times 64\text{B} \approx 320\text{GB}\)。考虑将两个文件中的数据各划分为 \(1000\) 份，这样每一份文件大小大概是 \(320\text{MB}\)，内存可以完整装载每一份文件。对每一个数据进行 Hash，将 hashValue % 1000 的结果作为标号，将数据分别存储到 \(1000\) 个文件中。这样我们就有了文件一对应的 \(1000\) 份文件和文件二对应的 \(1000\) 份文件。我们将这 \(2000\) 份文件分为标号相同的 \(1000\) 对文件，所有可能的重复数据只可能出现在同一对文件中，这样我们就将问题规模缩小到了 \(320\text{MB}\)。然后我们就可以将每一对文件的第一份全部加入到 HashSet 中，然后枚举第二份文件的数据，如果在 HashSet 中出现过，那么就是重复数据。

如何在大批量数据中寻找出现次数最多的 K 个数据¶

有一个 \(1\text{GB}\) 大小的文件，文件里每一行是一个词，每个词的大小不超过 \(16\text{B}\)，内存大小限制是 \(1\text{1MB}\)，要求范围频数最高的 \(100\) 个词。

为了满足内存限制，我们仍然需要先采取划分的方式来将大文件分割成小文件。可以按照 hash(x) % 5000 来进行划分，如果划分后仍不满足就继续划分。划分之后用 Hashmap 统计出现次数即可，统计完所有文件的所有词的出现次数之后再开一个小根堆，如果某一个数字大于堆顶元素就将其加入到堆中。维护堆的大小不超过 K 即可。

如何在一个超大文件中找到出现次数最多的数据¶

与上一题同理，超大文件无法直接读入内存，那就需要一边读入一边将信息写出到文件中，先划分，再统计每个文件内数据的出现次数，最后求 max。

如何在 2.5 亿个整数中找出不重复的整数（内存无法容纳完整的这些数字）¶

有两种方法：

按照跟之前一样的方法，按照哈希余数进行划分，然后分别统计再整合。
位图法，简单来说就是操作二进制位来进行判断。空间占用与整数的大小有关，如果数字过于稀疏可能反而会导致更大的占用。也有一种位图索引的方法例如 RoaringBitmap 可以进行压缩。从最朴素的位图来说，可以将大小为 \(x\) 的数字映射到第 \(2x\) 和第 \(2x+1\) 个二进制位中，利用二进制位来表示状态：00 表示未出现过, 01 表示出现过一次, 10 表示出现过多次。这样的话假设所有整数都在 int 范围内，那么只需要 \(2*2^{32}\) 个二进制位，也就是 \(1\text{GB}\) 的空间。

如何在 40 亿个整数中判断某个数字是否出现过¶

可以按照哈希余数进行划分，然后再分别判断。
通过位图法，将数字映射到位图中，然后判断。

如何在 1000 万个记录中找到出现次数最多的记录¶

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询床的长度不超过 255 字节。假设目前有 1000w 个记录（这些查询串的重复度比较高，虽然总数是 1000w，但如果除去重复后，则不超过 300w 个）。请统计最热门的 10 个查询串，要求使用的内存不能超过 1G。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。）

首先计算内存，每个串 \(255\text{B}\)，那么 \(10 \times 10^7\) 大概就是 \(2.55\text{GB}\) 的空间占用。肯定是无法直接读入的，所以我们可以选择：

按照 Hash 结果划分为子问题，然后再统计
因为题目中提到了重复的串比较多，所以我们可以考虑通过 HashMap 储存，占用空间 \(300w*(255+4)\approx 777\text{MB}\)
Trie 树。

如何在大量电话号码中统计不同号码的个数，每个号码为 8 位数字¶

位图法 \(10^9 / 8 / 1024 / 1024 \approx 100\text{MB}\)

如何从大量数字中找到中位数（5亿个数）¶

双堆法
二分中位数的值，二分之后将数据分为大于 mid 和小于 mid 的两个部分，然后递归操作。