DoorDash Dasher Pay：订单事件扫描与 Peak 双倍费率

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 时间单位分钟、基础0.3美元；FULFILLED和CANCELLED/CANCELED都结束订单，输入适配器应规范同义状态。获取上游记录的API需明确日期窗口、分页、订单去重及失败返回。
• 每个订单有 ACCEPTED 开始事件和 FULFILLED 或 CANCELED 结束事件，时间为整数单位。示例把取消前已配送时间计入费用。
• 基础费率按每个活跃订单、每个时间单位计算；peak 时间窗 [start,end) 内费率翻倍。这里的 0.3 只是可读面经示例值，面试时以题面为准。
• 同时间戳事件先共同更新状态，再计算到下一事件时刻的费用。重复开始、未开始就结束、最终未闭合的订单视为无效输入。

解题路线

1. POST payout(dasherId)先按业务日期读取完整上游事件再计算，不把上游超时当零工资。示例15/18/36/45分钟两单对应0.9+10.8+2.7=14.4；高峰窗口内倍率2，高峰重叠不变4。金额使用Decimal，最终货币舍入政策由合同指定。
2. 把接单与结束事件、peak 开始与结束时刻放到同一条时间线上，按时间排序。
3. 维护活跃订单集合与当前 peak 覆盖数。处理时刻 t 的所有变化后，到下一时刻 t' 之间活跃数和倍率都不变。
4. 将每段的 活跃订单数 × 基础费率 × 时间长度 × peak 倍率 累加。金额用 Decimal，避免二进制浮点误差。

手动走一遍

示例有两单：A 在 15 接、26 完成，B 在 20 接、35 取消。活跃订单数依次为 15–20 的 1、20–26 的 2、26–35 的 1；总活跃时间为 26 个订单时间单位。若基础费率为 0.3，总额是 7.8。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import defaultdict
from decimal import Decimal


def calculate_pay(events, peak_windows, rate, end_time=None):
    """Pay per active delivery per time unit; peak windows double the rate.

    events: (order_id, time, status), status in ACCEPTED/FULFILLED/CANCELED.
    Time values are integer units. Peak windows use [start, end).
    """
    if isinstance(rate, float):
        raise ValueError("pass rate as a string or Decimal, not float")
    rate = Decimal(rate)
    if rate < 0:
        raise ValueError("rate must be nonnegative")

    at_time = defaultdict(list)
    boundaries = set()
    for order_id, time, status in events:
        if status == "CANCELLED": status = "CANCELED"
        if status not in {"ACCEPTED", "FULFILLED", "CANCELED"}:
            raise ValueError(f"unknown status: {status}")
        at_time[time].append((order_id, status))
        boundaries.add(time)

    peak_delta = defaultdict(int)
    for start, end in peak_windows:
        if start >= end:
            raise ValueError("invalid peak window")
        peak_delta[start] += 1
        peak_delta[end] -= 1
        boundaries.update((start, end))
    if end_time is not None:
        boundaries.add(end_time)
    if not boundaries:
        return Decimal(0)

    timeline = sorted(boundaries)
    active = set()
    finished = set()
    peak_count = 0
    total = Decimal(0)

    for index, time in enumerate(timeline):
        peak_count += peak_delta[time]
        for order_id, status in at_time[time]:
            if status == "ACCEPTED":
                if order_id in active or order_id in finished:
                    raise ValueError(f"duplicate order start: {order_id}")
                active.add(order_id)
            else:
                if order_id not in active:
                    raise ValueError(f"order not active: {order_id}")
                active.remove(order_id)
                finished.add(order_id)
        if index + 1 < len(timeline):
            duration = timeline[index + 1] - time
            total += rate * len(active) * duration * (2 if peak_count else 1)

    if active:
        raise ValueError("unfinished orders need an end event")
    return total

复杂度

设订单事件数为 E、peak 边界数为 P，排序需 O((E+P)log(E+P))，扫描需 O(E+P)；活跃订单集合和事件索引占 O(E+P) 空间。

易错点与追问

容易失分的边界

• 把每条订单独立计费后才检查 peak，容易漏掉时间窗切分；把所有边界并到同一时间线更稳。
• 金额运算不要从 Python float 构造 Decimal；传入字符串或整数最小货币单位。
• peak 窗口可能重叠。示例用覆盖数判断是否处于 peak，重叠并不让费率翻四倍。

继续深挖

• 如果上游事件乱序或可能重复，先定义订单状态机与幂等事件 id；可以在校验层排序后再计费。
• 如果流式到达、不能每次重排历史，需维护有序事件索引与已结算水位，并说明迟到事件如何重算或补账。