GPU Credit Ledger: Spend Earliest-Expiring Credits First, Stop on Overdraft

Implement an in-memory ledger of GPU credits for one account. Credits are granted in amounts that expire, usage is charged against them, and the balance can be queried at a given time. Two rules define the behavior: 1. **Earliest-expiring credit first.** A charge is paid from the unexpired credit that expires soonest. Only when that credit is used up does the charge continue with the credit that expires next, and so on. 2. **An overdraft is terminal.** If at any point a charge would make the balance negative, the ledger enters a broken state: from then on, every `get_balance` call returns `None`. Assume an interface along these lines, with integer timestamps and amounts: ```python class GpuCredits: def add_credit(self, amount: int, timestamp: int, expires_at: int) -> None: """Grant `amount` credits, usable from `timestamp` until they expire at `expires_at`.""" def use_credit(self, amount: int, timestamp: int) -> None: """Charge `amount` credits at `timestamp`.""" def get_balance(self, timestamp: int) -> int | None: """Unspent, unexpired credit at `timestamp`, or None once the ledger is broken.""" ``` **Example.** The calls below arrive in this order. Every query is far enough from each expiry that the boundary convention does not matter. | Call | Effect or result | |---|---| | `add_credit(10, 0, 5)` | credit A: 10 units expiring at time 5 | | `add_credit(10, 0, 100)` | credit B: 10 units expiring at time 100 | | `use_credit(10, 1)` | paid entirely from A, which expires first | | `get_balance(10)` | `10`: A has expired but was already empty, and B is untouched | | `use_credit(15, 20)` | only 10 is available, so the ledger breaks | | `get_balance(30)` | `None` | Had the charge at time 1 been paid from B instead, A would have expired unused and `get_balance(10)` would return `0`. ### Clarifying Questions - Is `expires_at` an absolute timestamp or a duration counted from `timestamp`, and is a credit still usable at exactly its expiry time? - Do calls arrive in non-decreasing timestamp order, or can a call refer to a time earlier than one already recorded? - If a grant and a charge have the same timestamp, can that grant pay for that charge? - Does "from then on" mean every later call, or every query at a timestamp at or after the charge that overdrew? The two differ only when calls can arrive out of order. - Should invalid input, such as a negative amount or an expiry at or before the grant time, raise an error or be ignored? ### Part 1 — Implement the ledger Implement the three operations under the two rules. State the conventions you chose for the open questions above, and give the time complexity of each operation. ```hint Share one ordering Charging and expiry both visit credits in the same order. Use that to avoid scanning every credit on every call. ``` #### What This Part Should Cover - Correct consumption order, including one charge that spans several credits. - Expired credits excluded both from the balance and from paying for charges. - A broken state that persists, and the chosen boundary conventions. - Time complexity per operation. ### Part 2 — A very large number of credit changes Suppose the ledger has to handle a very large number of grants and charges. How would you optimize it? ```hint Find what grows List what your Part 1 implementation keeps forever and which calls do work proportional to history, then decide what can be discarded, merged or summarized. ``` #### Clarifying Questions for this Part - Is the load many accounts with a few changes each, or a few accounts with a very large number of changes each? - Must balances at arbitrary past timestamps remain answerable? #### What This Part Should Cover - Where cost grows with history in the Part 1 design, and how to bound it. - Handling out-of-order or historical queries without replaying the full history on every call. - Scaling beyond one process: partitioning, durability and retried requests. ### What a Strong Answer Covers - Explicit conventions for expiry boundaries, equal timestamps and call order, isolated so they can be changed quickly. - A working implementation finished early, tested on multi-credit charges, expiry and the overdraft rule. - Complexity reasoning that links the Part 1 data structure to the Part 2 optimizations. ### Follow-up Questions - How would the design change if an overdrawing charge had to be rejected, leaving the balance unchanged, instead of breaking the ledger? - How would you report how much credit will expire within the next `w` time units? - How would you support a refund that returns credit to the grant it was taken from? - How would you persist the ledger so that a restart loses nothing, and how would you audit a disputed balance?