Skip to main content

Oracle

Oracle OA-8 2024

Problem Description

As new students begin to arrive at college, each receives a unique ID number from 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:

  1. queryType: Contains a query type which will be either "Friend" or "Total".
  2. students1: Contains a student ID.
  3. students2: Contains 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:

For (n = 4):

queryType = ['Friend', 'Friend', 'Total']  
student1 = [1, 2, 1]  
student2 = [2, 3, 4]

The queries are assembled, aligned by index:

Index                query Type      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}.
  1. Students 1 and 2 become friends with the first query, resulting in the groups:
    • {1, 2} and {3}, {4}.
  2. Students 2 and 3 become friends with the second query, resulting in the groups:
    • {1, 2, 3} and {4}.

In the third query, the number of friends for student 1 is 3 and for student 4 is 1, resulting in a Total of 4.

Notice that student 3 is indirectly part of the circle of friends of student 1 because of student 2.

Function Description:

Complete the function getTheGroups in the editor below.

getTheGroups has the following parameters:

  • int n: the number of students
  • string queryType[q]: an array of query types
  • int student1[q]: an array of student integer IDs
  • int student2[q]: an array of student integer IDs

Constraints:

  • (1 <= n <= 10^5)
  • (1 <= q <= 10^5)
  • (1 <= students1[i], students2[i] < n)
  • queryTypes[i] are in the set {'Friend', 'Total'}

Input Format for Custom Testing:

Sample Case 0:

Sample Input:

STDIN                         Function
3                           → n = 3
2                           → queryType[] size q = 2
Friend                      → query = ['Friend','Total']
Total
2                           → students1[] size q = 2
1                           → students1 = [1, 2]
2
2                           → students2[] size q = 2
2                           → students2 = [2, 3]
3

Sample Output:

3

Explanation:

There are (n = 3) students labeled with the IDs {1, 2, 3}. Perform the following (q = 2) queries:

  1. First, students 1 and 2 become friends.
  2. The second query asks for the total size of the friend groups for students 1 and 3, which sums to 3.