Count Cross-Group Employee Pairs
Company: Snapchat
Role: Backend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given `n` employees labeled from `0` to `n - 1` and a list of relationships `relations`, where each pair `[a, b]` means employees `a` and `b` belong to the same group. Group membership is transitive, so if `[0, 1]` and `[0, 2]` are present, then `0`, `1`, and `2` are all in one group.
Your task is to count how many unordered pairs of employees `(i, j)` can be formed such that `i` and `j` come from different groups.
Example:
- `n = 5`
- `relations = [[0, 1], [0, 2], [3, 4]]`
This creates two groups: `{0, 1, 2}` and `{3, 4}`.
The valid cross-group pairs are:
- `(0, 3)`, `(0, 4)`
- `(1, 3)`, `(1, 4)`
- `(2, 3)`, `(2, 4)`
So the answer is `6`.
Return the total number of valid pairs.
Quick Answer: This question evaluates understanding of graph connectivity and component aggregation (often involving disjoint-set concepts) along with combinatorial counting to compute cross-group pairs.
Return the number of unordered employee pairs whose members are in different union-find groups.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (5, [[0,1],[0,2],[3,4]])
Expected Output: 6
Explanation: Two groups of sizes 3 and 2 produce 6 pairs.
Input: (4, [])
Expected Output: 6
Explanation: All employees isolated produce C(4,2) pairs.
Input: (3, [[0,1],[1,2]])
Expected Output: 0
Explanation: One group means no cross-group pairs.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.