Rule Evaluation Engine for Expenses

Problem: Build an Expense Rule Evaluation Engine Given a list of expenses and a list of business rules, implement a rule evaluation engine that reports all rule violations. Expense Fields Each expense contains: expenseId: string tripId: string amount: integer vendorName: string vendorType: string, such as Food, Travel, Entertainment Rule Fields Each rule contains: ruleId: string ruleType: string key: string. Use - if the rule does not need a key limit: integer amount limit Support the following 3 rule types: MAX_EXPENSE_BY_VENDOR_TYPE key limit For every expense whose vendorType == key, the single expense amount must not exceed limit. MAX_TRIP_TOTAL - limit For every trip, the sum of all expenses under the same tripId must not exceed limit. MAX_TOTAL_BY_VENDOR_TYPE key limit The total amount of all expenses whose vendorType == key must not exceed limit. Input Format R E ruleId ruleType key limit ... R lines expenseId tripId amount vendorName vendorType ... E lines Constraints: 1 <= R <= 10^4 1 <= E <= 10^5 0 <= amount, limit <= 10^9 No field contains spaces. Output Format Print every violation in the following format: ruleId entityId value Meaning: For MAX_EXPENSE_BY_VENDOR_TYPE, entityId is expenseId, and value is the expense amount. For MAX_TRIP_TOTAL, entityId is tripId, and value is the trip total. For MAX_TOTAL_BY_VENDOR_TYPE, entityId is vendorType, and value is the vendor type total. Ordering: Process rules in input order. For the same rule, output violating entities in ascending lexicographical order of entityId. If there is no violation, print: OK Example Input: 3 5 r1 MAX_TRIP_TOTAL - 100 r2 MAX_EXPENSE_BY_VENDOR_TYPE Food 50 r3 MAX_TOTAL_BY_VENDOR_TYPE Entertainment 80 e1 t1 40 Uber Travel e2 t1 70 Sushi Food e3 t2 60 Movie Entertainment e4 t2 30 Game Entertainment e5 t3 10 Cafe Food Output: r1 t1 110 r2 e2 70 r3 Entertainment 90 Example Input 3 5 r1 MAX_TRIP_TOTAL - 100 r2 MAX_EXPENSE_BY_VENDOR_TYPE Food 50 r3 MAX_TOTAL_BY_VENDOR_TYPE Entertainment 80 e1 t1 40 Uber Travel e2 t1 70 Sushi Food e3 t2 60 Movie Entertainment e4 t2 30 Game Entertainment e5 t3 10 Cafe Food Output r1 t1 110 r2 e2 70 r3 Entertainment 90