Payment Invoice Reconciliation

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:

1. ID-Based Matching: Match payments to invoices using explicit invoice IDs in the payment memo
2. Amount-Based Matching: Match payments by amount when no invoice ID is provided, selecting the earliest invoice
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 invoice reference

Invoices (list of strings): [Source: darkinterview.com]

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

• invoice-id: Unique identifier for the invoice
• due-date: Invoice due date in YYYY-MM-DD format
• amount: Invoice amount (integer, in cents)

Output Format

Return a string describing the matched payment:

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

If no match is found, return:

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

Part 1: ID-Based Invoice Matching

Problem Statement

Implement a function reconcile_payment(payment, invoices) that matches a payment to an invoice when the payment memo explicitly references an invoice ID. [Source: darkinterview.com]

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.

Example

Input:

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"
]

Output: [Source: darkinterview.com]

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

Requirements

• 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 doesn't exist in the invoice list

Edge Cases to Consider

• Invoice ID in memo doesn't exist in the invoice list
• Multiple invoices in the list (only one should match)
• Different memo formats or casing variations
• Missing or malformed data in payment string

Part 2: Amount-Based Invoice Matching

Problem Statement

Extend your solution to handle payments that don't 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. [Source: darkinterview.com]

Example

Input:

payment = "payment-002, 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"
]

Output:

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

Note: inv-004 is selected because it has the earliest due date among invoices with amount 500 [Source: darkinterview.com]

Requirements

• Check for invoice ID in memo first (Part 1 logic)
• If no ID found, search for invoices matching the payment amount
• When multiple amount matches exist, select the earliest due date
• Parse dates correctly to compare chronological order
• Return "could not be matched" if no amount match is found

Clarification Questions to Ask

• Should we validate that the amount in ID-matched invoices also matches the payment amount?
• How should we handle ties in due dates (if two invoices have the same amount and date)?
• What date format should we expect and support?
• Should we handle negative amounts or zero amounts?

Part 3: Fuzzy Amount Matching with Forgiveness

Problem Statement

Bank transfers may incur fees or rounding differences. A customer might receive an invoice for $100 but the bank charges a$2 fee, resulting in only $98 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.

Matching Priority: [Source: darkinterview.com]

1. Invoice ID match (from Part 1)
2. Exact amount match (from Part 2)
3. Fuzzy amount match within forgiveness range (Part 3)

Example

Input:

payment = "payment-003, 98, Customer payment"

invoices = [
    "inv-100, 2024-03-15, 100",
    "inv-200, 2024-02-20, 98",
    "inv-300, 2024-01-10, 102"
]

forgiveness = 5

Output:

"Payment payment-003 paid 98 for invoice inv-200 due on 2024-02-20"

Note: inv-200 has exact amount match, so it's selected over inv-100 (which would match within forgiveness) [Source: darkinterview.com]

Another Example with Fuzzy Match:

payment = "payment-004, 95, Customer payment"

invoices = [
    "inv-100, 2024-03-15, 100",
    "inv-300, 2024-01-10, 97"
]

forgiveness = 5

Output:

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

Note: Both invoices are within ±5 of 95, so we select inv-300 (earliest due date) [Source: darkinterview.com]

Requirements

• Accept forgiveness as an additional parameter
• Implement three-tier matching priority (ID → exact amount → 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 fuzzy match has earlier due date

Testing Considerations

When writing test cases, ensure:

• Tests verify that each matching tier is checked in correct priority order
• ID match takes precedence even if amount differs
• Exact amount match takes precedence over fuzzy match
• Fuzzy match only triggers when no exact match exists
• Edge of forgiveness range is handled correctly (e.g., forgiveness=5, difference=5)
• Multiple invoices in the same tier select earliest due date

Solution Approach

Part 1: ID-Based Matching

Strategy:

1. Parse the payment string to extract components
2. Search the memo for invoice ID patterns (e.g., "paying for: X", "paying off: X")
3. Look up the invoice ID in the invoice list
4. Format and return the result

Implementation Approach: [Source: darkinterview.com]

def reconcile_payment(payment, invoices):
    # Parse payment
    parts = payment.split(", ")
    payment_id = parts[0]
    payment_amount = int(parts[1])
    memo = ", ".join(parts[2:])  # Memo may contain commas

    # Try to extract invoice ID from memo (case-insensitive search)
    invoice_id = None
    memo_lower = memo.lower()
    if "paying for:" in memo_lower:
        # Find position in lowercase, extract from original to preserve case
        pos = memo_lower.find("paying for:") + len("paying for:")
        invoice_id = memo[pos:].strip()
    elif "paying off:" in memo_lower:
        pos = memo_lower.find("paying off:") + len("paying off:")
        invoice_id = memo[pos:].strip()

    # Find matching invoice
    if invoice_id:
        for invoice in invoices:
            inv_parts = invoice.split(", ")
            inv_id = inv_parts[0]
            if inv_id == invoice_id:
                inv_date = inv_parts[1]
                inv_amount = inv_parts[2]
                return f"Payment {payment_id} paid {payment_amount} for invoice {inv_id} due on {inv_date}"

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

Time Complexity: O(n) where n is the number of invoices (linear search)

Space Complexity: O(1) - only storing parsed values

Part 2: Amount-Based Matching with Date Selection

Strategy: [Source: darkinterview.com]

1. First try ID-based matching (Part 1 logic)
2. If no ID match, search for invoices with exact amount match
3. Among amount matches, find the invoice with earliest due date
4. Return formatted result

Key Implementation Details:

• Parse dates as strings and compare lexicographically (YYYY-MM-DD format naturally sorts correctly)
• Track the best match (earliest date) while iterating through invoices
• Only perform amount matching if ID matching failed

def reconcile_payment(payment, invoices):
    # Parse payment
    parts = payment.split(", ")
    payment_id = parts[0]
    payment_amount = int(parts[1])
    memo = ", ".join(parts[2:])

    # Try ID-based matching first
    invoice_id = extract_invoice_id_from_memo(memo)
    if invoice_id:
        match = find_invoice_by_id(invoice_id, invoices)
        if match:
            return format_result(payment_id, payment_amount, match)

    # Try amount-based matching
    best_match = None
    earliest_date = None

    for invoice in invoices:
        inv_id, inv_date, inv_amount = parse_invoice(invoice)

        if int(inv_amount) == payment_amount:
            if earliest_date is None or inv_date < earliest_date:
                earliest_date = inv_date
                best_match = (inv_id, inv_date, inv_amount)

    if best_match:
        return format_result(payment_id, payment_amount, best_match)

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

def parse_invoice(invoice):
    """Parse invoice string into components."""
    parts = invoice.split(", ")
    return parts[0], parts[1], parts[2]

def format_result(payment_id, payment_amount, invoice_match):
    """Format the reconciliation result."""
    inv_id, inv_date, inv_amount = invoice_match
     

Time Complexity: O(n) - single pass through invoices for amount matching

Date Comparison Note: YYYY-MM-DD format can be compared as strings because it's lexicographically sortable. [Source: darkinterview.com]

Part 3: Three-Tier Matching with Forgiveness

Strategy:

1. Try ID-based matching (highest priority)
2. Try exact amount matching (second priority)
3. Try fuzzy amount matching within forgiveness range (lowest priority)
4. For each tier, select earliest due date if multiple matches exist

Implementation Structure:

def reconcile_payment(payment, invoices, forgiveness=0):
    # Parse payment
    payment_id, payment_amount, memo = parse_payment(payment)

    # Tier 1: ID-based matching
    invoice_id = extract_invoice_id_from_memo(memo)
    if invoice_id:
        match = find_invoice_by_id(invoice_id, invoices)
        if match:
            return format_result(payment_id, payment_amount, match)

    # Tier 2: Exact amount matching
    exact_match = find_best_amount_match(
        invoices,
        payment_amount,
        exact_only=True
    )
    if exact_match:
        return format_result(payment_id, payment_amount, exact_match)

    # Tier 3: Fuzzy amount matching
    if forgiveness > 0:
        fuzzy_match = find_best_fuzzy_match(
            invoices,
            payment_amount,
            forgiveness
        )
        if fuzzy_match:
            return format_result(payment_id, payment_amount, fuzzy_match)

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

def find_best_fuzzy_match(invoices, payment_amount, forgiveness):
    """Find earliest invoice within forgiveness range."""
    best_match = None
    earliest_date = None

    min_amount = payment_amount - forgiveness
    max_amount = payment_amount + forgiveness

    for invoice in invoices:
        inv_id, inv_date, inv_amount = parse_invoice(invoice)
        inv_amount_int = int(inv_amount)

        # Check if within forgiveness range (but not exact match)
        if (min_amount <= inv_amount_int <= max_amount
            and inv_amount_int != payment_amount):

            if earliest_date is   inv_date < earliest_date:
                earliest_date = inv_date
                best_match = (inv_id, inv_date, inv_amount)

     best_match

Time Complexity: O(n) - at most three passes through invoices (one per tier) [Source: darkinterview.com]

Critical Logic:

• Each matching tier is completely independent
• Lower tiers only execute if higher tiers found no match
• Within each tier, earliest date selection is consistent

Follow-Up Discussion Topics

Test Cases and Matching Priority

Question: How would you design test cases to ensure the matching priority system works correctly across all three parts?

Key Testing Principles: [Source: darkinterview.com]

1. Backward Compatibility: Each part's test cases must verify that previous parts still function correctly

   • Part 2 tests should include Part 1 scenarios (ID-based matching still works)
   • Part 3 tests should include both Part 1 and Part 2 scenarios

2. Priority Verification: Test cases must clearly demonstrate the matching hierarchy:

   • Highest Priority: Invoice ID match (ignore amount considerations)
   • Medium Priority: Exact amount match (don't fall back to forgiveness)
   • Lowest Priority: Fuzzy amount match within forgiveness range

Example Test Cases: [Source: darkinterview.com]

def test_id_match_takes_precedence_over_amount():
    """Verify ID matching ignores amount-based matching."""
    payment = "pay-001, 500, Paying for: inv-100"
    invoices = [
        "inv-100, 2024-03-15, 1000",  # ID matches but amount differs
        "inv-200, 2024-02-10, 500"    # Amount matches but no ID match
    ]
    # Should match inv-100 via ID, not inv-200 via amount
    result = reconcile_payment(payment, invoices)
    assert "inv-100" in result

def test_exact_amount_takes_precedence_over_fuzzy():
    """Verify exact amount match beats fuzzy match."""
    payment = "pay-002, 100, Payment"
    invoices = [
        "inv-100, 2024-03-15, 100",   # Exact match
        "inv-200, 2024-01-10, 98"     # Fuzzy match (within forgiveness)
    ]
    forgiveness = 5
    # Should match inv-100 (exact), not inv-200 (fuzzy)
    result = reconcile_payment(payment, invoices, forgiveness)
    assert "inv-100" in result

def test_fuzzy_match_only_when_no_exact_match():
    """Verify fuzzy matching only activates when needed."""
    payment = "pay-003, 97, Payment"
    invoices = [
        "inv-100, 2024-03-15, 100",   # Within forgiveness range
        "inv-200, 2024-02-10, 200"    # Outside range
    ]
    forgiveness = 5
    # Should match inv-100 via fuzzy logic
    result = reconcile_payment(payment, invoices, forgiveness)
    assert "inv-100" in result

def test_earliest_date_selection_within_same_tier():
    """Verify earliest date selection applies within each matching tier."""
    payment = 
    invoices = [
        ,
        ,   
        
    ]
    
    result = reconcile_payment(payment, invoices)
       result

 ():
    
    
       reconcile_payment(
        ,
        [, ]
    )

    
       reconcile_payment(
        ,
        [, ]
    )

    
       reconcile_payment(
        ,
        [, ],
        forgiveness=
    )

Testing Strategy Summary:

• Always test matching priority: ID > exact amount > fuzzy amount
• Verify that higher-priority matches prevent lower-priority matching logic from executing
• Ensure date selection works correctly within each matching tier
• Test edge cases: exact boundary of forgiveness range, no matches found, multiple candidates