美团 软件开发-C++ 二面

1. 自我介绍

2. 多态

答案：多态是指同一个接口在不同对象上表现出不同的行为。在 C++ 里，多态主要分成编译期多态和运行时多态。编译期多态一般是函数重载、模板；运行时多态主要依赖继承、虚函数、基类指针或引用。运行时多态的本质是动态绑定。也就是说，虽然表面上通过基类接口调用函数，但真正执行的是对象实际类型对应的实现。底层通常依赖虚函数表和虚表指针来完成。它的意义主要在于解耦，上层代码只依赖抽象接口，不依赖具体实现，扩展性会更好。

代码：

#include <iostream>
using namespace std;

class Base {
public:
    virtual void work() { cout << "Base work\n"; }
    virtual ~Base() = default;
};

class Derived : public Base {
public:
    void work() override { cout << "Derived work\n"; }
};

int main() {
    Base* p = new Derived();
    p->work();
    delete p;
    return 0;
}

3. 如果我有一堆正整数需要频繁的插入和删除并且要知道第几大的数应该用什么数据结构？为什么？

如果要求频繁插入、删除，还要支持“第 k 大”查询，那我会优先考虑 平衡二叉搜索树 + 子树大小维护，也可以理解成顺序统计树。原因是普通堆虽然能快速得到最大值或者最小值，但不擅长删除任意元素，也不适合查第 k 大。如果用平衡树，比如红黑树、AVL、Treap，每个节点再额外维护一份子树节点数，那么：插入是 O(logn)，删除是 O(logn)，查第 k 大也是 O(logn)。如果数据范围已知而且不大，也可以用树状数组或者线段树做离散化处理，这样同样能支持第 k 大查询。所以关键不只是“有序”，而是要支持动态更新和顺序统计，这时候顺序统计树会更合适。

4. 现在有四个连接请求，前面三个已经收到了需要把第四个拼起来要求要高并发，应该怎么做？

这种场景下核心点不是“拼接字符串”本身，而是 连接状态管理、并发模型、内存控制和超时清理。我会这样做：每个连接维护一个独立的上下文，里面保存当前已接收的数据块、长度信息、请求状态和最后活跃时间；网络层用 epoll 或者成熟事件库做事件驱动，不为每个连接直接开线程；收到数据后先写入连接缓冲区，再根据协议字段判断是否已经凑够完整请求；如果完整了，再投递到业务线程池处理；如果长时间没等到第四段，就做超时回收，避免连接状态一直占内存。如果并发量更高，还会考虑零拷贝缓冲区、环形缓冲区或者分段 buffer，减少重复拷贝。本质上这是一个典型的高并发半包/拆包处理问题。

5. 现在有一个很大的数需要得到相乘之后的结果，使用int类型肯定溢出，怎么做，思路以及时间复杂度？回答使用字符串模拟之后追问如果长度非常长呢？还可以怎么做？

答案：假设两个数长度分别是 n 和 m，那么时间复杂度是 O(nm)，空间复杂度是 O(n+m)。这也是最稳妥、最容易实现的方法。如果长度非常长，比如上万位、几十万位，那普通竖式乘法就会比较慢。这时候可以考虑更高效的算法：像 Karatsuba 可以把复杂度降到大约 O(n^1.58)；再往后还有 FFT/NTT 做多项式卷积，可以做到 O(nlogn) 量级。本质上大整数乘法可以转化成卷积问题，所以长度非常大时，FFT 思路会更有优势。工程上如果不是手写算法题，通常也会直接用成熟的大整数库。

代码：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string multiply(string a, string b) {
    if (a == "0" || b == "0") return "0";
    vector<int> res(a.size() + b.size(), 0);

    for (int i = (int)a.size() - 1; i >= 0; --i) {
        for (int j = (int)b.size() - 1; j >= 0; --j) {
            int mul = (a[i] - '0') * (b[j] - '0');
            int sum = mul + res[i + j + 1];
            res[i + j + 1] = sum % 10;
            res[i + j] += sum / 10;
        }
    }

    string ans;
    int i = 0;
    while (i < res.size() && res[i] == 0) ++i;
    while (i < res.size()) ans.push_back(res[i++] + '0');
    return ans;
}

int main() {
    cout << multiply("123456789", "987654321") <<