Feature #5: Fetch Most Recently Watched Titles
Explore how to design a data structure that tracks the n most recently watched titles by maintaining access order. Understand how combining a doubly linked list with a dictionary allows efficient updates and retrievals, ensuring constant time complexity. This lesson helps you implement a cache-like feature similar to Netflix's recent watch history.
We'll cover the following...
Description
We want to implement a feature so that the user can view the n titles that they’ve watched or accessed most recently. We need to come up with a data structure for this feature. Let’s break it down. If we think it through, we realize the following: i) This data structure should maintain titles in order of time since last access; ii) If the data structure is at its capacity, an insertion should replace the least recently accessed item.
Let’s say that a user has gone through the following titles:
We need to design a structure that takes the ID of our movies, adds them to our data structure, and fetches movie titles when accessed through their ID. We also need to consider the size of our data structure and maintain the least recently watched property.
Take a look at an illustration of this process:
Solution
A doubly linked list provides an ideal way of maintaining ordered elements. We can keep the most recently accessed item at the tail. But when a recently watched item is accessed again, we’ll move it to the tail of the linked list. This will require searching for an element in the linked list, which is expensive. To fix this, we can use dictionary to store the nodes of the linked list elements. ...