Stripe OA：Payment Events 支付事件聚合（状态机 + 去重 + 退款 + 商户拉黑）

Stripe 很典型的一道 OA：不考算法技巧，考的是把一长串业务规则一条不漏地实现对。题目分 4 个 Part，建议按顺序做，每个 Part 都在前一个的基础上加规则。

题目

Stripe 每天处理海量支付，大量依赖异步事件。你要实现：

def process_events(events: list[str]) -> list[str]:

• events 按接收顺序给出，每条是一行 CSV，固定 7 列： event_id,event_time,event_type,payment_id,payment_event_type,merchant_id,amount
• event_type：payment / refund / merchant_update
• payment_event_type：create / authorize / capture
• 空值用 - 表示。merchant_id 只在 create 里有，amount 只在 authorize / capture 里有（merchant_update 里 amount 是风险分）
• 同一个 event_id 只能处理一次

输出：每个 payment 一行，没有表头，按 payment 被成功 create 的顺序排列：

payment_id,merchant_id,state,amount_authorized,amount_captured,last_event_at

数字列没有值时为 0，例如 payment_1,merchant_1,created,0,0,0。输出里不能出现 -，缺失的字段留空。

Part 1：聚合支付状态

一笔支付分两步：Authorization（买家授权，钱还没动）和 Capture（商户把授权的钱收走）。authorize 和 capture 都可以有多次，金额累加。

• capture 之后 amount_captured < amount_authorized → partially_captured
• amount_captured == amount_authorized → successful
• 保证 captured 不会超过 authorized

当前状态	允许的事件
不存在	create
created	authorize
authorized	authorize, capture
partially_captured	capture
successful	无

例子（含重复 event_id）：

evt_1,0,payment,payment_1,create,merchant_1,-
evt_2,1,payment,payment_2,create,merchant_2,-
evt_3,2,payment,payment_1,authorize,-,10
evt_4,3,payment,payment_1,authorize,-,10
evt_5,4,payment,payment_2,authorize,-,15
evt_6,5,payment,payment_1,capture,-,10
evt_6,5,payment,payment_1,capture,-,10
evt_7,6,payment,payment_2,capture,-,15

输出：

payment_1,merchant_1,partially_captured,20,10,5
payment_2,merchant_2,successful,15,15,6

重复的 evt_6 只算一次，所以 payment_1 的 captured 是 10 不是 20。

Part 2：忽略乱序事件

事件可能乱序到达。不符合当前状态的事件直接忽略：不改状态、不改金额、也不更新 last_event_at。比如还没 authorize 就 capture、已经 partially_captured 再 authorize，都是无效事件。

evt_1,0,payment,payment_1,create,merchant_1,-
evt_2,1,payment,payment_2,capture,-,20
evt_3,2,payment,payment_1,capture,-,10
evt_4,3,payment,payment_2,create,merchant_2,-
evt_5,4,payment,payment_1,authorize,-,10
evt_6,5,payment,payment_2,authorize,-,20
evt_7,6,payment,payment_1,capture,-,10
evt_8,7,payment,payment_1,authorize,-,5
evt_9,8,payment,payment_2,capture,-,10
evt_10,9,payment,payment_2,capture,-,10

输出：

payment_1,merchant_1,successful,10,10,6
payment_2,merchant_2,successful,20,20,9

原题这个例子下面的文字说明里，事件编号和上面的输入对不上，应该是题面 typo，以状态转换表为准。

Part 3：退款

新增 event_type = refund，只带 payment_id，例如 evt_7,6,refund,payment_1,-,-,-。

• 只有 successful 能退款，变成 refunded；refunded 之后不再接受任何事件
• 有效的退款只改 state 和 last_event_at，金额和商户都不变

例子：payment_1、payment_2 都走到 successful 后各退款一次（时间 6、7），再对 payment_1 退款一次（时间 8）。第二次退款被忽略，所以 payment_1 的 last_event_at 是 6 不是 8：

payment_1,merchant_1,refunded,10,10,6
payment_2,merchant_2,refunded,20,20,7

Part 4：商户风险拉黑

新增 merchant_update，merchant_id 是商户，amount 是风险分（0–100），例如 evt_1,0,merchant_update,-,-,merchant_1,95。

• 风险分 ≥ 80 时商户立刻被拉黑，而且永久有效，之后分数降下来也不解除
• 拉黑后，这个商户的 authorize 一律忽略，不管 payment 是拉黑前还是拉黑后创建的
• create、capture、refund 照常处理，已经授权的支付可以走完流程
• merchant_update 本身不改变任何 payment 的状态、金额和 last_event_at

evt_1,0,payment,payment_1,create,merchant_1,-
evt_2,1,payment,payment_1,authorize,-,10
evt_3,2,merchant_update,-,-,merchant_1,85
evt_4,3,payment,payment_2,create,merchant_1,-
evt_5,4,payment,payment_2,authorize,-,20
evt_6,5,payment,payment_1,capture,-,10
evt_7,6,merchant_update,-,-,merchant_1,10

输出：

payment_1,merchant_1,successful,10,10,5
payment_2,merchant_1,created,0,0,3

Clarify

动手前值得确认的几点：

• 重复 event_id 怎么算？ 只要见过就算处理过：第一次出现时哪怕因为状态不对被忽略，后面同 id 的事件也不再处理。
• 对已存在的 payment 再 create？ 状态表里只有「不存在」能 create，所以忽略。
• merchant_update 的风险分不在 0–100？ 题目说「有效的」merchant_update 才拉黑，超范围的当无效事件跳过。
• last_event_at 记什么？ 最后一个被接受的事件的 event_time，被忽略的事件不算。

思路

整道题就是一个状态机，外加两条全局规则：

不存在 --create--> created --authorize--> authorized (可以继续 authorize)
authorized --capture--> partially_captured / successful
partially_captured --capture--> partially_captured / successful
successful --refund--> refunded

• 全局规则 1：event_id 用一个 set 去重
• 全局规则 2：风险分 ≥ 80 的商户放进 blocked set，之后它的 authorize 全部忽略

实现上把状态表直接写成「状态 → 允许的事件」的字典，每条事件先查表，不合法就 continue。这样 Part 2、Part 3 加规则时只需要改表。

payment 用 dict 存，Python 3.7+ 的 dict 保持插入顺序，正好就是 create 的顺序，输出时不用另外排序。

参考代码（补充，已测试）

以下代码为本站补充，已通过题目的 5 个例子，并和一个独立写的暴力实现对拍了 2 万组随机数据，结果完全一致。

def process_events(events: list[str]) -> list[str]:
    # 状态机：当前状态 -> 允许的事件
    VALID = {
        None: {"create"},
        "created": {"authorize"},
        "authorized": {"authorize", "capture"},
        "partially_captured": {"capture"},
        "successful": {"refund"},
        "refunded": set(),
    }
    seen = set()            # 处理过的 event_id
    payments = {}           # payment_id -> dict（Python 3.7+ 保持插入顺序 = 创建顺序）
    blocked = set()         # 被拉黑的 merchant

    for line in events:
        cols = [None if c == "-" else c for c in line.strip().split(",")]
        if len(cols) != 7:
            continue
        event_id, t, event_type, pid, pe_type, merchant, amount = cols
        if event_id is None or event_id in seen:
            continue
        seen.add(event_id)
        t = int(t)

        if event_type == "merchant_update":
            # Part 4：风险分 >= 80 永久拉黑
            if merchant is not None and amount is not None and 0 <= int(amount) <= 100:
                if int(amount) >= 80:
                    blocked.add(merchant)
            continue

        if event_type == "refund":
            action = "refund"
        elif event_type == "payment":
            action = pe_type
        else:
            continue

        p = payments.get(pid)
        state = p["state"] if p else None
        if action not in VALID[state]:
            continue  # 不合法的事件直接忽略

        if action == "create":
            if merchant is None:
                continue
            payments[pid] = {"merchant": merchant, "state": "created", "auth": 0, "cap": 0, "last": t}
            continue
        if action in ("authorize", "capture") and amount is None:
            continue
        if action == "authorize":
            if p["merchant"] in blocked:
                continue  # Part 4：拉黑后的 authorize 一律忽略
            p["auth"] += int(amount)
            p["state"] = "authorized"
        elif action == "capture":
            p["cap"] += int(amount)
            p["state"] = "successful" if p["cap"] == p["auth"] else "partially_captured"
        elif action == "refund":
            p["state"] = "refunded"
        p["last"] = t

    return [
        f'{pid},{p["merchant"]},{p["state"]},{p["auth"]},{p["cap"]},{p["last"]}'
        for pid, p in payments.items()
    ]

时间复杂度 O(n)，空间 O(n)。

容易踩的坑

• 被忽略的事件不能更新 last_event_at。Part 3 的例子就是专门考这个的。
• 拉黑判断要看 payment 的商户。authorize 事件本身不带 merchant_id，要从 create 时记下的商户去查。
• 拉黑后 create 仍然有效。Part 4 例子里 payment_2 是拉黑后创建的，照样要出现在输出里，状态停在 created。
• capture 后的状态要每次重新判断：等于 authorized 就是 successful，否则是 partially_captured。
• 重复的 event_id 在函数最开头就要拦住，不然后面的累加会算两次。

Follow-up

• 如果事件量非常大、要分布式处理，seen 这个去重集合放哪里？可以聊幂等键、按 payment_id 分区保证同一笔支付的事件有序。
• 乱序事件现在是直接丢掉。如果要求「先缓存，等前置事件到了再补处理」，怎么设计？
• 拉黑规则如果改成「只拦拉黑后新创建的 payment」，代码要改哪里？把状态表和业务规则分开写，改起来就很快。