Q7 - Stripe Invoice Reconciliation Problem (3 Parts)

Scenario: Stripe Invoicing lets a business send an invoice and get paid for it. Most of the time the customer pays the invoice directly and there is nothing to work out. The awkward case is the bank transfer. Money lands in the account carrying almost nothing: an amount, and a short memo line the customer's bank passed along. Something still has to decide which open invoice that money was meant for, and that something is what you are writing.

You are given one payment and the list of open invoices for that one customer, and you return a single line of text. Both arrive as plain comma-separated strings:

payment:   payment-id,amount,memo
invoice:   invoice-id,due-date,amount-due

• amount and amount-due are in USD minor units, so $450.00 arrives as 45000. Every number in this problem is an integer and no float is ever needed.
• due-date is YYYY-MM-DD.
• memo is everything after the second comma, and it is allowed to contain commas of its own. Banks write these lines, not people, and they are rarely tidy.

Your answer is one of these two strings:

matched:    <payment-id> pays off <amount> for <invoice-id> due on <due-date>
no match:   <payment-id> could not be matched to any invoice

Every example on this page runs against the same five open invoices, so you can keep one picture in your head the whole way down:

invoices = [
    "inv_1028,2024-02-24,45800",
    "inv_1041,2024-03-02,45000",
    "inv_1055,2024-03-09,128000",
    "inv_1062,2024-03-09,45000",
    "inv_1078,2024-03-21,96500",
]

Part 1: The Memo Names the Invoice (~10 minutes)

Customers paying by transfer are asked to put the invoice number in the reference field, and most of them do. When they have, the memo carries a marker followed by the invoice id.

• The marker is Paying off: or Paying for:, matched case-insensitively, and it can sit anywhere inside the memo, not only at the start. Banks happily staple their own text on the front.
• The invoice id is everything after the marker, trimmed.
• If an invoice with that id is in the book, that is the match, whatever the amounts say. A customer who tells you which invoice they are paying does not get overruled by arithmetic.
• If there is no marker, or the id is not in the book, Part 1 reports no match.

INPUT:
   payment = "py_7744,45000,Paying off: inv_1078"

OUTPUT:
   py_7744 pays off 45000 for inv_1078 due on 2024-03-21

WHY:
   The memo names inv_1078, which is in the book, so that is the answer.
   inv_1078 is owed 96500 and only 45000 arrived, and it does not matter:
   this is a part payment, and the customer already said where it goes.

INPUT:
   payment = "py_7731,128000,Wire from Northwind Traders, paying off: inv_1055"

OUTPUT:
   py_7731 pays off 128000 for inv_1055 due on 2024-03-09

WHY:
   The bank put its own words first and a comma in the middle of the memo.
   The marker is lowercase here and capitalised in Example 1. Neither the
   position nor the case is allowed to change the answer.

INPUT:
   payment = "py_7752,45000,Bank Transaction"

OUTPUT:
   py_7752 could not be matched to any invoice

WHY:
   No marker, so there is no reference to read. Two invoices in the book are
   owed exactly 45000, and in Part 1 you are not allowed to use that yet.

Solution - Part 1

Three small steps, and each one has a trap in it that has nothing to do with algorithms and everything to do with reading the format carefully.

Step 1: Split the payment into exactly three fields

The memo can contain commas, so splitting on every comma shreds it. You want to split on the first two commas only and let the third field keep everything that is left.

"py_7731,128000,Wire from Northwind Traders, paying off: inv_1055"

split on EVERY comma   ->  4 pieces, and the memo is in ruins
   "py_7731" | "128000" | "Wire from Northwind Traders" | " paying off: inv_1055"

split on the FIRST TWO ->  3 pieces, memo intact
   "py_7731" | "128000" | "Wire from Northwind Traders, paying off: inv_1055"

Every language has a way to say this, and the argument means slightly different things in each:

# "py_7731,128000,Wire from Acme, paying off: inv_1055"
#     -> ("py_7731", "128000", "Wire from Acme, paying off: inv_1055")
payment_id, raw_amount, memo = payment.split(",", 2)
amount = int(raw_amount)

Step 2: Find the reference inside the memo

Lowercase a copy of the memo to search it, then slice the original so the invoice id keeps its real capitalisation.

memo:     "Wire from Northwind Traders, paying off: inv_1055"
lowered:  "wire from northwind traders, paying off: inv_1055"
                                        ^ marker found at index 29

slice the ORIGINAL from 29 + len("paying off:"), then trim  ->  "inv_1055"

def referenced_invoice_id(memo):
    lowered_memo = memo.lower()
    for marker in MARKERS:
        position = lowered_memo.find(marker)
        if position != -1:
            return memo[position + len(marker):].strip()
    return ""

Returning "" when there is no marker saves you a null check later. No real invoice is called "", so the lookup in Step 3 fails on its own, and the memo "Paying off: " with nothing after it takes the same harmless path.

Step 3: Look that id up in the book

A straight scan. Five invoices in the examples and a few dozen in the worst real case, so there is nothing to optimise here.

referenced id: "inv_1055"

   inv_1028   no
   inv_1041   no
   inv_1055   yes  ->  pays off 128000 for inv_1055 due on 2024-03-09

from dataclasses import dataclass

MARKERS = ("paying off:", "paying for:")


@dataclass
class Invoice:
    invoice_id: str
    due_date: str
    amount_due: int


def parse_invoices(invoices):
    # "inv_1041,2024-03-02,45000" -> Invoice("inv_1041", "2024-03-02", 45000)
    book = []
    for line in invoices:
        invoice_id, due_date, amount_due = line.split(",")
        book.append(Invoice(invoice_id, due_date, int(amount_due)))
    return book


def referenced_invoice_id(memo):
    # "Wire from Acme, paying off: inv_1055" -> "inv_1055"
    lowered_memo = memo.lower()
    for marker in MARKERS:
        position = lowered_memo.find(marker)
        if position != -1:
            return memo[position + len(marker):].strip()
    return ""


def settled(payment_id, amount, invoice):
    return (f"{payment_id} pays off {amount} for {invoice.invoice_id} "
            f"due on {invoice.due_date}")


def reconcile(payment, invoices):
    payment_id, raw_amount, memo = payment.split(",", 2)
    amount = int(raw_amount)
    book = parse_invoices(invoices)

    referenced_id = referenced_invoice_id(memo)
    for invoice in book:
        if invoice.invoice_id == referenced_id:
            return settled(payment_id, amount, invoice)

    return f"{payment_id} could not be matched to any invoice"

Complexity Analysis

• Time: O(n + m) for n invoices and a memo of length m. One pass to parse the book, one scan for the marker, one scan for the id.
• Space: O(n) for the parsed book.

Part 2: No Reference, So Match on the Amount (~15 minutes)

Plenty of transfers arrive with a memo the bank wrote rather than the customer: Bank Transaction, ACH credit, ref 00231, a sort code and a date. There is no reference to read, and the money still has to land somewhere.

So Part 1's rule stops being the answer and becomes the first of two rules:

1. The memo reference still goes first, and still wins whenever it names an invoice that is actually in the book.
2. A memo naming an invoice nobody has counts as no reference at all. Stale invoice numbers get copied into transfer forms constantly. That payment is still real money and still has to be reconciled, so it falls through to the next rule rather than being dropped.
3. Otherwise, match on the amount exactly. Collect every invoice whose amount due equals the payment, and take the one with the earliest due date. If two of those share a due date, take the smaller invoice id, purely so there is one right answer rather than two.

INPUT:
   payment = "py_7802,45000,ACH credit, ref 00231"

OUTPUT:
   py_7802 pays off 45000 for inv_1041 due on 2024-03-02

WHY:
   Nothing in the memo to read. Two invoices are owed exactly 45000:
   inv_1041 due 2024-03-02 and inv_1062 due 2024-03-09. The older bill
   gets paid first, so inv_1041 takes it.

INPUT:
   payment = "py_7815,96500,PAYING OFF: inv_9999"

OUTPUT:
   py_7815 pays off 96500 for inv_1078 due on 2024-03-21

WHY:
   There IS a marker, in capitals, and it names inv_9999, which is not in
   the book. Rule 1 therefore produces nothing and rule 2 gets its turn.
   Exactly one invoice is owed 96500, so inv_1078 takes it.

INPUT:
   payment = "py_7820,31000,Bank Transaction"

OUTPUT:
   py_7820 could not be matched to any invoice

WHY:
   No reference, and no invoice is owed exactly 31000. Both rules come up
   empty, so the honest answer is that this payment needs a human.

Solution - Part 2

The code barely grows. What changes is its shape: the memo lookup is no longer a function that answers the question, it is the first of a list of attempts.

Step 1: Turn the answer into a tier

In Part 1, missing the memo reference meant falling straight to the failure string at the bottom of the function. Now that failure string moves down past the new rule, so a miss means "keep going" rather than "give up". The edit is small. The idea behind it is the most important one in the question.

Part 1:
   rule 1 hits    ->  that invoice
   rule 1 misses  ->  "could not be matched"     <- the function ends here

Part 2:
   rule 1 hits    ->  that invoice
   rule 1 misses  ->  fall through to rule 2     <- the only real change
   rule 2 hits    ->  earliest due date wins
   rule 2 misses  ->  "could not be matched"

Notice that "the memo named inv_9999 and we have never heard of it" and "there was no memo at all" land in exactly the same place. You get that for free from a scan that simply finds nothing, which is why no special case for an unknown id ever appears in the code.

Step 2: Collect every exact-amount candidate

Filter the book rather than returning the first hit, because you cannot tell whether the first hit is the right one until you have seen the rest.

payment amount: 45000

   inv_1028   45800    no
   inv_1041   45000    YES   due 2024-03-02
   inv_1055  128000    no
   inv_1062   45000    YES   due 2024-03-09
   inv_1078   96500    no

candidates = [inv_1041, inv_1062]

Step 3: The earliest due date wins, and the dates sort themselves

YYYY-MM-DD is fixed-width with the most significant field first, so plain text comparison already orders it correctly. No date parsing is needed anywhere in this problem.

"2024-03-02" < "2024-03-09"   ->  true
"2024-03-09" < "2024-03-21"   ->  true

candidates = [inv_1041 (2024-03-02), inv_1062 (2024-03-09)]
                      ^ earliest, so this is the match

def earliest_due(candidates):
    return min(candidates,
               key=lambda invoice: (invoice.due_date, invoice.invoice_id))

The second key is the tie-break. Two invoices for the same customer, the same amount and the same due date is unusual but not impossible, and an interviewer who notices you handled it without being asked will say so.

from dataclasses import dataclass

MARKERS = ("paying off:", "paying for:")


@dataclass
class Invoice:
    invoice_id: str
    due_date: str
    amount_due: int


def parse_invoices(invoices):
    # "inv_1041,2024-03-02,45000" -> Invoice("inv_1041", "2024-03-02", 45000)
    book = []
    for line in invoices:
        invoice_id, due_date, amount_due = line.split(",")
        book.append(Invoice(invoice_id, due_date, int(amount_due)))
    return book


def referenced_invoice_id(memo):
    # "Wire from Acme, paying off: inv_1055" -> "inv_1055"
    lowered_memo = memo.lower()
    for marker in MARKERS:
        position = lowered_memo.find(marker)
        if position != -1:
            return memo[position + len(marker):].strip()
    return ""


def earliest_due(candidates):
    return min(candidates,
               key=lambda invoice: (invoice.due_date, invoice.invoice_id))


def settled(payment_id, amount, invoice):
    return (f"{payment_id} pays off {amount} for {invoice.invoice_id} "
            f"due on {invoice.due_date}")


def reconcile(payment, invoices):
    payment_id, raw_amount, memo = payment.split(",", 2)
    amount = int(raw_amount)
    book = parse_invoices(invoices)

    referenced_id = referenced_invoice_id(memo)
    for invoice in book:
        if invoice.invoice_id == referenced_id:
            return settled(payment_id, amount, invoice)

    exact = [invoice for invoice in book if invoice.amount_due == amount]
    if exact:
        return settled(payment_id, amount, earliest_due(exact))

    return f"{payment_id} could not be matched to any invoice"

Complexity Analysis

• Time: O(n + m) still, for n invoices and a memo of length m. The amount filter is one more pass over the same book.
• Space: O(n) for the book plus the candidate list.

Part 3: The Wire Arrived Short (~20 minutes)

International transfers lose money on the way. An intermediary bank takes its fee out of the amount while it is still in flight, so a customer who sends $1,280.00 against a $1,280.00 invoice can leave you looking at $1,272.00. Chasing someone for the missing eight dollars costs more than eight dollars.

So you are now given a third input, forgiveness, a non-negative integer in minor units, and a third rule to try when the first two come up empty:

• An invoice qualifies when its amount due is above the payment but no more than forgiveness above it: amount < amountDue <= amount + forgiveness.
• Among the invoices that qualify, the earliest due date wins, same as before.
• When this rule fires, the output has to say how much was written off. The line gains a suffix:

<payment-id> pays off <amount> for <invoice-id> due on <due-date>, forgiving <n>

INPUT:
   payment     = "py_7830,127200,Wire transfer, GB intermediary"
   forgiveness = 2500

OUTPUT:
   py_7830 pays off 127200 for inv_1055 due on 2024-03-09, forgiving 800

WHY:
   No reference in the memo, and no invoice is owed exactly 127200. Rule 3
   looks at (127200, 129700] and finds inv_1055 at 128000. The bank took
   800 on the way, which is inside the 2500 allowance.

INPUT:
   payment     = "py_7841,46200,Bank Transaction"
   forgiveness = 2500

OUTPUT:
   py_7841 could not be matched to any invoice

WHY:
   inv_1028 is owed 45800, which is only 400 from 46200, and it still does
   not qualify: 45800 is BELOW what arrived. That is an overpayment, not a
   shortfall, and forgiveness does not reach downward.

INPUT:
   payment     = "py_7856,45000,Bank Transaction"
   forgiveness = 2500

OUTPUT:
   py_7856 pays off 45000 for inv_1041 due on 2024-03-02

WHY:
   Rule 2 finds inv_1041 and inv_1062, both owed exactly 45000, and takes
   the earlier one. Rule 3 never runs, so inv_1028 is never considered even
   though its due date is the earliest in the whole book.

Solution - Part 3

One more tier on the end, and two ways to get it wrong that the examples above are built to catch.

Step 1: The window only reaches upward

Picture the payment as a point on a number line. Everything at or below it is out of reach, and the window is the stretch immediately above it.

Forgiveness reaches up from the payment, never down

forgivable = [invoice for invoice in book
              if amount < invoice.amount_due <= amount + forgiveness]

The lower bound is strict and the upper bound is inclusive. The strict lower bound is free correctness: an invoice owed exactly amount would have been caught by rule 2, so if you have reached rule 3 at all, there are none left to exclude. You never need a separate check for "already matched exactly".

Step 2: Keep the tiers apart

The tempting shortcut is to collapse rules 2 and 3 into one window, [amount, amount + forgiveness], and take the earliest due date out of that. It is shorter, and it is wrong. Example 3 is the proof:

payment 45000, forgiveness 2500

   ONE MERGED WINDOW  [45000, 47500]
      inv_1028   45800   due 2024-02-24   <- earliest, so this would win
      inv_1041   45000   due 2024-03-02
      inv_1062   45000   due 2024-03-09
   answer: pays off 45000 for inv_1028 ... forgiving 800        WRONG

   TWO SEPARATE TIERS
      rule 2  [45000]          -> inv_1041, inv_1062  -> inv_1041 is earlier
      rule 3  never runs, because rule 2 already produced an answer
   answer: pays off 45000 for inv_1041 due on 2024-03-02        RIGHT

An invoice that costs exactly what arrived beats one that merely costs nearly that, no matter how old the near miss is. Writing off money is the last resort, not a tie-break.

Step 3: The output has to explain itself

settled now needs to know why it matched, not just what it matched. Pass the forgiven amount in and let it decide, rather than inferring it from the numbers:

def settled(payment_id, amount, invoice, forgiven=0):
    line = (f"{payment_id} pays off {amount} for {invoice.invoice_id} "
            f"due on {invoice.due_date}")
    if forgiven > 0:
        line += f", forgiving {forgiven}"
    return line

That default of 0 is doing real work. The obvious alternative, computing invoice.amount_due - amount inside settled and printing the suffix whenever it comes out positive, looks equivalent and is not: Example 1 of Part 1 is a part payment of 45000 against an invoice owed 96500, matched by its memo reference. The difference is positive, so that version would announce forgiving 51500 on a payment where nothing was forgiven at all. The caller knows which rule fired, so the caller is the one that gets to say.

from dataclasses import dataclass

MARKERS = ("paying off:", "paying for:")


@dataclass
class Invoice:
    invoice_id: str
    due_date: str
    amount_due: int


def parse_invoices(invoices):
    # "inv_1041,2024-03-02,45000" -> Invoice("inv_1041", "2024-03-02", 45000)
    book = []
    for line in invoices:
        invoice_id, due_date, amount_due = line.split(",")
        book.append(Invoice(invoice_id, due_date, int(amount_due)))
    return book


def referenced_invoice_id(memo):
    # "Wire from Acme, paying off: inv_1055" -> "inv_1055"
    lowered_memo = memo.lower()
    for marker in MARKERS:
        position = lowered_memo.find(marker)
        if position != -1:
            return memo[position + len(marker):].strip()
    return ""


def earliest_due(candidates):
    return min(candidates,
               key=lambda invoice: (invoice.due_date, invoice.invoice_id))


def settled(payment_id, amount, invoice, forgiven=0):
    line = (f"{payment_id} pays off {amount} for {invoice.invoice_id} "
            f"due on {invoice.due_date}")
    if forgiven > 0:
        line += f", forgiving {forgiven}"
    return line


def reconcile(payment, invoices, forgiveness):
    payment_id, raw_amount, memo = payment.split(",", 2)
    amount = int(raw_amount)
    book = parse_invoices(invoices)

    referenced_id = referenced_invoice_id(memo)
    for invoice in book:
        if invoice.invoice_id == referenced_id:
            return settled(payment_id, amount, invoice)

    exact = [invoice for invoice in book if invoice.amount_due == amount]
    if exact:
        return settled(payment_id, amount, earliest_due(exact))

    forgivable = [invoice for invoice in book
                  if amount < invoice.amount_due <= amount + forgiveness]
    if forgivable:
        invoice = earliest_due(forgivable)
        return settled(payment_id, amount, invoice, invoice.amount_due - amount)

    return f"{payment_id} could not be matched to any invoice"

Complexity Analysis

• Time: O(n + m) for n invoices and a memo of length m. Three passes over the same small book, each O(n), plus one scan of the memo.
• Space: O(n) for the book and whichever candidate list is live.
• earliest_due is O(c) on c candidates with a linear minimum, or O(c log c) if you reach for a sort. On a single customer's open invoices the difference is theoretical.

The Complete Matcher

Part 3's code above is the complete matcher. Each part only ever added a tier to the end of the same function, which is why the final version is barely longer than the first. What is worth seeing at once is the shape of it:

The whole question, in one picture

And here is the same book answering six different payments, one rule at a time:

1 / 6

Expect to write the test cases yourself

Candidates report being asked to invent their own inputs and supply their own test cases, more than a couple of them, rather than being handed a prepared harness. That is worth knowing before you sit down. People go into this round expecting to fill in a function and watch someone else's tests run against it, and lose real time when the test data never arrives and has to be written under pressure at the end.

Writing them as you go is also the only way to stay honest, because each new rule reaches back and changes what the earlier ones do. "Part 2 works" is not the same claim as "Part 2 works and Part 1 still does". Keep the list, re-run all of it after every part, and the cheapest insurance in the round costs you a minute.

BOOK = [
    "inv_1028,2024-02-24,45800",
    "inv_1041,2024-03-02,45000",
    "inv_1055,2024-03-09,128000",
    "inv_1062,2024-03-09,45000",
    "inv_1078,2024-03-21,96500",
]

CASES = [
    # the memo names an invoice, so the amounts are never looked at
    ("py_7744,45000,Paying off: inv_1078", 0,
     "py_7744 pays off 45000 for inv_1078 due on 2024-03-21"),
    # the memo has its own comma, and the marker is not at the front
    ("py_7731,128000,Wire from Northwind Traders, paying off: inv_1055", 0,
     "py_7731 pays off 128000 for inv_1055 due on 2024-03-09"),
    # a reference nobody has, so it falls through to the amount
    ("py_7815,96500,PAYING OFF: inv_9999", 0,
     "py_7815 pays off 96500 for inv_1078 due on 2024-03-21"),
    # two invoices cost 45000; the earlier due date takes it
    ("py_7802,45000,ACH credit, ref 00231", 0,
     "py_7802 pays off 45000 for inv_1041 due on 2024-03-02"),
    # nothing fits at all
    ("py_7820,31000,Bank Transaction", 0,
     "py_7820 could not be matched to any invoice"),
    # a short wire, inside the allowance
    ("py_7830,127200,Wire transfer, GB intermediary", 2500,
     "py_7830 pays off 127200 for inv_1055 due on 2024-03-09, forgiving 800"),
    # 400 away, but on the wrong side of the payment
    ("py_7841,46200,Bank Transaction", 2500,
     "py_7841 could not be matched to any invoice"),
    # an exact match outranks an older invoice inside the window
    ("py_7856,45000,Bank Transaction", 2500,
     "py_7856 pays off 45000 for inv_1041 due on 2024-03-02"),
    # the three nobody writes a test for:
    ("py_7900,45000,Paying off:   inv_1062  ", 2500,       # padded reference
     "py_7900 pays off 45000 for inv_1062 due on 2024-03-09"),
    ("py_7901,45000,Paying off: ", 2500,                    # marker, no id
     "py_7901 pays off 45000 for inv_1041 due on 2024-03-02"),
    ("py_7902,96000,Wire, ref 42, PAYING FOR: inv_1055", 500,
     "py_7902 pays off 96000 for inv_1055 due on 2024-03-09"),
]

for payment, forgiveness, expected in CASES:
    actual = reconcile(payment, BOOK, forgiveness)
    assert actual == expected, f"{payment}\n  got  {actual}\n  want {expected}"

print(f"{len(CASES)} cases pass")

The last three are the ones that separate a careful answer from a lucky one. A padded reference has to be trimmed, a marker with nothing after it has to fail harmlessly rather than crash, and PAYING FOR: has to work exactly like paying off: even sitting behind two commas of bank noise.

Final Notes

1. The memo is not a field, it is the rest of the line. Split on the first two commas and let the third piece keep everything else. In JavaScript and TypeScript the obvious split(',', 3) does the opposite of what you want, taking the first three pieces and discarding the tail, so find the commas by index instead. It costs people the whole question, and the only symptom is a single failing test.
2. Priority is the question. Rule 1 beats rule 2 beats rule 3, full stop, and a later rule never gets a turn once an earlier one has produced an answer. Merging the exact and the forgiven matches into a single window is the shortcut that looks fine and passes seven of the eight examples on this page. The one it fails is Example 3 of Part 3, which exists for exactly that reason.
3. An unknown reference is a fall-through, not a failure. A memo pointing at inv_9999 is treated exactly like a memo with no marker in it. You get that behaviour for free from a lookup that simply finds nothing, so resist writing a special case for it.
4. Tell settled why it matched. Working the forgiven amount out from amountDue - amount inside the formatter looks tidy and is wrong: a part payment matched by its memo has a positive difference too, and would be reported as forgiven when nothing was. The caller knows which rule fired.
5. Forgiveness points one way. Up, never down. Confirm it with your interviewer in one sentence before you write the comparison, because the symmetric window is what everyone reaches for first.
6. Your Part 1 answer expires the moment Part 2 arrives. "py_7752,45000,Bank Transaction" correctly returns no match under Part 1's rules and correctly matches inv_1041 under Part 2's. That is not a regression, but telling the two apart is only possible if you kept the cases written down. Keep the list, re-run it after every part, and say out loud which answers were supposed to change.
7. Integers everywhere, and dates that sort themselves. Minor units mean no floats, no rounding and no cent that goes missing. YYYY-MM-DD is fixed-width with the big field first, so plain text comparison already orders it and nothing needs parsing into a date type.

Nothing here is hard to write. What is hard is holding four rules steady while a fifth one arrives, and that is precisely the job. A bank file lands every morning, and the lines this code produces go straight onto somebody's real invoice. Get the ladder in the right order and the rest is twenty minutes of work you would be happy to put your name on. 🚀