Implement prioritized refund allocation engine

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:

1. Fully exhaust a payment's remaining refundable amount before moving to another payment.
2. Prioritize methods in this order: CREDIT, then CREDIT_CARD, then PAYPAL.
3. Within the same method, refund more recent payments before older ones (most recent date first).
4. A payment’s remaining refundable amount = amountPaid − sum(existing refunds linked to it), never negative.
5. 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.

Implement Prioritized Refund Allocation Engine

Write a function solution(payments, existing_refunds, refund_request) that allocates a new refund request across prior payments.

Each payment is a tuple of strings: (paymentId, method, date, amountPaid).

• paymentId is unique.
• method is one of CREDIT, CREDIT_CARD, PAYPAL.
• date is ISO-8601 in yyyy-mm-dd format.
• amountPaid is a non-negative decimal string.

Each existing refund is a tuple of strings: (paymentId, amountRefunded).

refund_request is a non-negative decimal string.

Return a tuple (allocations, shortfall) where:

• allocations is a list of tuples (paymentId, method, amount) in the exact order the refund is applied.
• shortfall is the part of the request that could not be refunded, as a string with exactly two decimal places.

Allocation rules:

1. Fully exhaust a payment's remaining refundable amount before moving to another payment.
2. Prioritize methods in this order: CREDIT, then CREDIT_CARD, then PAYPAL.
3. Within the same method, refund more recent payments before older ones (most recent date first).
4. A payment's remaining refundable amount is amountPaid - sum(existing refunds for that payment), but never below 0.
5. If refund_request exceeds the total refundable amount, return all possible allocations and a positive shortfall.
6. If two payments have the same method and same date, preserve their original input order.

Use exact decimal arithmetic. In an interview discussion, you should be able to explain the data structures used: for example, a hash map to total existing refunds by paymentId, plus either method-grouped lists or one sortable list ordered by method priority and date descending.

Constraints

• 0 <= len(payments) <= 100000
• 0 <= len(existing_refunds) <= 100000
• Each paymentId in payments is unique
• method is one of CREDIT, CREDIT_CARD, PAYPAL
• Amounts are non-negative decimal strings with at most two digits after the decimal point
• Dates are valid yyyy-mm-dd strings and can be ordered by calendar date

Examples

Example 1

Input: ([('p1', 'CREDIT_CARD', '2024-01-10', '100.00'), ('p2', 'CREDIT', '2024-03-01', '80.00'), ('p3', 'PAYPAL', '2024-02-15', '50.00'), ('p4', 'CREDIT', '2024-01-20', '70.00')], [('p2', '30.00'), ('p1', '20.00'), ('p4', '10.00')], '120.00')
Output: ([('p2', 'CREDIT', '50.00'), ('p4', 'CREDIT', '60.00'), ('p1', 'CREDIT_CARD', '10.00')], '0.00')

Explanation: Remaining amounts are p2=50, p4=60, p1=80, p3=50. CREDIT payments are processed first, newest to oldest: p2 then p4. After refunding 50 and 60, 10 remains, so 10 is taken from p1.

Example 2

Input: ([('a', 'PAYPAL', '2024-04-01', '40.00'), ('b', 'CREDIT_CARD', '2024-04-02', '25.00'), ('c', 'CREDIT', '2024-03-30', '10.00')], [('a', '50.00'), ('b', '5.00'), ('c', '10.00')], '30.00')
Output: ([('b', 'CREDIT_CARD', '20.00')], '10.00')

Explanation: Payment a is over-refunded already, so its remaining refundable amount is capped at 0. Payment c also has 0 left. Only b has 20 remaining, so 20 is allocated and 10 is left as shortfall.

Hints

1. First aggregate all existing refunds by paymentId so each payment has one remaining refundable amount.
2. A custom sort key can enforce both method priority and most-recent-first ordering before you do a single allocation pass.

Approach

Approach: greedy allocation over a single sorted list

The refund must drain payments in a fixed priority order, so the core idea is to build one comparison key per payment, sort once, then greedily pour the request into payments until it runs dry.

Step 1 — aggregate existing refunds. existing_refunds may have multiple entries per payment, so we first sum them into a defaultdict keyed by paymentId. This lets us compute each payment's remaining refundable amount in O(1) later. All money uses Decimal (never floats) for exact arithmetic.

Step 2 — compute remaining + build sort keys. For each payment, remaining = amountPaid - refunded, clamped to 0 if negative (over-refunded payments contribute nothing). We push a tuple:

• method_priority maps CREDIT→0, CREDIT_CARD→1, PAYPAL→2, giving rule 2.
• Negating the dashless date integer (2024-03-01 → -20240301) sorts most-recent-first (rule 3).
• The original index breaks ties so same-method/same-date payments keep input order (rule 6).

Step 3 — sort and greedily allocate. ordered_payments.sort() orders by the tuple lexicographically. Walking the sorted list, for each payment with positive remaining we take min(remaining, request_left), record (paymentId, method, amount), and decrement the request. We fully exhaust one payment before moving on (rule 1), and stop once request_left hits 0.

Correctness: the lexicographic sort key exactly encodes the required priority chain, and greedy draining is optimal because every dollar must be placed in the highest-priority available slot. Whatever request remains after all payments is the shortfall. Amounts are formatted to two decimals with ROUND_HALF_UP.

• Time complexity: O(n log n + m)
• Space complexity: O(n + m)