Implement a GPU credit ledger with expiring grants and out-of-order operations

You are implementing the credit accounting behind a GPU compute product. An account receives credits through grants, spends them through usage, and asks for its balance. Every grant expires, and any credits still left in a grant when it expires are lost. Implement three operations: - `grant(grant_id, amount, timestamp, expiration)` adds a grant of `amount` credits that is usable from `timestamp` until `expiration`. - `subtract(amount, timestamp)` spends `amount` credits at `timestamp`. - `get_balance(timestamp)` returns the number of credits usable at `timestamp`. Two requirements make this harder than a running counter: - **Expiration priority.** A subtraction draws first from the usable grant that expires soonest, then from the next soonest, and so on. - **Out-of-order operations.** Calls do not arrive in timestamp order. A call can carry an earlier timestamp than calls already received, and every later answer must be consistent with all operations received so far. Assume a single account (several accounts are independent copies of the same structure), positive integer amounts, and integer timestamps. ### Constraints and Clarifications - Every grant has `expiration > timestamp`, and `grant_id` values are unique. - `get_balance(t)` must reflect every grant and subtraction received so far whose timestamp is at or before `t`, whatever order they arrived in. ### Clarifying Questions - Is a grant usable at exactly its expiration time? In other words, is the usable interval `[timestamp, expiration)` or `[timestamp, expiration]`? - When a subtraction asks for more credits than are usable at its timestamp, is it rejected, applied partially, or allowed to push the account into debt? - When two operations share a timestamp, which applies first: grants or subtractions? - When two usable grants expire at the same time, which one is spent first? - How late can an operation arrive relative to the newest timestamp already seen: without limit, or within a known window? ### Part 1 — Ledger with expiration priority and out-of-order operations Implement `grant`, `subtract` and `get_balance` so that balances are correct even when calls arrive out of timestamp order. State the time and space complexity of each operation. ```hint Order matters for spending A grant that arrives late can change which grant an earlier subtraction should have drawn from. Think about what you need to keep so that the effect of every subtraction can be re-derived. ``` #### What This Part Should Cover - Exact semantics for expiry boundaries, same-timestamp ordering and overspending, consistent with the clarifying answers - A structure that always finds the usable grant expiring soonest - Correct balances when an operation arrives with an older timestamp than operations already applied - Complexity of each operation ### Part 2 — Follow-up: avoid recomputing from time zero A straightforward solution answers each balance query by replaying every operation from the first timestamp (T0). The interviewer asks how you would optimize this for production so that queries do not recompute from T0. ```hint What can still change Ask which part of the history an out-of-order operation can still affect, and which part can be treated as settled. ``` #### Clarifying Questions for this Part - Is there a bound on how late an operation can arrive, after which it may be rejected or booked as a correction? - Are balance queries mostly for the current time, or for arbitrary past timestamps? #### What This Part Should Cover - Persisted intermediate state, and how an out-of-order operation invalidates it - How settled history is compacted, so that memory and replay cost stop growing with total history - The cost of a query and of a late operation under the optimized design ### What a Strong Answer Covers - Semantics settled before coding: interval boundaries, ties, and overspending - Why expiration priority must be applied in timestamp order rather than arrival order - A correct baseline first, then an optimization with its cost stated - Production concerns specific to a credit ledger: integer amounts, idempotent retries of grants and subtractions, and an audit trail of which grants paid for what - Tests for late-arriving grants and subtractions, and for a grant that expires exactly at a query time ### Follow-up Questions - How would you report which grants paid for a given subtraction, for example on an invoice? - A client sends the same `subtract` call twice because of a network timeout. How does your ledger avoid charging twice? - If many workers record usage for the same account at the same time, how do you keep the ledger consistent?