Taro Logo

Design Movie Rental System

Hard
Flipkart logo
Flipkart
1 view
Topics:
ArraysDesign

You have a movie renting company consisting of n shops. You want to implement a renting system that supports searching for, booking, and returning movies. The system should also support generating a report of the currently rented movies.

Each movie is given as a 2D integer array entries where entries[i] = [shopi, moviei, pricei] indicates that there is a copy of movie moviei at shop shopi with a rental price of pricei. Each shop carries at most one copy of a movie moviei.

The system should support the following functions:

  • Search: Finds the cheapest 5 shops that have an unrented copy of a given movie. The shops should be sorted by price in ascending order, and in case of a tie, the one with the smaller shopi should appear first. If there are less than 5 matching shops, then all of them should be returned. If no shop has an unrented copy, then an empty list should be returned.
  • Rent: Rents an unrented copy of a given movie from a given shop.
  • Drop: Drops off a previously rented copy of a given movie at a given shop.
  • Report: Returns the cheapest 5 rented movies (possibly of the same movie ID) as a 2D list res where res[j] = [shopj, moviej] describes that the jth cheapest rented movie moviej was rented from the shop shopj. The movies in res should be sorted by price in ascending order, and in case of a tie, the one with the smaller shopj should appear first, and if there is still tie, the one with the smaller moviej should appear first. If there are fewer than 5 rented movies, then all of them should be returned. If no movies are currently being rented, then an empty list should be returned.

Implement the MovieRentingSystem class:

  • MovieRentingSystem(int n, int[][] entries) Initializes the MovieRentingSystem object with n shops and the movies in entries.
  • List<Integer> search(int movie) Returns a list of shops that have an unrented copy of the given movie as described above.
  • void rent(int shop, int movie) Rents the given movie from the given shop.
  • void drop(int shop, int movie) Drops off a previously rented movie at the given shop.
  • List<List<Integer>> report() Returns a list of cheapest rented movies as described above.

Note: The test cases will be generated such that rent will only be called if the shop has an unrented copy of the movie, and drop will only be called if the shop had previously rented out the movie.

Example 1:

Input
["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
[[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]
Output
[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]

Explanation
MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
movieRentingSystem.search(1);  // return [1, 0, 2], Movies of ID 1 are unrented at shops 1, 0, and 2. Shop 1 is cheapest; shop 0 and 2 are the same price, so order by shop number.
movieRentingSystem.rent(0, 1); // Rent movie 1 from shop 0. Unrented movies at shop 0 are now [2,3].
movieRentingSystem.rent(1, 2); // Rent movie 2 from shop 1. Unrented movies at shop 1 are now [1].
movieRentingSystem.report();   // return [[0, 1], [1, 2]]. Movie 1 from shop 0 is cheapest, followed by movie 2 from shop 1.
movieRentingSystem.drop(1, 2); // Drop off movie 2 at shop 1. Unrented movies at shop 1 are now [1,2].
movieRentingSystem.search(2);  // return [0, 1]. Movies of ID 2 are unrented at shops 0 and 1. Shop 0 is cheapest, followed by shop 1.

Constraints:

  • 1 <= n <= 3 * 105
  • 1 <= entries.length <= 105
  • 0 <= shopi < n
  • 1 <= moviei, pricei <= 104
  • Each shop carries at most one copy of a movie moviei.
  • At most 105 calls in total will be made to search, rent, drop and report.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the constraints on the number of shops, movies, and prices? What is the maximum number of movies a shop can have?
  2. Can a movie have the same price in different shops? How should this be handled?
  3. If no movies are currently rented, what should the `report` method return? An empty list, or is there a specific sentinel value?
  4. Are the movie IDs unique across all shops, or could different shops have movies with the same ID? What are valid movie ID ranges?
  5. Are there any constraints on the magnitude of prices? Can prices be floating-point numbers, or are they strictly integers?

Brute Force Solution

Approach

The brute force approach to designing a movie rental system means we'll explore every possible action a user could take and check if it's valid. We will simulate all possible rental and return scenarios to ensure correctness. This involves trying everything until we find a solution that works.

Here's how the algorithm would work step-by-step:

  1. To add a movie, simply add it to our list of available movies.
  2. To add a customer, simply add them to our list of customers.
  3. When a customer wants to rent a movie, go through every movie we have and see if it matches what the customer wants and if it's available.
  4. If we find a matching, available movie, mark that movie as rented to that customer.
  5. When a customer returns a movie, go through all rentals to find the one associated with that customer and movie.
  6. Once found, mark that movie as available again.
  7. If the customer asks for a list of available movies, check the status of every movie we have and return those that are currently available.
  8. To find the most popular movies, we go through the entire history of rentals and count how many times each movie has been rented.

Code Implementation

class MovieRentalSystem:

    def __init__(self):
        self.available_movies = {}
        self.customers = {}
        self.rentals = []

    def add_movie(self, movie_id, title):
        self.available_movies[movie_id] = {
            'title': title,
            'available': True
        }

    def add_customer(self, customer_id, name):
        self.customers[customer_id] = {
            'name': name
        }

    def rent_movie(self, customer_id, movie_id):
        # Find the movie and check if it's available
        if movie_id in self.available_movies and \
           self.available_movies[movie_id]['available']:

            self.available_movies[movie_id]['available'] = False

            self.rentals.append({
                'customer_id': customer_id,
                'movie_id': movie_id
            })

            return True
        return False

    def return_movie(self, customer_id, movie_id):
        # Go through each rental and find the matching one to remove
        for rental in self.rentals:

            if rental['customer_id'] == customer_id and \
               rental['movie_id'] == movie_id:
                self.rentals.remove(rental)
                self.available_movies[movie_id]['available'] = True
                return True
        return False

    def list_available_movies(self):
        available_movie_list = []
        for movie_id, movie_details in self.available_movies.items():

            if movie_details['available']:
                available_movie_list.append({
                    'movie_id': movie_id,
                    'title': movie_details['title']
                })
        return available_movie_list

    def get_most_popular_movies(self):
        movie_rental_counts = {}
        # Count the number of times each movie has been rented
        for rental in self.rentals:

            movie_id = rental['movie_id']
            if movie_id in movie_rental_counts:
                movie_rental_counts[movie_id] += 1
            else:
                movie_rental_counts[movie_id] = 1

        sorted_movies = sorted(movie_rental_counts.items(), \
                               key=lambda item: item[1], reverse=True)
        return sorted_movies

Big(O) Analysis

Time Complexity
O(n*m) – Adding a movie or customer takes O(1) as it's a simple append operation. Renting a movie requires iterating through all m movies to find a match, taking O(m). Returning a movie necessitates searching through all rentals, which, in the worst case, could be proportional to n (number of customers) times m (number of movies), thus O(n*m). Listing available movies involves checking the availability of each of the m movies, resulting in O(m). Finding the most popular movies means iterating through the entire rental history of n*m potential rentals giving us O(n*m) for that operation. So we have a mixture of O(1), O(m), and O(n*m) operations but O(n*m) is the biggest scaling factor.
Space Complexity
O(N + M + R) – The space complexity is determined by the size of the data structures used to store the movies, customers, and rental history. The list of available movies takes O(N) space, where N is the number of movies. The list of customers takes O(M) space, where M is the number of customers. The rental history, which stores all rental transactions, could grow to O(R), where R is the total number of rentals. Therefore, the overall space complexity is O(N + M + R).

Optimal Solution

Approach

The best way to design a movie rental system is to organize information so we can quickly find movies, customers, and rentals. We use special containers to store and quickly retrieve these things, so we don't have to search through everything every time.

Here's how the algorithm would work step-by-step:

  1. Keep track of all the movies in a special container that lets us quickly find a movie by its name or ID.
  2. Store customer information in a similar container, allowing us to quickly find a customer by their ID.
  3. For each movie, keep a list of its available copies and their prices. Think of this as a small inventory for each movie.
  4. When a customer rents a movie, record the details of the rental (movie, customer, rental date, return date) in a rental log.
  5. When a movie is returned, update the rental log to mark it as returned, and make the movie copy available again.
  6. To find the most popular movies, keep track of how many times each movie has been rented. A sorted container helps to quickly identify the most rented movies.
  7. To find movies rented by a specific customer, use the rental log to find all rentals associated with that customer's ID.
  8. By using these organized containers, we can quickly perform common operations like renting a movie, returning a movie, searching for movies, and checking rental history without having to go through tons of information.

Code Implementation

class MovieRentalSystem:
    def __init__(self):
        self.movies = {}
        self.customers = {}
        self.movie_inventories = {}
        self.rental_log = []
        self.movie_rental_counts = {}

    def add_movie(self, movie_id, movie_name, number_of_copies, rental_price):
        self.movies[movie_id] = movie_name
        self.movie_inventories[movie_id] = {
            "copies_available": number_of_copies,
            "rental_price": rental_price
        }
        self.movie_rental_counts[movie_id] = 0

    def add_customer(self, customer_id, customer_name):
        self.customers[customer_id] = customer_name

    def rent_movie(self, customer_id, movie_id, rental_date, return_date):
        # Check if customer, movie and copies are available
        if customer_id in self.customers and movie_id in self.movies and self.movie_inventories[movie_id]["copies_available"] > 0:
            self.rental_log.append({
                "customer_id": customer_id,
                "movie_id": movie_id,
                "rental_date": rental_date,
                "return_date": return_date,
                "returned": False
            })

            self.movie_inventories[movie_id]["copies_available"] -= 1
            self.movie_rental_counts[movie_id] += 1
            return True
        else:
            return False

    def return_movie(self, customer_id, movie_id):
        # Find the rental record and mark movie as returned.
        for rental in self.rental_log:
            if rental["customer_id"] == customer_id and rental["movie_id"] == movie_id and not rental["returned"]:
                rental["returned"] = True
                self.movie_inventories[movie_id]["copies_available"] += 1
                return True
        return False

    def get_customer_rentals(self, customer_id):
        # Gather all rental records for a specific customer
        rentals = []
        for rental in self.rental_log:
            if rental["customer_id"] == customer_id:
                rentals.append(rental)
        return rentals

    def get_most_popular_movies(self, number_of_movies):
        # Sort movies by rental count in descending order.
        sorted_movies = sorted(self.movie_rental_counts.items(), key=lambda item: item[1], reverse=True)
        return sorted_movies[:number_of_movies]

Big(O) Analysis

Time Complexity
O(n) – The operations in this movie rental system design primarily involve accessing and updating data in hash maps and sorted containers. Accessing movie information by ID or name, customer information by ID, and updating rental logs all leverage hash maps, resulting in O(1) average time complexity for these operations, where n is the number of movies, customers, or rentals. Finding the most popular movies from the sorted container of rental counts would take O(n) to iterate through the entire container in the worst case. Therefore, the overall time complexity is dominated by the operations that take O(n) such as iterating through the sorted container of rentals, resulting in a time complexity of O(n).
Space Complexity
O(N + M + R) – The space complexity is determined by the storage of movies, customers, and rentals. We store movie information in a data structure that can grow linearly with the number of movies, N. Customer information is similarly stored in a structure that grows with the number of customers, M. The rental log stores rental details, growing linearly with the number of rentals, R. Therefore, the auxiliary space used is proportional to the sum of movies, customers and rentals.

Edge Cases

CaseHow to Handle
Null or empty input arrays (prices, movies, shops, rented)Throw IllegalArgumentException or return appropriate default value like empty list or boolean for failure depending on the method.
Arrays of different lengths for prices, movies, and shopsThrow IllegalArgumentException as these arrays should be the same length based on the problem statement.
Movie already rented from the same shop (rent called twice)Return false or throw exception to indicate rental failure or invalid operation since it's already rented.
Movie not rented from the shop when drop is calledReturn false or throw exception to indicate drop failure or invalid operation because the movie was never rented from there.
Very large number of shops or movies causing memory issuesUse appropriate data structures like HashMaps and HashSets to reduce space complexity and consider using disk-based storage for very large datasets if memory is still a constraint.
Large number of movies rented and report is called which could lead to time limit exceedingUse a priority queue or sorted set to efficiently keep track of the cheapest movies for the report functionality to meet the time constraints.
Prices with duplicate values during search or reportThe sorting criteria will correctly handle duplicate prices by sorting by shop and then by movie ID.
Integer overflow when calculating total price (if applicable, given the constraints)Use long data type for price calculations if the problem constraints allow prices to be large enough to cause integer overflow.