Match Payments to Invoices by ID, Exact Amount, then a Forgiveness Range

You are writing the reconciliation step of a billing system. The system holds a list of **invoices**, receives a list of **payments**, and must decide which invoice each payment pays. The matching rules arrive in three stages. Each stage adds a rule, and the code for a later stage must keep every earlier rule working. - An invoice has an invoice ID, an amount due, and a date. - A payment has a payment ID, an amount, and possibly the ID of the invoice it is meant to pay. In Part 1 every payment carries one. For every payment, report the invoice it matches, or report that it matches none. The problem does not fix the input encoding (parsed records, raw strings, or objects), so state the one you use. ### Constraints and Clarifications - Invoice IDs are unique. - All amounts are in one currency. Treat them as exact values, not floating-point numbers. - "Earliest" always refers to the invoice's date. ### Clarifying Questions - Once an invoice has been matched, is it closed, or may later payments match it again? - Are payments processed one at a time in the given order, with each decision final, or should the whole batch be matched at once? - What should be reported for a payment that matches nothing: a placeholder result, a separate list of unmatched payments, or an error? - If two candidate invoices share the earliest date, which one wins? ### Part 1 — Match by invoice ID Every payment names the invoice it pays. Match each payment to the invoice with that ID. Some payments name an invoice ID that cannot be matched. Your code must handle that case explicitly and must neither crash nor silently drop the payment. ```hint Decide what "no match" looks like Decide what the output looks like for an unmatched payment before you write the lookup, and make sure it cannot be confused with a successful match. ``` #### Clarifying Questions for this Part - If the payment amount differs from the named invoice's amount, is it still a match? - What should happen when two payments name the same invoice? #### What This Part Should Cover - A lookup from invoice ID to invoice that avoids scanning all invoices for each payment - Explicit, tested handling of payments whose invoice ID has no match - Time and space complexity for n invoices and m payments ### Part 2 — Fall back to the amount when there is no ID Now some payments carry no invoice ID. Match such a payment to an invoice with **exactly the same amount**. If several invoices have that amount, pick the one with the **earliest date**. Payments that do carry an invoice ID must still be matched with the Part 1 logic. ```hint Index the fallback Ask what lookup would take you straight from an amount to the earliest suitable invoice, and how that lookup stays correct after an invoice is taken through the ID path. ``` #### Clarifying Questions for this Part - If a payment carries an invoice ID that matches nothing, should it fall back to amount matching or stay unmatched? #### What This Part Should Cover - A data structure that finds the earliest invoice for a given amount without a full scan - Consistency between the ID path and the amount path, so that no invoice is matched twice when invoices close on match - Part 1 behavior preserved for payments that carry an ID ### Part 3 — Match within a forgiveness range Add a non-negative **forgiveness** value `f`. A payment without an invoice ID may now match any invoice whose amount lies between `payment amount - f` and `payment amount + f`. Among all such invoices, choose the one with the **earliest date**. Payments that carry an ID still follow the ID rule from Part 1. ```hint From a key lookup to a range lookup The candidates now span a range of amounts rather than one exact amount. Think about how to order the invoices so that the range is easy to locate, and what you would need to find the earliest date inside it quickly. ``` #### Clarifying Questions for this Part - Are the range bounds inclusive? - Does the forgiveness value also apply to payments that carry an invoice ID? #### What This Part Should Cover - The correct candidate set, with the earliest date chosen rather than the closest amount - Per-payment cost of the range query, for a simple version and a faster one - Part 3 with `f = 0` behaving exactly like Part 2 ### What a Strong Answer Covers - Incremental design, where each part extends the previous code instead of rewriting it and earlier behavior is kept - Every open policy stated before coding: closing matched invoices, fallbacks, ties, and the output for no match - Deterministic output for the same input - Exact money handling - Tests for unmatched payments, repeated amounts, date ties, and invoices already taken through the ID path ### Follow-up Questions - Matching greedily in arrival order can leave a later payment unmatched even though a different assignment would have matched both. How would you find an assignment that matches as many payments as possible, and when is that worth doing? - Invoices and payments now arrive continuously as streams. How do you change the data structures so each payment is matched as it arrives? - How would you support one payment that settles several invoices, or a partial payment that leaves a balance on an invoice?