Implement prioritized refund allocation engine
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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.
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.
Input: ([], [], '25.00')
Expected Output: ([], '25.00')
Explanation: There are no payments to refund against, so nothing can be allocated and the full request becomes shortfall.
Input: ([('z1', 'PAYPAL', '2024-01-01', '10.00')], [], '0.00')
Expected Output: ([], '0.00')
Explanation: A zero refund request needs no allocations and has no shortfall.
Input: ([('r1', 'CREDIT_CARD', '2024-02-01', '30.00'), ('r2', 'CREDIT', '2024-02-10', '15.00'), ('r3', 'CREDIT', '2024-02-05', '20.00'), ('r4', 'PAYPAL', '2024-03-01', '100.00')], [('r3', '5.00')], '40.00')
Expected Output: ([('r2', 'CREDIT', '15.00'), ('r3', 'CREDIT', '15.00'), ('r1', 'CREDIT_CARD', '10.00')], '0.00')
Explanation: CREDIT has highest priority. Among CREDIT payments, r2 is newer than r3, so refund 15 from r2, then 15 from r3. The remaining 10 comes from the next method priority, CREDIT_CARD.
Solution
def solution(payments, existing_refunds, refund_request):
from collections import defaultdict
from decimal import Decimal, ROUND_HALF_UP
def to_decimal(value):
return Decimal(str(value))
def fmt(value):
return f"{value.quantize(Decimal('0.01'), rounding=ROUND_HALF_UP):.2f}"
refunded_by_payment = defaultdict(lambda: Decimal('0'))
for payment_id, amount_refunded in existing_refunds:
refunded_by_payment[payment_id] += to_decimal(amount_refunded)
method_priority = {'CREDIT': 0, 'CREDIT_CARD': 1, 'PAYPAL': 2}
ordered_payments = []
for index, (payment_id, method, date, amount_paid) in enumerate(payments):
paid = to_decimal(amount_paid)
refunded = refunded_by_payment.get(payment_id, Decimal('0'))
remaining = paid - refunded
if remaining < 0:
remaining = Decimal('0')
ordered_payments.append(
(method_priority[method], -int(date.replace('-', '')), index, payment_id, method, remaining)
)
ordered_payments.sort()
request_left = to_decimal(refund_request)
if request_left < 0:
request_left = Decimal('0')
allocations = []
for _, _, _, payment_id, method, remaining in ordered_payments:
if request_left <= 0:
break
if remaining <= 0:
continue
allocated = remaining if remaining <= request_left else request_left
allocations.append((payment_id, method, fmt(allocated)))
request_left -= allocated
shortfall = request_left if request_left > 0 else Decimal('0')
return allocations, fmt(shortfall)Time complexity: O(n log n + m), where n is the number of payments and m is the number of existing refunds. Space complexity: O(n + m).
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.