拼多多服务端一面:C++ 死锁、手写优先队列与树的遍历
- 轮次
- 一面
- 时间
- 2026-10
- 来源
- 牛客网
《面试题目》
- 请做一下自我介绍和项目介绍,说说你的工作主要是什么、贡献是什么。
- 知道死锁吗?用你熟悉的语言(C++)写一个可能会死锁的代码,并解释一下为什么会出现死锁。
lock/mutex是哪个头文件里的?这个 mutex 是线程粒度的还是进程粒度的?- 上面那个死锁怎么解决?用代码表现一下。
- 写一个优先队列,实现 add、remove 和 poll,尽量降低时间复杂度。
- 求树的高度和非叶子节点的数目(第一遍用递归写)。
- 如果不使用递归,且要在一次循环遍历中同时计算这两个值,你会怎么做?
《参考解析》
死锁代码与成因:经典写法是两个线程以相反顺序申请同一对锁——
std::mutex m1, m2;
void t1() { std::lock_guard<std::mutex> a(m1); std::lock_guard<std::mutex> b(m2); }
void t2() { std::lock_guard<std::mutex> a(m2); std::lock_guard<std::mutex> b(m1); }
线程 1 拿到 m1 等 m2、线程 2 拿到 m2 等 m1,构成循环等待,谁也走不下去。这正好对应死锁的四个必要条件:互斥(锁本身)、请求并保持(持有一把再申请另一把)、不可剥夺(不能强行抢锁)、循环等待(申请顺序成环)。工程里更隐蔽的是”锁 + 条件变量”或”锁 + 回调”造成的死锁。
mutex 的粒度与头文件:std::mutex 在 <mutex> 里(std::lock_guard、std::unique_lock、std::lock 同头文件)。它是线程粒度的同步原语——同一进程内的多个线程互斥;跨进程要换 pthread_mutex 的进程共享属性、文件锁(flock/fcntl)、信号量或共享内存里的原子量。这道题的关键是别把”互斥锁”和”进程间同步”混为一谈。
怎么破死锁:三招最实用。① 固定加锁顺序:所有线程按同一地址顺序加锁(比如先 m1 后 m2),循环等待就不成立;② 一次性加锁:C++17 的 std::scoped_lock lk(m1, m2) 内部用 std::lock 的死锁避免算法,要么全拿到要么不持有;③ 用 try_lock 加超时回退,拿不到就释放已持有的锁重试。再往上还有减少锁粒度(分段锁、无锁队列)、避免在持锁期间做回调或 IO、以及用 std::atomic 替代简单计数。答的时候能指出”哪个条件被破坏了”比背方案更好。
优先队列的设计:底层用二叉堆(数组实现),add 是 push 后上浮,poll 是取堆顶后把末尾元素放上来下沉,都是 O(log n)。难点在 remove:如果只给值,要先找到位置——两种做法,一是额外维护 unordered_map<值, 下标> 并同步更新(支持 O(log n) 删除 + O(1) 定位),二是”懒惰删除”(删除时只打标记,poll 时跳过失效元素),实现简单但有内存增长和均摊不确定性。手写时注意 remove 之后要按新值与父节点比较决定上浮还是下沉,别只写一种。面试里可以主动说清”是否允许重复元素""是否要求稳定”这两个前提,再定实现。
树高与非叶子节点数:递归版本很直白——height = 1 + max(h(left), h(right)),空树为 0;非叶子节点就是左右孩子至少有一个非空的节点数。要求一趟遍历且不用递归,就用队列做层序(BFS):队列里存 (节点, 深度) 或按层计数,每弹出一个节点就更新最大深度、判断是否非叶子(有任一孩子就计数)、并把孩子入队。也可以用一个显式栈做后序 DFS,用 pair<节点, 是否已访问> 避免重复,效果一样。两者复杂度都是 O(n) 时间、O(宽度) 或 O(高度) 空间。讲的时候补一句取舍:BFS 的空间跟树的最大宽度相关,深而窄的树用 BFS 更省,宽而浅的树用 DFS 更省。
项目叙述的复盘:作者自己提到项目介绍”有点混乱”,这类题其实是可准备度最高的——固定成”业务背景 → 我的职责 → 技术难点 → 结果数据 → 复盘”五段,每段控制在 30 秒,提前录音练两遍,现场就不会散。