GPU Credit Ledger with Expiring Grants, Out-of-Order Operations and Fast Balances

Implement a ledger for GPU compute credits with three operations: - `create_grant(grant_id, amount, timestamp, expiration)`: adds a grant of `amount` credits that can be used from `timestamp` until `expiration`. Unless the interviewer says otherwise, treat the start as inclusive and the expiration as exclusive. - `subtract(amount, timestamp)`: spends `amount` credits at time `timestamp`. Credits are always taken from the active grant that **expires soonest** first, then from the next soonest, and so on. - `get_balance(timestamp)`: returns the total of unspent, unexpired credits at time `timestamp`. Operations can be called **out of timestamp order**. For example, a grant stamped at time 10 may be created after a subtraction stamped at time 20 has already been recorded. Every query must return the balance as if all operations recorded so far had been applied in timestamp order. After a working version, the interviewer asks for a production-grade optimization: the balance must not be recomputed from time 0 on every query. ```hint Order matters more than it looks Work through a late-arriving grant that expires sooner than an existing one, and check whether it changes which grant an earlier-recorded subtraction should have drawn from. ``` ```hint Reuse past work safely Think about which saved intermediate states are still valid after an operation is inserted at some point in the past, and which are not. ``` ### Constraints and Clarifications - Amounts are non-negative integers, and timestamps are integers. - Grant IDs are unique. ### Clarifying Questions - If a subtraction asks for more credits than are available at that time, should it fail, spend what is available, or allow a negative balance? - When several operations share a timestamp, in what order do they apply? For example, can a grant created at time `t` pay for a subtraction at time `t`? - If two grants expire at the same time, which one is used first? - Must a subtraction's success or failure be reported immediately, even though a later-arriving grant could change it? - How many operations are expected, and what is the ratio of queries to updates? ### What a Strong Answer Covers - A precise statement of the ordering, tie-breaking and insufficient-balance rules before coding - A correct baseline that applies events in timestamp order and finds the soonest-expiring credits efficiently - A clear explanation, with an example, of why out-of-order arrivals cannot be handled by adjusting a running total - An optimization that reuses saved state and invalidates exactly the part a late operation affects, with its complexity - Tests for expiry at the boundary, ties, late grants and late subtractions ### Follow-up Questions - How would you persist this ledger so that it survives restarts, and make it safe for concurrent writers? - Customers want an itemized statement showing which grant paid for each subtraction. What changes? - Out-of-order operations can arrive up to a week late. How does that bound change your design? - How would you shard the ledger across many customers?