Expiring GPU Credit Ledger with Out-of-Order Events and Point-in-Time Balance

Build an in-memory ledger for GPU credits. Credits arrive as grants that can be used only until they expire, usage is subtracted from them, and callers ask for the balance at a given logical timestamp. Events can be recorded out of timestamp order. Assume these operations unless the interviewer gives different signatures. Timestamps are integer logical times and amounts are positive integers. - `add_credit(grant_id, amount, timestamp, expiration)` records a grant of `amount` credits that becomes usable at `timestamp` and expires at `expiration`. - `subtract(amount, timestamp)` records usage of `amount` credits at `timestamp`. - `get_balance(timestamp)` returns the total credit that is unused and unexpired at `timestamp`. The rules: - `add_credit` and `subtract` only record the event; the work happens when a balance is requested. - Events can be recorded in any order. `get_balance(t)` must reflect every recorded event with a timestamp at or before `t`, applied in timestamp order, regardless of the order in which the events arrived. - A subtraction draws from the grants that are active at its timestamp, taking from the grant with the earliest expiration first and moving to the next grant only when that one is used up. - A subtraction therefore also lowers the balance at later timestamps, and an event that arrives late can change balances at every timestamp after its own. **Example.** Grant `a` has 100 credits usable from time 0 until it expires at 50, and grant `b` has 60 credits usable from time 10 until it expires at 30. Usage of 70 at time 20 takes all 60 from `b` (it expires first) and 10 from `a`, so the balance is 90 at time 20 and still 90 at time 35, after `b` has expired. If usage of 20 at time 12 is recorded afterwards, it takes 20 from `b`: the balance at time 15 becomes 140, and the usage at time 20 now takes 40 from `b` and 30 from `a`, so the balance at time 35 becomes 70. ### Clarifying Questions - Is a grant still usable at exactly its `expiration` timestamp, or does it expire at that instant? - When a grant and a subtraction share a timestamp, which applies first? How are several subtractions with the same timestamp ordered? - If a subtraction asks for more than the active balance, does it fail entirely, take what is available, or leave a debt that later grants must cover? - If two active grants expire at the same time, which one is used first? - Can a grant ID repeat, and can recorded events be cancelled or edited? - How often are balances queried compared with how often events are recorded, and how late can an out-of-order event arrive? ### Part 1 — A correct baseline Implement the three operations with exactly the semantics above. Recomputing the state from the earliest event on every `get_balance` call is acceptable in this part. ```hint Replay in time order, not arrival order Keep the recorded events in a form you can walk by timestamp, and fix how events with the same timestamp are ordered so that every replay gives the same result. ``` ```hint Choosing the grant to draw from During a replay, each subtraction repeatedly needs the unexpired grant with the earliest expiration. Think about which structure gives you that cheaply and how expired grants leave it. ``` #### What This Part Should Cover - A deterministic replay order, including ties at the same timestamp - Earliest-expiration-first deduction across several grants, skipping expired and used-up grants - A defined result when usage exceeds the active balance - Correct results when events are recorded out of timestamp order ### Part 2 — Stop replaying from time zero The Part 1 ledger recomputes everything from time zero on every `get_balance` call. Design and implement a way to avoid that. Explain what your optimization must do when an out-of-order event arrives with a timestamp earlier than work you have already done, and whether a heap for picking the earliest-expiring grant addresses this cost. ```hint Share work between queries Two queries at different timestamps replay the same prefix of events. Think about what could let the second query skip that shared work. ``` ```hint Late events When an event arrives with a timestamp earlier than state you have already computed, work out exactly which of that state it can change and which it cannot. ``` #### What This Part Should Cover - What state is saved, how often, and what it costs in memory - How a query finds the closest usable saved state and resumes from it - Exactly which saved state a late event invalidates, and what that invalidation costs - Whether the heap speeds up the replay itself or only each subtraction ### What a Strong Answer Covers - Integer amounts and explicit tie rules, so that balances are reproducible - Time complexity of recording, querying and late insertion in both versions - Tests that compare the optimized ledger against the plain replay on random event streams, including late events and queries at arbitrary times - When the optimization pays off (many queries, mostly in-order events) and when it does not (frequent very late events) ### Follow-up Questions - Most events arrive in order and most queries ask about the latest time. How would you make that common case close to constant time per query? - Events come from several servers, and the system can guarantee a maximum lateness. How would you use that guarantee to discard or freeze old state? - How would you support cancelling a subtraction that was recorded earlier? - The ledger must survive restarts. What would you persist: the events, the saved states, or both?