Allocate refund across payments

Question

Given a list of completed payment transactions (each with payment method, date, and amount) and a refund amount R,

write an algorithm that issues refunds according to the rules:

Always refund in full from one payment before moving to the next.

Prefer payment methods in the priority order CREDIT → CREDIT_CARD → PAYPAL.

Within the same method, refund the most recent payment first.

Return the list of refund allocations (payment id, method, amount). Explain the algorithm’s time complexity and data structures.