Design Movie Rental System

Design Movie Rental System

What is this problem about?

The Design Movie Rental System interview question asks you to build a platform that manages movie inventories across multiple shops. You need to support searching for the cheapest shops that have a specific movie available, renting a movie, dropping off a movie, and reporting the cheapest "rented" movies currently out. The system must handle potentially thousands of shops and movies, requiring highly efficient lookups and sorted results.

Why is this asked in interviews?

Flipkart frequently asks this "Hard" problem because it tests a candidate's ability to maintain multiple sorted views of the same data. It evaluations your skill in choosing the right combination of data structures (like Hash Maps and Trees) to balance the trade-offs between update speed and query speed. This coding problem is an excellent test of "Data Structure Composition"—using one structure to find data and another to keep it sorted.

Algorithmic pattern used

This problem uses the Ordered Set interview pattern and Hash Table design pattern. You need to maintain several structures:

1. A map from (shop, movie) to price for quick verification.
2. A map from movie to an OrderedSet of (price, shop) for searching available movies.
3. A single global OrderedSet of (price, shop, movie) to track all currently rented movies. Using a TreeSet or similar balanced BST allows for $O(\log N)$ updates and $O(K)$ retrieval of the top $K$ cheapest items.

Example explanation

Imagine two shops: Shop A and Shop B.

• search(Movie 1): Shop A has it for $5, Shop B has it for$2. The system returns Shop B then Shop A.
• rent(Shop B, Movie 1): Movie 1 is removed from Shop B's available list and added to the global "rented" list.
• report(): Shows the rented movies sorted by price. If Shop B's Movie 1 ($2) is the only one rented, it appears first.

Common mistakes candidates make

• Inefficient Search: Trying to iterate through all shops for every search query.
• Stale Data: Failing to remove a movie from the "available" set when it is moved to the "rented" set.
• Tie-breaking: Forgetting that when prices are equal, you must usually sort by shop ID or movie ID.
• Synchronization: Not realizing that rent and drop operations affect multiple data structures simultaneously.

Interview preparation tip

When a design problem involves "finding the cheapest" or "top K," always think of a Heap or an Ordered Set. If the data needs to be updated frequently (like renting and returning), an Ordered Set (Balanced BST) is better because it supports $O(\log N)$ deletions, whereas a standard Heap requires $O(N)$ to find and remove an arbitrary element.