Katkat
Back

Busiest Rental Car

GoogleSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manage state and apply custom sorting logic to simulate resource allocation across time intervals.

Busiest Rental Car

You are managing a fleet of rental cars at a popular agency. You are given a list of rentals, where each rental is represented as [start_time, end_time, car_id]. A car is considered 'in use' during the interval [start_time, end_time).

If a car is returned at exactly the same time another rental begins, the car is considered available for the new rental. Your goal is to identify which car_id was used for the highest number of rentals. If there is a tie, return the car_id with the smallest numerical value.

Function Signature

def busiest_car(rentals: List[List[int]]) -> int:

Constraints

  • 1 <= len(rentals) <= 10^5
  • 0 <= start_time < end_time <= 10^9
  • 1 <= car_id <= 1000

Example 1

Input: rentals = [[1, 5, 10], [2, 6, 20], [5, 10, 10]] Output: 10 Explanation: Car 10 was used twice (intervals [1, 5) and [5, 10)). Car 20 was used once. 10 is the winner.

Example 2

Input: rentals = [[1, 2, 1], [2, 3, 2], [3, 4, 1]] Output: 1 Explanation: Both car 1 and car 2 were used twice. The smaller ID, 1, is returned.

Edge Cases

  • Only one rental provided.
  • All cars used the same number of times.
  • Non-overlapping intervals for the same car.

Hints

Hint 1

You do not need to simulate the timeline minute-by-minute; simply counting the occurrences of each car ID is sufficient.

Hint 2

Use a hash map or a frequency array to store the total count of rentals associated with each unique car ID.

Hint 3

After aggregating the counts, iterate through the map to find the ID with the maximum value, applying the tie-breaking condition for equal counts.

Follow-up questions

  • How would your approach change if you needed to find the car that was used for the longest total duration rather than the most frequent number of rentals?
  • What if the rental list was streaming and you couldn't store all records in memory? How would you maintain the 'busiest' car?
  • If a car requires a mandatory 1-hour 'cleaning' buffer between rentals, how would you validate the input data to ensure no overlapping usage?