Episode 9 — System Design / 9.6 — LLD Problem Solving

9.6.d — Splitwise (Expense Sharing)

Problem: Design an expense-sharing application where users can create groups, add expenses with different split strategies (equal, exact, percentage), track balances, and simplify debts to minimize the number of transactions.

Table of Contents

  1. Requirements
  2. Entities and Enums
  3. Class Diagram
  4. Split Strategies
  5. Simplify Debts Algorithm
  6. Sequence Flow
  7. Complete Implementation
  8. Usage Walkthrough
  9. Edge Cases
  10. Key Takeaways

Requirements

Functional Requirements

  1. Users can register with a name, email, and phone.
  2. Users can create groups (e.g., "Trip to Goa", "Flat expenses").
  3. A user can add an expense to a group, specifying:
    • Who paid (the payer).
    • The total amount.
    • How to split among members (equal, exact amounts, or percentages).
  4. The system tracks balances — who owes whom and how much.
  5. The system can simplify debts to minimize the number of transactions.
  6. Users can view their overall balance and per-group balance.

Non-Functional Requirements

  • Amounts should be precise (handle rounding).
  • Extensible split strategies (future: by shares, by items).

Out of Scope

  • Payment integration.
  • Expense categories and analytics.
  • Recurring expenses.

Entities and Enums

┌────────────────────┐
│    SplitType        │
│────────────────────│
│  EQUAL              │
│  EXACT              │
│  PERCENTAGE         │
└────────────────────┘

How Each Split Works

Split TypeInputExample (Total: $300, 3 people)
EQUALJust the participantsEach pays $100
EXACTExact amount per personA: $150, B: $100, C: $50
PERCENTAGEPercentage per personA: 50%, B: 30%, C: 20% -> $150, $90, $60

Class Diagram

┌──────────────────────────────────┐
│            User                   │
│──────────────────────────────────│
│ - id: string                      │
│ - name: string                    │
│ - email: string                   │
│ - phone: string                   │
└──────────────────────────────────┘
         │
         │ belongs to many
         ▼
┌──────────────────────────────────┐
│            Group                  │
│──────────────────────────────────│
│ - id: string                      │
│ - name: string                    │
│ - members: User[]                 │
│ - expenses: Expense[]             │
│──────────────────────────────────│
│ + addMember(user): void           │
│ + addExpense(expense): void       │
│ + getBalances(): Map              │
│ + simplifyDebts(): Transaction[]  │
└──────────────┬───────────────────┘
               │ has-many
               ▼
┌──────────────────────────────────┐       ┌──────────────────────────────┐
│           Expense                 │       │      SplitStrategy (iface)    │
│──────────────────────────────────│       │──────────────────────────────│
│ - id: string                      │       │ + split(amount, splits): Map  │
│ - description: string             │       │ + validate(amount, splits)    │
│ - amount: number                  │       └──────────┬───────────────────┘
│ - paidBy: User                    │                  │ implemented by
│ - splits: Split[]                 │        ┌─────────┼──────────┐
│ - splitType: SplitType            │        ▼         ▼          ▼
│ - createdAt: Date                 │   EqualSplit  ExactSplit  PercentSplit
│──────────────────────────────────│
│ + getSplitAmounts(): Map          │
└──────────────────────────────────┘

┌──────────────────────────────────┐       ┌──────────────────────────────┐
│            Split                  │       │     ExpenseService            │
│──────────────────────────────────│       │──────────────────────────────│
│ - user: User                      │       │ - users: Map<id, User>        │
│ - amount: number (for EXACT)      │       │ - groups: Map<id, Group>      │
│ - percentage: number (for %)      │       │──────────────────────────────│
└──────────────────────────────────┘       │ + addUser(name, email, phone) │
                                            │ + createGroup(name, members)  │
                                            │ + addExpense(...)             │
                                            │ + getBalances(groupId)        │
                                            │ + simplifyDebts(groupId)      │
                                            │ + getUserBalance(userId)      │
                                            └──────────────────────────────┘

Split Strategies

Equal Split

Total: $300    Participants: [Alice, Bob, Charlie]

Each share = 300 / 3 = $100

If Alice paid:
  Bob   owes Alice $100
  Charlie owes Alice $100

Exact Split

Total: $300    Splits: [Alice: $150, Bob: $100, Charlie: $50]

Validation: 150 + 100 + 50 = 300  (must equal total)

If Alice paid:
  Bob owes Alice $100
  Charlie owes Alice $50
  (Alice's own share of $150 cancels out)

Percentage Split

Total: $300    Splits: [Alice: 50%, Bob: 30%, Charlie: 20%]

Validation: 50 + 30 + 20 = 100  (must equal 100%)

Amounts: Alice: $150, Bob: $90, Charlie: $60

If Alice paid:
  Bob owes Alice $90
  Charlie owes Alice $60

Simplify Debts Algorithm

The key insight: we only care about each person's net balance (total owed - total paid). Then we match the biggest creditor with the biggest debtor.

BEFORE simplification:
  Alice -> Bob:    $50
  Alice -> Charlie: $30
  Bob   -> Charlie: $20
  Charlie -> Alice: $10

  3 people, 4 transactions

STEP 1: Calculate net balances
  Alice:   -50 - 30 + 10 = -$70  (net debtor)
  Bob:     +50 - 20       = +$30  (net creditor)
  Charlie: +30 + 20 - 10  = +$40  (net creditor)

STEP 2: Sort: debtors [-70] and creditors [+30, +40]

STEP 3: Greedily match largest debtor with largest creditor
  Alice pays Charlie $40  ->  Alice: -$30, Charlie: $0
  Alice pays Bob $30      ->  Alice: $0,   Bob: $0

AFTER simplification:
  Alice -> Charlie: $40
  Alice -> Bob:     $30

  Only 2 transactions (reduced from 4)

Sequence Flow

Adding an Expense

  User         ExpenseService        Group           SplitStrategy
    │                │                  │                  │
    │── addExpense ─►│                  │                  │
    │  (groupId,     │── validate ─────────────────────────►│
    │   paidBy,      │◄── ok ──────────────────────────────│
    │   amount,      │                  │                  │
    │   splitType,   │── split() ──────────────────────────►│
    │   splits)      │◄── amounts map ─────────────────────│
    │                │                  │                  │
    │                │── addExpense() ─►│                  │
    │                │◄── done ─────────│                  │
    │◄── expense ────│                  │                  │

Complete Implementation

Enums and User

// ─── Enums ──────────────────────────────────────────────

const SplitType = Object.freeze({
  EQUAL: 'EQUAL',
  EXACT: 'EXACT',
  PERCENTAGE: 'PERCENTAGE',
});

User

// ─── User ───────────────────────────────────────────────

class User {
  static _counter = 0;

  constructor(name, email, phone) {
    this.id = `U-${++User._counter}`;
    this.name = name;
    this.email = email;
    this.phone = phone;
  }
}

Split Strategies (Strategy Pattern)

// ─── Split Strategies ───────────────────────────────────

class EqualSplitStrategy {
  validate(amount, splits) {
    if (splits.length === 0) {
      throw new Error('At least one participant is required for equal split.');
    }
    return true;
  }

  split(amount, splits) {
    // splits = [{ user }]  (no amount/percentage needed)
    const perPerson = Math.round((amount / splits.length) * 100) / 100;
    const result = new Map();

    let remaining = amount;
    for (let i = 0; i < splits.length; i++) {
      if (i === splits.length - 1) {
        // Last person gets the remainder to handle rounding
        result.set(splits[i].user.id, Math.round(remaining * 100) / 100);
      } else {
        result.set(splits[i].user.id, perPerson);
        remaining -= perPerson;
      }
    }
    return result;
  }
}

class ExactSplitStrategy {
  validate(amount, splits) {
    const total = splits.reduce((sum, s) => sum + s.amount, 0);
    if (Math.abs(total - amount) > 0.01) {
      throw new Error(
        `Exact split amounts ($${total}) do not add up to total ($${amount}).`
      );
    }
    return true;
  }

  split(amount, splits) {
    // splits = [{ user, amount }]
    const result = new Map();
    for (const s of splits) {
      result.set(s.user.id, s.amount);
    }
    return result;
  }
}

class PercentageSplitStrategy {
  validate(amount, splits) {
    const totalPercent = splits.reduce((sum, s) => sum + s.percentage, 0);
    if (Math.abs(totalPercent - 100) > 0.01) {
      throw new Error(
        `Percentages add up to ${totalPercent}%, not 100%.`
      );
    }
    return true;
  }

  split(amount, splits) {
    // splits = [{ user, percentage }]
    const result = new Map();
    let remaining = amount;

    for (let i = 0; i < splits.length; i++) {
      if (i === splits.length - 1) {
        result.set(splits[i].user.id, Math.round(remaining * 100) / 100);
      } else {
        const share = Math.round((amount * splits[i].percentage / 100) * 100) / 100;
        result.set(splits[i].user.id, share);
        remaining -= share;
      }
    }
    return result;
  }
}

// Strategy factory
const SPLIT_STRATEGIES = Object.freeze({
  [SplitType.EQUAL]: new EqualSplitStrategy(),
  [SplitType.EXACT]: new ExactSplitStrategy(),
  [SplitType.PERCENTAGE]: new PercentageSplitStrategy(),
});

Expense

// ─── Expense ────────────────────────────────────────────

class Expense {
  static _counter = 0;

  constructor(description, amount, paidBy, splits, splitType) {
    const strategy = SPLIT_STRATEGIES[splitType];
    strategy.validate(amount, splits);

    this.id = `EXP-${++Expense._counter}`;
    this.description = description;
    this.amount = amount;
    this.paidBy = paidBy;           // User who paid
    this.splitType = splitType;
    this.splitAmounts = strategy.split(amount, splits); // Map<userId, amount>
    this.createdAt = new Date();
  }
}

Group

// ─── Group ──────────────────────────────────────────────

class Group {
  static _counter = 0;

  constructor(name, members) {
    this.id = `GRP-${++Group._counter}`;
    this.name = name;
    this.members = new Map(); // userId -> User
    this.expenses = [];

    for (const member of members) {
      this.members.set(member.id, member);
    }
  }

  addMember(user) {
    this.members.set(user.id, user);
  }

  addExpense(expense) {
    this.expenses.push(expense);
  }

  // ── Calculate balances ────────────────────────────────
  // Returns a Map of: "payerId->owerId" -> amount
  // Meaning: the balances between every pair of users

  getBalances() {
    // balanceMap: userId -> net amount (positive = owed money, negative = owes money)
    const netBalances = new Map();

    for (const [userId] of this.members) {
      netBalances.set(userId, 0);
    }

    for (const expense of this.expenses) {
      const payerId = expense.paidBy.id;

      for (const [userId, share] of expense.splitAmounts) {
        if (userId === payerId) continue; // Payer's own share

        // userId owes payerId the share amount
        // Payer's balance goes up (they are owed money)
        netBalances.set(payerId, (netBalances.get(payerId) || 0) + share);
        // Ower's balance goes down (they owe money)
        netBalances.set(userId, (netBalances.get(userId) || 0) - share);
      }
    }

    return netBalances;
  }

  // ── Simplify Debts ────────────────────────────────────
  // Minimize number of transactions using greedy algorithm

  simplifyDebts() {
    const netBalances = this.getBalances();

    // Separate into creditors (positive) and debtors (negative)
    const creditors = []; // { userId, amount }
    const debtors = [];   // { userId, amount }  (stored as positive)

    for (const [userId, balance] of netBalances) {
      if (balance > 0.01) {
        creditors.push({ userId, amount: balance });
      } else if (balance < -0.01) {
        debtors.push({ userId, amount: -balance }); // Make positive
      }
    }

    // Sort descending by amount
    creditors.sort((a, b) => b.amount - a.amount);
    debtors.sort((a, b) => b.amount - a.amount);

    // Greedy matching
    const transactions = [];
    let i = 0; // creditor pointer
    let j = 0; // debtor pointer

    while (i < creditors.length && j < debtors.length) {
      const creditor = creditors[i];
      const debtor = debtors[j];
      const settleAmount = Math.min(creditor.amount, debtor.amount);

      transactions.push({
        from: debtor.userId,
        fromName: this.members.get(debtor.userId)?.name,
        to: creditor.userId,
        toName: this.members.get(creditor.userId)?.name,
        amount: Math.round(settleAmount * 100) / 100,
      });

      creditor.amount -= settleAmount;
      debtor.amount -= settleAmount;

      if (creditor.amount < 0.01) i++;
      if (debtor.amount < 0.01) j++;
    }

    return transactions;
  }
}

ExpenseService (Controller)

// ─── ExpenseService ─────────────────────────────────────

class ExpenseService {
  constructor() {
    this.users = new Map();  // userId -> User
    this.groups = new Map(); // groupId -> Group
  }

  // ── User management ───────────────────────────────────

  addUser(name, email, phone) {
    const user = new User(name, email, phone);
    this.users.set(user.id, user);
    console.log(`[USER] Created: ${user.name} (${user.id})`);
    return user;
  }

  // ── Group management ──────────────────────────────────

  createGroup(name, members) {
    const group = new Group(name, members);
    this.groups.set(group.id, group);
    console.log(
      `[GROUP] Created: "${group.name}" with ${members.map(m => m.name).join(', ')}`
    );
    return group;
  }

  // ── Expense management ────────────────────────────────

  addExpense(groupId, description, amount, paidBy, splits, splitType) {
    const group = this.groups.get(groupId);
    if (!group) throw new Error(`Group ${groupId} not found.`);

    const expense = new Expense(description, amount, paidBy, splits, splitType);
    group.addExpense(expense);

    console.log(
      `[EXPENSE] "${description}" $${amount} paid by ${paidBy.name} ` +
      `(${splitType} split) in "${group.name}"`
    );

    return expense;
  }

  // ── Balance queries ───────────────────────────────────

  getGroupBalances(groupId) {
    const group = this.groups.get(groupId);
    if (!group) throw new Error(`Group ${groupId} not found.`);

    const balances = group.getBalances();
    const result = [];

    for (const [userId, balance] of balances) {
      const user = this.users.get(userId) || group.members.get(userId);
      result.push({
        user: user?.name || userId,
        balance: Math.round(balance * 100) / 100,
        status: balance > 0.01 ? 'is owed' : balance < -0.01 ? 'owes' : 'settled',
      });
    }

    return result;
  }

  getSimplifiedDebts(groupId) {
    const group = this.groups.get(groupId);
    if (!group) throw new Error(`Group ${groupId} not found.`);
    return group.simplifyDebts();
  }

  // Overall balance for a user across all groups
  getUserBalance(userId) {
    let netBalance = 0;
    const details = [];

    for (const [groupId, group] of this.groups) {
      if (!group.members.has(userId)) continue;

      const balances = group.getBalances();
      const balance = balances.get(userId) || 0;
      netBalance += balance;

      if (Math.abs(balance) > 0.01) {
        details.push({
          group: group.name,
          balance: Math.round(balance * 100) / 100,
        });
      }
    }

    return {
      userId,
      netBalance: Math.round(netBalance * 100) / 100,
      groups: details,
    };
  }
}

Usage Walkthrough

// ─── Demo ───────────────────────────────────────────────

const service = new ExpenseService();

// Create users
const alice = service.addUser('Alice', 'alice@email.com', '111');
const bob = service.addUser('Bob', 'bob@email.com', '222');
const charlie = service.addUser('Charlie', 'charlie@email.com', '333');
const dave = service.addUser('Dave', 'dave@email.com', '444');

// Create a group
const tripGroup = service.createGroup('Goa Trip', [alice, bob, charlie, dave]);

// ── Expense 1: Hotel ($4000) paid by Alice, split equally ──

service.addExpense(
  tripGroup.id,
  'Hotel stay',
  4000,
  alice,
  [{ user: alice }, { user: bob }, { user: charlie }, { user: dave }],
  SplitType.EQUAL
);
// Each person's share: $1000
// Bob, Charlie, Dave each owe Alice $1000

// ── Expense 2: Dinner ($600) paid by Bob, exact split ──

service.addExpense(
  tripGroup.id,
  'Dinner',
  600,
  bob,
  [
    { user: alice, amount: 100 },
    { user: bob, amount: 200 },
    { user: charlie, amount: 150 },
    { user: dave, amount: 150 },
  ],
  SplitType.EXACT
);
// Alice owes Bob $100, Charlie owes Bob $150, Dave owes Bob $150

// ── Expense 3: Cab ($300) paid by Charlie, percentage split ──

service.addExpense(
  tripGroup.id,
  'Cab rides',
  300,
  charlie,
  [
    { user: alice, percentage: 25 },
    { user: bob, percentage: 25 },
    { user: charlie, percentage: 25 },
    { user: dave, percentage: 25 },
  ],
  SplitType.PERCENTAGE
);
// Each: $75. Alice, Bob, Dave each owe Charlie $75

// ── View balances ───────────────────────────────────────

console.log('\n--- Group Balances ---');
console.log(service.getGroupBalances(tripGroup.id));
// Alice:   +1000 -100 -75 = +$825   (is owed)
// Bob:     -1000 +400 -75 = -$675   (owes — net is +100+150+150-1000-75)
//          Actually: Bob paid dinner(600), gets back 400. Owes hotel 1000, cab 75.
//          Bob net: -1000 + (600-200) - 75 = -1000 + 400 - 75 = -675
// Charlie: -1000 -150 +225 = -$925  (owes)
// Dave:    -1000 -150 -75 = -$1225  (owes) ... let's check

// ── Simplified debts ───────────────────────────────────

console.log('\n--- Simplified Debts ---');
const debts = service.getSimplifiedDebts(tripGroup.id);
for (const d of debts) {
  console.log(`  ${d.fromName} pays ${d.toName}: $${d.amount}`);
}
// Minimal number of transactions to settle all debts

// ── Per-user balance ────────────────────────────────────

console.log('\n--- Alice overall ---');
console.log(service.getUserBalance(alice.id));

Edge Cases

Edge CaseHow It Is Handled
Exact split does not add up to totalExactSplitStrategy.validate() throws error
Percentages do not add up to 100%PercentageSplitStrategy.validate() throws error
Rounding errors in equal splitLast person gets the remainder
User not in group adds expenseShould validate (add check in addExpense)
Group with 1 personEqual split gives full amount to that person; no debts
All debts already settledsimplifyDebts() returns empty array
Payer is also in the splitPayer's own share is skipped in balance calculation

Key Takeaways

  1. Strategy Pattern for split types makes adding new split methods (by shares, by items) trivial — just add a new strategy class.
  2. Net balance calculation is the core algorithm: for each expense, the payer gains credit and each participant gains debt.
  3. Debt simplification uses a greedy two-pointer approach on sorted creditors and debtors — this minimizes transactions.
  4. Rounding is a real-world concern: always round to 2 decimal places and give the remainder to the last person.
  5. The ExpenseService acts as a facade, giving users a clean API without exposing internal Group/Expense logic.

Next -> 9.6.e — Uber/Ola