In an interview it was ask from me that You are given two objects, Student and Course, and there exist a many to many relation between them. One student can be enrolled for more than one course and there can be many students enrolled for a single course. Design an effective data structure to store such data keeping in mind that the time complexity for search should be optimum. A search can be for the list of students enrolled for a single course, or for the list of courses a single student is enrolled.
在一次采访中,有人问我,你有两个对象,即学生和课程,他们之间存在着多对多的关系。一名学生可以报名参加一门以上的课程,可以有很多学生报名参加一门课程。设计一个有效的数据结构来存储这些数据,记住搜索的时间复杂度应该是最佳的。搜索可以是针对单个课程注册的学生列表,也可以是单个学生注册的课程列表。
i have replied that we could use two HashMaps, one for StudentName -> Course List Lookup and one for Course Name -> Student List Lookup. Searching will be in O(1) for both cases.
我已经回复说我们可以使用两个HashMaps,一个用于StudentName - >课程列表查找,一个用于课程名称 - >学生列表查找。对于这两种情况,搜索将在O(1)中。
Drawbacks: You use a lot of memory and you need to do bookkeeping if the courses of a student change (you have to update the entry in the Course Name Map). But this was not the question and searching cannot be better than O(1) I guess.
缺点:如果学生的课程发生变化(您必须更新课程名称图中的条目),您需要使用大量内存并且需要进行簿记。但这不是问题,搜索不能比O(1)更好。
Can you please advise what would be the best data structure for this please
请问你能告诉我最好的数据结构
1 个解决方案
#1
If you don't need range lookups (e. g. "return all courses visited by students with name started on "B"), provided data structure is ideal. The only thing can be improved is replacing List by HashSet in order to make update/remove operate also in guaranteed O(1).
如果你不需要范围查找(例如“返回名字以”B“开头的学生访问的所有课程),那么提供的数据结构是理想的。唯一可以改进的是用HashSet替换List以便进行更新/删除也在保证O(1)中运作。
Map<Student, Set<Course>> studentsToCources; // HashMap, HashSet
Map<Course, Set<Student>> coursesToStudents; // HashMap, HashSet
For sure, these maps must be encapsulated in some class which duty is perform operations on both maps transparently to caller.
当然,这些映射必须封装在某个类中,其中任务在两个映射上对调用者透明地执行操作。
#1
If you don't need range lookups (e. g. "return all courses visited by students with name started on "B"), provided data structure is ideal. The only thing can be improved is replacing List by HashSet in order to make update/remove operate also in guaranteed O(1).
如果你不需要范围查找(例如“返回名字以”B“开头的学生访问的所有课程),那么提供的数据结构是理想的。唯一可以改进的是用HashSet替换List以便进行更新/删除也在保证O(1)中运作。
Map<Student, Set<Course>> studentsToCources; // HashMap, HashSet
Map<Course, Set<Student>> coursesToStudents; // HashMap, HashSet
For sure, these maps must be encapsulated in some class which duty is perform operations on both maps transparently to caller.
当然,这些映射必须封装在某个类中,其中任务在两个映射上对调用者透明地执行操作。