面经 | Search Infra / 后端 | 🔥🔥 | Google
2026(10月) Software Engineer, Infrastructure, Search Platforms @ Google | Mountain View, CA · Onsite · 1 轮 | 😐 Neutral | Medium
只记得这一轮，C++。
Onsite — Coding
coding 是 lc886 变种：n 个 index shard，给一些 pair 表示这两个 shard 不能放在同一个 cell，要分到两个 cell，分不了返回 -1。分完之后每个 cell 里 shard 两两配对放一台机器，每个 shard 有 qps，求最忙那台机器的 qps 最小是多少。
问了 shard 个数是奇数怎么办，面试官说多出来的单独一台。又问图是不是连通的，说先当连通。
BFS 染色，冲突边两头颜色一样就返回 -1。第一版只看了 visited，没比颜色，三个 shard 互相冲突的例子跑出来没报错，改了。配对是每个 cell 按 qps 排序，最小配最大，取 pair 和的最大值，再和单独那台比。面试官问为什么首尾配是对的，讲了交换论证，讲得比较绕。面试官给了个小例子让手算：A 里 qps 是 1、4、6、9，1+9、4+6 是 10，1+4、6+9 是 15，这样一比就好讲了。复杂度 BFS O(n + m)，排序 O(n log n)。又问冲突列表里会不会有重复的 pair、或者 shard 跟自己冲突。重复的对 BFS 没影响，自己跟自己冲突要直接返回 -1，建图前补了这个判断。
followup：图不连通，每个连通块都可以整体翻过来，两个 cell 的分法有很多种，要整体最优。说了连通块多的话没法暴力枚举，想往按块大小做 dp 上靠，但目标是最大值最小，状态怎么设没想出来，到点了。