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.

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.

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