Build a Flexible Expense Rules Engine
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are building a rules engine for a corporate credit card product. Employees use company cards for business expenses, and managers define policies that should flag invalid expenses.
Each expense is provided as a dictionary with string keys and values, for example:
`{"expense_id":"001","trip_id":"001","amount_usd":"49.99","expense_type":"client_hosting","vendor_type":"restaurant","vendor_name":"Outback Roadhouse"}`
Implement:
`evaluate_rules(rules, expenses) -> result`
Requirements:
- Evaluate both expense-level and trip-level policies.
- Choose a return type that clearly reports which expenses or trips violated which rules.
- Support multiple violations for the same expense or trip.
- Design the rule representation so it can be extended later and created through an API.
Initially support these rules:
1. No restaurant expense may exceed `$75` when `vendor_type == "restaurant"`.
2. No airfare expenses when `expense_type == "airfare"`.
3. No entertainment expenses when `expense_type == "entertainment"`.
4. No single expense may exceed `$250`.
5. The total amount for a trip may not exceed `$2000`.
6. Total meal expenses for a trip may not exceed `$200`.
Then extend the design to support composite rules built from simpler predicates:
- `(vendor_type == "restaurant") AND (expense_type == "meals") AND (amount_usd > 50)`
- `((expense_type == "entertainment") AND (amount_usd > 100)) OR (expense_type == "client_hosting")`
- `(amount_usd > 100) AND NOT (vendor_name == "Staples")`
Assume some predicates may be expensive to evaluate, including ones that require database access. Explain and, if time permits, implement practical optimizations for rule evaluation, such as short-circuiting, predicate ordering, caching, or pre-aggregation.
Quick Answer: This question evaluates designing extensible rule engines, predicate composition, data modeling for expense- and trip-level aggregation, and reasoning about correctness when reporting multiple violations.
Part 1: Evaluate Fixed Expense and Trip Policies
You are given a list of expense dictionaries. Implement `solution(expenses)` to apply six fixed corporate-card policies. Expense-level rules: (1) if `vendor_type == 'restaurant'`, the amount must be at most 75, (2) `expense_type == 'airfare'` is always a violation, (3) `expense_type == 'entertainment'` is always a violation, and (4) any single expense over 250 is a violation. Trip-level rules: (5) total amount for the same `trip_id` must be at most 2000, and (6) total amount of expenses with `expense_type == 'meals'` in the same trip must be at most 200. Return a report showing all violated rules for each expense and each trip. Keep rule names in the exact order listed above, and omit IDs with no violations.