字节跳动广告基础架构实习一面

1. 自我介绍

2. 介绍一下你常用的 STL 容器

答案：我常用的 STL 容器主要有 vector、list、deque、map、unordered_map、set、unordered_set、queue、stack 和 priority_queue。如果从使用频率看，vector 和 unordered_map 是最常用的。vector 适合连续存储、随机访问和频繁遍历；unordered_map 适合根据 key 做快速查找；map 适合需要有序遍历或者范围查询的场景。

工程里我不会只看理论复杂度，还会看缓存局部性、扩容成本、迭代器失效、内存占用和数据规模。比如元素数量不大时，vector 线性查找有时反而比链表或者树结构更快。

3. 对比一下 `vector` 和 `list`

答案：vector 底层是连续内存，支持随机访问，遍历性能好，缓存命中率高。缺点是中间插入删除需要移动元素，扩容时可能导致整体搬迁。list 底层是双向链表，每个节点单独分配，插入删除某个已知节点很快，但不支持随机访问，而且缓存局部性差，遍历时会频繁跳地址。

所以不是简单说 list 插入删除一定快。真实场景下，如果数据量不大或者主要是遍历，vector 往往更快；只有在频繁在中间插入删除，并且已经拿到节点位置时，list 才比较有优势。

4. 如果想让 `list` 像数组一样连续存储，应该怎么做

答案：严格来说，list 的设计目标就是节点式存储，不可能直接让标准库 list 变成连续内存。如果希望有链表的插入删除语义，同时减少内存碎片和缓存 miss，可以考虑自己实现基于内存池的链表，把节点从一大块连续内存里分配出来。这样节点逻辑上还是链表，但物理分配更集中。

另一种思路是不用 list，而是用 vector 存节点，通过下标模拟链表的 next/prev，这样可以获得更好的连续内存访问特性。

代码：

#include <vector>
using namespace std;

struct Node {
    int val;
    int prev;
    int next;
};

class IndexList {
private:
    vector<Node> nodes;
    int head = -1;
    int tail = -1;

public:
    int push_back(int x) {
        int id = nodes.size();
        nodes.push_back({x, tail, -1});
        if (tail != -1) nodes[tail].next = id;
        tail = id;
        if (head == -1) head = id;
        return id;
    }
};

5. 为什么有时候遍历 `vector` 比遍历 `list` 更快

答案：主要原因是缓存局部性。vector 的元素连续存储，CPU 读取一个元素时，通常会把相邻的一段内存一起加载到 cache 里，后续遍历可以直接命中缓存。list 每个节点可能分散在堆上的不同位置，遍历时要不断通过指针跳转，容易 cache miss，而且每个节点还要额外存前后指针，内存占用也更高。

所以即使 list 某些操作理论复杂度更低，在现代 CPU 上也不一定更快。很多性能问题不能只看大 O，还要看内存访问模式。

6. `vector` 和 `list` 删除元素时迭代器会失效吗

答案：会，但规则不一样。vector 删除元素后，被删除位置以及其后的迭代器、引用、指针一般都会失效，因为后面的元素会向前移动。如果触发扩容，那原来的所有迭代器都会失效。list 删除某个节点时，只有指向被删除节点的迭代器失效，其他节点的迭代器通常仍然有效，因为节点之间不需要整体搬移。

遍历删除时要特别注意写法，不能删除后继续使用旧迭代器。

代码：

#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0) {
            it = v.erase(it);
        } else {
            ++it;
        }
    }
}

7. `map` 和 `unordered_map` 的区别

答案：map 底层通常是红黑树，元素按 key 有序存储，查找、插入、删除复杂度一般是 O(logN)。unordered_map 底层是哈希表，平均查找、插入、删除复杂度是 O(1)，但不保证顺序，极端哈希冲突时可能退化。

如果需要有序遍历、范围查询、找上下界，用 map 更合适；如果只是根据 key 快速查找，通常用 unordered_map。工程里还要考虑 key 的哈希质量、内存占用、扩容成本和迭代器稳定性。

8. `unordered_map` 和 `map` 的使用场景有什么差异

答案：如果业务逻辑关心 key 的顺序，比如按文件路径排序输出、查找某个范围内的数据、做前缀范围扫描，那么 map 更合适。如果只是做 ID 到对象、字符串到配置、用户到状态的快速映射，unordered_map 更常见。

不过 unordered_map 不是永远更好。它扩容时会 rehash，可能造成延迟抖动；哈希质量不好时冲突会变多；内存占用也往往比 map 更高。所以高性能场景里，可能还会提前 reserve，控制 max_load_factor，避免运行中频繁扩容。

代码：

#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, int> cnt;
    cnt.reserve(10000);
    cnt.max_load_factor(0.7);

    cnt["read"]++;
    cnt["write"]++;
}

9. `unordered_map` 的底层原理是什么

答案：unordered_map 底层一般是哈希表。插入元素时，先对 key 计算 hash 值，然后根据桶数量取模或者做映射，找到对应 bucket。不同 key 可能落到同一个 bucket，这就是哈希冲突。标准库常见实现里，冲突通常用链地址法处理，也就是每个 bucket 后面挂一个链表或节点结构。

当元素数量增长到一定程度，负载因子超过阈值时，哈希表会扩容并 rehash。这个过程需要重新分布已有元素，成本比较高，所以在性能敏感场景下要尽量提前预估容量。

10. 哈希冲突的链地址法怎么理解

答案：链地址法就是每个哈希桶后面挂一个链表或类似节点结构。如果多个 key 经过哈希后落到同一个桶，就把它们都放在这个桶对应的链上。查找时先定位 bucket，再在冲突链里比较 key。

它的优点是实现简单，删除也比较方便；缺点是如果冲突链太长，查询性能会下降，而且链表节点分散，缓存局部性不太好。所以哈希函数质量、桶数量、负载因子控制都很重要。

11. 链地址法如何优化，什么时候需要扩容

答案：链地址法优化主要从几个方向做。第一是选择更好的哈希函数，让 key 尽量均匀分布；第二是控制负载因子，桶里元素太多时及时扩容；第三是减少节点分配开销，比如使用内存池；第四是冲突严重时可以把长链转换成更高效的结构，不过标准库不一定这样做。

一般来说，当元素个数和 bucket 数量的比例超过阈值，就需要扩容。这个比例就是负载因子。扩容后会重新计算每个元素所在桶位置，也就是 rehash。

12. 除了链地址法，哈希冲突还有哪些解决方式

答案：还可以用开放寻址法，比如线性探测、二次探测、双重哈希。线性探测是在冲突后继续找下一个空位，实现简单，缓存局部性好，但容易形成聚集。二次探测能缓解一部分聚集问题，但探测序列设计更复杂。双重哈希则使用第二个哈希函数决定探测步长，分布更好一些。

开放寻址法删除元素时比较麻烦，不能简单把位置清空，否则会影响后续查找，通常要用删除标记。它前期性能可能很好，但负载因子太高后性能会明显抖动，所以通常要控制装载率。

13. 你用过其他库里的哈希表吗，和标准库有什么区别

答案：用过或者了解过一些高性能哈希表，比如 robin hood hashing、flat hash map 这类思想。它们通常更关注缓存局部性和探测距离控制。标准库 unordered_map 接口稳定、通用性好，但节点式结构比较多，内存局部性和常数性能不一定最优。

一些高性能哈希表会把元素放得更紧凑，减少指针跳转，查找时更容易命中 cache。代价是迭代器稳定性、删除实现、扩容策略可能和标准库不同。工程里如果性能瓶颈明确在哈希表，并且能接受额外依赖，才会考虑替换。

14. 智能指针有哪些，分别解决什么问题

答案：常见智能指针有 unique_ptr、shared_ptr 和 weak_ptr。unique_ptr 表示独占所有权，不能拷贝，只能移动，适合资源唯一归属的场景。shared_ptr 表示共享所有权，通过引用计数管理对象生命周期。weak_ptr 不增加引用计数，主要用于观察 shared_ptr 管理的对象，解决循环引用和异步回调里的生命周期判断问题。

使用智能指针的核心不是“把裸指针都换掉”，而是先想清楚对象的所有权。如果所有权不清楚，智能指针也会被用乱。