Solving Job Interview Question using Trees

Recently, I had the following Job Interview Question where I was only asked to suggest an algorithm or data structure that satisfies the following:

In the following question space complexity is O(n+m) while n is the number of courses and m the number of total classes.

Init() initializing data structure O(1)

AddCourse (Course_id,Num_of_classes) Adding a new course whose id is Course_id and contains Num_of_classes classes where they are numbered 0,1,2... O(log(n)+Num_of_classes)

RemoveCourse(Course_id) Removing a course and all of its classes from the data structure O(log(n)+m)

WatchClass(Course_id,class_id,time) saving that the class with id class_id in course Course_id was watched for time minutes O(log(n)+time)

TimeViewed(Course_id,class_id) Return how much class with an id of class_id in course Course_id was watched O(log(n))

GetMostViewedClasses(num_of_classes,int courses[], int classes[]) Save top num_of_classes viewed classes in Desending order with the courses ids being matched and saved in courses. In case two courses shared the same number of views we prefer the one with bigger course id in cause of another equality we prefer the one with bigger class id. O(num_of_classes)


I know for sure (As I told the interviewer and he confirmed it) that the the solution for this one uses AVL trees which are a self balancing trees that allow Inserting/Finding/Deleting a node in O(log(n)) where n is the total number of nodes in the tree.

What I tried? I thought about Saving courses ids as nodes in an AVL tree and for each node I declare an array whose size is as the number of classes for that specific course. This solves all requirements except the last one. Any ideas on what I can do? Somehow I think this requires the use of linked lists.

General Note: Only Arrays/Trees/(doubly)linked Lists/Queues are allowed.



Read more here: https://stackoverflow.com/questions/64938296/solving-job-interview-question-using-trees

Content Attribution

This content was originally published by Smith at Recent Questions - Stack Overflow, and is syndicated here via their RSS feed. You can read the original post over there.

%d bloggers like this: