Get the Groups

Reported in interviews at Citadel

Problem statement

As new students arrive at college, each receives a unique ID number from 1 to n. Initially no two students know each other, so each student forms their own group of friends. As the semester progresses, friendships form. You are given q queries described by three parallel arrays queryType, student1, and student2, aligned by index.

For query i:

  • If queryType[i] == 'Friend', students student1[i] and student2[i] become friends, merging their two groups into one (friendship is transitive, so groups grow as friends of friends connect).
  • If queryType[i] == 'Total', report the sum of the sizes of student1[i]'s group and student2[i]'s group.

Return an array of integers containing the answers to the 'Total' queries, in the order they appear.

Implement:

def getTheGroups(n: int, queryType: list[str], student1: list[int], student2: list[int]) -> list[int]:

Constraints: $1 \le n \le 10^5$; $1 \le q \le 10^5$; $1 \le student1[i], student2[i] \le n$; queryType[i] is in {'Friend', 'Total'}.

Example: n = 4, queryType = ['Friend', 'Friend', 'Total'], student1 = [1, 2, 1], student2 = [2, 3, 4]. After 'Friend 1 2' and 'Friend 2 3' the groups are {1,2,3} (size 3) and {4} (size 1). The 'Total 1 4' query reports 3 + 1 = 4, so the function returns [4]. Note that student 3 is indirectly in student 1's circle through student 2.

Show hint

Groups here only ever grow; what kind of structure lets you ask which group a student is in quickly as groups merge?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems