Implement prioritized refund allocation engine
Overview
This question evaluates algorithmic problem-solving, data modeling, and implementation skills for prioritized refund allocation, including parsing inputs, grouping by payment method, sorting by date, aggregating remaining balances, and handling partial fulfillment and edge cases; it is commonly asked to assess the ability to implement ordered, constraint-driven allocation logic while reasoning about correctness and performance. It belongs to the Coding & Algorithms domain and represents a practical implementation problem emphasizing applied algorithmic reasoning and complexity analysis rather than purely conceptual discussion.
Implement a refund allocation function that takes: (a) a list of payments, each with a unique paymentId, method ∈ {CREDIT, CREDIT_CARD, PAYPAL}, ISO-8601 date (yyyy-mm-dd), and amountPaid; (b) a list of existing refunds, each linked to a paymentId with amountRefunded; and (c) a new refundRequest amount. Output a list of allocations [(paymentId, method, amount)] that satisfies all rules:
- Fully exhaust a payment's remaining refundable amount before moving to another payment.
- Prioritize methods in this order: CREDIT, then CREDIT_CARD, then PAYPAL.
- Within the same method, refund more recent payments before older ones (most recent date first).
- A payment’s remaining refundable amount = amountPaid − sum(existing refunds linked to it), never negative.
- If refundRequest exceeds total refundable amount, return allocations for what is available and the shortfall. Assume inputs are strings to be parsed; dates are comparable by calendar order and there are no time zones. Provide function signature, explain data structures (e.g., grouping by method, sorting by date desc, tracking remaining amounts), and analyze complexity.