0

Refund allocation across prioritized payment methods

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Refund allocation across prioritized payment methods

Companies: Airbnb

Difficulty: Medium

Problem statement

A customer's order was paid with one or more payments, and some of them may already have been partly refunded. Implement a function that splits a new refund across those payments.

def allocate_refund(transactions: list[list[str]], refund: int) -> list[tuple[str, int]]: ...

Each transaction is a list of strings in one of two shapes:

  • Payment: [payment_id, "PAYMENT", method, timestamp, amount], where method is CREDIT, CREDIT_CARD, or PAYPAL.
  • Refund: [refund_id, "REFUND", payment_id, timestamp, amount], a refund already made against that payment.

All amounts are whole cents. Timestamps are integers.

Rules

  1. A payment can give back only what is left on it: its amount minus all earlier refunds against it.
  2. Refund by method first: all CREDIT payments, then CREDIT_CARD, then PAYPAL.
  3. Within one method, refund the most recent payment first. Break exact ties by payment id.
  4. Take as much as possible from each payment before moving to the next.
  5. If the payments cannot cover the full refund, raise an error and allocate nothing.

Return a list of (payment_id, amount) pairs in the order the money is refunded. Skip payments that receive nothing.

Example

transactions = [
  ["a", "PAYMENT", "PAYPAL",      "10", "4000"],
  ["b", "PAYMENT", "CREDIT_CARD", "20", "2500"],
  ["c", "PAYMENT", "CREDIT",      "30",  "800"],
  ["d", "PAYMENT", "CREDIT_CARD", "40", "1500"],
  ["x", "REFUND",  "d",           "50",  "300"],
]
allocate_refund(transactions, 4000)
# -> [("c", 800), ("d", 1200), ("b", 2000)]

Credit c goes first. Card d is newer than b, but only 1200 is left on it after the earlier refund. The last 2000 comes from b, and PayPal is not touched. A request of 8501 or more raises an error, because only 8500 is refundable.

Constraints: up to 10^5 transactions; a refund always names a payment in the list, but it may appear before that payment.

Approach

Clarify first. Pin these down before you write code:

  • Money is integer cents. Never use floats for money. Parse each amount string with int.
  • Priority order. Refund store credit first, then credit cards, then PayPal. Within one method, refund the newest payment first. If two payments have the same method and timestamp, break the tie by payment id so the output is the same every run.
  • Past refunds count. A payment that was already partly refunded can give back only what is left on it. Ask if a refund row can come before its payment in the list. Assume it can, so apply refunds after you load every payment.
  • Not enough money. Ask what happens when the request is bigger than everything still refundable. The usual answer is to reject the whole request and change nothing. A partial refund that leaves the customer short is a worse bug than an error.
  • Output. A list of (payment_id, amount) pairs, in the order the money goes back.

Brute force. Loop until the refund is used up. On each pass, scan every payment to find the best one that still has money left, take what you can, and repeat. This is O(n) per pass and O(n^2) in total. It is correct but a little clumsy.

Optimal: one pass to load, one sort, one greedy walk.

  1. Load every PAYMENT row into a record with amount and refunded = 0.
  2. For every REFUND row, add its amount to that payment's refunded. Reject a refund for an unknown payment, or one that takes a payment below zero.
  3. Check that the total still refundable covers the request. If not, raise an error before you allocate anything.
  4. Sort the payments that have money left by (method rank, -timestamp, payment_id).
  5. Walk the sorted list. Take min(left, payment.remaining) from each payment until left is zero.

Why greedy is correct. The rules are a strict ordering of payments, not an optimization. The only correct answer is to drain payment 1 before you touch payment 2, and so on. So taking as much as possible from each payment in sort order gives exactly the required split.

Invariants.

  • For every payment, 0 <= refunded <= amount.
  • The sum of the allocations equals the request, or nothing is allocated.
  • At most one payment in the output is partly refunded, and it is the last one.

Code

from __future__ import annotations

from dataclasses import dataclass

# Lower rank is refunded first.
METHOD_PRIORITY: dict[str, int] = {"CREDIT": 0, "CREDIT_CARD": 1, "PAYPAL": 2}


@dataclass
class Payment:
    payment_id: str
    method: str
    timestamp: int
    amount: int          # cents
    refunded: int = 0    # cents already refunded

    @property
    def remaining(self) -> int:
        return self.amount - self.refunded


def load_payments(transactions: list[list[str]]) -> dict[str, Payment]:
    """Build payments, then subtract every earlier refund from its payment."""
    payments: dict[str, Payment] = {}
    refunds: list[list[str]] = []
    for row in transactions:
        if row[1] == "PAYMENT":
            pid, _, method, ts, amount = row
            if method not in METHOD_PRIORITY:
                raise ValueError(f"unknown method {method!r}")
            payments[pid] = Payment(pid, method, int(ts), int(amount))
        elif row[1] == "REFUND":
            refunds.append(row)
        else:
            raise ValueError(f"unknown transaction type {row[1]!r}")

    # Refunds may appear before their payment in the list, so apply them last.
    for _, _, pid, _, amount in refunds:
        payment = payments.get(pid)
        if payment is None:
            raise ValueError(f"refund for unknown payment {pid!r}")
        payment.refunded += int(amount)
        if payment.remaining < 0:
            raise ValueError(f"payment {pid!r} refunded more than it paid")
    return payments


def allocate_refund(transactions: list[list[str]], refund: int) -> list[tuple[str, int]]:
    """Split `refund` cents across payments.

    Order: method priority (CREDIT, CREDIT_CARD, PAYPAL), then newest
    payment first, then payment id for a stable tie-break.
    Returns (payment_id, amount) pairs in the order they are refunded.
    Raises ValueError if the payments cannot cover the refund.
    """
    if refund < 0:
        raise ValueError("refund must be non-negative")
    payments = load_payments(transactions)
    total_left = sum(p.remaining for p in payments.values())
    if refund > total_left:
        raise ValueError(f"refund {refund} exceeds refundable {total_left}")

    order = sorted(
        (p for p in payments.values() if p.remaining > 0),
        key=lambda p: (METHOD_PRIORITY[p.method], -p.timestamp, p.payment_id),
    )
    allocations: list[tuple[str, int]] = []
    left = refund
    for payment in order:
        if left == 0:
            break
        take = min(left, payment.remaining)
        allocations.append((payment.payment_id, take))
        left -= take
    return allocations

Complexity

Let n be the number of transactions and p the number of payments.

  • Loading payments and past refunds: O(n) time, O(p) space.
  • Sorting: O(p log p) time.
  • Greedy walk: O(p) time. It stops as soon as the refund is covered.
  • Total per call: O(n + p log p) time and O(p) space.
  • Brute force: O(p^2) time. Fine for a handful of payments, but the sort is just as easy to write.

If refunds are requested many times on the same order, keep the payment records and a sorted list between calls (see Follow-ups). Then each request costs O(k), where k is the number of payments it touches.

Test cases

Payments below are [id, "PAYMENT", method, timestamp, cents]. Refunds are [id, "REFUND", payment_id, timestamp, cents].

  • Mixed methods with a past refund. p1 PAYPAL t=100 5000, p2 CREDIT_CARD t=200 3000, p3 CREDIT t=300 1000, p4 CREDIT_CARD t=400 2000, and a past refund of 500 on p4. A refund of 6000 gives [("p3", 1000), ("p4", 1500), ("p2", 3000), ("p1", 500)]. Credit goes first. p4 is the newer card, but only 1500 is left on it.
  • Zero refund. Same data, refund 0, gives [].
  • Exact total. Same data, refund 10500 (everything left), drains every payment. The last pair is ("p1", 5000).
  • Too large. Same data, refund 10501, raises ValueError and allocates nothing.
  • Refund listed before its payment. [["r", "REFUND", "a", "5", "100"], ["a", "PAYMENT", "CREDIT", "1", "100"], ["b", "PAYMENT", "CREDIT", "1", "50"]], refund 50, gives [("b", 50)]. Payment a is already fully refunded.
  • Tie on method and time. Two PAYPAL payments a and b, both t=1 and 100 cents, refund 150, gives [("a", 100), ("b", 50)] because of the id tie-break.
  • Bad input. An unknown method, an unknown transaction type, a refund for an unknown payment, or past refunds larger than the payment all raise ValueError.

Follow-ups

  1. Record the refund. "Now the system must remember this refund." Turn the function into a class RefundLedger with add_payment, add_refund, and refund(amount, timestamp). refund allocates as above, then writes one REFUND row per allocation so the next call sees them. Make the check and the writes one step, so a failure leaves no half-applied refund.
  2. Several orders or customers. Transactions carry an order_id or customer_id, and a refund may only use payments from that order. Group payments by that key in a dict, and run the same allocation on one group.
  3. Configurable rules. The business adds a method such as GIFT_CARD, or wants oldest-first inside some methods. Pass the priority map and a per-method ordering in, and build the sort key from them. Keep the rules as data, not as if branches.
  4. Refund windows and limits. Cards can only be refunded within 180 days, or PayPal has a per-transaction cap. Filter or cap each payment's remaining before the walk. The greedy walk does not change, because the rules still give a strict order.
  5. Many refunds on a large order. Keep the payments in a list sorted once, plus a pointer to the first payment that still has money. Each refund then starts from the pointer, so the cost is O(k) for the k payments it touches. If new payments can arrive between refunds, keep one heap per method instead.

Interviewer expectations

Mid-level (L4)

  • Parses both row types and applies past refunds to the right payment.
  • Sorts by method, then newest first, and fills the refund greedily.
  • Uses integer cents, and handles a zero refund and a refund larger than the total.

Senior (L5)

  • Asks about the ordering, ties, insufficient funds, and refunds that appear before their payment, before coding.
  • Validates input and rejects the whole request instead of returning a short refund.
  • Explains why greedy is exactly right here, and states the invariants.
  • Moves to the stateful RefundLedger follow-up without rewriting the core.

Staff (L6+)

  • Treats the priority rules as configuration, and keeps the allocation separate from parsing and storage.
  • Talks about atomic writes, idempotency keys for retried refund requests, and an audit trail of which payment each cent went back to.
  • Raises real payment concerns: per-processor refund windows, partial failures at a processor, currency, and reconciling the ledger with the processor's records.

Sign in to comment, vote or remix.