滴滴 9 月 19 日笔试：选择题与消息主题积压清零

《面试题目》

1. 从一批尚未排序的读数里用快速选择找中位数，平均时间复杂度是多少？
2. UDP 协议提供的基本服务不包括哪一项？
3. 单核上采用非抢占式短作业优先（SJF）调度 5 份工单，执行顺序是什么？
4. 下面这个用静态计数器计数的 C++ 程序，运行结果是什么？
5. 解决死锁问题的几种方法中，哪一种可以使系统获得较好的资源利用率和系统吞吐量？
6. 接入层挂着 m 条消息主题，每轮只能指定一条主题做主消费（该主题清 p 条、其余各清 q 条，保证 p > q），最少需要多少轮才能让所有主题的积压都不高于 0？

《参考解析》

第 1 题：快速选择是 O(n)

快速选择只对划分后包含目标下标的那一侧继续递归，期望比较次数是 n + n/2 + n/4 + …，收敛到 O(n)，而不是快排的 O(n log n)。它在最坏情况下仍是 O(n²)（每次划分都极不均衡），要做到最坏 O(n) 需要用中位数的中位数做枢轴。答案选 O(n)。

第 2 题：UDP 不提供可靠交付与流量控制

UDP 只在 IP 之上加了端口复用和可选的校验和，发送前不需要建立连接，也不做确认、重传、拥塞控制与流量控制。所以”可靠交付和流量控制”不是它的服务，答案选这一项。

第 3 题：非抢占式 SJF 的执行顺序

t=0 只有 J1 到达，非抢占调度下必须让它跑完 8 个时间单位。到 t=8 时 J2、J3、J4、J5 都已进入就绪队列，按服务时间升序排：J3(1)、J5(2)、J4(3)、J2(3)。顺序是 J1 → J3 → J5 → J4 → J2。顺带一提，SJF 只保证平均等待时间最短，长作业可能被不断插队而饿死。

第 4 题：静态成员在整个类里只有一份

cnt 是 static，p、q 两次构造后 cnt = 2。p.dump(3) 走带参重载，输出 2 + 3 = 5；q.dump() 走无参重载，输出 2。两次输出连续打印就是这个结果。

第 5 题：死锁避免

死锁处理大致分四档：预防（破坏四个必要条件之一，限制最强、资源利用率最低）、避免（运行时动态判断安全性，如银行家算法）、检测与恢复（允许发生再解开）、忽略。题目问的是资源利用率和吞吐量较好的一档，对应死锁避免。

第 6 题：二分答案

设一共做 z 轮，第 i 条主题被指定做主消费 t(i) 轮，那么主题 i 总共被清掉 q·z + (p−q)·t(i) 条，要求 w(i) − q·z − (p−q)·t(i) ≤ 0。

• z 越大越容易满足，判定具有单调性，可以二分。
• 判定方式：先让所有主题都吃满顺带消费 q·z；仍有剩余的，这条主题还需要 ⌈(w(i) − q·z) / (p−q)⌉ 轮主消费。把所有主题的需求加起来不超过 z 即可行——总共只有 z 个主消费名额。
• 二分上下界：下界取 max⌈w(i)/p⌉（每轮都点积压最大那条的理想情形），上界取 max⌈w(i)/q⌉（完全不做主消费也一定够）。
• 复杂度 O(m·log X)。w、p、q 都可能到 10^9，中间乘积必须用 64 位整数。

以样例 p=5, q=2, w=[10,8,7] 为例，答案是 4：取 z=4 时顺带消费已清掉 8 条，只有第一条还差 2 条，补 1 轮主消费就够；取 z=3 时三条分别还差 4、2、1 条，合计需要 2+1+1=4 轮主消费，超过 3 轮名额。

有人会想每轮直接点当前积压最大的主题。这个贪心在小规模穷举验证里恰好都能得到最优值，但它的正确性并不显然，考场上用二分答案更稳妥、也更好证明。另外别忘了向上取整。