Count Cross-Group Employee Pairs

Q: Count Cross-Group Employee Pairs

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

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Count Cross-Group Employee Pairs

Quick Overview

Comments (0)