Change-Making Vending Machine

Medium

Online Assessment

Simulate a vending machine that sells items and makes change out of a limited box of coins.

The machine has numbered slots (starting at 1). slots[i] = [price, stock] describes slot i + 1. It accepts only coins of 25, 10, 5 and 1. The machine's coin box holds bank = [n25, n10, n5, n1] coins at the start. Coins the customer has inserted but not yet spent are kept apart as the inserted coins; their total is the balance. Process commands in order; each command produces exactly one output string.

["insert", v]: if v is one of 25, 10, 5, 1, add that coin to the inserted coins and output BALANCE <balance> (the new balance). Otherwise the coin is not accepted: output REJECT <v> and nothing else changes.
["select", k]: checks happen in this order, and the first that applies decides the outcome (nothing changes unless the sale succeeds):

k is not a slot number: INVALID.
the slot's stock is 0: SOLD OUT.
the balance is less than the price: NEED <price - balance>.
Otherwise try to pay out balance - price in change. The coin pool for change is the coin box plus the inserted coins. Take coins greedily: for 25, then 10, then 5, then 1, take as many coins of that value as are in the pool without exceeding the amount still owed. The machine never looks for a cleverer combination. If the amount owed is not exactly zero at the end, output NO CHANGE: the sale is cancelled and the inserted coins stay inserted.
If change can be paid, the sale succeeds: all inserted coins go into the coin box, the change coins leave the box, the stock drops by one, the balance returns to 0, and the output is SOLD <k> CHANGE <coins>, where <coins> lists the change coins from largest to smallest joined with + (for example 25+10+10), or none if no change was due.

["refund"]: if there are no inserted coins output NOTHING. Otherwise output REFUND <coins> (the inserted coins themselves, largest to smallest, joined with +, as above) and the balance returns to 0. The coin box is unaffected.
["restock", k, n]: if k is a slot number and n >= 1, add n to that slot's stock and output STOCK <k>=<new stock>; otherwise output INVALID.
Anything else (an unknown name, or the wrong number of items for the command) outputs INVALID and changes nothing.

Input: slots, a list of [price, stock]; bank, a list of four coin counts; commands, a list of commands as described.

Output: a list of strings, one per command.

Example 1

Input:: [[[65,2],[30,1]],[0,0,0,0],[["insert",25],["insert",25],["insert",25],["insert",10],["select",1],["insert",5],["insert",5],["select",1],["select",2],["refund"]]]
Output:: ["BALANCE 25","BALANCE 50","BALANCE 75","BALANCE 85","NO CHANGE","BALANCE 90","BALANCE 95","SOLD 1 CHANGE 25+5","NEED 30","NOTHING"]
Explanation: The customer inserts 25, 25, 25, 10 (balance 85) and selects slot 1 (price 65). Change would be 20: the machine's box is empty, but the inserted coins count, so the pool is 25x3 and 10x1. Greedy takes no 25 (25 > 20) and one 10, leaving 10 that no coin can cover, so NO CHANGE; the coins stay inserted. After two more 5s the balance is 95 and the change is 30: one 25 from the pool, then one 5, so SOLD 1 CHANGE 25+5. All inserted coins moved into the box, so refund finds nothing, and slot 2 (price 30) with balance 0 needs 30.

Example 2

Input:: [[[55,1],[30,2]],[1,3,0,0],[["insert",25],["insert",25],["insert",10],["insert",2],["select",1],["insert",25],["select",1],["refund"],["refund"]]]
Output:: ["BALANCE 25","BALANCE 50","BALANCE 60","REJECT 2","NO CHANGE","BALANCE 85","NO CHANGE","REFUND 25+25+25+10","NOTHING"]
Explanation: The box holds one 25 and three 10s. After 25, 25, 10 the balance is 60; the 2 is rejected and not counted. Slot 1 costs 55, so the change is 5, but no 5 or 1 exists anywhere, so NO CHANGE. After another 25 the balance is 85 and the change is 30: greedy takes 25 (plenty available), then needs 5 more and cannot, so NO CHANGE again even though three 10s would have worked. Refund returns the four inserted coins, largest first.

Example 3

Input:: [[[40,1],[40,0]],[0,0,0,0],[["select",3],["select",2],["insert",25],["select",1],["insert",5],["insert",10],["select",1],["select",1],["restock",2,2],["restock",9,1],["restock",1],["dance"]]]
Output:: ["INVALID","SOLD OUT","BALANCE 25","NEED 15","BALANCE 30","BALANCE 40","SOLD 1 CHANGE none","SOLD OUT","STOCK 2=2","INVALID","INVALID","INVALID"]
Explanation: select 3 is not a slot (INVALID). Slot 2 has stock 0, which is reported before any price check (SOLD OUT). After 25 the balance is 25 and slot 1 costs 40, so NEED 15. With 5 and 10 inserted the balance is exactly 40, so no change is needed and the machine sells (CHANGE none); slot 1 is then sold out. restock 2 2 gives slot 2 two items, while restock 9 1, restock 1 (missing quantity) and dance are all INVALID.

Constraints

1 ≤ slots.length ≤ 6; each slot is [price, stock] with 1 ≤ price ≤ 200 and 0 ≤ stock ≤ 5
bank has exactly 4 counts, each between 0 and 20
0 ≤ commands.length ≤ 150
coin values and slot numbers in commands can be any integers from -5 to 300