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:
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.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
moviei
.105
calls in total will be made to search
, rent
, drop
and report
.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:
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:
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
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:
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]
Case | How 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 shops | Throw 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 called | Return 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 issues | Use 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 exceeding | Use 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 report | The 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. |