CODEWITHSUNDEEP
javadata-structures
ndsfd ddsfd
ndsfd ddsfd

Reputation: 235

storing the data in effective data structure so that search would be fast

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.

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.

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

Upvotes: 4

Views: 337

Answers (1)

Alex Salauyou
Alex Salauyou

Reputation: 14338

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).

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.

Upvotes: 1

Related Questions