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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Design Movie Rental System

Number: 2023

Difficulty: Hard

Paid? No

Companies: Flipkart

Problem Description

Design a movie rental system for n shops where each shop holds at most one copy of a movie. You must support four operations:

  1. Search – Given a movie id, return the cheapest 5 shops (sorted by price, then shop id) that have an unrented copy.
  2. Rent – Rent an unrented copy of a movie from a given shop.
  3. Drop – Return a previously rented movie to its shop.
  4. Report – Return the cheapest 5 currently rented movies (sorted by price, then shop id, then movie id).

Key Insights

  • We need to maintain two views of the data: one sorted by movie (for available copies) and another global view (for rented movies).
  • For each movie id, use an ordered data structure (balanced BST, TreeSet, or sorted list with binary search) to quickly extract the cheapest unrented shops.
  • Use another global ordered data structure for all rented movies, sorting by price, then shop, then movie.
  • Each operation (search, rent, drop, report) affects only one or both of these data structures via insertion or deletion.
  • Data structures like TreeSet in Java or std::set in C++ can offer O(log n) insertion/deletion and retrieval of the top k items.

Space and Time Complexity

Time Complexity:

  • Search, rent, drop, and report operations take O(log n) per insertion/deletion and O(k) for returning top k (with k ≤ 5) elements. Space Complexity:
  • O(m) where m is the number of entries, for storing available and rented movie records.

Solution

The solution uses two core data structures:

  1. A mapping from movie id to an ordered set (or sorted list) of available copies, each represented as a tuple (price, shop). This allows us to quickly search for the cheapest available shops for a given movie.
  2. A global ordered set (or sorted list) for rented movies, each represented as a tuple (price, shop, movie) to support the report operation in the required order. Additionally, a mapping (or hash table) from (shop, movie) pair to price helps to lookup prices for updates.

Operations are handled as follows:

  • Search(movie): Lookup the ordered set for the movie and return up to 5 shop ids from the beginning.
  • Rent(shop, movie): Remove the corresponding (price, shop) tuple from the movie’s available set, then insert (price, shop, movie) into the global rented set.
  • Drop(shop, movie): Remove the corresponding (price, shop, movie) tuple from the rented set and add back (price, shop) into the movie’s available set.
  • Report(): Return the first 5 entries (shop, movie) from the global rented set.

Code Solutions

# Python solution using bisect for sorted list management.
import bisect
from collections import defaultdict

class MovieRentingSystem:
    def __init__(self, n, entries):
        # Mapping from (shop, movie) to price.
        self.info = {}
        # For each movie id, a sorted list of (price, shop) for available copies.
        self.available = defaultdict(list)
        # A sorted list for global rented movies: (price, shop, movie).
        self.rented = []
        
        # Initialize available structure from entries.
        for shop, movie, price in entries:
            self.info[(shop, movie)] = price
            # Insert into available[movie] while keeping it sorted.
            bisect.insort(self.available[movie], (price, shop))
    
    def search(self, movie: int):
        # Return at most 5 shop ids from available copies sorted by (price, shop)
        result = []
        for price, shop in self.available.get(movie, []):
            result.append(shop)
            if len(result) == 5:
                break
        return result
    
    def rent(self, shop: int, movie: int):
        price = self.info[(shop, movie)]
        # Remove (price, shop) from available[movie] using binary search.
        lst = self.available[movie]
        index = bisect.bisect_left(lst, (price, shop))
        if index < len(lst) and lst[index] == (price, shop):
            lst.pop(index)
        # Add to rented list while keeping it sorted.
        bisect.insort(self.rented, (price, shop, movie))
    
    def drop(self, shop: int, movie: int):
        price = self.info[(shop, movie)]
        # Remove from rented list.
        index = bisect.bisect_left(self.rented, (price, shop, movie))
        if index < len(self.rented) and self.rented[index] == (price, shop, movie):
            self.rented.pop(index)
        # Add back to available[movie].
        bisect.insort(self.available[movie], (price, shop))
    
    def report(self):
        # Return at most 5 rented movies in order: [shop, movie]
        result = []
        for price, shop, movie in self.rented:
            result.append([shop, movie])
            if len(result) == 5:
                break
        return result

# Example usage:
# movieRentingSystem = MovieRentingSystem(3, [[0,1,5],[0,2,6],[0,3,7],[1,1,4],[1,2,7],[2,1,5]])
# print(movieRentingSystem.search(1))
# movieRentingSystem.rent(0, 1)
# movieRentingSystem.rent(1, 2)
# print(movieRentingSystem.report())
# movieRentingSystem.drop(1, 2)
# print(movieRentingSystem.search(2))
← Back to All Questions