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.

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.

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.

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

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

Loading coding console...

Show the approach

Approach

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.

Time complexity:
O(n log n)
Space complexity:
O(n)