## Design a Scalable Expense-Policy Violation Engine You are building the production version of a corporate-card policy system. Companies issue corporate cards to employees, and managers configure **policies** (rules) that flag expenses or trips that violate spending limits. In an earlier coding round you wrote an in-memory `evaluate_rules(rules, expenses)` function against a small fixed rule set; you now need to **productionize** it. Each expense is a record such as: ```json { "expense_id": "001", "trip_id": "001", "amount_usd": "49.99", "expense_type": "client_hosting", "vendor_type": "restaurant", "vendor_name": "Outback Roadhouse" } ``` Rules come in two scopes: - **Expense-level** rules evaluate a single expense in isolation — e.g. "no restaurant expense (`vendor_type == "restaurant"`) over \$75", "no `airfare` or `entertainment` expenses", "no single expense over \$250". - **Trip-level** rules depend on accumulated state across all expenses in a trip — e.g. "a trip cannot exceed \$2000 total", "total meal expenses cannot exceed \$200 per trip". Rules can also be **composite** (combinations of leaf predicates), e.g. `(vendor_type == restaurant) AND (expense_type == meals) AND (amount > 50)`, or `(expense_type == entertainment AND amount > 100) OR (expense_type == client_hosting)`, or `(amount > 100) AND NOT (vendor_name == "Staples")`. Design a system that can **process millions of expenses per day against tens of thousands of rules**, flag both expense-level and trip-level violations, and let managers create new rules through an API in the future. Concretely, address: - how expenses are **ingested and evaluated**, - how rules are **stored, versioned, and loaded efficiently**, - how **stateful trip-level limits** are accumulated and evaluated, - how violations are **persisted for audit and reporting**, - how employees and managers are **notified** of violations, - how the system **scales**, handles **retries and idempotency**, and supports **future rule types and API-based rule creation**. ```hint Where to start The two rule scopes have fundamentally different shapes: an **expense-level** rule is decidable from a single record, while a **trip-level** rule depends on everything else in the same trip. Forcing both through one evaluation path is the most common mistake here — think about what that difference implies for where you compute, what you have to remember between events, and how you keep a trip's events together. ``` ```hint What actually has to scale The headline isn't raw QPS — millions/day is only low-thousands/sec. The thing that explodes is *rules × expenses*: tens of thousands of rules naively touched on every expense. Before you reach for more machines, ask what lets you skip rules that obviously can't apply to a given expense. ``` ### Constraints & Assumptions - **Scale:** millions of expenses ingested per day (assume low-thousands/sec average, bursty); tens of thousands of active rules across all tenants. - **Multi-tenant:** each company (tenant) defines its own rules; rules and data must be isolated per tenant. - **Field typing:** expense fields arrive as strings (e.g. `"amount_usd": "49.99"`); normalization/typing happens at ingest. - **Latency:** common expense-level rules should flag near-real-time (sub-second to low-seconds); trip-level checks may be slightly slower as they depend on accumulated state. Anything blocking a transaction synchronously has a tens-of-ms budget. - **Rule lifecycle:** new rule *types* will be added over time and managers will create rules via an API — the engine must not require a code change per new rule, and it must validate and bound the cost of arbitrary composite predicates. - **Correctness:** every violation must be explainable and reproducible — it records exactly which rule version fired and why. The same `expense_id` may be re-delivered, and expenses can be corrected, reversed, or arrive late/out of order. ### Clarifying Questions to Ask - What latency SLA distinguishes a "hard-stop / block" violation from a "warn / review" one — does anything need to block the transaction synchronously, or is all evaluation post-authorization? - Are expense records immutable once ingested, or can amounts/attributes be amended after the fact (requiring re-evaluation of past violations)? - When a rule is edited or a new rule is activated, must it be applied **retroactively** to already-ingested expenses, or only to new ones? - What defines a trip's lifecycle and "close" — is there a point after which trip-level aggregates can expire, and can expenses arrive after a trip closes? - Who are the notification recipients per violation (employee, manager, finance), and does that mapping vary by tenant? - Do composite rules reference external/enriched data (vendor metadata, employee role), how fresh must it be, and is there a per-rule cost budget? ### What a Strong Answer Covers - **Functional vs non-functional requirements**, with explicit scale/latency/durability/auditability and multi-tenant isolation called out. - A clear **separation of stateless expense-level evaluation from stateful trip-level evaluation**, tied together by an event log/stream, with the read/write path for a single expense traced end to end. - A **declarative, versioned rule model** (predicate-tree AST) that supports composite rules and API-driven creation without evaluator changes, and how it compiles/loads into evaluators. - An **efficient matching strategy** for tens of thousands of rules: field/value indexing of candidate rules, compiled rules cached in memory, short-circuiting, optional Rete-style sharing of subexpressions. - A **trip-aggregate design** keyed by `(tenant_id, trip_id)` with atomic updates, plus handling of duplicates, reversals, late events, trip closure, and replay. - A **persistence strategy** matching each data shape to a store (relational for rules/violations, durable log for raw expenses, KV/stream-state for aggregates, optional search index for analysts) and a violation record schema that captures `rule_version_id` + matched-predicate explanation. - **Idempotency, ordered partitioning, retries with backoff, and an outbox/transactional-publish pattern** for correctness at scale. - An **event-driven notification path** decoupled from evaluation, with recipient routing, dedup, throttling, and delivery retries. - **Observability** (consumer lag, evaluation latency, error rates) and **rule-API safety** (validation, draft/test mode, historical impact preview, cost limits, explanation API). ### Follow-up Questions - A manager edits a rule that previously flagged 10,000 historical expenses. How do you preview the impact before activation, and how do you apply a new rule retroactively to the last 90 days without blocking the live path? - An expense is reversed three days after it triggered a trip-total violation. How does the trip aggregate and the existing violation get corrected without losing the audit trail or double-counting? - One tenant authors a pathologically expensive composite rule (deep nesting + external lookups) that slows every evaluator. How do you detect, bound, and isolate it so it can't starve other tenants? - If you needed a synchronous "would this purchase be blocked?" check at card-authorization time (tens-of-ms budget), what subset of this design would you reuse and what would you have to change?