Design payment-to-invoice matcher with priorities
Company: Stripe
Role: Software Engineer
Category: Data Manipulation (SQL/Python)
Difficulty: medium
Interview Round: Technical Screen
Design and implement a payment-to-invoice matcher. Inputs:
(a) invoices, a list like ["invoice-id-1, 10000, 2022-01-01", "invoice-id-2, 30000, 2022-01-01"], where amounts are integer cents;
(b) payment, a single string like "payment-id, 30000, paying for: invoice-id-1" or "payment-id, 30000" when the invoice id is absent; and
(c) an optional forgiveness value (integer cents). Output: a canonical message "{payment-id} paid {paid_amount} amount for invoice {invoice-id} on date {invoice_date}" and, when forgiveness is used, append "; forgave {difference}" indicating how much was forgiven. Matching rules and priorities:
1) If the payment explicitly contains an invoice id, match that invoice and ignore amount-based or forgiveness-based matching.
2) Otherwise, match by exact amount; if multiple invoices have that amount, pick the earliest by date; if still tied, break ties by smallest invoice-id lexicographically.
3) Otherwise, if a forgiveness value is provided, match the invoice whose amount differs from the payment by at most forgiveness; if multiple qualify, pick the earliest by date, then invoice-id.
4) If nothing matches, specify no match found. Requirements: describe your data structures for invoices and payments, your parsing approach (prefer simple substring/split over regex), and why you use integer cents instead of floats. Provide pseudocode or code for match_payment(invoices, payment, forgiveness=None). Finally, enumerate a comprehensive test suite covering: explicit id present/absent, multiple exact-amount candidates, forgiveness matches (including boundary equals and just-over-the-limit), tie-breaking by date and id, and regression tests ensuring earlier behaviors remain correct after adding forgiveness.
Overview: This question evaluates parsing and data modeling skills, deterministic matching algorithms with prioritization and tie-breaking, handling monetary values as integer cents, and the ability to design comprehensive test suites for edge cases.
Read the full Stripe Software Engineer interview experience this question came from
You are given two tables, invoices and payments, that store invoice and payment information in integer cents (to avoid floating point rounding issues). Write a single SQL query that, for every payment, determines the best matching invoice according to the rules below and produces a canonical message.
Matching rules and priorities:
1) If the payment description explicitly contains an invoice id in the form 'paying for: {invoice_id}', then match to that invoice_id and ignore any amount-based or forgiveness-based matching for that payment.
- If the explicit invoice_id does not exist in the invoices table, treat the payment as having no match and do not fall back to amount or forgiveness matching.
2) Otherwise, try to match by exact amount_cents (payment.amount_cents = invoice.amount_cents).
- If multiple invoices have that amount, pick the earliest invoice_date.
- If there is still a tie, pick the lexicographically smallest invoice_id.
3) Otherwise, if a forgiveness tolerance is provided for the payment (payments.forgiveness_cents is not NULL), match the invoice whose amount_cents differs from the payment by at most forgiveness_cents, i.e. ABS(invoice.amount_cents - payment.amount_cents) <= payments.forgiveness_cents.
- If multiple invoices qualify, pick the earliest invoice_date, then invoice_id lexicographically.
4) If nothing matches, the payment has no matching invoice.
Output requirements:
- For each payment, return:
- payment_id
- matched_invoice_id (NULL if no match)
- paid_amount_cents (the payment.amount_cents)
- invoice_date (NULL if no match)
- forgiveness_used_cents (0 if the match was explicit or exact, or if there is no match; otherwise the absolute difference between invoice and payment amounts for forgiveness-based matches)
- match_type: one of 'explicit_match', 'exact_match', 'forgiveness_match', or 'no_match'
- canonical_message:
* If there is a match without forgiveness: '{payment_id} paid {paid_amount_cents} amount for invoice {invoice_id} on date {invoice_date}'
* If there is a forgiveness-based match: '{payment_id} paid {paid_amount_cents} amount for invoice {invoice_id} on date {invoice_date}; forgave {forgiveness_used_cents}'
* If there is no match: '{payment_id} had no matching invoice'
Assumptions:
- Any payment description that contains an explicit invoice reference will follow the pattern 'paying for: {invoice_id}', with a colon and a space before the invoice_id, and no extra text after the invoice_id.
- Use simple string functions (e.g., POSITION, SUBSTRING) rather than regular expressions to extract the explicit invoice_id from the payments.description field.
Write a SQL query that implements this matching logic and produces the required output for all rows in payments.
Tables
invoices(invoice_id VARCHAR(50), amount_cents INT, invoice_date DATE)
payments(payment_id VARCHAR(50), amount_cents INT, payment_date DATE, description VARCHAR(255), forgiveness_cents INT)
Hints
- First, extract any explicit invoice_id from payments.description using POSITION and SUBSTRING into a separate column or CTE.
- Use ROW_NUMBER() over candidate invoices per payment (exact and forgiveness) to pick the earliest invoice_date, then smallest invoice_id, and then combine explicit, exact, and forgiveness matches with CASE logic.