华为 9 月 18 日笔试：主机灰度分批

《面试题目》

1. 有 p 台主机，每台带 d 个维度的标签，要把它们分成 b 个波次滚动升级，每个波次的容量怎样由 p 和 b 算出？
2. 填当前波次时，为什么优先选”能给本波次补进最多尚未出现标签”的主机？增量相同时取哪一台？
3. 已经入选过前面波次的主机，后面的波次还会被考虑吗？
4. 样例中 p=5、d=2、b=2，第 1 波为什么是 1 4，第 2 波为什么是 2 3 5？
5. 输出格式有什么要求？

《参考解析》

容量先把余数摊到末尾

q = p / b，r = p mod b，前 b - r 个波次容量为 q，最后 r 个波次容量为 q + 1。余数必须压在末尾，把它摊到前几波是最常见的错法。

增量只统计”本波次”已经出现过的标签

每个波次单独维护 d 个集合，记录该维度在本波次里已经出现过的标签，换波次时清空。对每台尚未入选的主机算增量：第 j 维的标签不在第 j 个集合里就记 1 分。取增量最大者，打平取 nid 更小者；入选后把它的各维标签写进本波次的集合，并标记为已用。

波次刚开始时集合是空的，所有剩余主机的增量都等于 d，所以每波第一台必定是当前剩余 nid 最小的那台。样例里第 1 波先取 1，随后主机 4 的标签组 b y 能一次补进两个新标签，增量最大，于是第 1 波是 {1, 4}；第 2 波对剩下的 2、3、5 重开集合，依次取到 2 3 5。

复杂度

一共要选 p 台，每选一台都扫描剩余主机、每台再看 d 个维度，时间 O(p²·d)；存每台的标签加上每波至多 p 个已出现标签，空间 O(p·d)。

容易写错的几处

• 增量按”全局已选”统计，而不是按本波次；
• 把 d 个维度混进同一个集合；
• 增量打平时取了大编号；
• 输出前忘记按 nid 升序排列。