20. Machine Coding Case Study 4: Splitwise / Expense Sharing App with Graph Simplification • Low-Level Design (LLD) & Object-Oriented Machine Coding • Rishabh Ki Kaksha

Design an expense sharing app:
*   Split Types: `EQUAL`, `EXACT`, `PERCENTAGE`.
*   User Balances & Ledger tracking.
*   **Debt Simplification Algorithm (Minimizing Cash Flow Transactions via Greedy Min/Max Heaps)!**

---

### 2. Strategy Pattern for Split Types

```typescript
enum SplitType { EQUAL, EXACT, PERCENTAGE }

interface ISplitStrategy {
    validate(splits: Split[], totalAmount: number): boolean;
}

class EqualSplitStrategy implements ISplitStrategy {
    validate(splits: Split[], totalAmount: number): boolean {
        const expected = totalAmount / splits.length;
        return splits.every(s => Math.abs(s.amount - expected) < 0.01);
    }
}
```

---

### 3. Debt Simplification Algorithm (Greedy Heap Min-Cash-Flow 🧠)

Agar A pays B ₹100, B pays C ₹100 $\rightarrow$ Direct **A pays C ₹100 (Reduces 2 transactions to 1!)**:

```python
import heapq

def simplifyDebts(transactions: list[tuple[str, str, int]]):
    balance = {} # user -> net balance (+ means creditor, - means debtor)
    for payer, payee, amount in transactions:
        balance[payer] = balance.get(payer, 0) + amount
        balance[payee] = balance.get(payee, 0) - amount

debtors = []  # Min-heap of [debt_amount, user]
    creditors = [] # Min-heap of [-credit_amount, user]

for user, net in balance.items():
        if net < 0: heapq.heappush(debtors, (net, user))
        elif net > 0: heapq.heappush(creditors, (-net, user))

simplified_transactions = []
    while debtors and creditors:
        debt_amt, debtor = heapq.heappop(debtors)
        credit_amt_neg, creditor = heapq.heappop(creditors)
        credit_amt = -credit_amt_neg

settled = min(-debt_amt, credit_amt)
        simplified_transactions.append((debtor, creditor, settled))

remaining_debt = debt_amt + settled
        remaining_credit = credit_amt - settled

if remaining_debt < 0: heapq.heappush(debtors, (remaining_debt, debtor))
        if remaining_credit > 0: heapq.heappush(creditors, (-remaining_credit, creditor))

return simplified_transactions
```

---

### 4. Master Comparison Matrix

| Expense Split Type | Validation Rule | Edge Case |
| :--- | :--- | :--- |
| **`EQUAL`** | $\text{Amount} / N$ | Floating point precision division rounding |
| **`EXACT`** | $\sum \text{splits} == \text{Total}$ | Negative values not allowed |
| **`PERCENT`** | $\sum \text{percentages} == 100\%$ | Total percentage must strictly sum to 100 |

---

### 5. Interview Ke 3 Sawal Is Topic Se

1. **Splitwise debt simplification problem NP-Hard kyu hoti hai?** -> Exact minimum transaction count dhoondhna Subset Sum problem me reduce hota hai; Greedy heap approach optimal practical approximation ($O(N \log N)$) provide karti hai.
2. **Rounding differences (e.g. ₹100 split 3 ways = 33.33, 33.33, 33.34) kaise handle karte hain?** -> Pehle user par remainder penny ($100 - 33.33 \times 3 = 0.01$) add karke.
3. **Group vs Non-Group balances kaise manage kiye jaate hain?** -> User level par overall global ledger maintain karte huye Group ID ke basis par scoped sub-ledgers filter karna.

---
**Course Completed:** Low-Level Design (LLD) & Object-Oriented Machine Coding (All 20 Lessons Completed!) 🎉🚀🏗️📐💎

Loading lesson content...

Python 3.12

Full IDE

Live Execution Terminal

Click "Execute Live" to run code.
                

Lesson Mastery AI Quiz

AI Doubt Solver

CERTIFICATE OF COMPLETION

Rishabh Gehlot

PHP 8+ & Laravel 11 Master Track