PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • hard
  • Rippling
  • Coding & Algorithms
  • Software Engineer

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.

Constraints

  • `0 <= len(expenses) <= 100000`
  • Each `expense_id` is unique, and every expense belongs to exactly one `trip_id`
  • `amount_usd` has at most 2 decimal places and fits in normal decimal arithmetic

Examples

Input: ([],)

Expected Output: {'expense_violations': {}, 'trip_violations': {}}

Explanation: Edge case: no expenses means no violations.

Input: ([{'expense_id': '001', 'trip_id': '001', 'amount_usd': '80.00', 'expense_type': 'meals', 'vendor_type': 'restaurant', 'vendor_name': 'Outback Roadhouse'}],)

Expected Output: {'expense_violations': {'001': ['restaurant_over_75']}, 'trip_violations': {}}

Explanation: A restaurant expense above 75 violates the restaurant-specific rule.

Input: ([{'expense_id': '001', 'trip_id': 't1', 'amount_usd': '300.00', 'expense_type': 'meals', 'vendor_type': 'restaurant', 'vendor_name': 'Bistro'}, {'expense_id': '002', 'trip_id': 't1', 'amount_usd': '50.00', 'expense_type': 'airfare', 'vendor_type': 'airline', 'vendor_name': 'Delta'}, {'expense_id': '003', 'trip_id': 't1', 'amount_usd': '1900.00', 'expense_type': 'lodging', 'vendor_type': 'hotel', 'vendor_name': 'Grand Hotel'}],)

Expected Output: {'expense_violations': {'001': ['restaurant_over_75', 'single_expense_over_250'], '002': ['no_airfare'], '003': ['single_expense_over_250']}, 'trip_violations': {'t1': ['trip_total_over_2000', 'trip_meals_over_200']}}

Explanation: This trip violates both trip-level limits, and some expenses also violate expense-level rules.

Input: ([{'expense_id': '010', 'trip_id': 't2', 'amount_usd': '260.00', 'expense_type': 'entertainment', 'vendor_type': 'event', 'vendor_name': 'Arena'}, {'expense_id': '011', 'trip_id': 't2', 'amount_usd': '100.00', 'expense_type': 'meals', 'vendor_type': 'cafe', 'vendor_name': 'Cafe 9'}],)

Expected Output: {'expense_violations': {'010': ['no_entertainment', 'single_expense_over_250']}, 'trip_violations': {}}

Explanation: Entertainment is banned, and the same expense also exceeds the single-expense cap.

Hints

  1. A single pass can collect expense-level violations and also build trip aggregates.
  2. An expense or trip may violate more than one rule, so store violations in a list.

Part 2: Evaluate Composite Boolean Expense Rules

Implement `solution(rules, expenses)` for an extensible expense-rule model. Each rule has a `rule_id` and a nested boolean expression. A rule is violated when its expression evaluates to `True` for an expense. Support leaf predicates of the form `{'field': str, 'cmp': op, 'value': str}` and boolean nodes `{'op': 'AND', 'args': [...]}`, `{'op': 'OR', 'args': [...]}`, and `{'op': 'NOT', 'arg': ...}`. Return every violated `rule_id` for each expense. Preserve the order of rules as given in the input, and omit expenses with no violations.

Constraints

  • `0 <= len(rules), len(expenses) <= 10000`
  • The total number of expression nodes across all rules is at most `100000`
  • Expressions are valid trees, and `expense_id` values are unique

Examples

Input: ([{'rule_id': 'R1', 'expr': {'op': 'AND', 'args': [{'field': 'vendor_type', 'cmp': '==', 'value': 'restaurant'}, {'field': 'expense_type', 'cmp': '==', 'value': 'meals'}, {'field': 'amount_usd', 'cmp': '>', 'value': '50'}]}}, {'rule_id': 'R2', 'expr': {'op': 'OR', 'args': [{'op': 'AND', 'args': [{'field': 'expense_type', 'cmp': '==', 'value': 'entertainment'}, {'field': 'amount_usd', 'cmp': '>', 'value': '100'}]}, {'field': 'expense_type', 'cmp': '==', 'value': 'client_hosting'}]}}, {'rule_id': 'R3', 'expr': {'op': 'AND', 'args': [{'field': 'amount_usd', 'cmp': '>', 'value': '100'}, {'op': 'NOT', 'arg': {'field': 'vendor_name', 'cmp': '==', 'value': 'Staples'}}]}}], [{'expense_id': 'e1', 'amount_usd': '60', 'expense_type': 'meals', 'vendor_type': 'restaurant', 'vendor_name': 'Bistro'}, {'expense_id': 'e2', 'amount_usd': '120', 'expense_type': 'entertainment', 'vendor_type': 'event', 'vendor_name': 'Arena'}, {'expense_id': 'e3', 'amount_usd': '150', 'expense_type': 'supplies', 'vendor_type': 'office', 'vendor_name': 'Staples'}, {'expense_id': 'e4', 'amount_usd': '130', 'expense_type': 'client_hosting', 'vendor_type': 'restaurant', 'vendor_name': 'Steakhouse'}])

Expected Output: {'e1': ['R1'], 'e2': ['R2', 'R3'], 'e4': ['R2', 'R3']}

Explanation: This covers nested `AND`, `OR`, and `NOT`, with multiple violations for the same expense.

Input: ([], [{'expense_id': '1', 'amount_usd': '10', 'expense_type': 'meals', 'vendor_type': 'restaurant', 'vendor_name': 'A'}])

Expected Output: {}

Explanation: Edge case: no rules means nothing can be violated.

Input: ([{'rule_id': 'X', 'expr': {'op': 'NOT', 'arg': {'op': 'OR', 'args': [{'field': 'vendor_type', 'cmp': '==', 'value': 'restaurant'}, {'field': 'amount_usd', 'cmp': '<=', 'value': '10'}]}}}], [{'expense_id': 'a', 'amount_usd': '9', 'vendor_type': 'taxi'}, {'expense_id': 'b', 'amount_usd': '11', 'vendor_type': 'taxi'}, {'expense_id': 'c', 'amount_usd': '20', 'vendor_type': 'restaurant'}])

Expected Output: {'b': ['X']}

Explanation: Only expense `b` makes the inner `OR` false, so the outer `NOT` becomes true.

Input: ([{'rule_id': 'Y', 'expr': {'field': 'expense_type', 'cmp': '!=', 'value': 'meals'}}], [])

Expected Output: {}

Explanation: Edge case: there are rules, but no expenses to evaluate.

Hints

  1. A recursive evaluator is a natural fit for nested `AND`/`OR`/`NOT` expressions.
  2. Use short-circuiting: for `AND`, stop on the first false child; for `OR`, stop on the first true child.

Part 3: Optimize Rule Evaluation with Short-Circuiting, Caching, and Pre-Aggregation

Implement an optimized rules engine `solution(rules, expenses, blocklisted_vendors)`. Rules may have scope `expense` or `trip`. Expressions use the same boolean structure as Part 2, but leaf predicates are one of: `{'type': 'field', 'field': str, 'cmp': op, 'value': str, 'cost': int}`, `{'type': 'blocklist_contains', 'field': 'vendor_name', 'cost': int}`, `{'type': 'trip_total', 'cmp': op, 'value': str, 'cost': int}`, or `{'type': 'trip_meals_total', 'cmp': op, 'value': str, 'cost': int}`. To make optimizations observable, also return stats. Your evaluator must: (1) short-circuit boolean expressions, (2) evaluate lower-cost children before higher-cost children inside `AND` and `OR`, (3) cache repeated leaf results for the same expense or trip, and (4) pre-aggregate trip totals and trip meal totals once up front.

Constraints

  • `0 <= len(expenses), len(rules) <= 10000`
  • The total number of expression nodes across all rules is at most `100000`
  • Each `cost` is a positive integer, and all `expense_id` values are unique

Examples

Input: ([{'rule_id': 'E1', 'scope': 'expense', 'expr': {'op': 'AND', 'args': [{'type': 'blocklist_contains', 'field': 'vendor_name', 'cost': 10}, {'type': 'field', 'field': 'amount_usd', 'cmp': '>', 'value': '100', 'cost': 1}]}}, {'rule_id': 'E2', 'scope': 'expense', 'expr': {'op': 'OR', 'args': [{'type': 'blocklist_contains', 'field': 'vendor_name', 'cost': 10}, {'type': 'field', 'field': 'expense_type', 'cmp': '==', 'value': 'airfare', 'cost': 1}]}}, {'rule_id': 'T1', 'scope': 'trip', 'expr': {'type': 'trip_total', 'cmp': '>', 'value': '2000', 'cost': 1}}, {'rule_id': 'T2', 'scope': 'trip', 'expr': {'type': 'trip_meals_total', 'cmp': '>', 'value': '200', 'cost': 1}}], [{'expense_id': 'a', 'trip_id': 't1', 'amount_usd': '50', 'expense_type': 'supplies', 'vendor_name': 'BadVendor'}, {'expense_id': 'b', 'trip_id': 't1', 'amount_usd': '150', 'expense_type': 'supplies', 'vendor_name': 'BadVendor'}, {'expense_id': 'c', 'trip_id': 't1', 'amount_usd': '2100', 'expense_type': 'lodging', 'vendor_name': 'GoodHotel'}], {'BadVendor'})

Expected Output: {'expense_violations': {'a': ['E2'], 'b': ['E1', 'E2']}, 'trip_violations': {'t1': ['T1']}, 'stats': {'expensive_lookups': 3, 'trips_preaggregated': 1}}

Explanation: Ordering, short-circuiting, and caching reduce blocklist checks: the repeated vendor predicate is not recomputed for the same expense.

Input: ([{'rule_id': 'R', 'scope': 'expense', 'expr': {'op': 'AND', 'args': [{'type': 'blocklist_contains', 'field': 'vendor_name', 'cost': 10}, {'type': 'field', 'field': 'expense_type', 'cmp': '==', 'value': 'meals', 'cost': 1}]}}], [{'expense_id': '1', 'trip_id': 'x', 'amount_usd': '20', 'expense_type': 'taxi', 'vendor_name': 'BadVendor'}], {'BadVendor'})

Expected Output: {'expense_violations': {}, 'trip_violations': {}, 'stats': {'expensive_lookups': 0, 'trips_preaggregated': 1}}

Explanation: The cheap predicate is false, so the expensive blocklist lookup is skipped entirely.

Input: ([], [], set())

Expected Output: {'expense_violations': {}, 'trip_violations': {}, 'stats': {'expensive_lookups': 0, 'trips_preaggregated': 0}}

Explanation: Edge case: no rules and no expenses.

Input: ([{'rule_id': 'E', 'scope': 'expense', 'expr': {'op': 'OR', 'args': [{'type': 'blocklist_contains', 'field': 'vendor_name', 'cost': 10}, {'type': 'field', 'field': 'expense_type', 'cmp': '==', 'value': 'airfare', 'cost': 1}]}}, {'rule_id': 'T', 'scope': 'trip', 'expr': {'type': 'trip_meals_total', 'cmp': '>', 'value': '200', 'cost': 1}}], [{'expense_id': '1', 'trip_id': 't2', 'amount_usd': '30', 'expense_type': 'airfare', 'vendor_name': 'GoodAir'}, {'expense_id': '2', 'trip_id': 't2', 'amount_usd': '190', 'expense_type': 'meals', 'vendor_name': 'Cafe'}, {'expense_id': '3', 'trip_id': 't2', 'amount_usd': '20', 'expense_type': 'meals', 'vendor_name': 'Cafe2'}], {'BadVendor'})

Expected Output: {'expense_violations': {'1': ['E']}, 'trip_violations': {'t2': ['T']}, 'stats': {'expensive_lookups': 2, 'trips_preaggregated': 1}}

Explanation: The airfare expense makes the cheap side of the `OR` true, so its expensive lookup is avoided. The trip exceeds the meal-total limit.

Hints

  1. Before evaluating any rules, compute `trip_total` and `trip_meals_total` for every trip in one pass.
  2. Use a cache key based on `(context_id, predicate)` and ignore the `cost` field when deciding whether two predicates are the same.
Last updated: Apr 19, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement a Searchable Logger Pipeline - Rippling (hard)
  • Implement an In-Memory File System - Rippling
  • Compare Complete and Partial Poker Hands - Rippling (medium)
  • Implement Courier Delivery Cost Tracking - Rippling (medium)
  • Implement Article Vote Tracking - Rippling (medium)