Google SDE VO Round 1: Minimum Cars for Rental Records + Assignment (Sort + Min-Heap)

Overview

The interviewer was cheerful and smiled throughout — easy to talk to and not the type to give you a hard time.

After a self-introduction she asked briefly about a project. I think it was just a formality: no follow-ups, and the questions were very general.

Coding: car rental scheduling

Problem

You're given last year's rental records, each with a pickup_time, a return_time and a record ID, roughly like this:

(id=101, pickup=3, return=5)

Find the minimum number of cars needed to serve every rental, and return an assignment (which car serves each record).

Two key clarifications

1. Edge case: if A's return time equals B's pickup time, can they share a car? — Yes.
2. Is the input sorted? The optimal solution differs depending on whether it's sorted by pickup. — It's not sorted.

Approach: sort + greedy min-heap

• Sort by pickup time.
• The min-heap stores each car's available time (its return time) and car ID.
• For each request: if its pickup time is at or after the top car's return time, reuse that car; otherwise add a new car to the heap.
• A map records the assignment for each record.

import heapq

def assign_rentals(rentals):
    """rentals: [(id, pickup, return)]; returns (min number of cars, {rental id: car id})"""
    heap, assignment, cars = [], {}, 0       # heap: (available time, car id)
    for rid, pickup, ret in sorted(rentals, key=lambda r: (r[1], r[2])):
        if heap and heap[0][0] <= pickup:    # reusable if returned at or before pickup
            _, car = heapq.heappop(heap)
        else:
            car, cars = cars, cars + 1
        assignment[rid] = car
        heapq.heappush(heap, (ret, car))
    return cars, assignment

Time O(n log n), space O(n).

For a similar problem, see Google SDE VO 8/5: car rental interval scheduling, which uses a sweep line plus an idle-car pool.