Process Restricted Friend Requests

Process Restricted Friend Requests

What is this problem about?

The Process Restricted Friend Requests problem gives you n people, a list of existing restrictions (pairs that cannot be in the same friend group), and a list of friend requests. For each request (u, v), determine if adding the friendship would violate any restriction (directly or transitively). This hard coding problem extends Union-Find with restriction checking. The union find and graph interview pattern is the core.

Why is this asked in interviews?

Google asks this because it tests whether candidates can check if a Union-Find merge would create a group containing any restricted pair. For each potential merge, verify that the resulting component would not contain both endpoints of any restriction.

Algorithmic pattern used

Union-Find with restriction validation per request. For each request (u, v): temporarily check if merging u and v would violate any restriction. For each restriction (a, b): if find(u)==find(a) and find(v)==find(b), or find(u)==find(b) and find(v)==find(a), then merging would put a and b in the same group → deny request. If no restriction is violated, union u and v and mark request as approved.

Example explanation

n=3, restrictions=[(0,1)], requests=[(0,2),(2,1)].

• Request (0,2): check restriction (0,1): find(0)=0, find(2)=2. find(0)=0 ≠ find(1)=1, and find(0)=0 ≠ find(1). No violation. Approve! Union 0 and 2.
• Request (2,1): find(2)=find(0)=0, find(1)=1. Check (0,1): find(0)=0=find(2), find(1)=1=find(1). Would put 0 and 1 in same group → Deny! Result: [true, false].

Common mistakes candidates make

• Not checking all restrictions for each request (only checking direct pair).
• Modifying Union-Find before checking all restrictions (must check, then merge).
• Not considering transitive restrictions (if 0-1 restricted and 0 is merged with 2, then 2-1 is also transitively restricted).
• Incorrect root comparison (must use find() not direct comparison).

Interview preparation tip

Process Restricted Friend Requests adds a validation step to standard Union-Find. The key: before each union, check ALL restrictions to ensure no restricted pair would end up in the same component. This O(R * restrictions) per request is acceptable for small inputs. For larger inputs, maintain component restriction sets. Practice "conditional Union-Find" problems where merges have preconditions.