This is a design round. You write the classes, and the interviewer checks that they behave.
Here you build BillSplitter. A group of friends uses it to share expenses. All money is in whole cents.
Implement the class:
new BillSplitter()starts with nobody owing anything.addExpense(payer, amount, people)records thatpayerpaidamountfor everyone inpeople, an array of names.balance(person)returns what the group owesperson.pay(payer, receiver, amount)records a direct payment. It returnstrueif the payment is accepted.settle()returns the payments that clear every balance.
An expense is split equally among people. The payer may or may not be one of them.
Sometimes the amount doesn't divide evenly. Then the cents left over go one each to the first names in the list. So 100 cents among Ana, Ben and Cy makes parts of 34, 33 and 33.
The payer's balance goes up by amount. Each person's balance goes down by their part.
A positive balance means the group owes that person money. A negative balance means the person owes the group. Someone never seen has a balance of 0.
A payment needs two things. The payer must owe at least amount. The receiver must be owed at least amount. If both hold, the payment is accepted. Then the payer's balance goes up by amount, and the receiver's goes down by it. A refused payment returns false and changes nothing.
The payments from settle follow one rule, so the answer is unique. Sort the people who owe by name. Sort the people who are owed by name too.
The first person who owes pays the first person who is owed. The payment is the smaller of the two amounts. Whoever reaches 0 steps aside for the next name on their list. This repeats until nobody is left.
Each payment is a text such as "Ana pays Cy 20". After settle, every balance is 0. When nobody owes anything, the list is empty.
The calls run in order on one new BillSplitter. A call to addExpense writes nothing. A call to balance writes the number. A call to pay writes True or False. A call to settle writes the number of payments on one line. Then it writes each payment on its own line.
Example 1:
Input:
new BillSplitter()
1. addExpense("Ana", 100, ["Ana", "Ben", "Cy"])
2. balance("Ana")
3. balance("Ben")
4. balance("Cy")
5. addExpense("Ben", 30, ["Cy"])
6. balance("Ben")
7. balance("Cy")
8. balance("Dee")
Output:
66
-33
-33
-3
-63
0
Explanation:
Call 1 splits 100 cents among three people.
Ana is first in the list, so Ana gets the extra cent.
Ana's part is 34, and Ben and Cy owe 33 each.
Ana paid 100, so Ana's balance is 100 - 34 = 66.
In call 5, Ben pays 30 for Cy alone.
So Ben owes 33 - 30 = 3, and Cy owes 33 + 30 = 63.
Dee never took part, so Dee's balance is 0.
Example 2:
Input:
new BillSplitter()
1. addExpense("Eve", 90, ["Fay", "Gus"])
2. pay("Fay", "Eve", 50)
3. pay("Fay", "Gus", 10)
4. pay("Fay", "Eve", 45)
5. balance("Fay")
6. balance("Eve")
7. pay("Gus", "Eve", 45)
8. balance("Eve")
Output:
False
False
True
0
45
True
0
Explanation:
Eve paid 90 for Fay and Gus. Each owes Eve 45.
Call 2 fails, because Fay owes only 45.
Call 3 fails, because Gus owes money and isn't owed any.
Call 4 works. Fay is now even, and Eve is still owed 45.
Gus pays the last 45 in call 7.
Example 3:
Input:
new BillSplitter()
1. addExpense("Cy", 60, ["Ana", "Ben", "Cy"])
2. addExpense("Dee", 50, ["Ben", "Eve"])
3. settle()
4. balance("Ben")
5. settle()
Output:
4
Ana pays Cy 20
Ben pays Cy 20
Ben pays Dee 25
Eve pays Dee 25
0
0
Explanation:
After calls 1 and 2, Ana owes 20, Ben owes 45 and Eve owes 25.
Cy is owed 40, and Dee is owed 50.
Ana pays Cy 20. Now Ana is even.
Ben pays Cy the 20 still owed to Cy.
Ben pays the other 25 to Dee, and Eve pays Dee 25.
Every balance is now 0, so call 4 returns 0.
Call 5 writes 0, because there is nothing left to pay.
Constraints:
- A name has 1 to 10 English letters.
- A name starts with a capital letter, and its other letters are lowercase.
peopleholds 1 to 10 different names.- Each
amountis a whole number from 1 to 10,000. - At most 100,000 calls follow the constructor.
settleis called at most 20 times.- Every balance stays between -1,000,000,000 and 1,000,000,000.
- So a plain 32-bit integer is enough for any balance.
Note:
Each call to balance or pay should run in O(1) time. A call to addExpense should take O(k) for k people. A call to settle should take O(n log n) for n people. It sorts two lists and walks them with two indexes.
Free plan: 30 tutor messages. PRO is unlimited.
