Katkat
Back

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

OpenAISoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Implement a GPU credit ledger with expiring grants, subtractions that spend the soonest-expiring credits first, and balance queries, where operations can arrive out of timestamp order. Then avoid recomputing from time zero on every query. It tests event replay, priority queues and checkpoint invalidation.

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.

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?

Hints

Hint 1

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 2

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.

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?