LLD Problem

Design Splitwise

Expense sharing application with multiple split types, balance tracking, and debt simplification.

1Problem Statement

Design an expense sharing application that allows users to:

Add expenses and split them among users
Track balances (who owes whom)
Support multiple split types (Equal, Exact, Percentage, Share)
Manage groups for recurring expenses
Settle debts and simplify transactions
Handle multi-currency support

2Requirements

Functional Requirements

✓User management & friends
✓Create/Edit/Delete expenses
✓Group management
✓Balance calculation
✓Debt simplification
✓Settlement tracking
✓Expense reports

Non-Functional Requirements

✓P95 latency < 200ms
✓99.9% availability
✓10M+ users support
✓ACID transactions
✓Multi-region replication
✓Strong security (OAuth 2.0)

3Core Entities

Entity	Key Attributes	Relationships
User	userId, name, email, currency	1-to-Many Expenses, Balances
Group	groupId, name, createdBy	1-to-Many GroupMember, Expenses
Expense	expenseId, amount, paidBy, date	1-to-Many ExpenseSplit
ExpenseSplit	splitId, userId, amount, type	Many-to-1 Expense, User
Balance	balanceId, userOwes, userOwed, amount	Many-to-1 User (both sides)
Settlement	settlementId, paidBy, paidTo, amount	Many-to-1 User (both sides)

4Class Diagram

Domain Model


    ┌─────────────────┐         ┌─────────────────┐
    │      User       │         │      Group      │
    ├─────────────────┤         ├─────────────────┤
    │ - userId        │         │ - groupId       │
    │ - name          │◄───────►│ - name          │
    │ - email         │ members │ - members[]     │
    │ - balanceSheet  │         │ - expenses[]    │
    └────────┬────────┘         └────────┬────────┘
             │                           │
             │ creates                   │ contains
             ▼                           ▼
    ┌─────────────────────────────────────────────┐
    │                  Expense                     │
    ├─────────────────────────────────────────────┤
    │ - expenseId: String                          │
    │ - description: String                        │
    │ - amount: double                             │
    │ - paidBy: User                               │
    │ - splits: List<ExpenseSplit>                 │
    │ - splitType: SplitType                       │
    └──────────────────────┬──────────────────────┘
                           │
                           │ has many
                           ▼
    ┌─────────────────────────────────────────────┐
    │                ExpenseSplit                  │
    ├─────────────────────────────────────────────┤
    │ - user: User                                 │
    │ - amount: double                             │
    └─────────────────────────────────────────────┘

Strategy Pattern for Splits


            ┌──────────────────────────────────────┐
            │    <<interface>> SplitStrategy       │
            ├──────────────────────────────────────┤
            │ + split(amount, users): List<Split>  │
            │ + validate(splits, total): boolean   │
            └──────────────────────────────────────┘
                             ▲
           ┌─────────────────┼─────────────────┐
           │                 │                 │
    ┌──────┴──────┐   ┌──────┴──────┐   ┌──────┴──────┐
    │ EqualSplit  │   │ ExactSplit  │   │PercentSplit │
    ├─────────────┤   ├─────────────┤   ├─────────────┤
    │ amount / n  │   │ user inputs │   │ % of total  │
    └─────────────┘   └─────────────┘   └─────────────┘

5Key Flows

1. Create Expense Flow

User Input

User enters expense details: amount, description, participants

↓

Validate

Check if amount > 0, participants exist, payer is valid

↓

Select Split Type

Choose: EQUAL | EXACT | PERCENTAGE | SHARE

↓

Calculate Splits

Strategy pattern calculates each participant's share

↓

Validate Splits

Ensure sum(splits) == totalAmount

↓

Save & Update

Save expense, update balances, notify users

2. Debt Simplification Flow

Get Balances

Fetch all balances for group members

↓

Calculate Net

For each user: netBalance = owed - owes

↓

Separate Users

Creditors (positive) vs Debtors (negative)

↓

Sort Lists

Sort both by amount descending

↓

Greedy Match

Match largest creditor with largest debtor

↓

Output

Minimized list of transactions

6Algorithms

Debt Simplification - Greedy Algorithm

Problem: Minimize number of transactions in a group

Steps:

Calculate net balance for each user (total owed - total owes)
Create creditors list (positive balance) and debtors list (negative balance)
Sort both lists by absolute amount (descending)
Match largest creditor with largest debtor
Settle min(creditor_amount, |debtor_amount|)
Remove settled users, repeat until all balanced

Complexity: O(n²) where n = number of users

Optimization: Cache results per group, invalidate on new expense

Balance Calculation - Incremental Update

Strategy: Update balances incrementally, not full recalculation

On Expense Creation:

For each split where participant ≠ payer
Fetch or create balance(payer, participant)
Update balance += split_amount
Save balance

Performance: O(m) where m = number of participants

7Design Patterns

Strategy Pattern

Where: Split calculation logic

Why: Different split types need different algorithms. Easily extensible.

EqualSplitExactSplitPercentSplitShareSplit

Factory Pattern

Where: Creating split strategies

Why: Centralize object creation. Hide instantiation complexity.

SplitStrategyFactory

Singleton Pattern

Where: SplitwiseService

Why: Global access. Single instance. Resource optimization.

getInstance()

Observer Pattern

Where: Notification system

Why: Decouple expense creation from notifications.

EmailPushSMS

Builder Pattern

Where: Expense creation

Why: Many optional fields. Improve readability. Validate construction.

ExpenseBuilder

Repository Pattern

Where: Data access layer

Why: Abstract database operations. Enable easy testing with mocks.

ExpenseRepoBalanceRepo

8API Design

User APIs

Method	Endpoint	Description
POST	/api/v1/users	Register new user
GET	/api/v1/users/{userId}	Get user details
GET	/api/v1/users/{userId}/balances	Get all user balances

Expense APIs

Method	Endpoint	Description
POST	/api/v1/expenses	Create new expense
GET	/api/v1/expenses/{expenseId}	Get expense details
PUT	/api/v1/expenses/{expenseId}	Update expense
DELETE	/api/v1/expenses/{expenseId}	Delete expense

Group & Settlement APIs

Method	Endpoint	Description
POST	/api/v1/groups	Create new group
POST	/api/v1/groups/{groupId}/members	Add member to group
POST	/api/v1/groups/{groupId}/simplify	Simplify group debts
POST	/api/v1/settlements	Record settlement

9Java Implementation

Enums and Interfacesjava

public enum SplitType {
    EQUAL, EXACT, PERCENTAGE, SHARE
}

public interface SplitStrategy {
    List<Split> split(double amount, List<User> users, Map<String, Double> data);
    boolean validate(List<Split> splits, double totalAmount);
}

Split Strategiesjava

public class EqualSplitStrategy implements SplitStrategy {
    @Override
    public List<Split> split(double amount, List<User> users, Map<String, Double> data) {
        double splitAmount = Math.round(amount / users.size() * 100.0) / 100.0;
        return users.stream()
            .map(user -> new Split(user, splitAmount))
            .collect(Collectors.toList());
    }
    
    @Override
    public boolean validate(List<Split> splits, double totalAmount) {
        double sum = splits.stream().mapToDouble(Split::getAmount).sum();
        return Math.abs(sum - totalAmount) < 0.01;
    }
}

public class ExactSplitStrategy implements SplitStrategy {
    @Override
    public List<Split> split(double amount, List<User> users, Map<String, Double> exactAmounts) {
        return users.stream()
            .map(user -> new Split(user, exactAmounts.getOrDefault(user.getId(), 0.0)))
            .collect(Collectors.toList());
    }
    
    @Override
    public boolean validate(List<Split> splits, double totalAmount) {
        double sum = splits.stream().mapToDouble(Split::getAmount).sum();
        return Math.abs(sum - totalAmount) < 0.01;
    }
}

public class PercentageSplitStrategy implements SplitStrategy {
    @Override
    public List<Split> split(double amount, List<User> users, Map<String, Double> percentages) {
        return users.stream()
            .map(user -> {
                double pct = percentages.getOrDefault(user.getId(), 0.0);
                double splitAmount = Math.round(amount * pct / 100.0 * 100.0) / 100.0;
                return new Split(user, splitAmount);
            })
            .collect(Collectors.toList());
    }
    
    @Override
    public boolean validate(List<Split> splits, double totalAmount) {
        double sum = splits.stream().mapToDouble(Split::getAmount).sum();
        return Math.abs(sum - totalAmount) < 0.01;
    }
}

Core Classesjava

public class User {
    private String id;
    private String name;
    private String email;
    private Map<String, Double> balanceSheet = new ConcurrentHashMap<>();
    
    public User(String id, String name, String email) {
        this.id = id;
        this.name = name;
        this.email = email;
    }
    
    public void updateBalance(String userId, double amount) {
        balanceSheet.merge(userId, amount, Double::sum);
        // Clean up zero balances
        if (Math.abs(balanceSheet.getOrDefault(userId, 0.0)) < 0.01) {
            balanceSheet.remove(userId);
        }
    }
    
    public double getNetBalance() {
        return balanceSheet.values().stream().mapToDouble(Double::doubleValue).sum();
    }
    
    public Map<String, Double> getBalanceSheet() {
        return new HashMap<>(balanceSheet);
    }
    
    // Getters
    public String getId() { return id; }
    public String getName() { return name; }
}

public class Split {
    private User user;
    private double amount;
    
    public Split(User user, double amount) {
        this.user = user;
        this.amount = amount;
    }
    
    public User getUser() { return user; }
    public double getAmount() { return amount; }
}

public class Expense {
    private String id;
    private String description;
    private double amount;
    private User paidBy;
    private List<Split> splits;
    private SplitType splitType;
    private LocalDateTime createdAt;
    
    public Expense(String id, String description, double amount, 
                   User paidBy, List<Split> splits, SplitType splitType) {
        this.id = id;
        this.description = description;
        this.amount = amount;
        this.paidBy = paidBy;
        this.splits = splits;
        this.splitType = splitType;
        this.createdAt = LocalDateTime.now();
    }
    
    // Getters
    public String getId() { return id; }
    public double getAmount() { return amount; }
    public User getPaidBy() { return paidBy; }
    public List<Split> getSplits() { return splits; }
}

public class Group {
    private String id;
    private String name;
    private List<User> members = new ArrayList<>();
    private List<Expense> expenses = new ArrayList<>();
    
    public Group(String id, String name, User createdBy) {
        this.id = id;
        this.name = name;
        this.members.add(createdBy);
    }
    
    public void addMember(User user) {
        if (members.stream().noneMatch(m -> m.getId().equals(user.getId()))) {
            members.add(user);
        }
    }
    
    public void addExpense(Expense expense) {
        expenses.add(expense);
    }
    
    public List<User> getMembers() { return members; }
}

SplitwiseService (Singleton)java

public class SplitwiseService {
    private static SplitwiseService instance;
    
    private Map<String, User> users = new ConcurrentHashMap<>();
    private Map<String, Group> groups = new ConcurrentHashMap<>();
    private Map<String, Expense> expenses = new ConcurrentHashMap<>();
    private Map<SplitType, SplitStrategy> strategies = new EnumMap<>(SplitType.class);
    
    private SplitwiseService() {
        strategies.put(SplitType.EQUAL, new EqualSplitStrategy());
        strategies.put(SplitType.EXACT, new ExactSplitStrategy());
        strategies.put(SplitType.PERCENTAGE, new PercentageSplitStrategy());
    }
    
    public static synchronized SplitwiseService getInstance() {
        if (instance == null) {
            instance = new SplitwiseService();
        }
        return instance;
    }
    
    public void addUser(User user) {
        users.put(user.getId(), user);
    }
    
    public Expense addExpense(String description, double amount, String payerId,
                              List<String> participantIds, SplitType splitType,
                              Map<String, Double> splitData) {
        User payer = users.get(payerId);
        if (payer == null) throw new IllegalArgumentException("Payer not found");
        
        List<User> participants = participantIds.stream()
            .map(users::get)
            .filter(Objects::nonNull)
            .collect(Collectors.toList());
        
        SplitStrategy strategy = strategies.get(splitType);
        List<Split> splits = strategy.split(amount, participants, splitData);
        
        if (!strategy.validate(splits, amount)) {
            throw new IllegalArgumentException("Split amounts don't match total");
        }
        
        String expenseId = "EXP-" + System.currentTimeMillis();
        Expense expense = new Expense(expenseId, description, amount, payer, splits, splitType);
        expenses.put(expenseId, expense);
        
        updateBalances(expense);
        return expense;
    }
    
    private void updateBalances(Expense expense) {
        User payer = expense.getPaidBy();
        
        for (Split split : expense.getSplits()) {
            if (split.getUser().getId().equals(payer.getId())) continue;
            
            User participant = split.getUser();
            double amount = split.getAmount();
            
            // Payer is owed this amount
            payer.updateBalance(participant.getId(), amount);
            // Participant owes payer
            participant.updateBalance(payer.getId(), -amount);
        }
    }
    
    public void settleUp(String payerId, String payeeId, double amount) {
        User payer = users.get(payerId);
        User payee = users.get(payeeId);
        
        if (payer == null || payee == null) {
            throw new IllegalArgumentException("User not found");
        }
        
        payer.updateBalance(payeeId, amount);
        payee.updateBalance(payerId, -amount);
    }
    
    public Map<String, Double> getBalances(String userId) {
        User user = users.get(userId);
        if (user == null) throw new IllegalArgumentException("User not found");
        return user.getBalanceSheet();
    }
}

Debt Simplificationjava

public class DebtSimplifier {
    
    public List<Transaction> simplifyDebts(List<User> users) {
        // Step 1: Calculate net balance for each user
        Map<String, Double> netBalances = new HashMap<>();
        for (User user : users) {
            netBalances.put(user.getId(), user.getNetBalance());
        }
        
        // Step 2: Separate into creditors and debtors
        List<UserBalance> creditors = new ArrayList<>();
        List<UserBalance> debtors = new ArrayList<>();
        
        for (Map.Entry<String, Double> entry : netBalances.entrySet()) {
            double balance = entry.getValue();
            if (balance > 0.01) {
                creditors.add(new UserBalance(entry.getKey(), balance));
            } else if (balance < -0.01) {
                debtors.add(new UserBalance(entry.getKey(), Math.abs(balance)));
            }
        }
        
        // Step 3: Sort by amount descending
        creditors.sort((a, b) -> Double.compare(b.amount, a.amount));
        debtors.sort((a, b) -> Double.compare(b.amount, a.amount));
        
        // Step 4: Greedy matching
        List<Transaction> transactions = new ArrayList<>();
        int i = 0, j = 0;
        
        while (i < creditors.size() && j < debtors.size()) {
            UserBalance creditor = creditors.get(i);
            UserBalance debtor = debtors.get(j);
            
            double settlementAmount = Math.min(creditor.amount, debtor.amount);
            
            transactions.add(new Transaction(
                debtor.userId,    // from
                creditor.userId,  // to
                settlementAmount
            ));
            
            creditor.amount -= settlementAmount;
            debtor.amount -= settlementAmount;
            
            if (creditor.amount < 0.01) i++;
            if (debtor.amount < 0.01) j++;
        }
        
        return transactions;
    }
    
    private static class UserBalance {
        String userId;
        double amount;
        
        UserBalance(String userId, double amount) {
            this.userId = userId;
            this.amount = amount;
        }
    }
}

public class Transaction {
    private String from;
    private String to;
    private double amount;
    
    public Transaction(String from, String to, double amount) {
        this.from = from;
        this.to = to;
        this.amount = amount;
    }
    
    @Override
    public String toString() {
        return from + " pays " + to + ": $" + String.format("%.2f", amount);
    }
}

Demo Usagejava

public class SplitwiseDemo {
    public static void main(String[] args) {
        SplitwiseService service = SplitwiseService.getInstance();
        
        // Create users
        User alice = new User("u1", "Alice", "alice@email.com");
        User bob = new User("u2", "Bob", "bob@email.com");
        User carol = new User("u3", "Carol", "carol@email.com");
        
        service.addUser(alice);
        service.addUser(bob);
        service.addUser(carol);
        
        // Alice pays $90 for dinner, split equally
        service.addExpense(
            "Dinner",
            90.0,
            "u1",  // Alice pays
            Arrays.asList("u1", "u2", "u3"),  // Split among all three
            SplitType.EQUAL,
            null
        );
        
        System.out.println("After dinner expense:");
        System.out.println("Alice balances: " + service.getBalances("u1"));
        // Output: {u2=30.0, u3=30.0}  (Bob and Carol owe Alice $30 each)
        
        System.out.println("Bob balances: " + service.getBalances("u2"));
        // Output: {u1=-30.0}  (Bob owes Alice $30)
        
        // Bob settles up with Alice
        service.settleUp("u2", "u1", 30.0);
        
        System.out.println("\nAfter Bob settles:");
        System.out.println("Alice balances: " + service.getBalances("u1"));
        // Output: {u3=30.0}  (Only Carol still owes Alice)
        
        System.out.println("Bob balances: " + service.getBalances("u2"));
        // Output: {}  (Bob is settled)
    }
}

10Interview Follow-up Questions

Handle Concurrent Expense Creation?

Optimistic locking with version field, database transactions with READ_COMMITTED isolation, idempotency keys, queue-based balance updates.

Multi-Currency Support?

Store native currency, use exchange rate service, convert at expense time (not current date), cache rates per day, display in user's preference.

Database Sharding Strategy?

Primary shard by user_id, secondary index on group_id. Users/Balances by user_id, Groups by group_id, Expenses by paid_by.

Handle Expense Deletion?

Soft delete (deleted_at timestamp), maintain audit trail, create compensating transactions to reverse balances, restrict deletion conditions.

Rate Limiting?

Token bucket algorithm, different limits per operation type, implement at API gateway (NGINX) and application level, use Redis for distributed limiting.

Data Consistency Across Services?

Saga pattern with choreography, Outbox pattern for reliable events, eventual consistency, compensating transactions on failure.

11Key Takeaways

1Strategy Pattern for split types makes adding new split logic easy (EQUAL, EXACT, PERCENTAGE, SHARE)

2Incremental balance updates on each expense instead of full recalculation for O(m) performance

3Debt simplification uses greedy algorithm to minimize transactions - O(n²) complexity

4ConcurrentHashMap for thread-safe balance management in multi-threaded environment

5Singleton SplitwiseService manages all users, groups, and expenses with centralized access

?Quiz

1. $120 expense split equally among 4 people. How much does each owe the payer?

2. What's the main benefit of debt simplification?

3. Why use Strategy pattern for split types?