Pergunta de entrevista da empresa Google

Design and implement a solution for a dynamic connectivity problem where users can become friends or break connections, and queries determine if two users are still connected.

Resposta da entrevista

Sigiloso

24 de mar. de 2026

I modeled the problem using Union-Find (Disjoint Set Union) for efficient connectivity checks. I explained path compression and union by rank for optimization. For handling break operations, I discussed limitations of DSU and proposed approaches like offline processing or maintaining additional structures to track disconnections. I also covered edge cases such as isolated nodes and multiple operations sequences.