Waymo Software Engineer interview experience

I was asked to populate an m by n grid with four tokens, making sure each token ended up on the same set of nodes and that each token region was connected across the grid. I remember immediately thinking about BFS for connectivity, but the “randomness” requirement threw me off and slowed me down—my initial approach didn’t really address how the exploration needed to behave under randomness.

Eventually, I landed on a strategy that involved running multiple BFS processes. The idea was to generate random seed points for where the token regions start, then BFS outward through neighboring cells