Student Enrollment Interview Question

Introduction

This is another interview question which I find interesting. The problem statement goes as follow:

“Its the beginning of a new academic year and I am a teacher of Data Structures and Algorithm subject. Many students with distinct roll numbers want to enroll for the class. After sometime few students wanted to opt out from the enrollment because they found some other subject much more interesting. Now, I also have a teaching assistant who can ask me the roll number of a student who is still enrolled into my class. It is not mandatory to tell him a different roll number every time. I can tell the same roll number to the TA each time he asks me for a roll number provided the student with the roll number is still enrolled in my class.”

I want to provide a solution such that I can add a new student roll number on enrollment, remove the student’s roll number once he opts out and perform the lookup for my TA in constant time. All the operations must be performed in O(1) time.

Definitely space is not a constraint and we need to define a data structure which can do this in the given time constraint.

Approach for Student Enrollment Interview Question

Whatever data structure we think of, two of the three operations can be done in O(1). We have to compromise somewhere. Let us see the following solutions:

Using an array

Assume that I use an array with sufficient size. It provides me indexed access and I will be able to access elements at any index in O(1) time.

  • Adding a student and his roll number : This can be done in O(1) time, I go to the index (which is equal to the roll number and insert this record) in O(1) time.
  • Removing a student given a roll number : This can be done in O(1) time because I know the roll number and I can reach that index in O(1) time and set the value to -1 or something
  • Accessing a roll number which is still enrolled : This can only be done if we start from the beginning and travel until we get an array index with value greater that -1. This is O(N) operation in worst case.
A working solution

We cannot fix this if we use a simple data structure, we need to use some of our learning from the Data Structures tutorial and use it here.
Consider the above array attached to a doubly linked list where each index with a value greater than zero is attached to a node of the linked list. For visualization here is an image:

In the image, the array index (0, 4, 6 and 9) contains null, that means the students with these roll numbers are not enrolled. That is why the linked list doesn’t contain these nodes. The other cells of the array point to the corresponding linked list nodes.
Student Enrollment - Interview Question
Let us consider the below operations:

  • Adding a student with roll number 9 : We can create a linked list node with the roll number 9 and add it to the beginning or end of the linked list in O(1) time. At the same time we can access the 9th index of the array and point it to the newly created node.
  • Removing the student with roll number 5 :We can access the 5th index of the array and get the pointer to the node which stores the roll number 5 and remove the node in O(1) time. Then update the value in the array to null.
  • Lookup for an enrolled student : Just access the first node of the linked list and return it.

Source Code for Student Enrollment Interview Question

The complete code can be downloaded from the github repository for techieme. But here is a method wise explanation.

Enroll Method

The above meethod helps in enrolling students and registering them in our fancy data structure. See that we create a new LinkedNode and add it to the linked list. and also populate the array at the same time. All in O(1) time.

Optout method

The above method deletes the node from the linked list and marks the corresponding index of the array as null.

Lookup method

Here we just fetch the head of the linked list and return the data from there.

Conclusion

This definitely was a fancy problem and we learnt to wisely use data structures. Definitely there are many combinations of data structures which can solve this problem with the given restrictions. Please feel free to add your solution in the comments.

Don’t forget to subscribe to TechieMe to get updates on latest posts.