Implement Time-Aware GPU Credit Ledger
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement an in-memory GPU credit ledger with three operations:
- `create_grant(amount, start_time, expire_time)`: add a credit grant. The grant is active for times `t` such that `start_time <= t < expire_time`.
- `subtract(amount, at_time)`: consume `amount` credits at time `at_time`. A subtraction permanently changes future balances, because consumed credits are no longer available later. Only grants active at `at_time` may be used, and credits must be deducted from the active grants with the earliest expiration time first.
- `get_balance(at_time)`: return the total remaining active credits at time `at_time`.
Assume times are integers, grants may overlap, and multiple grants can share the same expiration time. If `subtract` requests more credits than are available at `at_time`, the operation should fail without changing state.
Design the data structures and implement these operations.
Quick Answer: This question evaluates the ability to design efficient data structures and algorithms for time-aware resource accounting, including handling overlapping grants, ordering by expiration, and maintaining atomic state changes across time.