22. Splitwise Simplify Debt Algorithm | LLD of Splitwise | Optimal Account Balancing | LLD Splitwise

This is the most common and frequently asked question in system design round of Top product based companies like amazon, microsoft, google, facebook etc.

Splitwise Simplify debt Algorithm is Part 2 of Video Low Level Design of Splitwise. And can be asked with below names:
- Splitwise Simplify Debt Algorithm
- LLD of Splitwise
- Optimal Account Balancing

Gadget used, showed in below video 🔥:

You can also connect with me 1:1 on Topmate:

Join this channel to get access to perks:

#splitwise #lld #lowleveldesign #systemdesign

[ShubhamGhuleCodes]

I was asked this in Amazon interview in 2022. I solved it using min heap and max heap. Min heap will have all -ve transactions(essentially max heap with highest negative money) and max heap to all +ve transactions. In each iteration, I pop top entries from both the heaps and then reduced the lower one to zero and other one will be again pushed in the heap after subtraction. I cleared that round.

[growwithriu]

I was asked this in my google onsite interview in 2019. I gave the max min heap approach, which was not optimal. After 5 years, I finally have the correct solution

[chetansinha]

Same problem asked in my Udaan Round 1 Interview process(offcampus). But I created this problem bit more difficult by suppose to simplify by using Bridge articulation (Graph topic) and didn't conclude that solution. So at the end Interviewer is not satisfy.
So as a 0 YOE(Fresher Candidate) it'll be difficult to understand these LLD concept. But it may help me in another company's Interview.
thanks Shrayansh sir for entire playlist.

[Lucifer-xtun]

Lots of respect towards your hardwork and dedication sir.

[kolasphoorti]

Hi Shreyansh, Couple of questions here

1.Doesn't greedy work here? Just sort lists of amounts owed/given(-ve for owed, +ve for given). keep 2 pointers one pointing to max value and another one min. At each stage min will give amount to max, if max+min< 0, keep remainingbalance min owes and advance max pointer (max--), if max-min>0, advance min pointer(min++) and keep remaining balance max gets .

2.Here we are just getting the graph or calculating at the end who gets/owes how much and simplifying the array by taking all users in the system.But what if there is a transaction where A owes B and B owes C equal amounts, and A and C aren't friends. In this case the simplify says A owes C x amount but in real it is not possible to settle since they are not friends. So how are there constructing this graph taking car that it is only between friends? does this work only for groups where everyone knows each other?

[Lucifer-xtun]

You always surprise me with the level of quality you are providing.

Just pure gold brother❤️❤️

[Tom-fgkl]

Congratulations and thank you very much. It is by far the best explanation I have seen so far!

[SouhardyaDasChowdhury]

Nice video but one question-
Where are you tracking the receiver and sender of the transactions? ( you are only outputting the number of transactions).

I have one alternate solution. Will post once I validate it and complete it.

[aeshwer]

The algo is ok, but u cannot take a list here and do DFS on it.
Reason: the minTransaction values computed is of no use. We still need to get the mapping of user to own/borrow

[mohammadfaraz]

Can you explain how this design of simplify will integrate with the current splitwise design of yours. Like for example:
In which class this method will reside?
When will it be called?
what all expenses will be part of this?
How is the balancesheet impacted after simplify
How is the balancesheet updated after repeated simplify calls?

[Akashdeepkashyap]

we can use dp to bring down the time complexity to O(N*2)

[trilokchandra]

What a video never ever seen this kind of channel and content.

[suheabkhan]

Maza aagaya @shrayansh.. keep it up the good work.. looking forward for complete playlist after seeing the contents in the lld and hld

[ritvikryadav]

Hi, great explanation, just one correction, from would add the amount and to would deduct .... we are doing opposite ... line number 18-19

[ManognaM-tznk]

Why do we use the controller class and why not service class ? would't the service class be more apt over here ?

[kunalthakur]

We can memoize the result to bring down the complexity from exponetial to O(N*2). Anyways Great Content

[lovleshbhatt]

I think we can apply dynamic programming to solve this problem in n^2 time complexity

[harshtripathi-qlyx]

do we have any leetcode problem similar to this algorithm?

[kaustubhdixit]

Can we use two priority queues for giver and receiver, pop from both and keep settling those amounts?. That may reduce time complexity, but not sure about min. No of transactions..

[jaisamtani]

I have been asked this question in few of the Machine Coding rounds. I was expected to write the executable code of this algorithm. I don't think it can be thought of in 2 hours and can be coded unless it's being practiced thoroughly couple of times. What are your thoughts on this?