A strong answer
Rerunning a graph search for every question costs O(V + E) each time, which is hopeless with a stream of edges and questions. Friendship groups only merge, which is exactly the case union-find is built for.
Keep a parent array, one entry per user, where each group is a tree and its root names the group. A new friendship is union(a, b): find both roots and, if they differ, point one at the other. A question is find(a) == find(b). With union by size and path compression, each operation costs O(α(n)) amortized, effectively constant, and memory is one or two integers per user.
Group sizes come almost for free: keep a size per root and add sizes on each successful union. The number of groups starts at the number of users and drops by one on every successful union. String ids are mapped to integers with a hash map as users first appear, or the union-find is keyed by dictionary.
The limit is deletion. Union-find can't split a group, so if friendships can be removed, options are: rebuild periodically from the current edge list; process an offline sequence backwards so deletions become additions; or use a fully dynamic connectivity structure, which is far more complex. It also can't answer how two users are connected; for that, keep the graph and search it when needed.
What the interviewer is listening for
- Recognizing "groups only merge" as the signal for union-find.
- Union by size and path compression, and the nearly constant cost.
- Clear limits: no deletions, no paths, and how to work around them.
Common mistakes
- Running BFS or DFS per query.
- Relabeling every member of a group on each merge, which is O(n) per union.
- Claiming union-find supports removing an edge.