Invoice Reconciliation

Invoice Reconciliation Problem Overview
Stripe's "Invoice Reconciliation" interview question involves parsing payment and invoice data to match payments to specific invoices, typically using string parsing to extract invoice references from payment memos and a hash table for efficient lookups. It's designed to test precise text extraction and O(1) average-time matching.[7][10]

Full Problem Statement
You're given two lists: one of customer payments (each with amount, date, and a memo field possibly containing an invoice ID like "INV-123") and one of outstanding invoices (each with ID and amount). Parse each payment's memo to identify referenced invoice(s), then reconcile by matching payments to invoices—marking exact matches as paid, handling partial payments by applying to oldest invoices first, and reporting unmatched items. Output a formatted reconciliation summary, such as "Payment of $X on DATE reconciled to INV-Y (remaining $Z)" or "Invoice INV-Y remains unpaid." Use a hash table (dictionary/map) keyed by invoice ID for fast lookups during parsing.[10][7]

Key Techniques

• String Parsing: Scan memo strings for patterns like "INV-\d+" using regex or manual iteration to extract IDs reliably, even with noise (e.g., "Paid INV-456 via bank").
• Hash Table Usage: Store invoices in a map<ID, details> for O(1) payment-to-invoice matching; track remaining balances per invoice.
  This simulates Stripe's automatic reconciliation where memos trigger invoice fulfillment.[3][7]

Input/Output Examples
No complete coded examples surfaced, but based on descriptions:

Example Input:
Payments: [ {amount: 1000, date: "2025-01-15", memo: "Payment for INV-123"}, {amount: 500, date: "2025-01-16", memo: "INV-124 and INV-125"} ] Invoices: [ {id: "INV-123", amount: 1000}, {id: "INV-124", amount: 300}, {id: "INV-125", amount: 400}, {id: "INV-126", amount: 200} ]

Example Output:
Reconciled: Payment $1000 on 2025-01-15 -> INV-123 (paid in full) Reconciled: Payment $500 on 2025-01-16 -> INV-124 ($300 paid, INV-125 ($200 paid; $100 overage) Unpaid: INV-126 ($200) (Partial payments apply sequentially to listed invoices; extras noted as overpayments.)[3][7][10]

Constraints

• 1 ≤ payments/invoices ≤ 10^5 (hash table ensures efficiency).
• Amounts: 1 ≤ value ≤ 10^9 (use 64-bit ints).
• Memos/invoice IDs: strings up to 100 chars; IDs in "INV-\d{1,10}" format.
• Multiple invoices per memo possible (split by "and"/",").
• Edge cases: No memo (apply to oldest unpaid), partial matches, overpayments, duplicates.
  Time: O(N + M) where N=payment chars, M=invoices; Space: O(M).[7]