Expense Splitting (LLD)

What you'll learn

• Problem Statement

  Design the backend for a group expense sharing application. Users create groups, add shared expenses, and the system computes the minimum number of transactions needed to settle all debts. Core challenges: - Efficient debt simplification…

• Functional Requirements

  1. User management: Create accounts, manage profiles 2. Group management: Create groups, add/remove members 3. Expense tracking: Add expenses with flexible splitting 4. Balance computation: Real-time net balances per user 5. Settlement:…

• Non-Functional Requirements

  - Consistency: Balance calculations must be exactly correct - Availability: Users can always view/add expenses - Latency: Balance queries , wrap in a domain object: Benefits: - Encapsulates merge logic (add to existing balance) - Returns…

• Expense: Immutable Once Created

• PaymentGraph: Settlement Result

  ---

• Settlement Algorithm: Greedy Two-Heap

• Why This Algorithm?

  The minimum transaction problem is NP-hard in general (reducible to Subset Sum). However, the greedy two-heap approach gives an excellent approximation: - Guarantees ≤ N-1 transactions (where N = users with non-zero balance) - Often prod…

• Implementation

• Correctness Proof Sketch

  1. Conservation: Total positive = Total negative (expenses sum to zero) 2. Progress: Each iteration eliminates at least one user from a heap 3. Termination: At most N-1 iterations (one user eliminated per step) 4. Completeness: When heap…

• Summing Expenses

  Before running the settlement algorithm, sum all expenses in a group: ---

• Simplified vs Transitive Settlement

• The Stranger Problem

• Transitive Settlement (Alternative)

  Instead of computing net balance per USER, compute per USER PAIR: More transactions (3 vs 2) but preserves social relationships.

• Handling Pair Conflicts

  If in a later expense, D owes B $30: If pair values are negative, reverse the direction:

• Design Decision

  Make this a group setting: ---

• Concurrency Deep Dive

• The Problem

  Two users add expenses to the same group simultaneously: 1. User A reads current balances: {X: +50, Y: -50} 2. User B reads current balances: {X: +50, Y: -50} 3. User A adds expense, writes: {X: +70, Y: -70} 4. User B adds expense, write…

• Solution 1: Read-Write Lock

  Characteristics: - Multiple readers can proceed in parallel - Writer gets exclusive access - Readers and writer are mutually exclusive - Best when reads >> writes

• Solution 2: Immutable Snapshot (Preferred for this system)

  Why this works: - Expenses are immutable once created (append-only) - Balance is derived from current expense list at read time - No lost updates possible (we're not updating balances, we're adding expenses) - ConcurrentHashMap.compute()…

• Solution 3: Database-Level (Production)

  No concurrency issue at DB level because: - Expense insertion is independent (different rows) - Balance query is a SUM over all rows (sees whatever's committed) - Only need transaction isolation for the INSERT (prevent duplicate expenses…

• Caching Architecture

• What to Cache

• Cache IDs, Not Objects

• Invalidation Strategy

  | Event | Invalidate | |-------|-----------| | New expense added | groupexpenses:{groupId} | | User removed from group | groupmembers:{groupId} | | User profile updated | userprofile:{userId} | | Expense deleted | groupexpenses:{groupId}…

• Database Design (Production)

• Schema

• Query Patterns

• Indexing Strategy

  | Query Pattern | Index | |--------------|-------| | Expenses by group | idxexpensesgroup on expenses(groupid) | | Splits by user | idxsplitsuser on expensesplits(userid) | | Splits by expense | Already PK (expenseid, userid) | | Recent…

• Service Layer Design

• GroupService (Coordinator)

• ExpenseService (Core Logic)

  ---

• Testing Strategy

• Unit Tests

• Edge Cases to Test

  | Case | Expected Behavior | |------|-------------------| | All balances zero | Empty payment graph | | Single user owes everyone | N-1 transactions | | Two users, one expense | Single transaction | | Same amount owed and owing | Zero ne…

• Scalability Considerations

• For Large Groups (100+ members)

  | Concern | Solution | |---------|----------| | Expense list grows unbounded | Paginate, archive settled periods | | Balance computation slow | Pre-compute and cache net balances | | Many concurrent writers | Append-only expense store |…

• For Many Groups per User

  - Partition expenses by groupid (natural shard key) - User's cross-group balance = fan-out query to each group shard - Consider materialized view for "user dashboard" showing all groups

• For Real-Time Updates

  - When User A adds expense → push notification to group members - WebSocket for real-time balance updates on group page - Settlement graph recomputed on each page load (cheap for < 50 members) ---

• Common Interview Mistakes

  1. Storing the payment graph: It's derived data — compute it, don't store it 2. Using double for money: Instant red flag. Always BigDecimal 3. Forgetting conservation: Sum of splits MUST equal zero 4. Ignoring the stranger problem: Discu…