Interview Experience | Search Infra / Backend | π₯π₯ | Google
2026 (Oct) Software Engineer, Infrastructure, Search Platforms @ Google β Mountain View, CA β Onsite β 1 round | π Neutral | Medium
Only remember this one round, C++.
Onsite β Coding
Coding was an lc886 variant: n index shards, plus pairs meaning those two shards can't be in the same cell. Split them into two cells, return -1 if impossible. Then inside each cell pair shards onto machines, each shard has a qps, minimize the qps of the busiest machine.
Asked about an odd count; interviewer said the extra one gets its own machine. Asked if the graph is connected; assume connected for now.
BFS coloring, an edge with the same color on both ends returns -1. First version only checked visited and never compared colors, so three mutually conflicting shards didn't error. Fixed it. Pairing: sort each cell by qps, smallest with largest, take the max pair sum, compare with the lone machine. Interviewer asked why pairing ends is right; gave an exchange argument, pretty roundabout. Interviewer then gave a small case to check by hand: cell A has qps 1, 4, 6, 9, so pairing 1+9 and 4+6 gives 10, while 1+4 and 6+9 gives 15. That made the argument easier to say out loud. Complexity: BFS is O(n + m), sorting is O(n log n). He asked whether the conflict list could have duplicate pairs or a shard conflicting with itself. Said duplicates are fine for BFS, but a self-conflict should return -1 right away, so I added that check before building the graph.
Follow-up: graph not connected, each component can be flipped as a whole, so there are many ways to split into two cells and you want the global best. Said too many components to brute force, tried to go toward a dp over component sizes, but with a min-max objective I couldn't figure out the state. Time ran out.