> For the complete documentation index, see [llms.txt](https://harshityadav95.gitbook.io/system-design/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://harshityadav95.gitbook.io/system-design/low-level-design-payment-tracking-app.md).

# Low Level Design: Payment Tracking App

This is the problem statement.

We are to design the low level architecture of a payment tracking app. Here are some of it's features:

1. Adding expenses
2. Editing expenses
3. Settling expenses
4. Adding group expenses. Settling them in a simplified way.
5. Adding comments to expenses
6. Track all state change activity using an activity log.

Out of these, we identify the first 4 as core to a payment tracking app. These features will be implemented in the remaining videos of the chapter.

We define the objects in our system with a 'State Based Approach'.

We then find a way to show user balances for a group: summing group expenses per user.

*When finding the overall balances in a group, why didn't we use a "group by" clause to sum all the user balances from the expense table?*

The number of users in a group is variable. We could try to denormalize the expenses table into two tables of balances and expense\_info:

**balances**:

| expense\_id | user\_id | balance | paid | owes |
| ----------- | -------- | ------- | ---- | ---- |
|             |          |         |      |      |

**expense\_info**:

| id | title | desc | imageUrl | group\_id |
| -- | ----- | ---- | -------- | --------- |
|    |       |      |          |           |

On a 'getGroupExpenses' request for group id=123, we fire the database query:

*'select user\_id, sum(balance) from balances where expense\_id in (select id from expense where group\_id = '123') group by user\_id'*

This requires a nested query, which could perform poorly.\
However, this style of querying will perform very well for finding an individual user's expenses.\
Depending on what you are trying to optimize, you may not may not denormalize the tables.

Subset Sum Problem: <https://en.wikipedia.org/wiki/Subset_sum_problem>

Blog on the algorithm: <https://medium.com/@mithunmk93/algorithm-behind-splitwises-debt-simplification-feature-8ac485e97688>

Stackoverflow Question: <https://stackoverflow.com/questions/877728/what-algorithm-to-use-to-determine-minimum-number-of-actions-required-to-get-the/>

We set our coding requirements by looking at the following:

1. APIs
2. Caching
3. Concurrency
4. Testing

We draw the low level architecture diagram of the system. We then move forward with 3 steps in mind:

1. Object definitions (Naming, composition and interfaces)
2. Algorithm
3. Test cases

Point to note:

Using a BigDecimal instead of a double value would be preferred in a financial application. The double may have precision errors.

**Algorithm:**

1. User passes groupId in request for payment graph
2. Check if user belongs to group
3. Get all expenses belonging to the group from Expense Service
4. Sum all expenses to get a map of user balances
5. Separate positive and negative balances into two heaps
6. Poll the two heaps and store the difference
7. Repeat the above step till the heaps are empty
8. Refactor code where necessary
9. Write tests and refactor more if necessary

**Tips:**

1. Don't jump into coding before you have understood the problem well
2. Attack the main problem first
3. Get comfortable with your IDE, and practice writing code

![](https://2828957172-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFPF_rDo5w1k3YcJibC%2Fsync%2F3da0ad00db7ddd7d75fcda095359adeee3e0744b.png?generation=1621152380043969\&alt=media)

![](https://2828957172-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFPF_rDo5w1k3YcJibC%2Fsync%2Fa7dfe42f9591a8a8c6f0ac5419a6411ad2117203.png?generation=1621152359123528\&alt=media)

![](https://2828957172-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFPF_rDo5w1k3YcJibC%2Fsync%2F0f8c3e403360063785800d1f3a57ca3cb7b14adf.png?generation=1621152364387258\&alt=media)

![](https://2828957172-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFPF_rDo5w1k3YcJibC%2Fsync%2F2552f966911a7e972478467cc7212e43a5861cb2.png?generation=1621152387799657\&alt=media)

![](https://2828957172-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFPF_rDo5w1k3YcJibC%2Fsync%2F3b781f9ba6b2842287d41a32ec81081605840128.png?generation=1621152390824469\&alt=media)

![](https://2828957172-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFPF_rDo5w1k3YcJibC%2Fsync%2F4e63b3ae1aedcee2b8262fcc83fd5eb3e1d3adf4.png?generation=1621152381160445\&alt=media)

![](https://2828957172-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFPF_rDo5w1k3YcJibC%2Fsync%2F3a7949c95e2e14e71a85e1460907f0f98fa8badd.png?generation=1621152361060095\&alt=media)

![](https://2828957172-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFPF_rDo5w1k3YcJibC%2Fsync%2F08d7d000ad86f2de735365c6ca05f5b215157113.png?generation=1621152371333284\&alt=media)

![](https://2828957172-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFPF_rDo5w1k3YcJibC%2Fsync%2F96e0e0309cb2e77d5d176a64b1ae7316e72848db.png?generation=1621152385170993\&alt=media)

Code  : <https://gitlab.com/harshityadav95/splitwise-code-sample><br>

{% embed url="<https://youtu.be/xxtKnynf9_I>" %}