Storing data in an efficient data structure for quick search

Question

In the interview I was asked that you were given two subjects: “Student and course”, and there are many, many relationships between them. One student may be enrolled in several courses, and there may be many students enrolled in the same course. Create an effective data structure for storing such data, bearing in mind that the time complexity of the search should be optimal. The search can be for a list of students enrolled in one course, or for a list of courses in which one student is registered.

I replied that we could use two HashMaps, one for StudentName → View a list of courses and one for a course name → Search for a list of students. The search will be in O (1) for both cases.

Disadvantages: you use a lot of memory, and you need to keep accounting if the student’s courses change (you need to update the record on the course name map). But this is not a question, and the search could not be better than O (1). I suppose.

Could you please advise what would be the best data structure for this.

Answer 1

If you do not need a search range (for example, "to return all the courses, students attending with a name beginning with" B "), provided that the data structure is perfect. The only thing that could be improved is the replacement Listto HashSetmake update / removal work also in guaranteed O (1).

Map<Student, Set<Course>> studentsToCources;  // HashMap, HashSet
Map<Course, Set<Student>> coursesToStudents;  // HashMap, HashSet

, - , .