GPU Credit Management System

Question

Implement a GPU credit management system with the following three methods:

1. `add_credit(grant_id, amount, timestamp, expiration)` — Add a credit grant identified by `grant_id` with a given `amount`, valid starting from `timestamp` and expiring at `expiration` (exclusive, i.e., the credit is invalid at or after `expiration`). Multiple grants can overlap in time.

2. `subtract(amount, timestamp)` (also called `charge`, `use_credit`) — Deduct the given `amount` of credits as of the given `timestamp`. When consuming credits, prioritize grants that expire soonest first. The deduction affects future available credit (i.e., if grant A expires at t=40 and grant B at t=70, a subtract at t=30 drains A first). Operations may arrive out of order (timestamps need not be monotonically increasing), so computation may be deferred until `get_balance` is called.

3. `get_balance(timestamp)` — Return the credit balance at the given `timestamp`. Expired credits (those whose expiration ≤ timestamp) are not counted. If the balance at that point would be negative (i.e., subtracts exceed available credits), return `None` (or throw an `InsufficientCreditException`). Return `0` if no subtract has occurred but no active credit covers that timestamp.

**Key behaviors / edge cases:**
- Credits are time-bounded: a credit added with `timestamp=10, expiration=40` is active during [10, 40) (right-exclusive).
- `subtract` deducts from the earliest-expiring active grants first (greedy, min-heap by expiration).
- A `subtract` that reduces a grant reduces that grant's remaining amount and propagates to later-expiring grants if needed.
- `get_balance(ts)` should reflect the state as of `ts`: only grants whose start ≤ ts < expiration count; prior subtracts that occurred at ts' ≤ ts count; past negative states (i.e., a prior `get_balance` returned `None`) propagate — all subsequent `get_balance` calls also return `None`.
- All `add_credit` and `subtract` calls may be provided in any order; the system must reconstruct the correct timeline at query time.
- No time-complexity optimization is required; brute-force (recompute from scratch on each `get_balance`) is acceptable.

**Variant I (simpler):** `subtract` deducts only from currently available credits and does not affect future credit amounts — use a sweep-line to sum all credit intervals, then subtract usage.

**Variant II (harder, more common):** `subtract` deducts from active grants in earliest-expiration order and permanently reduces those grant amounts, affecting future queries.

AceOffer · Accepted Answer

Implement a GPU credit management system with the following three methods:

1. `add_credit(grant_id, amount, timestamp, expiration)` — Add a credit grant identified by `grant_id` with a given `amount`, valid starting from `timestamp` and expiring at `expiration` (exclusive, i.e., the credit is invalid at or after `expiration`). Multiple grants can overlap in time.

2. `subtract(amount, timestamp)` (also called `charge`, `use_credit`) — Deduct the given `amount` of credits as of the given `timestamp`. When consuming credits, prioritize grants that expire soonest first. The deduction affects future available credit (i.e., if grant A expires at t=40 and grant B at t=70, a subtract at t=30 drains A first). Operations may arrive out of order (timestamps need not be monotonically increasing), so computation may be deferred until `get_balance` is called.

3. `get_balance(timestamp)` — Return the credit balance at the given `timestamp`. Expired credits (those whose expiration ≤ timestamp) are not counted. If the balance at that point would be negative (i.e., subtracts exceed available credits), return `None` (or throw an `InsufficientCreditException`). Return `0` if no subtract has occurred but no active credit covers that timestamp.

**Key behaviors / edge cases:**
- Credits are time-bounded: a credit added with `timestamp=10, expiration=40` is active during [10, 40) (right-exclusive).
- `subtract` deducts from the earliest-expiring active grants first (greedy, min-heap by expiration).
- A `subtract` that reduces a grant reduces that grant's remaining amount and propagates to later-expiring grants if needed.
- `get_balance(ts)` should reflect the state as of `ts`: only grants whose start ≤ ts < expiration count; prior subtracts that occurred at ts' ≤ ts count; past negative states (i.e., a prior `get_balance` returned `None`) propagate — all subsequent `get_balance` calls also return `None`.
- All `add_credit` and `subtract` calls may be provided in any order; the system must reconstruct the correct timeline at query time.
- No time-complexity optimization is required; brute-force (recompute from scratch on each `get_balance`) is acceptable.

**Variant I (simpler):** `subtract` deducts only from currently available credits and does not affect future credit amounts — use a sweep-line to sum all credit intervals, then subtract usage.

**Variant II (harder, more common):** `subtract` deducts from active grants in earliest-expiration order and permanently reduces those grant amounts, affecting future queries.

Reported follow-ups:
1. How would you optimize performance if get_balance is called very frequently? (when: Candidate finishes the base implementation)
2. How would you handle concurrency — multiple threads calling add_credit, subtract, and get_balance simultaneously? (when: Candidate has a working solution)
3. How would you design this as a production system to control credit usage per customer tier (e.g., rate limiting)? (when: After correctness discussion)
4. What if the matrix/dataset is very large — how would you scale this? (when: Candidate's system handles in-order events correctly)

**Alternative approaches:** Sweep-line (Variant I only) (For the simpler variant where subtract doesn't affect future grants, collect all add-credit intervals and subtract events, sort by timestamp, and compute running balance using a sweep. Much simpler but incorrect for Variant II where subtracts must reduce specific grant amounts.); Event log with lazy evaluation (Append all add/subtract events into a sorted event list; only compute at get_balance time. Straightforward and correct for out-of-order inputs, but O(N log N) per query due to re-sorting. Acceptable since interviewers explicitly say performance is not a concern.); Append expiration as negative events (Model each grant as two events: (start, +amount) and (expiration, -amount). Process subtract by adjusting expiration events. Elegant conceptually but tricky to implement correctly when subtracts span multiple grants.)

GPU Credit Management System

Problem Overview

Follow-up Arc

Approach Trade-offs

Practice

More OpenAI Questions

Every question in the OpenAI catalog gets this depth

Approach	Notes
Sweep-line (Variant I only)	For the simpler variant where subtract doesn't affect future grants, collect all add-credit intervals and subtract events, sort by timestamp, and compute running balance using a sweep. Much simpler but incorrect for Variant II where subtracts must reduce specific grant amounts.
Event log with lazy evaluation	Append all add/subtract events into a sorted event list; only compute at get_balance time. Straightforward and correct for out-of-order inputs, but O(N log N) per query due to re-sorting. Acceptable since interviewers explicitly say performance is not a concern.
Append expiration as negative events	Model each grant as two events: (start, +amount) and (expiration, -amount). Process subtract by adjusting expiration events. Elegant conceptually but tricky to implement correctly when subtracts span multiple grants.