fork download
copy 
  1. /*
  2.  * Expense Policy Rule Engine
  3.  * 
  4.  * This is a low-level design problem that was asked in a Rippling interview.
  5.  * 
  6.  * Problem:
  7.  * You are given a list of expenses. Each expense belongs to a trip and has 
  8.  * an amount, type (restaurant, airfare, entertainment, etc.), and other details.
  9.  * The system needs to evaluate these expenses against company policies and 
  10.  * flag any violations with clear reasons.
  11.  * 
  12.  * Rules can be of two types:
  13.  * - Expense-level rules (checked on individual expenses)
  14.  *   e.g., restaurant expenses should not exceed $75, airfare not allowed
  15.  * - Trip-level rules (checked across all expenses of a trip)
  16.  *   e.g., total trip spend should not exceed a limit
  17.  * 
  18.  * New rules should be easy to add later without modifying existing code.
  19.  * 
  20.  * Approach:
  21.  * Instead of using a big if-else or creating a class for every expense type,
  22.  * I modeled the rules as strategies. Each rule is a separate class that 
  23.  * implements either ExpenseRule or TripRule. A RuleRegistry holds which 
  24.  * rules apply where, and a RuleEngine applies them and collects violations.
  25.  * 
  26.  * This keeps the design open for extension (new rules can be added by 
  27.  * writing a new class and registering it) and avoids duplicating logic.
  28.  * 
  29.  * Note: Everything is in one file here so it can run on Ideone. 
  30.  * In a normal project these would be split into separate classes and packages.
  31.  */
  32.  
  33. import java.util.*;
  34. import java.util.stream.Collectors;
  35.  
  36. enum ExpenseType {
  37.     RESTAURANT, AIRFARE, ENTERTAINMENT, HOTEL, SUPPLIES
  38. }
  39.  
  40. // Simple expense entity
  41. class Expense {
  42.     private final String expenseId;
  43.     private final String tripId;
  44.     private final double amountUSD;
  45.     private final ExpenseType type;
  46.  
  47.     public Expense(String expenseId, String tripId, double amountUSD, ExpenseType type) {
  48.         this.expenseId = expenseId;
  49.         this.tripId = tripId;
  50.         this.amountUSD = amountUSD;
  51.         this.type = type;
  52.     }
  53.  
  54.     public String getExpenseId() { return expenseId; }
  55.     public String getTripId() { return tripId; }
  56.     public double getAmountUSD() { return amountUSD; }
  57.     public ExpenseType getType() { return type; }
  58.  
  59.     @Override
  60.     public String toString() {
  61.         return "Expense{" + expenseId + ", trip=" + tripId + ", $" + amountUSD + ", " + type + "}";
  62.     }
  63. }
  64.  
  65. // Represents a rule violation with a message
  66. class Violation {
  67.     private final String message;
  68.  
  69.     private Violation(String message) {
  70.         this.message = message;
  71.     }
  72.  
  73.     // Factory method so we don't expose the constructor
  74.     public static Violation of(String message) {
  75.         return new Violation(message);
  76.     }
  77.  
  78.     public String getMessage() { return message; }
  79.  
  80.     @Override
  81.     public String toString() {
  82.         return "Violation: " + message;
  83.     }
  84. }
  85.  
  86. // Strategy interface for expense-level rules
  87. interface ExpenseRule {
  88.     Optional<Violation> check(Expense expense);
  89. }
  90.  
  91. // Strategy interface for trip-level rules
  92. interface TripRule {
  93.     Optional<Violation> check(List<Expense> expenses);
  94. }
  95.  
  96. // Rule that disallows a specific expense type entirely
  97. class DisallowRule implements ExpenseRule {
  98.     private final ExpenseType disallowedType;
  99.  
  100.     public DisallowRule(ExpenseType disallowedType) {
  101.         this.disallowedType = disallowedType;
  102.     }
  103.  
  104.     @Override
  105.     public Optional<Violation> check(Expense expense) {
  106.         if (expense.getType() == disallowedType) {
  107.             return Optional.of(Violation.of(disallowedType + " expenses are not allowed"));
  108.         }
  109.         return Optional.empty();
  110.     }
  111. }
  112.  
  113. // Rule that checks if an expense exceeds a maximum amount
  114. class MaxAmountRule implements ExpenseRule {
  115.     private final double maxAmount;
  116.  
  117.     public MaxAmountRule(double maxAmount) {
  118.         this.maxAmount = maxAmount;
  119.     }
  120.  
  121.     @Override
  122.     public Optional<Violation> check(Expense expense) {
  123.         if (expense.getAmountUSD() > maxAmount) {
  124.             return Optional.of(Violation.of(
  125.                 "Amount $" + expense.getAmountUSD() + " exceeds max allowed $" + maxAmount));
  126.         }
  127.         return Optional.empty();
  128.     }
  129. }
  130.  
  131. // Trip-level rule that checks total spend of a trip
  132. class TripTotalMaxRule implements TripRule {
  133.     private final double maxAmount;
  134.  
  135.     public TripTotalMaxRule(double maxAmount) {
  136.         this.maxAmount = maxAmount;
  137.     }
  138.  
  139.     @Override
  140.     public Optional<Violation> check(List<Expense> expenses) {
  141.         double total = expenses.stream().mapToDouble(Expense::getAmountUSD).sum();
  142.         if (total > maxAmount) {
  143.             return Optional.of(Violation.of(
  144.                 "Trip total $" + total + " exceeds max allowed $" + maxAmount));
  145.         }
  146.         return Optional.empty();
  147.     }
  148. }
  149.  
  150. // Holds all the rules. In a real system this would be loaded from config/DB.
  151. class RuleRegistry {
  152.     private final Map<ExpenseType, List<ExpenseRule>> typeRules = new HashMap<>();
  153.     private final List<ExpenseRule> globalExpenseRules = new ArrayList<>();
  154.     private final List<TripRule> tripRules = new ArrayList<>();
  155.  
  156.     public void addTypeRule(ExpenseType type, ExpenseRule rule) {
  157.         typeRules.computeIfAbsent(type, k -> new ArrayList<>()).add(rule);
  158.     }
  159.  
  160.     public void addGlobalExpenseRule(ExpenseRule rule) {
  161.         globalExpenseRules.add(rule);
  162.     }
  163.  
  164.     public void addTripRule(TripRule rule) {
  165.         tripRules.add(rule);
  166.     }
  167.  
  168.     // Returns both type-specific and global rules for an expense type
  169.     public List<ExpenseRule> getRulesFor(ExpenseType type) {
  170.         List<ExpenseRule> rules = new ArrayList<>(globalExpenseRules);
  171.         rules.addAll(typeRules.getOrDefault(type, Collections.emptyList()));
  172.         return rules;
  173.     }
  174.  
  175.     public List<TripRule> getTripRules() {
  176.         return tripRules;
  177.     }
  178. }
  179.  
  180. interface RuleEngine {
  181.     Map<String, List<Violation>> evaluate(List<Expense> expenses, RuleRegistry registry);
  182. }
  183.  
  184. class SimpleRuleEngine implements RuleEngine {
  185.     @Override
  186.     public Map<String, List<Violation>> evaluate(List<Expense> expenses, RuleRegistry registry) {
  187.         Map<String, List<Violation>> result = new LinkedHashMap<>();
  188.  
  189.         // Apply expense-level rules
  190.         for (Expense expense : expenses) {
  191.             List<Violation> violations = new ArrayList<>();
  192.             for (ExpenseRule rule : registry.getRulesFor(expense.getType())) {
  193.                 rule.check(expense).ifPresent(violations::add);
  194.             }
  195.             if (!violations.isEmpty()) {
  196.                 result.put(expense.getExpenseId(), violations);
  197.             }
  198.         }
  199.  
  200.         // Apply trip-level rules (group expenses by trip first)
  201.         Map<String, List<Expense>> byTrip = expenses.stream()
  202.             .collect(Collectors.groupingBy(Expense::getTripId));
  203.  
  204.         for (var entry : byTrip.entrySet()) {
  205.             String tripId = entry.getKey();
  206.             List<Expense> tripExpenses = entry.getValue();
  207.             List<Violation> tripViolations = new ArrayList<>();
  208.  
  209.             for (TripRule rule : registry.getTripRules()) {
  210.                 rule.check(tripExpenses).ifPresent(tripViolations::add);
  211.             }
  212.  
  213.             if (!tripViolations.isEmpty()) {
  214.                 result.computeIfAbsent("TRIP-" + tripId, k -> new ArrayList<>()).addAll(tripViolations);
  215.             }
  216.         }
  217.  
  218.         return result;
  219.     }
  220. }
  221.  
  222. public class Main {
  223.     public static void main(String[] args) {
  224.         // Sample expenses for demonstration
  225.         List<Expense> expenses = Arrays.asList(
  226.             new Expense("E1", "T1", 80, ExpenseType.RESTAURANT),
  227.             new Expense("E2", "T1", 120, ExpenseType.AIRFARE),
  228.             new Expense("E3", "T1", 40, ExpenseType.ENTERTAINMENT),
  229.             new Expense("E4", "T1", 200, ExpenseType.HOTEL)
  230.         );
  231.  
  232.         // Register the rules
  233.         RuleRegistry registry = new RuleRegistry();
  234.         registry.addTypeRule(ExpenseType.RESTAURANT, new MaxAmountRule(75));
  235.         registry.addTypeRule(ExpenseType.AIRFARE, new DisallowRule(ExpenseType.AIRFARE));
  236.         registry.addTypeRule(ExpenseType.ENTERTAINMENT, new DisallowRule(ExpenseType.ENTERTAINMENT));
  237.         registry.addGlobalExpenseRule(new MaxAmountRule(250));
  238.         registry.addTripRule(new TripTotalMaxRule(300));
  239.  
  240.         // Evaluate
  241.         RuleEngine engine = new SimpleRuleEngine();
  242.         Map<String, List<Violation>> violations = engine.evaluate(expenses, registry);
  243.  
  244.         System.out.println("=== Violations ===");
  245.         if (violations.isEmpty()) {
  246.             System.out.println("No violations found.");
  247.         } else {
  248.             violations.forEach((id, vList) -> {
  249.                 System.out.println(id + ":");
  250.                 vList.forEach(v -> System.out.println("  - " + v));
  251.             });
  252.         }
  253.     }
  254. }
Success #stdin #stdout 0.18s 59200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
=== Violations ===
E1:
  - Violation: Amount $80.0 exceeds max allowed $75.0
E2:
  - Violation: AIRFARE expenses are not allowed
E3:
  - Violation: ENTERTAINMENT expenses are not allowed
TRIP-T1:
  - Violation: Trip total $440.0 exceeds max allowed $300.0
https://ideone.com/sQFpir
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!