Pregunta de entrevista de 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.

Respuesta de la entrevista

Anónimo

24 mar 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.