Quick Overview

Evaluate configurable expense and trip-sum rules using exact cents, reusable typed predicates, strict thresholds, multiple flags, and deterministic result ordering.

Evaluate Expense and Trip-Level Rules as Data

Company: Rippling

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Evaluate expense-level rules and trip-level spending rules. Rules must be supplied as data; do not hard-code a separate branch for each business rule. Implement `evaluate_expense_rules(expenses: string[][], rules: string[][], conditions: string[][]) -> string[][]`. ### Input Contract The homogeneous table representation, operator vocabulary, and result order below are explicit practice choices. Amounts are integer cents to avoid floating-point money errors. - Each expense is `[expenseId,tripId,amountCents,expenseType,vendorType,vendorName]`. IDs are unique and all fields are present. There are at most 10000 expenses, 100 rules, and 1000 conditions. Amounts are nonnegative and at most 100000000 cents. Use wide integers for group sums. - Each rule is `[ruleId,scope,thresholdCents]`, with unique ruleId. Scope is `EXPENSE` or `TRIP_SUM`. For EXPENSE, thresholdCents is the empty string. For TRIP_SUM, it is a nonnegative integer threshold. - Each condition is `[ruleId,field,operator,value]`. Conditions with the same ruleId are combined with AND. Zero conditions means every expense matches. Conditions always reference an existing rule. - Fields are `expense_id`, `trip_id`, `amount_cents`, `expense_type`, `vendor_type`, or `vendor_name`. - For `amount_cents`, operators are EQ, NE, GT, GE, LT, LE and values are valid nonnegative integer strings, compared numerically. Other fields support EQ and NE with exact case-sensitive string comparison. No malformed rules are supplied. - An EXPENSE rule flags each matching expense. A TRIP_SUM rule sums amounts of matching expenses separately within each trip, then flags a trip only if its sum is strictly greater than threshold. A trip with no matching expenses has sum zero and is not flagged by these nonnegative thresholds. ### Output Contract Return `[scope,subjectId,ruleId,actualCents]` for every violation. SubjectId is an expense ID or trip ID. ActualCents is that expense amount or filtered trip sum, formatted as an integer string. Sort by rule order in the input; within an EXPENSE rule use expense input order, and within a TRIP_SUM rule use lexicographically ascending trip ID. The reported initial policies can all be expressed in this format: restaurant amount above 7500 cents; airfare expenses; entertainment expenses; any expense above 25000 cents; trip total above 200000 cents; and trip meals above 20000 cents. Multiple violations for the same expense are retained. ### Example ```text expenses = [["e1","t1","8000","meals","restaurant","Cafe"], ["e2","t1","30000","airfare","airline","Air"]] rules = [["restaurant_limit","EXPENSE",""], ["trip_limit","TRIP_SUM","35000"]] conditions = [["restaurant_limit","vendor_type","EQ","restaurant"], ["restaurant_limit","amount_cents","GT","7500"]] result = [["EXPENSE","e1","restaurant_limit","8000"], ["TRIP_SUM","t1","trip_limit","38000"]] ``` Explain the separation between condition evaluation, aggregation, and business-rule configuration. Discuss how a registry of supported operators can allow extension without adding a branch for every new manager-defined rule. Composite AND/OR/NOT trees are a separate design follow-up, not part of this function's grammar. ```hint Share predicates across scopes A rule's conditions can evaluate one expense regardless of whether the result triggers an immediate flag or contributes to a trip aggregate. ```

Overview: Evaluate configurable expense and trip-sum rules using exact cents, reusable typed predicates, strict thresholds, multiple flags, and deterministic result ordering.

Read the full Rippling Software Engineer interview experience this question came from

Evaluate expense-level rules and trip-level spending rules. Rules must be supplied as data; do not hard-code a separate branch for each business rule. Implement `evaluate_expense_rules(expenses: string[][], rules: string[][], conditions: string[][]) -> string[][]`. ### Input Contract The homogeneous table representation, operator vocabulary, and result order below are explicit practice choices. Amounts are integer cents to avoid floating-point money errors. - Each expense is `[expenseId,tripId,amountCents,expenseType,vendorType,vendorName]`. IDs are unique and all fields are present. There are at most 10000 expenses, 100 rules, and 1000 conditions. Amounts are nonnegative and at most 100000000 cents. Use wide integers for group sums. - Each rule is `[ruleId,scope,thresholdCents]`, with unique ruleId. Scope is `EXPENSE` or `TRIP_SUM`. For EXPENSE, thresholdCents is the empty string. For TRIP_SUM, it is a nonnegative integer threshold. - Each condition is `[ruleId,field,operator,value]`. Conditions with the same ruleId are combined with AND. Zero conditions means every expense matches. Conditions always reference an existing rule. - Fields are `expense_id`, `trip_id`, `amount_cents`, `expense_type`, `vendor_type`, or `vendor_name`. - For `amount_cents`, operators are EQ, NE, GT, GE, LT, LE and values are valid nonnegative integer strings, compared numerically. Other fields support EQ and NE with exact case-sensitive string comparison. No malformed rules are supplied. - An EXPENSE rule flags each matching expense. A TRIP_SUM rule sums amounts of matching expenses separately within each trip, then flags a trip only if its sum is strictly greater than threshold. A trip with no matching expenses has sum zero and is not flagged by these nonnegative thresholds. ### Output Contract Return `[scope,subjectId,ruleId,actualCents]` for every violation. SubjectId is an expense ID or trip ID. ActualCents is that expense amount or filtered trip sum, formatted as an integer string. Sort by rule order in the input; within an EXPENSE rule use expense input order, and within a TRIP_SUM rule use lexicographically ascending trip ID. The reported initial policies can all be expressed in this format: restaurant amount above 7500 cents; airfare expenses; entertainment expenses; any expense above 25000 cents; trip total above 200000 cents; and trip meals above 20000 cents. Multiple violations for the same expense are retained. ### Example ```text expenses = [["e1","t1","8000","meals","restaurant","Cafe"], ["e2","t1","30000","airfare","airline","Air"]] rules = [["restaurant_limit","EXPENSE",""], ["trip_limit","TRIP_SUM","35000"]] conditions = [["restaurant_limit","vendor_type","EQ","restaurant"], ["restaurant_limit","amount_cents","GT","7500"]] result = [["EXPENSE","e1","restaurant_limit","8000"], ["TRIP_SUM","t1","trip_limit","38000"]] ``` Explain the separation between condition evaluation, aggregation, and business-rule configuration. Discuss how a registry of supported operators can allow extension without adding a branch for every new manager-defined rule. Composite AND/OR/NOT trees are a separate design follow-up, not part of this function's grammar. ```hint Share predicates across scopes A rule's conditions can evaluate one expense regardless of whether the result triggers an immediate flag or contributes to a trip aggregate. ```

Constraints

  • At most 10000 expense rows, 100 unique-ID rules and 1000 conditions; every condition references an existing rule.
  • Expenses are [expenseId,tripId,amountCents,expenseType,vendorType,vendorName]; expense IDs are unique and amounts are between 0 and 100000000 cents.
  • Rules are [ruleId,EXPENSE,empty string] or [ruleId,TRIP_SUM,nonnegative integer threshold]; threshold and condition numeric strings have no stated upper bound.
  • Conditions AND together, with none matching every expense. Numeric amount operators are EQ, NE, GT, GE, LT, LE; other supported fields use exact case-sensitive EQ or NE.
  • TRIP_SUM totals only matching expenses within each trip and flags strictly greater sums; nonmatching trips do not flag.
  • Return [scope,subjectId,ruleId,actualCents] sorted by rule input order, then expense input order or lexicographic trip ID. Retain multiple violations.

Examples

Input: ([['e1', 't1', '8000', 'meals', 'restaurant', 'Cafe'], ['e2', 't1', '30000', 'airfare', 'airline', 'Air']], [['restaurant_limit', 'EXPENSE', ''], ['trip_limit', 'TRIP_SUM', '35000']], [['restaurant_limit', 'vendor_type', 'EQ', 'restaurant'], ['restaurant_limit', 'amount_cents', 'GT', '7500']])

Expected Output: [['EXPENSE', 'e1', 'restaurant_limit', '8000'], ['TRIP_SUM', 't1', 'trip_limit', '38000']]

Explanation: The source example separates matching predicates and filtered aggregation.

Input: ([['z', 't2', '5', 'meal', 'v', 'N'], ['a', 't10', '7', 'meal', 'v', 'N'], ['b', 't2', '3', 'other', 'v', 'N']], [['Z', 'TRIP_SUM', '6'], ['A', 'EXPENSE', '']], [])

Expected Output: [['TRIP_SUM', 't10', 'Z', '7'], ['TRIP_SUM', 't2', 'Z', '8'], ['EXPENSE', 'z', 'A', '5'], ['EXPENSE', 'a', 'A', '7'], ['EXPENSE', 'b', 'A', '3']]

Explanation: Rule order, lexicographic trip order and expense input order are distinct.

Loading coding console...

Show the approach

Approach

Index conditions by rule ID and map supported field names to expense columns. The reusable predicate layer evaluates each configured condition; all must pass, and the empty conjunction is true. Numeric predicates compare normalized nonnegative decimal strings by digit count and then lexicographically. This supports arbitrarily large thresholds and condition values without inventing a numeric bound or requiring big integers; only bounded expense amounts are parsed for summation. Nonamount fields use exact case-sensitive equality. For each rule, scan expenses in input order. EXPENSE immediately appends each matching expense, while TRIP_SUM accumulates matching amounts by trip and then emits only sums strictly above the threshold in sorted trip order. Each sum is at most 10000100000000=1000000000000, safe in signed 64-bit arithmetic and JavaScript exact integers. A zero or missing match sum never exceeds a nonnegative threshold. The outer rule loop establishes rule order, and no deduplication removes distinct violations. This separates data-defined business policies from the fixed operator vocabulary; a registry of operator evaluators can extend that vocabulary without branching on manager rule IDs. AND/OR/NOT trees would require a separately defined predicate grammar. Let E,R,C,T be expense, rule, total-condition and trip counts. Ignoring string-character costs, predicate evaluation takes O(E(R+C)); grouping/sorting adds up to O(RElog(T+1)) in the map-based variant, with hash-map variants taking O(RTlog(T+1)) for final sorting instead. Normalizing arbitrary numeric strings costs their full input length; comparisons also include any inspected string characters. Auxiliary state is O(E+C+T), plus copied string characters and output.

Time complexity:
O(E*(R+C) + R*E*log(T+1)) upper bound, plus string processing and output
Space complexity:
O(E + C + T) auxiliary entries, plus stored strings and output