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.

What difficulty level is this coding question?

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

What role is this question designed for?

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

Allocate refund across payments | Airbnb Coding Question

Allocate refund across payments

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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

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

You are given a list of completed payment transactions and a refund amount R. Each payment is a dictionary with fields: id (string or integer), method (one of CREDIT, CREDIT_CARD, PAYPAL), ts (integer UNIX timestamp), and amount (integer in smallest currency units, e.g., cents). Allocate the refund according to these rules: (1) Prefer methods in the priority order CREDIT → CREDIT_CARD → PAYPAL; (2) Within the same method, refund the most recent payment first (larger ts first); (3) Always refund a payment in full before moving to the next; if the remaining refund is less than the next payment amount, refund the remaining amount partially from that payment and stop; (4) Do not exceed the total available amount across all payments. Return the list of allocations in the order processed, where each allocation is a dictionary with id, method, and amount fields indicating how much was refunded from that payment.

Constraints

1 <= len(payments) <= 200000
0 <= refund <= 10^12
For each payment: method ∈ {CREDIT, CREDIT_CARD, PAYPAL}
For each payment: amount is an integer (0 <= amount <= 10^12)
For each payment: ts is an integer UNIX timestamp (0 <= ts <= 10^12)
Inputs are not pre-sorted
If refund exceeds total available amount, refund only the available total
Return allocations in the order they are applied

Hints

Map payment methods to integer priorities (e.g., CREDIT:0, CREDIT_CARD:1, PAYPAL:2) and sort by (priority, -ts).
Greedily consume each payment: allocate min(remaining_refund, payment_amount).
Stop after the first partial allocation or when the refund is fully satisfied.
Edge cases: refund = 0, no payments, or refund larger than total available.
Use integers for amounts to avoid floating-point precision issues.

Quick Overview

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.