0

Match payments to invoices by memo and amount

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Match payments to invoices by memo and amount

Companies: Stripe

Difficulty: Medium

Problem statement

A billing system has to match incoming payments to open invoices. Both arrive as comma-separated strings.

  • Invoice: invoice_id,amount,due_date. The amount is an integer in cents. The due date is YYYY-MM-DD.
  • Payment: payment_id,amount,memo. The memo is free text written by the customer. It may be empty, and it may contain commas. When the customer names an invoice, the memo contains Paying off: <invoice_id>. Match the phrase in any letter case, with optional spaces around the colon.

Implement Reconciler(invoice_lines, tolerance=0) with match(payment_line) -> str and reconcile(payment_lines) -> list[str]. Process payments in order. Each invoice can be paid only once. Return "<payment_id> pays <invoice_id> (paid <payment amount>, invoiced <invoice amount>, due <due_date>, by <rule>)" or "<payment_id> unmatched".

Interviewers usually add the rules one part at a time:

  1. Memo (by memo): if the memo names an invoice, the payment pays that invoice. If the named invoice does not exist or is already paid, the payment is unmatched. Do not fall back to the other rules.
  2. Exact amount (by amount): if the memo names no invoice, pay the open invoice whose amount equals the payment. If several match, choose the earliest due date, then the smallest invoice id.
  3. Tolerance (by tolerance): if there is still no match and tolerance > 0, pay the open invoice within tolerance cents of the payment. Choose the smallest difference, then the earliest due date, then the smallest invoice id.

Constraints

  • Up to 10^5 invoices and 10^5 payments.
  • Invoice ids are unique and contain no spaces or commas.

Example

invoices = ["inv_a,5000,2026-03-10", "inv_b,2500,2026-02-01",
            "inv_c,2500,2026-01-15", "inv_d,9900,2026-04-01"]
r = Reconciler(invoices, tolerance=200)

r.match("p1,5000,Paying off: inv_a")
  -> "p1 pays inv_a (paid 5000, invoiced 5000, due 2026-03-10, by memo)"
r.match("p2,2500,thanks, see you")
  -> "p2 pays inv_c (paid 2500, invoiced 2500, due 2026-01-15, by amount)"
r.match("p3,9800,")
  -> "p3 pays inv_d (paid 9800, invoiced 9900, due 2026-04-01, by tolerance)"
r.match("p4,5000,paying off:inv_a")
  -> "p4 unmatched"      # inv_a is already paid

Later follow-ups can include partial payments, one payment covering several invoices, and matching only within the same customer.

Approach

Clarify first. Ask these before writing code:

  • Money is an integer. Amounts are minor units (cents). Never compare floats for money.
  • Dates are ISO YYYY-MM-DD. Then string order is date order and no date parsing is needed.
  • The memo is free text. It can be empty, can use any case ("PAYING OFF:", "paying off :"), and can contain commas. So split a payment line on the first two commas only, and treat everything after as the memo.
  • One payment pays one invoice, and an invoice closes once. Ask what happens to a second payment for a closed invoice. This write-up reports it as unmatched instead of guessing.
  • Output format. Agree on one line per payment. Here: "<payment> pays <invoice> (paid X, invoiced Y, due D, by <rule>)" or "<payment> unmatched".

Part 1: memo match. Load invoices into a dict keyed by id. For each payment, pull the id out of the memo with a regex such as paying\s+off\s*:\s*(\S+) (case-insensitive) and look it up. This is O(1) per payment. Most of the work is parsing, and that is what the interviewer is watching: careful splitting, stripping, and graceful handling of a missing or unknown reference.

Part 2: no reference, so match by amount. A brute-force scan over all invoices for the same amount and the earliest due date is O(n) per payment. That is fine to start with. The better version groups invoices by amount once, with each group sorted by (due_date, invoice_id). Then a payment takes the first open invoice in its amount group. Sorting by id too makes ties deterministic.

Part 3: allow a tolerance. Customers pay a little short or a little over (fees, rounding, FX). Among open invoices with |invoice - payment| <= tolerance, pick the smallest difference, then the earliest due date, then the smallest id. A linear scan is clear and is what most interviewers expect. For big inputs, keep the open invoices in a sorted list by amount and use binary search to check only the window [amount - tol, amount + tol].

Rule order is the invariant. For each payment the rules apply strictly in order: memo, exact amount, tolerance. A memo that names an invoice is authoritative. If that invoice is unknown or already paid, the payment is unmatched. It is not re-routed by amount, because silently paying the wrong customer's invoice is worse than raising an exception for a person to check. Once an invoice is matched it is marked paid, so a batch never uses one invoice twice. Payments are processed in input order, so results are deterministic.

Code

from __future__ import annotations

import re
from dataclasses import dataclass
from typing import Optional

MEMO_REF = re.compile(r"paying\s+off\s*:\s*(\S+)", re.IGNORECASE)


@dataclass
class Invoice:
    invoice_id: str
    amount: int        # minor units (cents)
    due_date: str      # ISO "YYYY-MM-DD", so string order is date order
    paid: bool = False


@dataclass
class Payment:
    payment_id: str
    amount: int
    memo: str


def parse_invoice(line: str) -> Invoice:
    invoice_id, amount, due = (part.strip() for part in line.split(",", 2))
    return Invoice(invoice_id, int(amount), due)


def parse_payment(line: str) -> Payment:
    # The memo is free text and may itself contain commas: split twice only.
    parts = line.split(",", 2)
    memo = parts[2] if len(parts) == 3 else ""
    return Payment(parts[0].strip(), int(parts[1]), memo.strip())


def memo_reference(memo: str) -> Optional[str]:
    m = MEMO_REF.search(memo)
    return m.group(1).rstrip(".,;") if m else None


class Reconciler:
    def __init__(self, invoice_lines: list[str], tolerance: int = 0) -> None:
        self.tolerance = tolerance
        self.invoices: dict[str, Invoice] = {}
        self.by_amount: dict[int, list[Invoice]] = {}
        for line in invoice_lines:
            inv = parse_invoice(line)
            self.invoices[inv.invoice_id] = inv
            self.by_amount.setdefault(inv.amount, []).append(inv)
        for bucket in self.by_amount.values():
            bucket.sort(key=lambda i: (i.due_date, i.invoice_id))

    # Part 1: the memo names the invoice.
    def _by_memo(self, p: Payment) -> Optional[Invoice]:
        ref = memo_reference(p.memo)
        return self.invoices.get(ref) if ref else None

    # Part 2: exact amount, earliest due date among open invoices.
    def _by_exact_amount(self, p: Payment) -> Optional[Invoice]:
        for inv in self.by_amount.get(p.amount, []):
            if not inv.paid:
                return inv
        return None

    # Part 3: closest amount within tolerance, then earliest due date.
    def _by_tolerance(self, p: Payment) -> Optional[Invoice]:
        best: Optional[Invoice] = None
        best_key: tuple[int, str, str] | None = None
        for inv in self.invoices.values():
            diff = abs(inv.amount - p.amount)
            if inv.paid or diff > self.tolerance:
                continue
            key = (diff, inv.due_date, inv.invoice_id)
            if best_key is None or key < best_key:
                best, best_key = inv, key
        return best

    def match(self, payment_line: str) -> str:
        p = parse_payment(payment_line)
        ref = memo_reference(p.memo)
        if ref is not None:
            inv = self._by_memo(p)
            if inv is None or inv.paid:
                # A named invoice is authoritative: never silently re-route it.
                return f"{p.payment_id} unmatched"
            how = "memo"
        else:
            inv = self._by_exact_amount(p)
            how = "amount"
            if inv is None and self.tolerance > 0:
                inv = self._by_tolerance(p)
                how = "tolerance"
            if inv is None:
                return f"{p.payment_id} unmatched"
        inv.paid = True
        return (f"{p.payment_id} pays {inv.invoice_id} "
                f"(paid {p.amount}, invoiced {inv.amount}, due {inv.due_date}, by {how})")

    def reconcile(self, payment_lines: list[str]) -> list[str]:
        return [self.match(line) for line in payment_lines]

Usage:

r = Reconciler(["inv_a,5000,2026-03-10", "inv_b,2500,2026-02-01",
                "inv_c,2500,2026-01-15"], tolerance=100)
r.reconcile(["p1,5000,Paying off: inv_a", "p2,2500,thanks", "p3,2450,"])
# ['p1 pays inv_a (paid 5000, invoiced 5000, due 2026-03-10, by memo)',
#  'p2 pays inv_c (paid 2500, invoiced 2500, due 2026-01-15, by amount)',
#  'p3 pays inv_b (paid 2450, invoiced 2500, due 2026-02-01, by tolerance)']

Complexity

Let n be the number of invoices and m the number of payments.

  • Build: O(n log n) time to group by amount and sort each group, O(n) space.
  • Memo match: O(L) to scan a memo of length L, then O(1) dict lookup.
  • Exact amount match: O(k) worst case, where k is the size of the amount group, because paid invoices at the front are skipped. Popping paid invoices off the front (or keeping a per-group pointer) makes this amortized O(1).
  • Tolerance match: O(n) per payment with the linear scan. With a sorted list of open invoices it is O(log n + w), where w is the number of invoices in the tolerance window.
  • Batch: O(m * n) worst case with the linear tolerance scan, and about O((n + m) log n) with the sorted-list version.

Test cases

Invoices: inv_a,5000,2026-03-10, inv_b,2500,2026-02-01, inv_c,2500,2026-01-15, inv_d,9900,2026-04-01.

  • "p1,5000,Paying off: inv_a" gives p1 pays inv_a (..., by memo).
  • "p2,2500,thanks!" (no reference) gives p2 pays inv_c, the earlier of the two 2500 invoices.
  • "p3,2500," (empty memo) gives p3 pays inv_b, because inv_c is now paid.
  • "p4,2500," gives p4 unmatched, because both 2500 invoices are paid.
  • "p5,5000,paying off: inv_a" (lowercase) after p1 gives p5 unmatched, because the named invoice is already paid and is not re-routed.
  • "p6,10,PAYING OFF:inv_zz" (unknown id, no space) gives p6 unmatched.
  • With tolerance=200: "q1,9800,hello, world" (commas in memo) gives q1 pays inv_d (..., by tolerance).
  • With tolerance=200: "q2,2450," gives q2 pays inv_c. Both 2500 invoices are 50 away, so the earlier due date wins.
  • With tolerance=200: "q3,7000," gives q3 unmatched, because no invoice is within 200.
  • Memo "Re: invoice, Paying off: inv_9. thx" extracts inv_9, with trailing punctuation removed.
  • No invoices at all: every payment is unmatched.

Follow-ups

  1. Partial payments. An invoice can be paid in several parts. Track remaining instead of paid, subtract each payment, and close the invoice at zero. Decide what happens with an overpayment: it can be an error, a credit on the customer's account, or applied to the next invoice by due date.
  2. One payment covers several invoices. The memo lists ids ("paying off: inv_1, inv_2"), or there is no memo and the amount equals a sum of open invoices. The memo case is a parse-and-loop. The no-memo case is subset sum, which is NP-hard in general. Limit it to a few invoices for the same customer, try the earliest-due combination first, and say why an exact search does not scale.
  3. Customer scoping. Payments and invoices carry a customer id. Match only within the same customer. Group invoices by (customer, amount) so lookups stay fast and one customer's payment never closes another customer's invoice.
  4. Streaming and idempotency. Payments arrive one at a time and can be retried. Keep a set of seen payment ids so a retry returns the earlier result. Persist the matches. A late invoice can be matched against earlier unmatched payments in the same way.
  5. Explainability. Finance needs to know why a match was made. Return a structured result (rule used, amount difference, competing candidates) instead of a string. Send ambiguous tolerance matches, where several invoices tie on difference and date, to a review queue.

Interviewer expectations

Mid-level (L4)

  • Parses both formats correctly, including an empty memo and a memo with commas.
  • Gets memo matching working first, then adds the amount fallback with a clear earliest-due-date tie-break.
  • Uses integer amounts and tests a few edge cases out loud.

Senior (L5)

  • Asks about rule priority, reused invoices, and the output format before coding. Defends the "named invoice is authoritative" choice.
  • Builds indexes (by id, by amount) so the hot path is not a full scan. Keeps the matching rules small and easy to extend for the tolerance part.
  • Makes all tie-breaks deterministic and explains the cost of each rule.

Staff (L6+)

  • Frames this as a ledger problem: idempotent retries, partial payments, customer scoping, and an audit trail for every match.
  • Sees that matching one payment to several invoices by amount alone is subset sum, and proposes bounded heuristics plus a human review queue.
  • Talks about running it in production: a structured match record, a sorted-amount index for tolerance, and metrics on the unmatched rate.

Sign in to comment, vote or remix.