Process One Transaction per Day to Minimize Total Late Fees

You are given a backlog of transactions, each with a due day. Exactly one transaction can be processed per day. A transaction processed after its due day is late and pays a late fee: \$3 for its first late day and \$1 for each later late day. Write a program that decides which transaction to process each day and, for every day, outputs at least the transaction processed that day and the total late fees paid so far. The output format is up to you. The input format was not reported; the illustration below is an assumption to make the task concrete. ```text transactions (id, due day) illustrative T1 1 T2 1 T3 2 T4 2 one line per day (format of your choice) day 1: processed T1, late fees paid so far 0 day 2: ... ``` ### Constraints and Clarifications - Reported: one transaction per day; a late fee of \$3 for the first late day and \$1 for every other late day; each day's output must include the processed transaction and the late fees paid so far. - Not given: the input format, whether transactions arrive during the run, and how large the backlog is. Ask, or state your assumptions. - The round also included 10 to 15 minutes of behavioral questions, so leave time to discuss alternatives once the code runs. ### Clarifying Questions - Does a transaction carry only an id and a due day, or also an amount or an arrival day? - Is a transaction processed on its due day on time, and is the fee the same for every transaction regardless of its amount? - Are all transactions known on the first day, or do new ones arrive while you are processing? - Is the late fee charged day by day while a transaction waits, or all at once when it is processed? The two give the same final total but different running totals. - Must a transaction be processed every day while any are waiting? ### Part 1 — Daily processing log Implement the processing loop: each day, choose one waiting transaction, process it, and output the day's line with the running total of late fees. Start with the policy of processing the transaction that is closest to becoming late, and keep the policy easy to replace. ```hint Decide, then account Keep the rule that picks today's transaction apart from the code that charges fees, so that each can be tested and swapped on its own. ``` #### What This Part Should Cover - Correct fee arithmetic, including the boundary between on time and late and the first-late-day fee - A daily log with a correct running total - A data structure that finds the next transaction quickly, with a deterministic tie rule ### Part 2 — Is that order the cheapest? Does always processing the transaction closest to becoming late minimize the total late fee? If not, find an input on which another order is cheaper, then propose approaches that minimize the total and compare their trade-offs. ```hint Price one more day of waiting Compare what one extra day of delay costs a transaction that is already late with what it costs a transaction that is about to become late. ``` #### Clarifying Questions for this Part - Is the only goal the smallest total fee, or must no single transaction be left late for too long? - How large can the backlog be, and how quickly must a schedule be produced? #### What This Part Should Cover - A concrete input on which the nearest-due order is not the cheapest, with both totals - An exact way to find the minimum total fee, and its cost - Heuristic versus exact approaches, and total fees versus how long one transaction may wait ### What a Strong Answer Covers - Pins down the fee rule, the on-time boundary and the input format before coding - Separates the scheduling policy from the fee accounting, with tests on small cases - Treats the nearest-due order as a heuristic and checks it against an exact method instead of assuming it is optimal - Explains why the shape of the fee makes the problem harder than ordering by due day - States the time and memory cost of each approach ### Follow-up Questions - New transactions arrive every day and you cannot see the future. Which policy do you use, and how would you judge it? - The late fee becomes proportional to each transaction's amount. What changes in your approaches? - No transaction may be more than a fixed number of days late. How do you add that rule? - The backlog has a million transactions. Which approach still works, and how do you know how far from optimal it is?