FastPrepMinimum Cars for Rental Requests
Problems/Minimum Cars for Rental Requests

Minimum Cars for Rental Requests

Google logoGoogle● MediumFULLTIMEINTERNNEW GRADOAPHONE SCREENONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The interview reports specify record IDs, endpoint reuse, unsorted input, and a minimum-car assignment. This practice uses deterministic car IDs and output ordering; the judged core matches at about 95%.

Special thanks: 🌷 A special thank you to a lovely, amazing fren for sharing that this question appeared again on November 2, 2026! ദ്ദി ˉ͈̀꒳ˉ͈́ )✧ 💜

You are given an unsorted array of rental records. Each record is [recordId, pickupTime, returnTime], where recordId uniquely identifies the rental.

A car can serve only non-overlapping rentals. Treat every rental as the half-open interval [pickupTime, returnTime), so a car returned at time t may be reused by a rental picked up at time t. A zero-duration interval [t,t) is empty: assign it to car 0 (creating car 0 if necessary) without changing that car's availability.

Assign every rental to a car while using the minimum possible number of cars. Car IDs are consecutive integers beginning at 0.

Use these deterministic rules when several minimum-car assignments are possible:

  1. Process records by increasing pickupTime, then increasing returnTime, then increasing recordId.
  2. Assign a zero-duration record to car 0 without changing any busy or available state.
  3. Before assigning a positive-duration record, make every car whose current rental has returned available.
  4. Reuse the available car with the smallest car ID. If no car is available, create the next car ID.

Return a String[] in increasing car-ID order. Each string has the form carId: recordId recordId ... and lists that car's rental IDs in assignment order. The array length is the minimum car count, and the lines also define the record-ID-to-car assignment.

Interview follow-up: a fleet limit

If the fleet contains at most K cars, the assignment becomes infeasible as soon as a positive-duration record finds no available car and K cars already exist. A production API could return the unassigned record IDs, but whether to reject a rental, delay pickup, or obtain an external car is a product decision rather than part of this judged function. For K = 0, every nonempty request set is immediately infeasible.

Function

solve(requests: int[][]) → String[]

Examples

Example 1

requests = [[101, 1, 3], [102, 2, 4], [103, 4, 6]]return = ["0: 101 103", "1: 102"]

Records 101 and 102 overlap, so two cars are necessary. Car 0 returns at time 3 and is available for record 103 at time 4.

Example 2

requests = [[203, 5, 7], [201, 1, 5], [202, 2, 3]]return = ["0: 201 203", "1: 202"]

The input is unsorted. At time 5, both cars are available, so the smallest available ID, car 0, receives record 203.

Example 3

requests = [[11, 3, 3], [10, 3, 3], [12, 3, 4]]return = ["0: 10 11 12"]

The tie rule processes record IDs 10, 11, and 12 in that order. Each zero-duration rental returns immediately, so one car serves all three records.

Constraints

  • 1 <= requests.length <= 200000
  • Each row contains exactly three integers: [recordId, pickupTime, returnTime].
  • 1 <= recordId <= 10^9, and all record IDs are unique.
  • 0 <= pickupTime <= returnTime <= 10^9.

More Google problems

  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public String[] solve(int[][] requests) {
      // Write your code here.
    }
}
Checking account…