7-18-腾讯-TEG-云架构平台-后台开发-一面

算法题

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

#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;
}

简答题

---

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

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。

✅ 结果输出：

*p = 255

💡 教学点：

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

---

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

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)）

✅ 输出：

p = 0x81000000
p + 1 = 0x81000004

💡 教学点：

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

---

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

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]。

✅ 输出：

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

💡 教学点：

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

---

第四题：unique_ptr 所有权迁移

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 拥有资源。

✅ 输出：

0
1
RealServer destructed

💡 教学点：

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

---

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

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 正常行为。

✅ 正确写法：

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？（前者不能保证同步）