I don’t usually think of algorithms in my free time. I rather workout or do anything that takes my mind off of software engineering for a while — it’s important to maintain your productivity they say. But every now and then, I download a new app on my phone and I get interested in knowing how the app works and what are the algorithms behind it (it’s a good exercise for any software engineer btw).
I recently moved to San Francisco for a job here. I share an apartment with 2 roommates and we use an app (which I won’t name since they didn’t pay me to advertise their product) to help us split our house expenses equally. And as you can probably guess, I tried determining how it was implemented.
Max Flow Theorem
For those of you unfamiliar with this algorithm, I suggest you take a quick look at its wikipedia page. If you’re in computer science or any related major, you have probably struggled already in one of your algorithms design classes that used this theorem to solve any kind of problem. You probably even asked yourself “Am i really going to use this in real life?”.
Without further ado, here’s a cool way I think someone can implement an expense sharing app.
The Big Kahuna
Suppose we have three roommates: John, Kate and Ann.
John paid a total of $40 in expenses, while Kate and Ann paid $10 each (easy example to demonstrate the usefulness of Max Flow in this scenario). How would you split the money equally?
We would need to build a Max-Flow graph by following these steps:
1- Calculate the total amount paid.
Amount = 40 + 10 + 10 = $60
2- Calculate how much money each person should have paid:
DuePerPerson = Amount / # people = 60 / 3 = $20
3- Calculate the difference between the amount paid by each person and the DuePerPerson
diff (John) = 40–20 = 20
diff (Kate) = 10–20 = -10
diff(Ann) = 10–20 = -10
4- Create a node in your graph for each person
5- Create an edge with capacity equal to ∞ that connects each person to the other people in the graph
each edge has capacity ∞ in this graph
6- Now, for each diff calculated before, if the value was negative, it means the person still needs to reimburse someone: we add an inward edge to the user with the capacity equal to |diff| (absolute value of diff). This represents an inward flow of money into the network. Else, we create an outward edge with capacity equal to diff. As you can guess, this will represent the outward flow of money from the graph. That way we make sure each person pays the right amount, and each person gets paid what they are owed.
20, 10, 10 represent the capacities of the 3 edges
Applying the max flow algorithm will result in multiple paths that represent the flow of money from one user to another, which is equivalent to dividing the expenses equally between the users.
10 / inf means there is a flow of 10 on the edge of capacity equal to infinity
Cool eh?
Next time you learn an algorithm, don’t ask yourself “Am i really going to use this in real life?”. The answer is Yes.
Good Day.