Implement prioritized refund allocation engine

Quick 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.

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.

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.

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.

Community answers

Answer by AS12

//payments: [{paymentId, method, date, amountPaid}]//refunds: [{paymentId, amountRefunded}]//refundRequest //Output: [(paymentId, method, amount)] function RefundAllocationSystem (payments, refunds, refundRequest){ const remaining = new Map(); const paymentInfo = new Map(); // const groups = { // CREDIT: [], // CREDIT_CARD: [], // PAYPAL: [] // }; const priority = { CREDIT: 0, CREDIT_CARD: 1, PAYPAL: 2 }; const groups = []; for(const payment of payments){ remaining.set(payment.paymentId, payment.amountPaid); paymentInfo.set(payment.paymentId, { method: payment.method, date: payment.date }); } for(const refund of refunds){ if(remaining.has(refund.paymentId)){ let rem = remaining.get(refund.paymentId) - refund.amountRefunded; remaining.set(refund.paymentId, Math.max(0, rem)); } } for(const p of payments){ const remainingAmount = remaining.get(p.paymentId); if(remainingAmount > 0){ groups.push({ paymentId: p.paymentId, method: p.method, date: p.date, amount: remaining }) } } groups.sort((a,b) => { if(prioirity[a.method] !== priority[b.method]){ return priority[a.method] - priority[b.method]; } return new Date(b.date) - new Date(a.date); }); let remainingRefund = Number(refundRequest); const allocations = []; for(const group in groups){ if(remainingRequest <= 0) break; const allocated = group.amount - remainingRefund; allocations.push({ paymentId: group.paymentId, method: p.method, amount: allocated }) remainingRefund -= allocated; } return { allocations, shortfall: remainingRefu

Answer by AS12

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)