Split Tender Part 2 - Expiration Dates
Problem statement
Many of Stripe's merchants rely on Stripe Terminal to accept in-person payments at the point of sale. In physical retail, it's common for a customer to cover a purchase with multiple payment methods. For example, they might cover a $100 purchase with a $40 gift card combined with a $60 credit card. This is called a split-tender transaction, and supporting it is a key requirement for retail merchants on Terminal.
For this multi-part question, we will be writing a system to process split-tender payments. When a transaction occurs, the system first deducts from the customer's available gift card balance, then charges the remaining balance to the customer's credit card. Given a chronological stream of payment events, your task is to calculate the correct credit card charge for each transaction. The question is broken down into four parts, each introducing a new event type: gift card expiration, regional credit card surcharges, and complex refund logic.
This exercise: Implement Part 2. Include basic split tendering and gift-card expiration; do not apply surcharges or process refunds.
Split Tender Series
These four exercises build on one another. Each page includes the rules needed to solve that part.
- Split Tender Part 1 - Basic Split Tendering
- Split Tender Part 2 - Expiration Dates (this part)
- Split Tender Part 3 - Surcharges
- Split Tender Part 4 - Refunds
The function parameters below are shared by the four-part source. This standalone exercise uses only the event types and parameters listed in its practice interface.
Source-Wide Function Parameters
string events[n]: lines for each event in chronological order. Lines have a format defined by one of three schemas:
timestamp,ADD_GIFTCARD,customer_id,card_id,amount,valid_beforetimestamp,CHARGE,charge_id,customer_id,amount,zip_codetimestamp,REFUND,charge_id,refund_amount
string surcharge_rates[m]: a list of non-overlapping zip code ranges mapped to a surcharge percentage in the format start_zip-end_zip:rate, where start and end are inclusive. Example: 90000-99999:0.05 (representing 5%).
General Constraints and Assumptions
- Events are in chronological order by timestamp.
- All event lines are well-formed.
charge_idvalues are unique acrossCHARGEevents.REFUNDevents always reference a priorCHARGEevent.- Each
charge_idwill receive at most oneREFUNDevent. card_idvalues fromADD_GIFTCARDevents are unique.surcharge_ratescontains non-overlapping, valid zip code ranges.zip_codevalues are five-digit numeric strings.
Monetary Representation and Precision
- All monetary amounts in the input and output are represented as non-negative integer numbers of cents.
- For example,
$40.00is represented as4000. - Surcharge rates are decimal fractions; for example,
0.05represents5%. - Each surcharge calculation results in a whole number. You don't need to round.
Returns: string[n]: an array of strings, one per input event, in the same order.
- For
CHARGEevents, return the formatted charge string using the schemaCC_CHARGE_AMOUNT,GIFT_CARD_ID_1:AMOUNT_USED,GIFT_CARD_ID_2:AMOUNT_USED. - For all other event types, return an empty string
""unless a later part specifies otherwise. - The length of the output array must exactly match the length of the input events array.
Part 1: Basic split tendering
For Part 1, process ADD_GIFTCARD and CHARGE events. All customer balances start at 0.
When an ADD_GIFTCARD event is received, add the specified amount to the designated customer's total gift card balance. Return an empty string "".
When a CHARGE event is received, attempt to cover the transaction cost using the customer's available gift card balance first.
- If the gift card balance is greater than or equal to the charge amount, deduct the charge amount from their gift card balance. The credit card charge is 0.
- If the charge amount exceeds the gift card balance, drain the entire gift card balance to 0. The remaining unpaid amount becomes the credit card charge.
Output Format for CHARGE: Return a string starting with the credit card charge, followed by a comma-separated list of the gift cards debited and their amounts (CARD_ID:AMOUNT). If no gift cards were debited, output only the credit card charge.
CC_CHARGE_AMOUNT,GIFT_CARD_ID_1:AMOUNT_USED,GIFT_CARD_ID_2:AMOUNT_USED
The single-active-card restriction applies only to Part 1. This exercise allows multiple gift cards, as described in Part 2.
Part 2: Expiration dates
All constraints from Part 1 still apply. In this part, each gift card has its own individual balance, and a customer may hold multiple gift cards simultaneously, tracked by card_id. Additionally, gift cards have expiration dates: they must be used before their valid_before time.
When a CHARGE event occurs at time T, evaluate the customer's available gift cards:
- A gift card is valid only if
Tis strictly less than itsvalid_beforevalue. IfTis at or aftervalid_before, the gift card is expired and its balance permanently voided. - The system must charge valid gift cards by the earliest expiration date first. Completely drain one gift card before moving to the next.
- Gift cards with no expiration date are considered valid forever and should be used after all valid gift cards with finite expiration timestamps.
- If multiple gift cards share the exact same expiration timestamp, prioritize the card whose
card_idappears first lexicographically.
Output Format for CHARGE: Identical to Part 1. Gift cards must be debited according to the priority rules above. Now that multiple gift cards can be consumed in a single charge, cards must be sorted.
Practice clarification for the cropped output rule: Sort positive debit entries lexicographically by card_id in the output, independently of their spending order.
The examples below show expiration, spending priority and output order.
Practice Details
Complete the function process_events in the editor below.
In this practice interface, the method is named processEvents. The only parameter is events; this part does not use the source-wide surcharge-rate input. Supplied gift cards have finite expiration timestamps. Refunds and refund-created non-expiring cards belong to Part 4.
Function
processEvents(events: String[]) → String[]Examples
Example 1
events = ["1,ADD_GIFTCARD,cust1,gc1,5000,10","2,ADD_GIFTCARD,cust1,gc2,4000,5","3,CHARGE,chg1,cust1,6000,10000","11,CHARGE,chg2,cust1,1000,10000"]return = ["","","0,gc1:2000,gc2:4000","1000"]gc2 expires first and is drained before gc1; output card IDs are sorted independently. At timestamp 11 the remaining gc1 balance is expired.
Example 2
events = ["1,ADD_GIFTCARD,alice,z,400,5","2,ADD_GIFTCARD,alice,a,500,10","3,CHARGE,c1,alice,600,10000","5,CHARGE,c2,alice,400,10000"]return = ["","","0,a:200,z:400","100,a:300"]Spend earlier-expiring z first, then 200 cents from a, while listing a before z. The next charge uses the last 300 cents from a.
Constraints
- For this exercise, assume there are between
1and10^5events. - For this exercise, assume events with equal timestamps are processed in input order.
- For this exercise, assume all input customer, card and charge IDs contain ASCII letters, digits or underscores, have length from
1to64, and contain no commas. - For this exercise, assume each input monetary amount is at most
10^9cents, and all running balances and intermediate money arithmetic fit signed 64-bit integers. - For this exercise, assume supplied gift cards have finite expiration timestamps, and timestamps and finite expirations are integers from
0to10^9. - For this exercise, assume debited gift cards are listed lexicographically by
card_idin the output, independently of their spending order. - This part: Only
ADD_GIFTCARDandCHARGEevents appear. Expiration and card priority apply; ZIP codes do not affect this part.