I8 · Thiết kế LLD: Chia sẻ chi phí (Splitwise)

I8 · Junior

Cả nhóm đi ăn, thay vì ai cũng trả cho ai, tính ai đang dư/thiếu bao nhiêu rồi trả ít lần nhất.

Cốt lõi

• Thực thể: Users, Groups, Expenses, Balance Sheet map<User, amount>.
• Đơn giản hóa bằng thuật toán Min Cash Flow / Heap (tham lam).
• Ví dụ: A trả 1000 cho A, B, C, D → A +750; B, C, D mỗi người −250 → 3 giao dịch B→A, C→A, D→A $250.

Đánh đổi

Kiến thức đồ thị + tham lam (greedy).

Trong thực tế

Splitwise, SettleUp.

Bug thường gặp

Dùng float cho tiền → 0,1 + 0,2 ≠ 0,3, số dư lệch vài xu.

Tự hỏi lại

Nếu chia không đều (theo %, theo phần) thì mở rộng thiết kế thế nào?