Match payments to invoices by memo or amount

Scenario

You are building a small reconciliation tool that matches payments to invoices.

Data structures

Assume you are given:

• invoices: a list of invoice objects/records with fields:

• invoice_id: string (unique)

• amount: int (or decimal; assume exact match is possible)

• due_date: string in ISO format YYYY-MM-DD

• payments: a list of payment objects/records with fields:

• payment_id: string (unique)

• amount: int

• memo: string (free-form text; may contain extra spaces)

Memo format

Some payments have a standard memo format that includes an invoice id, e.g.:

• "Paying off: INV-12345 ..."

If the memo contains the substring "Paying off:", then the invoice id immediately following it (after trimming spaces) is the target invoice_id. (You may assume the invoice id token ends at the next whitespace.)

Task

Implement matching logic to process each payment and produce a match result.

Part 1 (ID-based)

For payments whose memo contains "Paying off:":

1. Parse the invoice id from the memo.
2. Find the invoice with that invoice_id.
3. Output a record indicating the payment matched that invoice.
4. If no such invoice exists, output an error for that payment (e.g., "cannot find invoice_id=...").

Part 2 (extended: ID-based OR amount-based)

Extend the logic as follows:

• If the memo contains "Paying off:", use the ID-based logic from Part 1.
• Otherwise, use amount-based matching:

1. Find all invoices with invoice.amount == payment.amount.
2. If none exist, output an error for that payment (e.g., "cannot find matching invoice for amount=...").
3. If multiple invoices match by amount, choose the one with the earliest due_date.

Output requirements

Return a list of match results (one per payment), where each result includes:

• payment_id
• matched_invoice_id (or null if unmatched)
• match_mode: one of { "id", "amount" } (or "unmatched")
• optionally an error_message for unmatched cases

Constraints / edge cases to handle

• Extra spaces in memo around "Paying off:" and/or the invoice id token.
• Large input sizes: design for near-linear time in the number of invoices + payments.
• Multiple invoices can share the same amount; tie-break using earliest due date.