Low Level Design (LLD): Splitwise System Design

A comprehensive low-level design guide for an expense-sharing and optimal debt-settlement platform (Splitwise). This chapter covers Object-Oriented Domain Modeling, Design Patterns (Observer, Factory, Strategy), and a deep-dive algorithmic progression for minimizing transactions using Greedy Two-Pointers, Backtracking, and Dynamic Programming with Bitmasking.

1. System Overview & Problem Statement

Splitwise is an expense-sharing platform that allows groups of individuals (friends, housemates, colleagues) to track shared costs and settle balances efficiently. When multiple individuals incur various expenses across multiple events (e.g., dining out, groceries, trip expenses), calculating who owes whom can quickly become an entangled web of redundant payments.

Structure & Concept Flow

Without Optimization (Entangled):

User 1 ---> owes $30 ---> User 2

User 2 ---> owes $20 ---> User 3

User 3 ---> owes $30 ---> User 1

Optimized Settle Up (Simplified):

User 3 ---> owes $10 ---> User 2 (Only 1 transaction needed!)

Core Requirements

User & Expense Tracking: Register users and maintain records of individual shared expenses.
Flexible Expense Splitting: Support multiple split strategies:
- Equal Split: Expense divided evenly among participants.
- Percentage Split: Expense split according to explicit user-defined percentages.
- Exact / Custom Split: Custom dollar amounts assigned to each user.
Balance Sheet Maintenance: Real-time tracking of pairwise user debt balances and total net balances.
Optimal Debt Settlement: Calculate the minimum number of transactions required to settle all debts within a group.
Group Management Extension: Support isolated sub-ecosystems (e.g., "Office Trip", "Apartment Rent").

Real-Life Analogy

The Restaurant Bill & The Zero-Sum Household: Imagine eight friends going out to dinner where two people pay the upfront bill of $200. Some ordered alcohol, while others had only veg meals. Rather than executing 12 distinct peer-to-peer transfers later, a single "Household Treasurer" (the Balance Sheet) calculates each person's net financial state (Rich vs. Poor / Credit vs. Debit). In a closed group, money is never created or destroyed; it is a zero-sum game where total credit strictly equals total debit.

2. Domain Entities & Data Modeling

To translate the system requirements into clean Object-Oriented Code, we identify five primary domain entities:

Domain Entity	Primary Responsibility	Key Attributes
`User`	Represents an individual actor in the system.	`id`, `name`, `email`
`Expense`	Captures a discrete financial spend event.	`id`, `description`, `amount`, `payer`, `participants`, `splitType`, `splits`
`Transaction`	Represents an actual debt settlement transfer between two users.	`fromUser` (Debtor), `toUser` (Creditor), `amount`
`BalanceSheet`	Tracks pairwise user balances and aggregates user net balances.	`userBalances` (`Map<UserPair, Double>`), `netBalances` (`Map<User, Double>`)
`Group`	Encapsulates users and expenses inside an isolated context.	`groupId`, `groupName`, `members`, `groupBalanceSheet`

3. Architecture & Design Patterns

The system leverages several classical design patterns to remain decoupled, extensible, and maintainable:

Structure & Concept Flow

+------------------------+

| SplitFactory |

+------------------------+

| <<SplitStrategy>> |

+------------------------+

/ \

v v

+-------------------+ +-----------------------+

| EqualSplitStrategy| |PercentageSplitStrategy|

+-------------------+ +-----------------------+

***

+---------------------+ notifies +----------------------+ updates +-------------------+

| ExpenseManager | ------------> | <<ExpenseObserver>> | -----------> | BalanceSheet |

+---------------------+ +----------------------+ +-------------------+

Strategy Pattern (SplitStrategy): Encapsulates variations in expense calculation algorithms (Equal, Percentage, Exact).
Factory Pattern (SplitFactory): Instantiates the appropriate SplitStrategy based on runtime configuration (EQUAL, PERCENTAGE, EXACT).
Observer Pattern (ExpenseSubject / ExpenseObserver): ExpenseManager acts as the Subject. Whenever an expense is added or modified, registered observers (such as BalanceSheet or Notification services) are automatically updated.
Singleton Pattern (SplitwiseService): Ensures a centralized control point for user sessions, global configurations, and group routing.

Note: In an interview setting, focus primary attention on cleanly implementing the domain entities, the Observer/Factory mechanics, and the optimal Debt Settlement algorithm. Avoid over-engineering unnecessary getters/setters or boilerplate builder code.

4. Vertical System Flow & Execution Pipeline

The lifecycle of an expense addition and subsequent debt settlement proceeds vertically through the system pipeline:

Structure & Concept Flow

User / Client

| 1. addExpense(description, amount, payer, participants, splitType, splitDetails)

ExpenseManager (ExpenseSubject)

| 2. SplitFactory.getSplitStrategy(splitType)

SplitFactory / SplitStrategy

| 3. calculateSplits(amount, participants, splitDetails) -> returns Map<User, Double>

ExpenseManager

| 4. Constructs Expense object & registers in history

| 5. notifyObservers(Expense)

BalanceSheet (ExpenseObserver)

| 6. updateBalances(Expense):

| - Credit payer net balance (+amount)

| - Debit participants net balances (-share)

| - Update internal UserPair pairwise balances

Settlement Engine (Strategy)

| 7. getSimplifiedSettlements() -> Runs Debt Settlement Algorithm

List<Transaction> (Minimal transfers required to settle all debts)

5. Core Class Design & Implementation

Below is the production-ready Java implementation of the core domain objects, split factory, observer mechanism, and balance sheet.

5.1 Domain Models (`User`, `Transaction`, `UserPair`)

JAVA

package com.splitwise.model;

import java.util.Objects;

public class User {
    private final String userId;
    private final String name;

    public User(String userId, String name) {
        this.userId = userId;
        this.name = name;
    }

    public String getUserId() { return userId; }
    public String getName() { return name; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User user = (User) o;
        return Objects.equals(userId, user.userId);
    }

    @Override
    public int hashCode() {
        return Objects.hash(userId);
    }
}

JAVA

package com.splitwise.model;

public class Transaction {
    private final User fromUser; // Debtor (Owes money)
    private final User toUser;   // Creditor (Is owed money)
    private final double amount;

    public Transaction(User fromUser, User toUser, double amount) {
        this.fromUser = fromUser;
        this.toUser = toUser;
        this.amount = amount;
    }

    public User getFromUser() { return fromUser; }
    public User getToUser() { return toUser; }
    public double getAmount() { return amount; }

    @Override
    public String toString() {
        return String.format("%s pays %s : $%.2f", fromUser.getName(), toUser.getName(), amount);
    }
}

JAVA

package com.splitwise.model;

import java.util.Objects;

public class UserPair {
    private final User user1;
    private final User user2;

    public UserPair(User user1, User user2) {
        this.user1 = user1;
        this.user2 = user2;
    }

    public User getUser1() { return user1; }
    public User getUser2() { return user2; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof UserPair)) return false;
        UserPair userPair = (UserPair) o;
        return (Objects.equals(user1, userPair.user1) && Objects.equals(user2, userPair.user2)) ||
               (Objects.equals(user1, userPair.user2) && Objects.equals(user2, userPair.user1));
    }

    @Override
    public int hashCode() {
        return Objects.hash(user1.getUserId()) + Objects.hash(user2.getUserId());
    }
}

5.2 Strategy & Factory for Expense Splitting

JAVA

package com.splitwise.strategy;

import com.splitwise.model.User;
import java.util.*;

public interface SplitStrategy {
    Map<User, Double> calculateSplits(double totalAmount, List<User> participants, Map<User, Double> splitDetails);
}

public class EqualSplitStrategy implements SplitStrategy {
    @Override
    public Map<User, Double> calculateSplits(double totalAmount, List<User> participants, Map<User, Double> splitDetails) {
        Map<User, Double> splits = new HashMap<>();
        double share = totalAmount / participants.size();
        for (User participant : participants) {
            splits.put(participant, share);
        }
        return splits;
    }
}

public class PercentageSplitStrategy implements SplitStrategy {
    @Override
    public Map<User, Double> calculateSplits(double totalAmount, List<User> participants, Map<User, Double> splitDetails) {
        Map<User, Double> splits = new HashMap<>();
        for (User participant : participants) {
            double percentage = splitDetails.getOrDefault(participant, 0.0);
            splits.put(participant, (totalAmount * percentage) / 100.0);
        }
        return splits;
    }
}

public class SplitFactory {
    public static SplitStrategy getSplitStrategy(String splitType) {
        if ("PERCENTAGE".equalsIgnoreCase(splitType)) {
            return new PercentageSplitStrategy();
        }
        return new EqualSplitStrategy(); // Default fallback
    }
}

5.3 Observer Implementation & Expense Manager

JAVA

package com.splitwise.observer;

import com.splitwise.model.Expense;

public interface ExpenseObserver {
    void onExpenseAdded(Expense expense);
    void onExpenseUpdated(Expense expense);
}

public interface ExpenseSubject {
    void registerObserver(ExpenseObserver observer);
    void removeObserver(ExpenseObserver observer);
    void notifyObserversOnAddition(Expense expense);
}

JAVA

package com.splitwise.manager;

import com.splitwise.model.*;
import com.splitwise.observer.*;
import com.splitwise.strategy.*;
import java.util.*;

public class ExpenseManager implements ExpenseSubject {
    private final List<Expense> expenses = new ArrayList<>();
    private final List<ExpenseObserver> observers = new ArrayList<>();

    @Override
    public void registerObserver(ExpenseObserver observer) {
        observers.add(observer);
    }

    @Override
    public void removeObserver(ExpenseObserver observer) {
        observers.remove(observer);
    }

    @Override
    public void notifyObserversOnAddition(Expense expense) {
        for (ExpenseObserver observer : observers) {
            observer.onExpenseAdded(expense);
        }
    }

    public Expense createAndAddExpense(String description, double amount, User payer, 
                                       List<User> participants, String splitType, 
                                       Map<User, Double> splitDetails) {
        SplitStrategy strategy = SplitFactory.getSplitStrategy(splitType);
        Map<User, Double> splits = strategy.calculateSplits(amount, participants, splitDetails);

        Expense expense = new Expense(UUID.randomUUID().toString(), description, amount, payer, participants, splits);
        expenses.add(expense);
        notifyObserversOnAddition(expense);
        return expense;
    }
}

6. Debt Settlement: Net Balance Calculation

Before applying any settlement algorithm, the system converts all raw historical expenses into a simplified Net Balance Map (Map<User, Double>).

Mental Model: Poor (Debtors) vs. Rich (Creditors)

Net Balance ( $B_u$ ): Sum of all money paid by User $u$ $u$ minus sum of all shares owed by User $u$ $u$ .
- If $B_u > 0$ : User is a Creditor ("Rich"), meaning they are owed money by the group.
- If $B_u < 0$ : User is a Debtor ("Poor"), meaning they owe money to the group.
- If $B_u = 0$ : User is settled and requires zero transactions.

\sum_{u \in U} B_u = 0 \quad \text{(Zero-Sum Game Property)}

JAVA

package com.splitwise.model;

import com.splitwise.observer.ExpenseObserver;
import java.util.*;

public class BalanceSheet implements ExpenseObserver {
    private final Map<User, Double> netBalances = new HashMap<>();

    @Override
    public void onExpenseAdded(Expense expense) {
        User payer = expense.getPayer();
        double totalAmount = expense.getAmount();

        // Payer gets credited full amount
        netBalances.put(payer, netBalances.getOrDefault(payer, 0.0) + totalAmount);

        // Participants get debited their respective shares
        for (Map.Entry<User, Double> entry : expense.getSplits().entrySet()) {
            User participant = entry.getKey();
            double share = entry.getValue();
            netBalances.put(participant, netBalances.getOrDefault(participant, 0.0) - share);
        }
    }

    @Override
    public void onExpenseUpdated(Expense expense) {
        // Handle delta updates if expenses are edited
    }

    public Map<User, Double> getNetBalances() {
        return netBalances;
    }
}

7. Debt Settlement Algorithm 1: Naive Greedy Two-Pointer Approach

Intuition & Logic

The naive greedy approach separates users into two sorted lists:

debtors (sorted ascending by negative balance).
creditors (sorted descending by positive balance).

It sets two pointers ( $i = 0$ for debtors, $j = 0$ for creditors) and iteratively satisfies the smaller absolute balance between debtors[i] and creditors[j].

JAVA

public List<Transaction> settleGreedyTwoPointer(Map<User, Double> netBalances) {
    List<User> debtors = new ArrayList<>();
    List<User> creditors = new ArrayList<>();

    for (User u : netBalances.keySet()) {
        double bal = netBalances.get(u);
        if (bal < -1e-6) debtors.add(u);
        else if (bal > 1e-6) creditors.add(u);
    }

    // Sort debtors ascending (most negative first)
    debtors.sort(Comparator.comparingDouble(netBalances::get));
    // Sort creditors descending (most positive first)
    creditors.sort((u1, u2) -> Double.compare(netBalances.get(u2), netBalances.get(u1)));

    List<Transaction> transactions = new ArrayList<>();
    int i = 0, j = 0;

    Map<User, Double> balances = new HashMap<>(netBalances);

    while (i < debtors.size() && j < creditors.size()) {
        User debtor = debtors.get(i);
        User creditor = creditors.get(j);

        double debt = -balances.get(debtor);
        double credit = balances.get(creditor);

        double settledAmount = Math.min(debt, credit);
        transactions.add(new Transaction(debtor, creditor, settledAmount));

        balances.put(debtor, balances.get(debtor) + settledAmount);
        balances.put(creditor, balances.get(creditor) - settledAmount);

        if (Math.abs(balances.get(debtor)) < 1e-6) i++;
        if (Math.abs(balances.get(creditor)) < 1e-6) j++;
    }

    return transactions;
}

Critical Flaw / Pitfall of Greedy Two-Pointers

The Greedy Two-Pointer approach does NOT guarantee the minimum number of transactions.

Counterexample Scenario:

Consider 6 users with the following net balances:

Debtors: $U_1 = -20$ , $U_2 = -30$ , $U_3 = -30$
Creditors: $U_4 = +20$ , $U_5 = +30$ , $U_6 = +40$

Greedy Execution Pipeline:

Matches $U_1(-20)$ with $U_6(+40) \rightarrow$ $U_6$ remains $+20$ . (1 transaction)
Matches $U_2(-30)$ with $U_6(+20) \rightarrow$ $U_2$ remains $-10$ . (2 transactions)
Matches $U_2(-10)$ with $U_5(+30) \rightarrow$ $U_5$ remains $+20$ . (3 transactions)
Matches $U_3(-30)$ with $U_5(+20) \rightarrow$ $U_3$ remains $-10$ . (4 transactions)
Matches $U_3(-10)$ with $U_4(+20) \rightarrow$ $U_4$ remains $+10$ . (5 transactions)
Settlement finished in 6 transactions.

Optimal Matching:

Group 1: $U_1(-20) \rightarrow U_4(+20)$ (1 transaction)
Group 2: $U_2(-30) \rightarrow U_5(+30)$ (1 transaction)
Group 3: $U_3(-30)$ settled with $U_6(+40)$ leaving $U_6(+10)$ , etc. (3 transactions)
Total optimal transactions required: 5 transactions.

The Greedy algorithm fails because it arbitrarily pairs users without discovering disjoint zero-sum subsets.

8. Debt Settlement Algorithm 2: Backtracking / DFS (Exact Optimal)

Intuition & Logic

To guarantee the optimal result, we try all valid pairing options using Depth-First Search (DFS) with backtracking. We compress net balances into a single list creditList, filtering out $0$ balances. At each state, we attempt to resolve the debt of index $i$ by matching it with every subsequent candidate index $j$ ( $i < j$ ) where creditList[i] * creditList[j] < 0 (opposite signs).

CODE

                      [-20, -30, +20, +30] (i=0)
                      /                  \
   Match i=0 with j=2                   Match i=0 with j=3
          /                                      \
  [0, -30, 0, +30]                      [0, -30, +20, +10]
        |                                       |
  Match i=1 with j=3                   Match i=1 with j=2
        |                                       |
   [0, 0, 0, 0]                            [0, 0, -10, +10]
(2 Transactions)                                |
                                           [0, 0, 0, 0]
                                         (3 Transactions)

JAVA

public class BacktrackingSettlement {

    public int minTransactionsDFS(List<Double> creditList, int start) {
        // Skip users who already have 0 net balance
        while (start < creditList.size() && Math.abs(creditList.get(start)) < 1e-6) {
            start++;
        }
        if (start == creditList.size()) return 0;

        int minTransactions = Integer.MAX_VALUE;
        double currentBalance = creditList.get(start);

        for (int j = start + 1; j < creditList.size(); j++) {
            double nextBalance = creditList.get(j);

            // Match only between users of opposite signs (Debtor <-> Creditor)
            if (currentBalance * nextBalance < 0) {
                // Settle start user with j
                creditList.set(j, nextBalance + currentBalance);

                // Recurse for remaining users
                int count = 1 + minTransactionsDFS(creditList, start + 1);
                minTransactions = Math.min(minTransactions, count);

                // Backtrack
                creditList.set(j, nextBalance);
            }
        }

        return minTransactions;
    }
}

Complexity Analysis

Time Complexity: $O((N - 1)!)$ where $N$ is the number of users with non-zero balances. At step $1$ , we have $N-1$ choices; at step $2$ , $N-2$ choices, leading to factorial branching.
Space Complexity: $O(N)$ auxiliary stack space due to recursion depth.

9. Debt Settlement Algorithm 3: Dynamic Programming with Bitmasking

While Backtracking provides the exact optimal answer, $O(N!)$ scales poorly for large $N$ . Dynamic Programming with Bitmasking optimizes this to $O(N \cdot 2^N)$ .

Fundamental Mathematical Theorem

Subgroup Partitioning Theorem: If a set of $N$ users has a net balance sum of $0$ , and can be partitioned into $M$ disjoint zero-sum subgroups ( $G_1, G_2, \dots, G_M$ ), the minimum number of transactions required to settle the entire set is:

\text{Min Transactions} = N - M

Proof:

Let $Z_i = \vert G_i\vert$ be the number of users in zero-sum subgroup $G_i$ .

A connected zero-sum group of size $Z_i$ requires at least $Z_i - 1$ transactions to settle internally.
Summing across all $M$ disjoint subgroups:

\text{Total Transactions} = \sum_{i=1}^{M} (Z_i - 1) = \sum_{i=1}^{M} Z_i - \sum_{i=1}^{M} 1 = N - M

To minimize transactions ( $N - M$ ), we must maximize $M$ (the maximum number of disjoint zero-sum subgroups).

Bitmasking Approach Implementation

Represent each subset of users as a bitmask of length $N$ (where bit $k = 1$ indicates user $k$ is included).
Compute sum[mask]: The sum of net balances for users in mask.
Define dp[mask]: Maximum number of disjoint zero-sum subgroups that can be formed using the subset of users in mask.

JAVA

package com.splitwise.algorithm;

import java.util.*;

public class BitmaskDPSettlement {

    public int minTransactionsBitmask(List<Double> balances) {
        // Filter out zero balances
        List<Double> filtered = new ArrayList<>();
        for (double b : balances) {
            if (Math.abs(b) > 1e-6) {
                filtered.add(b);
            }
        }

        int N = filtered.size();
        if (N == 0) return 0;

        int numMasks = 1 << N;
        double[] sum = new double[numMasks];
        int[] dp = new int[numMasks];

        // Step 1: Precompute net balance sums for all bitmasks
        for (int mask = 0; mask < numMasks; mask++) {
            double currentSum = 0;
            for (int i = 0; i < N; i++) {
                if ((mask & (1 << i)) != 0) {
                    currentSum += filtered.get(i);
                }
            }
            sum[mask] = currentSum;
        }

        // Step 2: Compute Max Zero-Sum Subgroups via DP
        for (int mask = 1; mask < numMasks; mask++) {
            for (int i = 0; i < N; i++) {
                if ((mask & (1 << i)) != 0) {
                    int prevMask = mask ^ (1 << i);
                    dp[mask] = Math.max(dp[mask], dp[prevMask]);
                }
            }
            // If the current subset sums to 0, it forms an additional valid subgroup
            if (Math.abs(sum[mask]) < 1e-6) {
                dp[mask] += 1;
            }
        }

        // Min Transactions = N - (Max Zero-Sum Subgroups in full mask)
        int maxZeroSumSubgroups = dp[numMasks - 1];
        return N - maxZeroSumSubgroups;
    }
}

Complexity Analysis

Time Complexity: $O(N \cdot 2^N)$ . Iterating through $2^N$ states, each state making $N$ bitwise transitions.
Space Complexity: $O(2^N)$ to store the dp and sum arrays.

10. Algorithm Comparison & Trade-off Synthesis

Approach	Guarantees Minimal Transactions?	Time Complexity	Space Complexity	Best Used For
Greedy Two-Pointer	No (Heuristic)	$O(N \log N)$	$O(N)$	Massive scale ( $N > 1000$ ), where approximate settlement is acceptable.
Backtracking / DFS	Yes (Exact)	$O((N-1)!)$	$O(N)$	Small scale ( $N \le 10$ ), interview contexts demonstrating recursive branching.
Bitmask DP	Yes (Exact Optimal)	$O(N \cdot 2^N)$	$O(2^N)$	Production systems requiring exact optimal settlements for medium groups ( $N \le 20$ ).

11. System Extension: Multi-Group Support

In real-world applications, users maintain distinct balance contexts across isolated groups (e.g., "Flatmates", "Hawaii Trip").

Structure & Concept Flow

+-----------------------+

| GroupManager |

+-----------------------+

+-----------------+-----------------+

v v

+--------------------+ +--------------------+

| Group 1 ("Trip") | | Group 2 ("Home") |

+--------------------+ +--------------------+

| - groupId | | - groupId |

| - GroupBalanceSheet| | - GroupBalanceSheet|

+--------------------+ +--------------------+

Implementation Details

JAVA

package com.splitwise.group;

import com.splitwise.model.*;
import com.splitwise.algorithm.BitmaskDPSettlement;
import java.util.*;

public class Group {
    private final String groupId;
    private final String groupName;
    private final List<User> members = new ArrayList<>();
    private final BalanceSheet groupBalanceSheet = new BalanceSheet();

    public Group(String groupId, String groupName) {
        this.groupId = groupId;
        this.groupName = groupName;
    }

    public void addMember(User user) {
        members.add(user);
    }

    public BalanceSheet getGroupBalanceSheet() {
        return groupBalanceSheet;
    }

    public int settleGroupDebts() {
        Map<User, Double> netBalances = groupBalanceSheet.getNetBalances();
        List<Double> balances = new ArrayList<>(netBalances.values());
        BitmaskDPSettlement solver = new BitmaskDPSettlement();
        return solver.minTransactionsBitmask(balances);
    }
}

public class GroupManager {
    private final Map<String, Group> groups = new HashMap<>();

    public void createGroup(String groupId, String groupName) {
        groups.put(groupId, new Group(groupId, groupName));
    }

    public Group getGroup(String groupId) {
        return groups.get(groupId);
    }
}

12. Summary and Key Takeaways

System Objective: Splitwise is an expense-sharing system whose primary algorithmic challenge is finding the minimum number of transactions to settle all debts within a group.
Domain Separation: Core domain entities include User, Expense, Transaction, Group, and BalanceSheet. Keep expense logging separate from debt settlement execution.
Design Patterns:
- Factory Pattern (SplitFactory): Instantiates strategy implementations dynamically.
- Strategy Pattern (SplitStrategy): Encapsulates equal vs. percentage vs. exact expense splits.
- Observer Pattern (ExpenseSubject/ExpenseObserver): Automatically notifies registered balance sheets when expenses are added or changed.
Zero-Sum Principle: Total credits strictly equal total debits across a closed group ( $\sum B_u = 0$ ).
Greedy Algorithm Pitfall: The Greedy Two-Pointer approach executes in $O(N \log N)$ but fails to guarantee minimal transactions due to local non-optimal matches.
Backtracking DFS: Evaluates all debt pairing combinations in $O((N-1)!)$ time, guaranteeing an exact optimal settlement.
Subgroup Partitioning Theorem: Minimum transactions required to settle $N$ users equals $N - M$ , where $M$ is the maximum number of disjoint zero-sum subgroups.
Bitmask DP Solution: Solves the maximum zero-sum subgroup problem in $O(N \cdot 2^N)$ time and $O(2^N)$ space, offering an optimal balance of speed and exactness for practical group sizes ( $N \le 20$ ).
Extensibility: Group context isolation is achieved by scoping BalanceSheet instances within individual Group entities managed by a centralized GroupManager.

💰 Splitwise System Design with Full Code & Step-by-Step Explanation 🧑‍💻

Low Level Design (LLD): Splitwise System Design

1. System Overview & Problem Statement

Core Requirements

Real-Life Analogy

2. Domain Entities & Data Modeling

3. Architecture & Design Patterns

4. Vertical System Flow & Execution Pipeline

5. Core Class Design & Implementation

5.1 Domain Models (User, Transaction, UserPair)

5.2 Strategy & Factory for Expense Splitting

5.3 Observer Implementation & Expense Manager

6. Debt Settlement: Net Balance Calculation

Mental Model: Poor (Debtors) vs. Rich (Creditors)

7. Debt Settlement Algorithm 1: Naive Greedy Two-Pointer Approach

Intuition & Logic

Critical Flaw / Pitfall of Greedy Two-Pointers

Counterexample Scenario:

8. Debt Settlement Algorithm 2: Backtracking / DFS (Exact Optimal)

Intuition & Logic

Complexity Analysis

9. Debt Settlement Algorithm 3: Dynamic Programming with Bitmasking

Fundamental Mathematical Theorem

Proof:

Bitmasking Approach Implementation

Complexity Analysis

10. Algorithm Comparison & Trade-off Synthesis

11. System Extension: Multi-Group Support

Implementation Details

12. Summary and Key Takeaways

5.1 Domain Models (`User`, `Transaction`, `UserPair`)