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.