Expense Policy Rules Engine: Scale, Violation Storage and Shared Compound Rules

Build an expense rules engine. Employees submit expenses, and the engine checks every expense against a company's expense policy rules and reports the violations. The interview then probes how the engine scales, how its results are stored and delivered, and how compound rules are evaluated. The report names the base problem without describing it. The model below is an assumption that makes the parts concrete; settle the real fields and rule types with the interviewer first. The report does distinguish basic rules from group rules, and it mentions compound rules built from other rules. ```text expense (illustrative fields) expense_id, employee_id, trip_id, category, vendor, amount_cents, date basic rule: a condition on one expense A: the expense is a meal C: the amount is above a per-expense limit D: the vendor is on a disallowed list group rule: a condition on an aggregate over a group of expenses G1: total meal spend per trip is above a trip limit G2: total spend per employee per month is above a monthly limit compound rule: a combination of other rules B = A AND C (a meal above the per-expense limit) X = A AND B ``` A rule describes a violation: an expense (or a group) violates a rule when the rule's condition holds. ### Clarifying Questions - Which expense fields exist, and which of them do rules test (category, vendor, amount, date, trip, employee)? - Is every amount in one currency, and is a limit exceeded when the amount is above it or when it is at or above it? - Does a violation block the expense or only flag it for review? - For a group rule, is the violation reported on the group, on every expense in it, or on the expense that crossed the limit? ### Part 1 — Evaluate basic and group rules Implement the engine: given a list of expenses and a set of basic and group rules, return every violation, identified by the rule and by the expense (basic rules) or the group key (group rules). ```hint Two kinds of work A basic rule looks at one expense at a time; a group rule needs a total first. Structure the code so that each kind is evaluated in the way that suits it. ``` #### What This Part Should Cover - A rule representation that separates conditions, grouping keys and thresholds - Correct results for both rule kinds, with exact money arithmetic and boundary amounts - The cost of the straightforward evaluation, as the baseline for Part 2 ### Part 2 — A million expenses and ten thousand rules There are now on the order of a million expenses and ten thousand rules. How do you optimize the evaluation? Treat basic rules and group rules separately. ```hint Count the pairs Estimate how many expense-rule checks the straightforward loop performs, then look for structure in the rules, such as the fields they test or the totals they share, that lets most pairs be skipped or shared. ``` #### Clarifying Questions for this Part - Is evaluation a periodic batch over all expenses, or must each new expense be checked as it is submitted? - Does each rule belong to one company, and how many rules apply to a typical company? #### What This Part Should Cover - Why checking every expense against every rule does not scale - Narrowing the basic rules an expense must be checked against, and batch or set-based evaluation - Computing each distinct group aggregate once and keeping it up to date as expenses change ### Part 3 — Storing results and notifying the customer How do you store the evaluation results, and how do you notify the customer? ```hint Results change over time The same expense is evaluated again when it is edited or when a rule changes. Decide what the stored result must look like so that re-running is safe and the customer hears about changes rather than about every run. ``` #### Clarifying Questions for this Part - Who is the customer to notify: the company's finance administrators, the employee who submitted the expense, or both? - Must notifications be immediate, or is a periodic digest acceptable? #### What This Part Should Cover - A violations store keyed so that repeated evaluation is idempotent, recording the rule version behind each result - Notifications driven by state changes (new and resolved violations), delivered reliably and without duplicates - Querying violations for review by company, rule, employee and status ### Part 4 — Compound rules that reference each other Optimize the evaluation when compound rules reference other compound rules: for example, a compound rule X is A AND B, while B is itself A AND C. ```hint Expand before evaluating Write out what X requires in terms of basic conditions only, and notice what a straightforward recursive evaluation computes more than once. ``` #### Clarifying Questions for this Part - Can compound rules use OR and NOT as well as AND, and can they include group rules? - What should happen if a rule refers to itself through other rules? #### What This Part Should Cover - Compound rules as a dependency graph, with cycle detection when a rule is saved - Evaluating each shared sub-rule once per expense, or once per batch - Simplifying or merging equivalent compound rules, and ordering conditions so that evaluation can stop early ### What a Strong Answer Covers - Settles the expense fields, rule semantics and money representation before coding - A clean separation of per-expense conditions, group aggregates and composition, so that each optimization stays local - Quantified reasoning about evaluation cost at a million expenses and ten thousand rules - Durable, idempotent results and change-driven notifications - Tests covering boundary amounts, empty groups, edits that resolve a violation and cyclic definitions ### Follow-up Questions - A rule's limit is lowered after a month of evaluations. Which stored violations change, and what does the customer hear? - An expense is moved from one trip to another. Which group totals and violations must be updated? - Rules now support OR and NOT. What changes in sharing sub-results and in stopping early? - How would you let finance administrators write their own rules without letting them create rules that are expensive to evaluate?