Amazon Interview Question
Country: United States
If I understand it correctly, Given input is about stundent and the subjects which are attended by a particular student. And If focus is to get the query done faster, then a map can be created with string as Key and List as value. Now when any student-subject input is received, get the data using student as key and update the value list with the subject, do the same for subject as key and update the value list containing number of students attending it.
When query is done to find how many subjects are attended by a particular student named "ABC" , then get the corresponding list from map suing this student name as key and return the size of list.
First of all, what is the purpose of the data structure ?
- hankm2004 April 25, 2014If getting "no of student" and "no of subject" is the goal, we can use two maps, one with <stduent id, no_of_subject> pair as an element and the other one with <subject id, no_of_students> pair as an element.
However, if the goal is to retrieve students taking a specific subject or retrieve subjects that a specific student is taking, I would use two maps (or hashtable):
- stduent hash map: key => stduent id , value => list of subject ids(either linked list or std::vector)
- subject hash map: key=> subject id, value=> list of student ids(either linked list or std::vector)