Expense Sharing Application
Split types ke liye Strategy pattern: EQUAL, EXACT, PERCENTAGE. Har SplitStrategy validate bhi kare — exact splits ka jod total ke barabar hona chahiye, percentages ka jod 100 hona chahiye. Ye validation bhoolna common galti hai.
Star question hai DEBT SIMPLIFICATION. A→B ₹100 aur B→C ₹100 ka matlab hai A→C ₹100, do transactions ki jagah ek. Algorithm: har vyakti ka NET balance nikaalo, phir sabse bade deviyar ko sabse bade lenevaale se match karo (greedy, max-heap se). Ye batana is problem ka sabse strong answer hai.
interface SplitStrategy { Map<User, Money> split(Money total, List<User> users, List<Double> values); }
class ExactSplit implements SplitStrategy {
public Map<User, Money> split(Money total, List<User> users, List<Double> values) {
if (sum(values) != total.amount()) throw new InvalidSplitException();
// ...
}
}
// Debt simplification: net balance -> greedy match
// balances: A=-100, B=0, C=+100 => sirf A->C 100 (B beech se hat gaya)
void simplify(Map<User, Money> netBalance) {
PriorityQueue<Entry> debtors = maxHeapOfNegatives(netBalance);
PriorityQueue<Entry> creditors = maxHeapOfPositives(netBalance);
// dono se top nikaalo, min amount settle karo, bacha hua wapas daalo
}
- SplitStrategy: EQUAL/EXACT/PERCENTAGE, har ek khud validate kare
- Debt simplification: net balance nikaalo, greedy max-heap se match karo
- Minimum transactions NP-hard hai — greedy practical approximation hai
Har expense ke baad har user ka doosre user ke saath ka balance update hota hai. Do tareeke hain: PAIRWISE balance (A→B kitna) ya NET balance (A ka overall). Pairwise se "tum B ko kitna dete ho" seedha dikhta hai, net se simplification aasaan hoti hai.
Splitwise dono rakhta hai — pairwise display ke liye, net simplify ke liye. Ye batana ki dono ki alag zaroorat hai, ye design maturity dikhata hai.
// Pairwise: Map<UserPair, Money>
// A ne 300 diye, 3 log barabar => B aur C dono A ko 100 dete hain
balances.merge(new UserPair(B, A), Money.of(100), Money::plus);
balances.merge(new UserPair(C, A), Money.of(100), Money::plus);Expenses group ke andar hote hain (Goa Trip, Flatmates) par ek-ek dost ke saath bhi ho sakte hain. Group ek optional context hai, mandatory nahi — ye model karna zaroori hai.
Settlement ek alag transaction type hai: "A ne B ko 500 diye" — ye expense nahi hai, balance ko zero ki taraf le jaata hai. Ise Expense hi maan lena common design galti hai.