Quick Overview

This question evaluates understanding of graph connectivity and component aggregation (often involving disjoint-set concepts) along with combinatorial counting to compute cross-group pairs.

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.

Overview: 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.

Hints

  1. Clarify edge cases before coding.
  2. Keep the return value deterministic.

Count Cross-Group Employee Pairs

mediumSnapchatBackend Engineer

Return the number of unordered employee pairs whose members are in different union-find groups.

View full question (all parts)

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.

Examples

Example 1
Input
(5, [[0,1],[0,2],[3,4]])
Output
6
Notes
Two groups of sizes 3 and 2 produce 6 pairs.
Example 2
Input
(4, [])
Output
6
Notes
All employees isolated produce C(4,2) pairs.

Constraints

  • •Inputs are Python literals matching the function signature.
  • •Return a deterministic exact-match value.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Sample call
solution(5, [[0,1],[0,2],[3,4]])
Language
Case 1
Input
(5, [[0,1],[0,2],[3,4]])
Expected
6
Case 2
Input
(4, [])
Expected
6

Browse More Questions