Problem Overview

You are building a payment reconciliation system that matches incoming payments to outstanding invoices. When customers send payments, you need to determine which invoice each payment is settling. The matching logic becomes progressively more sophisticated across three parts:

• Part 1 -- ID-Based Matching: Match payments to invoices using explicit invoice IDs in the payment memo

• Part 2 -- Amount-Based Matching: Match payments by amount when no invoice ID is provided, selecting the earliest invoice

• Part 3 -- Fuzzy Amount Matching: Handle bank fees and rounding errors by matching within a tolerance range

Input Format

Payment (single string):

"payment-id, amount, memo"

• payment-id: Unique identifier for the payment

• amount: Payment amount (integer, in cents)

• memo: Payment description, may contain an invoice reference

Invoices (list of strings):

[ "invoice-id, due-date, amount", "invoice-id, due-date, amount", ... ]

• invoice-id: Unique identifier for the invoice

• due-date: Invoice due date in format

"Payment {payment-id} paid {amount} for invoice {invoice-id} due on {date}"

"Payment {payment-id} could not be matched to any invoice"

• There are multiple parts to this problem -- ask the interviewer how many parts there are to better manage your time

• Start with a simple parsing approach and extend matching logic as parts get more complex

• Write your own test cases and ensure your code compiles and runs correctly

Implement a function reconcile_payment(payment, invoices) that matches a payment to an invoice when the payment memo explicitly references an invoice ID.

The payment memo will contain text in the format "paying for: invoice-id" or "Paying off: invoice-id" (case-insensitive). Extract the invoice ID and find the matching invoice.

` payment = "payment-001, 1000, Paying off: inv-123" invoices = [ "inv-123, 2024-03-15, 1000", "inv-456, 2024-03-20, 1000", "inv-789, 2024-02-10, 500" ]

result = reconcile_payment(payment, invoices)

"Payment payment-001 paid 1000 for invoice inv-123 due on 2024-03-15"

`

• Parse the payment string to extract payment ID, amount, and memo

• Search the memo for an invoice ID reference (e.g., "paying for: inv-123")

• Match the extracted invoice ID against the invoice list

• Return the formatted output string

• Handle cases where the referenced invoice ID does not exist in the invoice list

• Can the memo contain multiple invoice references?

• Should we handle different casing in the memo keywords?

• What if the invoice ID in the memo has leading or trailing whitespace?

Extend your solution to handle payments that do not reference a specific invoice ID. When no invoice ID is found in the memo, match the payment to an invoice with the exact same amount.

If multiple invoices have the same amount, select the invoice with the earliest due date.

Your solution must still support ID-based matching from Part 1 -- prioritize ID matching over amount matching.

` payment = "payment-003, 500, Monthly subscription" invoices = [ "inv-001, 2024-03-22, 1000", "inv-002, 2024-02-05, 500", "inv-003, 2024-03-01, 500", "inv-004, 2024-01-15, 500" ]

result = reconcile_payment(payment, invoices)

"Payment payment-003 paid 500 for invoice inv-004 due on 2024-01-15"

inv-004 is selected because it has the earliest due date among invoices with amount 500

`

• Should we validate that the amount in ID-matched invoices also matches the payment amount?

• How should we handle ties in due dates (two invoices with the same amount and same date)?

• Should we handle negative amounts or zero amounts?

Bank transfers may incur fees or rounding differences. A customer might receive an invoice for 100 cents but the bank charges a 2-cent fee, resulting in only 98 cents reaching Stripe. You need to reconcile these near-matches.

Add a third matching strategy: fuzzy amount matching with a forgiveness threshold. If no exact amount match is found, search for invoices where the amount is within +/- forgiveness of the payment amount. Select the earliest due date if multiple invoices qualify.

• Invoice ID match (from Part 1)

• Exact amount match (from Part 2)

• Fuzzy amount match within forgiveness range (Part 3)

` payment = "payment-006, 95, Customer payment" invoices = [ "inv-100, 2024-03-15, 100", "inv-300, 2024-01-10, 97" ] forgiveness = 5

result = reconcile_payment(payment, invoices, forgiveness=5)

"Payment payment-006 paid 95 for invoice inv-300 due on 2024-01-10"

No exact match exists; both invoices are within +/-5 of 95; inv-300 has earliest date

`

• Accept forgiveness as an additional parameter (default 0)

• Implement three-tier matching priority: ID then exact amount then fuzzy amount

• For fuzzy matching, invoice amount must be within [payment_amount - forgiveness, payment_amount + forgiveness]

• Select earliest due date when multiple invoices match in the same tier

• Prefer exact matches over fuzzy matches even if the fuzzy match has an earlier due date