Register That Gives the Fewest Coins
Implement a class CashRegister that sells items and gives change from the coins in its drawer. Write these methods:
CashRegister(values, counts)sets up the drawer:valueslists the coin values in increasing order, and the drawer starts withcounts[i]coins of valuevalues[i].sell(price, paid)sells an item that costsprice. The customer hands overpaid[i]coins of valuevalues[i], and these go into the drawer first. The change is the amount paid minusprice, made from the drawer with as few coins as possible. If several ways use that few coins, the register picks the one with the most coins of the largest value, then the most of the next largest value, and so on. Returns the change as a list of counts, one per coin value. If the customer paid less thanprice, or the change cannot be made exactly, the sale is refused: the customer gets their coins back, nothing changes, and it returns[].read_drawer()returns how many coins of each value are in the drawer.read_total()returns the total value of the coins in the drawer.
The tests call the methods in sequence and compare every return value. The expected list holds null for the constructor.
Example 1
CashRegister([1,5,10,25], [0,0,5,2])
sell(70, [0,0,0,4]) returns [0,0,3,0]
read_drawer() returns [0,0,2,6]
read_total() returns 170
sell(15, [0,0,1,0]) returns []
sell(5, [0,0,1,0]) returns []
read_drawer() returns [0,0,2,6]
The 30 cents of change cannot start with a quarter, because no nickels or pennies are left for the other 5. Three dimes work. The second sale is underpaid, and the third needs 5 cents of change that the drawer cannot make, so both are refused.
Example 2
CashRegister([1,2,3], [2,2,2])
sell(2, [0,0,2]) returns [1,0,1]
read_drawer() returns [1,2,3]
The 4 of change can be 3 + 1 or 2 + 2, two coins either way. The register prefers more coins of the largest value, so it gives 3 + 1.
Constraints
1 <= len(values) <= 4and1 <= values[0] < values[1] < ... <= 25len(counts) == len(paid) == len(values)0 <= counts[i] <= 6and0 <= paid[i] <= 41 <= price <= 200- Each test makes
1to20method calls after the constructor.
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Classes problems
- Search Box SuggestionsHard
- Spreadsheet Sums Without CyclesHard
- Tiny DiskHard
- Tray of WeightsHard
- Two-Tier CacheHard
- Bank Account Without OverdraftsBeginner
- Grid With Row and Column AddsBeginner
- Guest Book SignaturesBeginner