Rippling Expense Rule Engine：每笔报销逐规则找违规

题目重点：将全局金额、商家类型限额和禁止费用类型抽成可扩展 Rule，逐笔保留全部违规原因。

题意与假设

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

训练版金额用 Decimal USD，单笔金额非负；规则次序决定输出违规 ID 顺序，每笔 expense_id 唯一。
可见三类规则为单笔规则；trip 聚合规则需要完整 trip 明细和生效口径，应作为第二阶段扩展，不能用单笔接口假装完成。

解题路线

定义统一 Rule 协议 `violates(expense)`，每种规则封装自身参数；主循环对每笔费用运行所有规则，收集违规 ID 而不是命中第一条就停。
全局上限 amount>175、restaurant 限额 amount>45、entertainment 禁止分别独立判断；边界恰好 175/45 不违反，因为原文写 not >。
扩展时将单笔规则和 trip 级规则分阶段：先算 trip 汇总，再把上下文传给需要汇总的规则；为规则加 ID、版本、生效时间，方便解释历史结果。
结果与真实付款/审批分开，flag 是审查信号，不等于拒付。规则重评须保留当时版本和原始 expense 快照。

手动走一遍

Food $250、restaurant 同时违反总额 175 和 restaurant 45 两条，输出两个 ID；Entertainment $20、非餐厅只违反禁止娱乐。金额等于阈值不违规。

Python 参考实现

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

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

from dataclasses import dataclass
from decimal import Decimal
from typing import Protocol


@dataclass(frozen=True)
class Expense:
    expense_id: str
    expense_type: str
    amount_usd: Decimal
    seller_type: str


class Rule(Protocol):
    rule_id: str

    def violates(self, expense: Expense) -> bool: ...


@dataclass(frozen=True)
class MaximumAmount:
    rule_id: str
    limit: Decimal

    def violates(self, expense: Expense) -> bool:
        return expense.amount_usd > self.limit


@dataclass(frozen=True)
class SellerTypeMaximum:
    rule_id: str
    seller_type: str
    limit: Decimal

    def violates(self, expense: Expense) -> bool:
        return expense.seller_type == self.seller_type and expense.amount_usd > self.limit


@dataclass(frozen=True)
class ForbiddenExpenseType:
    rule_id: str
    expense_type: str

    def violates(self, expense: Expense) -> bool:
        return expense.expense_type == self.expense_type


def evaluate_rules(rules: list[Rule], expenses: list[Expense]) -> dict[str, list[str]]:
    if len({rule.rule_id for rule in rules}) != len(rules):
        raise ValueError("duplicate rule ID")
    if len({expense.expense_id for expense in expenses}) != len(expenses):
        raise ValueError("duplicate expense ID")
    if any(expense.amount_usd < 0 for expense in expenses):
        raise ValueError("negative amount")
    return {
        expense.expense_id: [rule.rule_id for rule in rules if rule.violates(expense)]
        for expense in expenses
    }

复杂度

E 笔费用、R 条单笔规则，时间 O(E×R)，输出最多 O(E×R) 条违规；若可按 expense_type/seller_type 建规则索引，常见情况可少评无关规则，但需保留跨类型全局规则。

易错点与追问

容易失分的边界

用 if/elif 只返回第一条违规。
将 `>` 写成 `>=` 改了边界。
把币种或浮点误差留给隐式转换。
新增 trip 级规则仍只收到一笔 expense，无法正确评价总和。
更新规则覆盖历史版本导致旧审批不可复盘。

继续深挖

trip 总额或 per-category 规则需要怎样的两阶段 API？
若费用列表只以 stream 到达，trip 规则何时可终结、需要多少有界状态？
规则冲突时是否存在优先级或短路？
如何支持规则配置版本和灰度？
数百万费用批处理怎样优化规则选择与审计？