We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Movie Rental System

Difficulty: Hard

Problem Description

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] = [shop_i, movie_i, price_i] indicates that there is a copy of movie movie_i at shop shop_i with a rental price of price_i. Each shop carries at most one copy of a movie movie_i. The system should support the following functions:

  • Search: Finds the cheapest 5 shops that have an unrented copy of a given movie.
  • 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 as a 2D list.

Key Insights

  • Efficiently track available and rented movies using data structures.
  • Use sorting or priority queues to manage the cheapest options.
  • Ensure operations on rentals and returns maintain correct state.

Space and Time Complexity

Time Complexity:

  • Search: O(log k + k) where k is the number of unrented copies (at most 5)
  • Rent: O(1)
  • Drop: O(1)
  • Report: O(log m + m) where m is the number of rented movies (at most 5)

Space Complexity: O(n + m) where n is the number of shops and m is the number of currently rented movies.

Solution

To solve this problem, we will use a combination of hash maps and priority queues (or sorted lists) to maintain the state of unrented and rented movies. The hash map will map each movie to its available shops and prices. For rented movies, we will maintain a priority queue that allows us to quickly retrieve the cheapest rented movies.

  1. Initialization: Create a hash map to store the available movies and their shops with prices. Also, create a hash map to track rented movies.

  2. Search: When searching for a movie, retrieve the list of shops for that movie and sort them by price and shop number. Return the top 5 results.

  3. Rent: When renting a movie, remove it from the available list and add it to the rented list.

  4. Drop: When dropping off a movie, add it back to the available list from the rented list.

  5. Report: Retrieve and sort the rented movies based on price, shop number, and movie ID, returning the top 5.

Code Solutions

class MovieRentingSystem:
    def __init__(self, n: int, entries: List[List[int]]):
        self.available = defaultdict(list)  # movie -> [(price, shop)]
        self.rented = []  # [(price, shop, movie)]
        self.rented_map = {}  # (shop, movie) -> price
        
        for shop, movie, price in entries:
            self.available[movie].append((price, shop))
        
        for movie in self.available:
            self.available[movie].sort()  # Sort by price primarily, shop secondarily

    def search(self, movie: int) -> List[int]:
        if movie not in self.available:
            return []
        # Get the cheapest 5 shops
        return [shop for price, shop in self.available[movie][:5]]

    def rent(self, shop: int, movie: int) -> None:
        price = next(price for price, s in self.available[movie] if s == shop)
        self.available[movie] = [(p, s) for p, s in self.available[movie] if s != shop]  # Remove from available
        self.rented_map[(shop, movie)] = price  # Track rented movie
        self.rented.append((price, shop, movie))  # Add to rented list
        self.rented.sort()  # Sort rented movies

    def drop(self, shop: int, movie: int) -> None:
        price = self.rented_map.pop((shop, movie))  # Get price and remove from rented
        self.available[movie].append((price, shop))  # Add back to available
        self.available[movie].sort()  # Sort again

    def report(self) -> List[List[int]]:
        # Get the cheapest 5 rented movies
        return [[shop, movie] for price, shop, movie in self.rented[:5]]
← Back to All Questions