Round 1
Questions: As new students begin to arrive at college, each receives a unique ID number, 1 to n. Initially, the students do not know one another, and each has a different circle of friends. As the semester progresses, other groups of friends begin to form randomly.
There will be three arrays, each aligned by an index. The first array will contain a query type which will be either Friend or Total. The next two arrays, students1 and students2, will each contain a student ID. If the query type is Friend, the two students become friends. If the query type is Total, report the sum of the sizes of each group of friends for the two students.
Example:
n = 4 queryType = ['Friend', 'Friend', 'Total'] student1 = [1, 2, 1] student2 = [2, 3, 4]
The queries are assembled, aligned by index:
| Index | queryType | student1 | student2 | |-------|-----------|----------|----------| | 0 | Friend | 1 | 2 | | 1 | Friend | 2 | 3 | | 2 | Total | 1 | 4 |
Students will start as discrete groups (1), (2), (3) and (4). Students 1 and 2 become friends with the first query, as well as students 2 and 3 in the second. The new groups are (1, 2), (2, 3) and (4) which simplifies to {1, 2, 3} and (4). In the third query, the number of friends for student 1 = 3 and student 4 = 1 for a Total = 4. Notice that the student is indirectly part of the circle of friends of student 1.
def getTheGroups(n: int, queryType: List[str], student1: List[int], student2: List[int]) -> List[int]:
Candidate's Approach
My approach was to create an array of sets and to union any matching sets. For example:
[(1, 2)] and [(2, 3)] become [(1, 2, 3)]. Then return the number of friend groups by counting set lengths in the array. Another approach I was thinking was to append instead of union sets to save space.
Interviewer's Feedback
No feedback provided.