算法题

实现一个简单的文件系统，支持 mkdir、mkfile、ls、tree 等操作。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <iostream>
#include <unordered_map>
#include <memory>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

class FSNode {
public:
    string name;
    FSNode(const string& name) : name(name) {}
    virtual bool is_file() const = 0;
    virtual ~FSNode() = default;
};

class File : public FSNode {
public:
    string content;
    File(const string& name) : FSNode(name) {}
    bool is_file() const override { return true; }
};

class Dir : public FSNode {
public:
    unordered_map<string, unique_ptr<FSNode>> children;
    Dir(const string& name) : FSNode(name) {}
    bool is_file() const override { return false; }
};

class FileSystem {
private:
    unique_ptr<Dir> root;

    vector<string> split(const string& path) {
        vector<string> parts;
        stringstream ss(path);
        string item;
        while (getline(ss, item, '/')) {
            if (!item.empty()) parts.push_back(item);
        }
        return parts;
    }

    Dir* traverse_dir(const vector<string>& parts, bool create = false) {
        Dir* curr = root.get();
        for (const string& part : parts) {
            if (!curr->children.count(part)) {
                if (create) {
                    curr->children[part] = make_unique<Dir>(part);
                } else {
                    return nullptr;
                }
            }
            FSNode* node = curr->children[part].get();
            if (node->is_file()) return nullptr;
            curr = static_cast<Dir*>(node);
        }
        return curr;
    }

    FSNode* get_node(const vector<string>& parts) {
        Dir* curr = root.get();
        for (size_t i = 0; i < parts.size(); ++i) {
            if (!curr->children.count(parts[i])) return nullptr;
            FSNode* node = curr->children[parts[i]].get();
            if (i == parts.size() - 1) return node;
            if (node->is_file()) return nullptr;
            curr = static_cast<Dir*>(node);
        }
        return curr;
    }

public:
    FileSystem() {
        root = make_unique<Dir>("/");
    }

    void mkdir(const string& path) {
        auto parts = split(path);
        Dir* curr = root.get();
        for (const string& part : parts) {
            if (!curr->children.count(part)) {
                curr->children[part] = make_unique<Dir>(part);
            } else if (curr->children[part]->is_file()) {
                cout << "mkdir: cannot create directory '" << path << "': Not a directory\n";
                return;
            }
            curr = static_cast<Dir*>(curr->children[part].get());
        }
    }

    void mkfile(const string& path) {
        auto parts = split(path);
        if (parts.empty()) return;
        string filename = parts.back();
        parts.pop_back();
        Dir* dir = traverse_dir(parts, false);
        if (!dir) {
            cout << "mkfile: cannot create file '" << path << "': No such directory\n";
            return;
        }
        if (dir->children.count(filename) && !dir->children[filename]->is_file()) {
            cout << "mkfile: cannot create file '" << path << "': Is a directory\n";
            return;
        }
        dir->children[filename] = make_unique<File>(filename);
    }

    void ls(const string& path) {
        auto parts = split(path);
        if (parts.empty()) {
            // root dir
            vector<string> res;
            for (auto& [k, _] : root->children) res.push_back(k);
            sort(res.begin(), res.end());
            for (auto& name : res) cout << name << " ";
            cout << endl;
            return;
        }

        FSNode* node = get_node(parts);
        if (!node) {
            cout << "ls: cannot access '" << path << "': No such file or directory\n";
            return;
        }

        if (node->is_file()) {
            cout << node->name << endl;
            return;
        }

        Dir* dir = static_cast<Dir*>(node);
        vector<string> res;
        for (auto& [k, _] : dir->children) res.push_back(k);
        sort(res.begin(), res.end());
        for (auto& name : res) cout << name << " ";
        cout << endl;
    }

    void tree(const string& path = "/") {
        auto parts = split(path);
        FSNode* node = root.get();

        if (!parts.empty()) {
            node = get_node(parts);
            if (!node) {
                cout << "tree: cannot access '" << path << "': No such file or directory\n";
                return;
            }
            if (node->is_file()) {
                cout << "- " << node->name << endl;
                return;
            }
        }

        print_tree(node, 0);
    }

    void print_tree(FSNode* node, int depth) {
        if (node != root.get()) {
            cout << string(depth * 2, ' ') << (node->is_file() ? "- " : "+ ") << node->name << endl;
        }
        if (!node->is_file()) {
            Dir* dir = static_cast<Dir*>(node);
            for (auto& [_, child] : dir->children) {
                print_tree(child.get(), depth + 1);
            }
        }
    }
};

int main() {
    FileSystem fs;
    fs.mkdir("/a/b/c");
    fs.mkfile("/a/b/c/file.txt");
    fs.ls("/a/b/c");
    fs.tree("/a");
    fs.tree();
    fs.ls("/a/b/d"); // should show error
    fs.mkfile("/a/b/d/file.txt"); // should show error
    return 0;
}

简答题

第一题：结构体内存与指针偏移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct T {
    unsigned char a;
    int b;
};

int q1() {
    T t;
    memset(&t, 0xff, sizeof(T));
    t.a = 0;
    t.b = 0;
    unsigned char* p = &t.a + 1;
    printf("*p = %d\n", *p);
    return 0;
}

✅ 解析：

  • memset 将结构体所有 8 字节填充为 0xFF（255）。
  • t.a = 0 设置偏移 0 的字节为 0。
  • t.b = 0 设置偏移 47 为 0，其间偏移 13 为 padding 字节，没有被写入。
  • &t.a + 1 是偏移 1 的地址，即 padding 区第一个字节，值仍为 0xFF。

✅ 结果输出：

1
*p = 255

💡 教学点：

  • 结构体存在内存对齐和填充（padding）；
  • 读取 padding 区域不一定是 UB（未定义行为），但需谨慎；
  • unsigned char* 是合法的 byte-wise 访问指针。

第二题：指针运算与地址偏移

1
2
3
4
5
6
int q2() {
    uint32_t* p = (uint32_t*)(0x81000000);
    printf("p = %p\n", p);
    printf("p + 1 = %p\n", p + 1);
    return 0;
}

✅ 解析：

  • p 指向地址 0x81000000
  • p + 1 会跳过 4 字节（sizeof(uint32_t)）

✅ 输出：

1
2
p = 0x81000000
p + 1 = 0x81000004

💡 教学点：

  • 指针运算基于类型大小；
  • 这种裸地址操作在嵌入式开发中常见，但在用户态不安全。

第三题：指针传值与数组修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void fun(int* p) {
    p++;
    *p = 80;
}

int q3() {
    int a[4] = {20, 30, 40, 50};
    int* p = &a[1];
    printf("*p = %d\n", *p);
    fun(p);
    printf("*p = %d\n", *p);
    for (int i = 0; i < 4; i++) {
        printf("a[%d] = %d\n", i, a[i]);
    }
    return 0;
}

✅ 解析：

  • p 指向 a[1] → 初始为 30。
  • fun(p) 中 p++ 不影响原指针，仅作用于副本。
  • *p = 80 实际修改了 a[2]。

✅ 输出：

1
2
3
4
5
6
*p = 30
*p = 30
a[0] = 20
a[1] = 30
a[2] = 80
a[3] = 50

💡 教学点：

  • 指针作为参数传值，默认是副本；
  • 若要修改原始地址，应使用 int*& 或 int**。

第四题：unique_ptr 所有权迁移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class RealServer {
  public:
    ~RealServer() { printf("RealServer destructed\n"); }
};

struct Service {
    vector<unique_ptr<RealServer>> servers;
};

int q4() {
    Service* service1 = new Service();
    service1->servers.push_back(make_unique<RealServer>());
    Service* service2 = new Service(std::move(*service1));
    cout << service1->servers.size() << endl;
    cout << service2->servers.size() << endl;
    delete service1;
    delete service2;
    return 0;
}

✅ 解析：

  • service1 拥有一个 RealServer；
  • std::move(*service1) 会触发 Service 的成员变量 servers 的移动构造；
  • 所有权转移后，service1->servers 为空，service2 拥有资源。

✅ 输出：

1
2
3
0
1
RealServer destructed

💡 教学点：

  • unique_ptr 强制所有权唯一；
  • 移动构造将资源转移，原对象被清空；
  • 注意裸指针对象需手动 delete，推荐用 std::unique_ptr<Service> 管理。

### 第五题：map 键类型的比较运算符设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Key {
    int af;
    string id;

    Key(int af, string id) : af(af), id(id) {}
    Key(string id) : af(AF_INET), id(id) {}

    bool operator!=(const Key& other) const { return !(af == other.af && id == other.id); }
    bool operator==(const Key& other) const { return af == other.af && id == other.id; }

    // 错误的实现方式（有隐患）
    bool operator<(const Key& other) const { return af < other.af && id < other.id; }
};
map<Key, string> m;

❌ 错误点：

  • operator< 写成 af < other.af && id < other.id，不符合 STL 对严格弱序的要求；
  • 可能导致：!(a < b) && !(b < a) 成立但 a != b，破坏 map 正常行为。

✅ 正确写法：

1
2
3
bool operator<(const Key& other) const {
    return af < other.af || (af == other.af && id < other.id);
}

💡 教学点：

  • std::map 依赖 < 实现严格弱序（strict weak ordering）；
  • 自定义结构用作 map 的 key 时需小心 operator< 的定义逻辑；
  • 如果用于 unordered_map，则应实现 operator== 和自定义 std::hash<Key>。

1. 第四题，不调用 std::move 会怎么样？unique_ptr 的作用？（答：会编译失败，unique_ptr 是不可拷贝的）

标准答案： 在第四题中，Service 内部包含 std::vector<std::unique_ptr<RealServer>>，而 unique_ptr 是一个独占所有权的智能指针，不能拷贝，只能移动。如果调用 Service(*service1) 而不是 std::move(*service1)，会触发默认拷贝构造函数，而编译器会报错，因为 unique_ptr 拷贝构造是被禁用的。

扩展问题：

  • 如何实现支持拷贝的版本？（改为 shared_ptr 即可）
  • shared_ptr 和 unique_ptr 区别？（前者引用计数共享所有权，后者独占所有权）

2. 构造与析构顺序，调用了哪些函数？（答：构造 RealServer，移动构造 Service，析构 RealServer）

标准答案：

  • 首先调用 RealServer 的构造函数（匿名未显示）。
  • 然后执行 std::move(*service1)，调用编译器生成的 Service(Service&&) 移动构造函数。
  • 程序结束时，先析构 service2，其中 unique_ptr<RealServer> 被析构，打印 "RealServer destructed"。
  • 最后析构空的 service1。

扩展问题：

  • 如果 RealServer 的构造函数带参数怎么办？
  • 如何显示定义移动构造函数？

3. Ping 一个地址会发生什么？（答：DNS -> 创建 socket -> 构造 ICMP 包 -> 发送）

标准答案：

  1. DNS 解析将域名转换为 IP 地址。
  2. 创建原始 socket（raw socket）。
  3. 构造 ICMP Echo Request 报文。
  4. 使用 socket 发送报文到目标地址。
  5. 接收 ICMP Echo Reply。

扩展问题：

  • ping 为什么需要 root 权限？（因为 raw socket）
  • ping 默认使用哪个协议？（ICMP）

4. ICMP 包需要发送哪些内容？（答：type、code、校验和等）

标准答案： 一个标准 ICMP Echo Request 报文结构包括：

  • Type（8 表示 Echo Request）
  • Code（0）
  • Checksum（校验和）
  • Identifier + Sequence Number
  • Payload 数据

扩展问题：

  • 校验和如何计算？（对整个包按 16 位为单位求反码和）
  • ICMP 是否保证可靠性？（不保证）

5. ICMP 包是怎么到目标地址的？（答：通过 IP 路由转发）

标准答案：

  • 包由本地路由表决定下一跳；
  • 发送到默认网关（如目标不在同一子网）；
  • 路由器逐跳转发，直到到达目标地址。

扩展问题：

  • Traceroute 的原理？（逐步增加 TTL，看每跳返回的 ICMP Time Exceeded）

6. 如何判断 IP 地址是否在黑名单？（答：可用 set、位图、Trie）

标准答案：

  • 小量 IP 可用 std::set 或 unordered_set。
  • 大量连续 IP 可用位图（bitmap）或段树。
  • 如果是 CIDR 段，可用 Trie 或前缀树结构。

扩展问题：

  • 怎么存储 10.0.0.0/8 ？（前缀树）
  • 位图是否支持 IPv6？（空间开销过大）

7. 多线程常用的锁有哪些？（答：互斥锁、读写锁、递归锁）

标准答案：

  • mutex：最常用的互斥锁。
  • recursive_mutex：支持同一线程重复加锁。
  • shared_mutex：支持读写锁（C++17）。

扩展问题：

  • 自旋锁和互斥锁的区别？（忙等 vs 阻塞）
  • 条件变量是锁吗？（不是，用于线程同步）

8. 协程写 channel，需要加锁吗？（答：不需要）

标准答案： 在同一个线程中的协程共享 channel 时，无需加锁。 原因：协程在同一个线程调度，不存在并发访问问题。

扩展问题：

  • 如果多线程访问同一个 channel 呢？（需要加锁或使用线程安全的 channel 实现）

9. 网关如何支持高并发？（答：epoll/iouring + 线程池）

标准答案：

  • 使用 epoll、IOCP、io_uring 等高效 IO 多路复用；
  • 搭配线程池处理请求；
  • 优化内存分配，减少上下文切换。

扩展问题：

  • 为什么不用一个线程一个连接？（上下文切换开销大）
  • 什么是 io_uring？（Linux 新一代异步 IO 框架）

10. select/poll 能实现高并发吗？（答：可以，但效率低于 epoll）

标准答案：

  • select/poll 都是 IO 多路复用机制；

  • 支持高并发，但效率低：

    • select 有最大 fd 限制；
    • poll 每次都要遍历所有 fd；

  • epoll 更优，基于事件驱动，O(1) 复杂度。

扩展问题：

  • select 最多支持多少个 fd？（通常是 1024）

11. 线程池实现需要注意什么？（答：keep alive 时间）

标准答案：

  • 管理任务队列，避免阻塞；
  • 合理设置线程数与 keep alive 时间；
  • 避免线程泄露或资源竞争。

扩展问题：

  • 工作窃取机制？（work stealing）
  • 如何优雅退出线程池？（通知 + join）

12. 多核系统优化怎么做？（答：负载均衡 + 多路复用）

标准答案：

  • 使用多线程/多进程均匀利用 CPU；
  • 将不同连接或计算绑定到不同核心（CPU 亲和性）；
  • 使用 epoll/kqueue 实现 IO 多路复用。

扩展问题：

  • 如何避免 false sharing？（结构体成员填充对齐）

13. 多线程除了加锁还能用什么？（答：原子操作）

标准答案：

  • 使用 std::atomic 实现无锁编程；
  • 使用 CAS（Compare-And-Swap）处理并发冲突；
  • 使用 lock-free/ wait-free 数据结构提升性能。

扩展问题：

  • 原子操作和互斥锁的区别？（锁可能阻塞）
  • std::atomic<int>++ 是原子的吗？（是）

14. i++ 是原子操作吗？（答：不是，包含读-改-写三步）

标准答案： i++ 并不是原子操作，其背后是：

  1. 从内存读 i
  2. 在寄存器加一
  3. 写回内存

这三个步骤不是原子完成，存在线程安全问题。

扩展问题：

  • 如何让 i++ 成为原子？（使用 std::atomic<int>）

15. 在 64 位机器上，给 32 位变量赋值是原子的吗？（答：不是，或者取决于架构）

标准答案：

  • 对齐良好、硬件支持下，有可能是原子；
  • 但不能依赖实现，跨平台行为不一致；
  • 为保证原子性，使用 std::atomic<uint32_t>

扩展问题：

  • x86 上 32 位对齐变量通常是原子的，ARM 呢？（取决于架构）
  • 对比 volatile 和 atomic？（前者不能保证同步）