Allocate refund across payments

Q: Allocate refund across payments

This question evaluates algorithm design and data-structure selection skills, focusing on greedy allocation, ordering by priority and recency, aggregation of transaction amounts, and analysis of time complexity.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Airbnb.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Question

##### Question

Given a list of completed payment transactions (each with payment method, date, and amount) and a refund amount R,

write an algorithm that issues refunds according to the rules:

Always refund in full from one payment before moving to the next.

Prefer payment methods in the priority order CREDIT → CREDIT_CARD → PAYPAL.

Within the same method, refund the most recent payment first.

Return the list of refund allocations (payment id, method, amount). Explain the algorithm’s time complexity and data structures.

PracHub · Accepted Answer

def allocate_refund(payments, refund): priority = {'CREDIT': 0, 'CREDIT_CARD': 1, 'PAYPAL': 2} # Filter to recognized methods and positive amounts filtered = [p for p in payments if p.get('method') in priority and p.get('amount', 0) > 0] # Sort by method priority, then by timestamp descending (most recent first) filtered.sort(key=lambda p: (priority[p['method']], -p['ts'])) remaining = refund allocations = [] for p in filtered: if remaining <= 0: break amt = p['amount'] if amt <= 0: continue take = amt if amt <= remaining else remaining if take > 0: allocations.append({'id': p['id'], 'method': p['method'], 'amount': take}) remaining -= take return allocations Assign a priority rank to methods (CREDIT highest). Sort payments by (method priority, descending timestamp) to ensure we process the correct order. Then iterate and greedily allocate from each payment: take min(remaining, payment_amount). This fully uses each payment before moving on, except possibly the last one which may be partial if the remaining refund is smaller than the payment amount. Stop when refund is satisfied or payments are exhausted.

Quick Overview

Explanation

Hints

Quick Overview