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