People who will receive money from others. They have a positive balance.
People who will pay money to others. They have a negative balance.
So our balance object should be able to handle both positive and negative values.
struct Balance{string currency;int amount; //For simplicity we are using integers here.// We can also use float or double but in that case, we also need to handle precision errors.}
Expense object
Expense objects must map each user to their balance.
struct Expense{ ExpenseID eid; bool isSettled; map<User,Balance>; GroupID gid; //This expense belongs to which group //Metadata string title; int timestamp; string imageURI;}
Add Expense
We have user and balance objects, and then we can persist them in the database.
Edit Expense
Each expense object has a unique ID. We can use the ID to change the mapping or other metadata.
Settle Expense
We make the isSettled flag true. We will use a balancing algorithm to settle expenses.
Add, Settle and Edit expenses in group
Each expense object has a groupID. So we can add, settle and edit expenses in a group.
Balancing algorithm
Problem
Let us denote each user as a node and each payment as an edge in a graph.
So we need to minimize the number of edges in the graph
It means A paid x amount to B.
Solution
Note: When we talk about balance we are talking about the sum of all transactions for a user.
First, let's divide the user into two categories
People who have a positive balance.
People who have a negative balance.
If at the point any user has 0 balance that means his/her expenses are settled, and we can remove that node from the graph.
At each step we will pick the largest absolute value from each category and add an edge between them.
Let's say we pick A from the first category and B from the second category. So will add an edge from B to A (because B will pay and A will receive) and then update the balances. If the new balance of any node becomes 0 then we will not consider the node again.
To implement this we can use heap data structure.
Pseudocode
struct Node{ UserID uid; int finalBalance;}struct PaymentNode{ UserID from; UserID to; int amount;}List<PaymentNode> makePaymentGraph(){ Max_Heap<Node> firstCategory; Max_Heap<Node> secondCategory; //We are storing the absoulte value
API Design
Expenses[] getGroupExpenses(GroupID gid)
PaymentGraph getGroupPaymentGraph(GroupID gid)
User getUser(UserID uid)
User[] getUsersInGroup(GroupID gid)
ExpenseID addExpense(GroupID gid, UserID uid, int amount, string currency)
void editExpense(ExpenseID eid, UserID uid, int amount, string currency)
We want to cache responses that are required by many users or are expensive to calculate. So will cache the response of the following APIs.
Expenses[] getGroupExpenses(GroupID gid)
PaymentGraph getGroupPaymentGraph(GroupID gid)
Data consistency (Add example)
When performing simultaneous read and update operations the data users might get is incorrect. This is called data inconsistency.
Let's understand this using an example:
We have two users A and B. A received $30 from B. So we perform an update expression
Now the update operation on A was completed but not for B. And at the exact moment, there was a read request from a user.
The sum of all balances should be 0 but in this case, it is -30. So the data is inconsistent.
There are 2 ways we can solve this problem
Put read lock when updating expenses
While updating the expense objects we will not allow users to read data. It will make sure that the data users get will be consistent.
Make objects immutable
So whenever there is an edit request we will create a new object and update data in a new object. Once the update is completed we will point the reference to the new object. Users might get old data however we can be sure that data will be consistent. This will make our system eventually consistent.
Diagram
That's it for now!
You can check out more designs on our video course at InterviewReady.
List<PaymentNode> graph;
//The sum of balance of all users always results in 0 so if first heap is empty then second heap will also have no elements.
