Implement prioritized refund allocation engine
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: 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.
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
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')
Expected 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.
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')
Expected 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
- First aggregate all existing refunds by paymentId so each payment has one remaining refundable amount.
- A custom sort key can enforce both method priority and most-recent-first ordering before you do a single allocation pass.