Simplify Splitwise Transactions: A Low-Level Design Question
Introduction
Hello everyone! Today, we’re going to dive into a fascinating problem: simplifying the number of money transfers within a group of people, exactly as we see in a Splitwise group.
Note: I got asked about this in a low-level design interview for a top-notch product-based company.
Problem Statement
- Imagine you’re on a trip with your friends. At the end of the day, you realize that everyone has paid for different things, and it’s a mess to figure out who owes whom.
- Now, we need a program that can simplify the number of transactions by minimizing the cash flow among friends.
The Intuition:
Let’s say there are 3 friends in a group and their transactions looks like these: A -> B: 100, B -> C: 100. If we see that there are 2 transfers required to settle the money between three members without any optimization, but if we clearly observe that B is getting 100 and it is giving 100 to C.
So, instead of A giving 100 to B, if A gives 100 to C, then transactions involving B gets removed, and the overall number of transfers is reduced to 1.
Our intuition is simple: figure out people who only need to be part of transfers, like either borrowed (A) or lent (C), and remove members (B) who do not need to be part of transfers. And,
By strategically pairing users based on their net amounts to obtain a large money transfer for each transaction, we minimize the number of transactions required to settle all debts within the group.
- Calculate Net Amounts: Compute the net amount (total spent - total borrowed) each user owes or is owed by summing their transactions.
- Group Users: Separate users into two groups based on whether they owe or are owed money.
- Pairing Strategy: Strategically pair users to facilitate large transfers, minimizing the overall number of transactions.
Now, let’s translate this intuition into code. I have hosted the full working code on my Github account. You can check it later for reference.
Step 0: Driver method and Input Setup
This is the starting point. We create a SimplifyTransaction object and feed it with some sample transactions. Then, we call the minTransfers method to figure out the minimum number of transfers needed to settle these transactions.
Finally, we print out the result: the number of transfers required.
Let's see how this simplifyTransaction.minTransfers works.
public static void main(String[] args) {
SimplifyTransaction simplifyTransaction = new SimplifyTransaction();
//{fromUser, toUser, amount}
int[][] txns = {{0, 1, 10}, {1, 2, 3}, {2, 3, 5}, {3, 2, 28}, {1, 3, 17}, {2, 1, 8}, {3, 1, 5}};
int output = simplifyTransaction.minTransfers(txns);
System.out.println("No of transfers:" + output);
}All the code segments in below steps are part of minTransfers method. I am just segmenting to explain better.
Step 1: Calculating Net Amounts
Map<Integer, Integer> userToNetAmount = new HashMap<>();
for (int[] txn : transactions) {
int from = txn[0];
int to = txn[1];
int amount = txn[2];
userToNetAmount.put(from, userToNetAmount.getOrDefault(from, 0) - amount);
userToNetAmount.put(to, userToNetAmount.getOrDefault(to, 0) + amount);
}Here, we iterate through each transaction, updating the net amount for each user in the userToNetAmount map. If a user sends money (from), their net amount decreases, and if they receive money (to), their net amount increases.
Step 2: Grouping Users
PriorityQueue<Pair> receivers = new PriorityQueue<>(new PairMaxComparator());
PriorityQueue<Pair> givers = new PriorityQueue<>(new PairMinComparator());
for (Map.Entry<Integer, Integer> item : userToNetAmount.entrySet()) {
Pair pair = new Pair();
pair.user = item.getKey();
pair.netAmount = item.getValue();
if (item.getValue() != 0) {
if (item.getValue() < 0) {
givers.add(pair);
} else {
receivers.add(pair);
}
}
}We separate users into two groups based on whether they owe (givers) or are owed (receivers) money. These queues are sorted (minHeap for givers, maxHeap for receivers) based on the net amount, allowing us to prioritize users with larger debts or credits.
Step 3: Pairing Users Strategically
while(!receivers.isEmpty()) {
Pair maxPair = receivers.poll();
Pair minPair = givers.poll();
if ((maxPair.netAmount + minPair.netAmount) < 0) {
// Calculate remaining amount and add giver back to givers queue
} else if ((maxPair.netAmount + minPair.netAmount) > 0) {
// Calculate remaining amount and add receiver back to receivers queue
} else {
// Just one transaction
}
tns++;
}We iterate through the queues, pairing users strategically to settle debts efficiently. If a receiver owes more than what a giver can cover, we partially settle the debt and re-add the giver to the queue.
Conversely, if a giver has more than what a receiver needs, we partially settle the credit and re-add the receiver. This process continues until all debts are settled.
Full Code with Driver Class Execution and Output
package org.harikrishna.Splitwise;
import java.util.*;
class Pair {
public Integer user;
public Integer netAmount;
}
class PairMinComparator implements Comparator<Pair> {
@Override
public int compare(Pair o1, Pair o2) {
if (o1.netAmount > o2.netAmount) return 1;
else if (o1.netAmount < o2.netAmount) return -1;
return 0;
}
}
class PairMaxComparator implements Comparator<Pair> {
@Override
public int compare(Pair o1, Pair o2) {
if (o1.netAmount < o2.netAmount) return 1;
else if (o1.netAmount > o2.netAmount) return -1;
return 0;
}
}
public class SimplifyTransaction {
public int minTransfers(int[][] transactions) {
//Compute each user netAmount (Incoming - Outgoing)
Map<Integer, Integer> userToNetAmount = new HashMap<>();
for (int[] txn : transactions) {
int from = txn[0];
int to = txn[1];
int amount = txn[2];
userToNetAmount.put(from, userToNetAmount.getOrDefault(from, 0) - amount);
userToNetAmount.put(to, userToNetAmount.getOrDefault(to, 0) + amount);
}
//Divide receivers and givers into respective groups with max and min priority queue.
PriorityQueue<Pair> receivers = new PriorityQueue<>(new PairMaxComparator());
PriorityQueue<Pair> givers = new PriorityQueue<>(new PairMinComparator());
for (Map.Entry<Integer, Integer> item : userToNetAmount.entrySet()) {
Pair pair = new Pair();
pair.user = item.getKey();
pair.netAmount = item.getValue();
//If the net amount is Zero, then that user doesn't need to pay or receive anything
if (item.getValue() != 0) {
if (item.getValue() < 0) {
givers.add(pair);
} else {
receivers.add(pair);
}
}
}
//Find no of transfers required and transfers data
return findMinTransBtwUsers(receivers, givers);
}
public int findMinTransBtwUsers(PriorityQueue<Pair> receivers, PriorityQueue<Pair> givers) {
int tns = 0;
StringBuilder stringBuilder = new StringBuilder();
//Calculate till someone has to receive the money.
//Basically if someone has to receive the money then someone has to give the money and vice-versa
while(!receivers.isEmpty()) {
Pair maxPair = receivers.poll();
Pair minPair = givers.poll();
if ((maxPair.netAmount + minPair.netAmount) < 0) {
/*
If giver amount > receiver amount then giver still has some amount to give.
So we calculate remaining amount and add the giver back to givers queue.
*/
stringBuilder.append(minPair.user + "->" + maxPair.user + ": " + maxPair.netAmount + "\n");
Pair pair = new Pair();
pair.user = minPair.user;
pair.netAmount = maxPair.netAmount + minPair.netAmount;
givers.add(pair);
} else if ((maxPair.netAmount + minPair.netAmount) > 0) {
/*
If giver amount < receiver amount then receiver still has some amount to get.
So we calculate remaining amount and add the receiver back to receivers queue.
*/
stringBuilder.append(minPair.user + "->" + maxPair.user + ": " + Math.abs(minPair.netAmount) + "\n");
Pair pair = new Pair();
pair.user = maxPair.user;
pair.netAmount = maxPair.netAmount + minPair.netAmount;
receivers.add(pair);
} //If giver amount == receiver amount then just one transaction.
else {
stringBuilder.append(minPair.user + "->" + maxPair.user + ": " + maxPair.netAmount + "\n");
}
tns++;
}
System.out.println(stringBuilder);
return tns;
}
public static void main(String[] args) {
SimplifyTransaction simplifyTransaction = new SimplifyTransaction();
//{fromUser, toUser, amount}
int[][] txns = {{0, 1, 10}, {1, 2, 3}, {2, 3, 5}, {3, 2, 28}, {1, 3, 17}, {2, 1, 8}, {3, 1, 5}};
int output = simplifyTransaction.minTransfers(txns);
System.out.println("No of transfers:" + output);
}Output:
3->2: 11
0->2: 7
0->1: 3
No of transfers:3Even though there are 7 transactions involved at the end, with just 3 transfers, everyone in group 0, 1, 2 and 3 is settled. It’s just superb, right 😄
Rough Note
{{0, 1, 10}, {1, 2, 3}, {2, 3, 5}, {3, 2, 28}, {1, 3, 17}, {2, 1, 8}, {3, 1, 5}};
0 = -10
1 = 10-3-17+8+5 = 3
2 = 3-5+28-8 = 18
3 = 5 -28+17-5 = -11
3 -> 2: 11
0 -> 2: 7
0 -> 1: 3Conclusion
By following this algorithm, we can simplify the number of transactions required to settle debts among users in a split-wise group. Happy coding!
There may be other approaches as well, but I have explained this approach to the interviewer, and the round went very well.
— — — — — — — — — — — — — -
Thank you so much for reading the article! I hope you liked the content, and kindly appreciate it if you felt this article helped you in some way.
I put content on software engineering on LinkedIn and am happy to connect with you there. Do follow me on Medium for more such engineering content.
