Process Split-Tender Payments, Expirations, Surcharges, and Refunds

Implement process_events(events, surcharge_rates). Events are chronological comma-separated strings. Pay for each charge with valid gift-card funds first, then charge the remaining amount to a credit card. Return one string for every input event, in exactly the same order. ### Input Contract ```text timestamp,ADD_GIFTCARD,customer_id,card_id,amount,valid_before timestamp,CHARGE,charge_id,customer_id,amount,zip_code timestamp,REFUND,charge_id,refund_amount ``` All amounts are nonnegative integer cents. Rates are decimal fractions, and every surcharge is guaranteed to be an integer number of cents, so no rounding is needed. ZIP codes are five-digit numeric strings. Surcharge ranges have format start_zip-end_zip:rate, have inclusive endpoints, and do not overlap. An unmatched ZIP uses rate zero. Events are well-formed and chronological; preserve input order for equal timestamps. Charge IDs and added card IDs are unique, refunds reference prior charges, and each charge has at most one refund. A refund never exceeds the total originally paid, including surcharge. No numeric size bounds are reported. The supplied source implementation treats an absent or empty valid_before field as non-expiring; retain that input convention. As an explicit namespace clarification, added card IDs must not collide with generated REFUND_<charge_id> IDs. ### Part 1 — Basic Split Tender Start every customer with no gift-card funds. ADD_GIFTCARD creates the balance and returns an empty string. CHARGE consumes gift-card funds up to the purchase amount, with the unpaid remainder charged to credit. This first stage has at most one active gift card per customer. Return a CHARGE string as CC_CHARGE followed by comma-separated card_id:amount_used entries for cards actually debited. If no card was used, return only CC_CHARGE. #### What This Part Should Cover Preserve customer isolation, debit balances correctly, and produce one output per event. Example: adding gc1 with 5000 cents to cust1 and gc2 with 2000 to cust2, then charging cust2 3000 and cust1 3000, yields ["","","1000,gc2:2000","0,gc1:3000"]. ### Part 2 — Expiration and Multiple Cards A card is usable at time T only when T < valid_before. At or after expiration, its remaining balance is permanently void. Use valid finite-expiration cards first, ordered by earliest expiration and then lexicographic card ID; use non-expiring cards afterward with the same ID tie-break. Drain each selected card before proceeding. In the output, sort debited cards by card ID, which can differ from debit order. #### What This Part Should Cover Separate spending priority from output ordering and handle exact expiration boundaries. Example: add gc1 with 5000 cents expiring at 10 and gc2 with 4000 expiring at 5 for the same customer. A charge of 6000 at time 3 returns "0,gc1:2000,gc2:4000". A charge of 1000 at time 11 returns "1000". ### Part 3 — Regional Credit Surcharges After splitting the raw purchase amount, apply the matching ZIP rate only to the credit-card remainder. Add that surcharge to the credit-card amount shown in the output; gift-card debits are unchanged. #### What This Part Should Cover Parse decimal rates exactly and preserve the actual credit-card amount for future refunds. Example: a 15000-cent purchase with 5000 gift-card cents available and rate 0.05 returns "10500,gc1:5000". ### Part 4 — Refunds Refund credit first, up to the amount actually charged to credit for that charge, including surcharge. Any remainder becomes a new non-expiring gift card for the original customer, named REFUND_<charge_id>. Create that card only when its amount is positive. Return CC_REFUND,GC_REFUND. The new card participates in future spending priority normally; do not restore money to the original cards. #### What This Part Should Cover Use the historical charge's customer and actual credit payment, avoid recomputing a surcharge on the refund, and retain generated store credit for future charges. Example: refunding 12000 cents from the previous 10500-credit/5000-gift purchase returns "10500,1500" and creates REFUND_chg1 with 1500 cents if the original charge ID was chg1. ### What a Strong Answer Covers One chronological state machine combining all stages, exact monetary arithmetic, historical charge records, deterministic output, and complexity. Distinguish the specified refund amount from an unsupplied proportional-tax calculation. ### Follow-up Questions - Why are debit order and serialized card order different? - Why must the credit charge including surcharge be stored rather than recomputed at refund time? - How could a heap improve repeated spending without changing the rules?