Google SDE VO (8/5): Pure Behavioral + Car Rental Interval Scheduling — Passed

Overview

I did mock interviews beforehand, which gave me a lot more confidence, and passed both rounds.

Round 1: Pure behavioral

1. What's your biggest weakness?
2. Why are you leaving your current role?
3. Where do you see yourself in five years?

Round 2: Car rental assignment (interval scheduling)

The interviewer was relaxed and easy to talk to. After a quick resume walkthrough we moved to the problem.

Problem: given rental orders (pickup time, return time), find the minimum number of cars needed and assign a car to each order.

Approach: turn it into an interval-overlap problem.

• Use a sweep line over the intervals, and process returns before pickups at the same timestamp so a car returned at that moment can be reused right away.
• Keep an idle-car pool: returned cars go back into the pool; pickups take from the pool first and only add a new car when the pool is empty.
• After the sweep, the number of cars ever created is the minimum, and you also have the full assignment.

import heapq

def assign_cars(orders):
    """orders: [(start, end)]; returns (min number of cars, car id assigned to each order)"""
    events = []
    for i, (s, e) in enumerate(orders):
        events.append((s, 1, i))  # 1 = pickup
        events.append((e, 0, i))  # 0 = return; processed first at the same timestamp
    events.sort()

    idle, assigned, total = [], [None] * len(orders), 0
    for _, kind, i in events:
        if kind == 0:
            heapq.heappush(idle, assigned[i])
        else:
            if idle:
                assigned[i] = heapq.heappop(idle)
            else:
                assigned[i] = total
                total += 1
    return total, assigned

Time complexity O(n log n).

What the interviewer focused on: edge cases (ordering of pickups and returns at the same time) and coding ability.