Google SDE VO 8.5 面经：纯 BQ + 租车分配区间调度，稳步通过

面试概况

提前做了 mock，心里有底多了，整场下来顺利通过。

第一轮：纯 BQ

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

第二轮：租车分配（区间调度）

面试官是华人，聊天氛围轻松融洽。简单梳理简历后开始考题。

题目：给定一系列租车订单（取车时间、还车时间），求最少需要多少辆车，并给出每个订单的车辆分配方案。

思路：把租车场景转成区间重叠问题。

• 用扫描线计算区间重叠，时间相同时优先处理还车，这样刚还的车可以马上被下一单复用。
• 维护一个闲置车辆池，还车时把车放回池中，取车时优先从池里调配，池空了再新增车辆。
• 扫描结束后，新增过的车辆总数就是最少用车数量，同时得到完整的分配方案。

import heapq

def assign_cars(orders):
    """orders: [(start, end)]，返回 (最少车辆数, 每个订单分到的车编号)"""
    events = []
    for i, (s, e) in enumerate(orders):
        events.append((s, 1, i))  # 1 = 取车
        events.append((e, 0, i))  # 0 = 还车，同一时刻优先处理
    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

时间复杂度 O(n log n)。

面试官重点考察：边界条件的处理（同一时刻的取车 / 还车顺序）以及代码编写能力。