Implement an expiring GPU-credit manager
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This question evaluates understanding of efficient data structures, algorithmic complexity, concurrency control, and time-based resource accounting required to implement an expiring GPU-credit manager.
Constraints
- 1 <= len(operations) <= 200000
- 1 <= amount <= 10^18
- 0 <= expiresAt, now, atTime <= 10^18
- Timestamped operations (consume, balance, refund) appear in nondecreasing time order in the input
- Each grant is issued before it expires
- A grant is expired when currentTime >= expiresAt
Examples
Input: ([('grant', 'alice', 10, 6), ('grant', 'alice', 5, 10), ('balance', 'alice', 1), ('consume', 'alice', 12, 2), ('balance', 'alice', 2), ('refund', 'alice', 4, 4), ('balance', 'alice', 4), ('consume', 'alice', 8, 5), ('balance', 'alice', 5)],)
Expected Output: [15, True, 3, 4, 7, False, 7]
Explanation: Alice starts with 15 credits. Consuming 12 at time 2 uses the grant expiring at 6 first, then the later one, leaving 3. Refunding 4 at time 4 restores the most recently consumed chunks first, bringing the balance to 7. A later attempt to consume 8 fails because only 7 unexpired credits remain.
Input: ([('grant', 'bob', 5, 3), ('consume', 'bob', 5, 1), ('refund', 'bob', 5, 3), ('balance', 'bob', 3)],)
Expected Output: [True, 0, 0]
Explanation: Bob consumes all 5 credits at time 1. At time 3 the original grant is already expired, so none of those consumed credits can be refunded. Balance is 0.
Input: ([('grant', 'u1', 4, 10), ('grant', 'u1', 3, 7), ('consume', 'u1', 5, 2), ('refund', 'u1', 4, 8), ('balance', 'u1', 8)],)
Expected Output: [True, 2, 4]
Explanation: The consume at time 2 uses all 3 credits from the earlier-expiring grant and 2 from the later grant. At time 8, only the later grant is still unexpired, so the refund can restore only 2 credits.
Input: ([('grant', 'a', 5, 5), ('grant', 'b', 4, 6), ('balance', 'a', 5), ('balance', 'b', 5), ('consume', 'a', 1, 5), ('consume', 'b', 4, 6), ('balance', 'b', 6)],)
Expected Output: [0, 4, False, False, 0]
Explanation: A grant is already expired at its exact expiration time. So user a has 0 at time 5, and user b cannot consume at time 6 because that grant is also expired at that boundary.
Input: ([('balance', 'nobody', 0), ('consume', 'nobody', 1, 0), ('refund', 'nobody', 5, 0)],)
Expected Output: [0, False, 0]
Explanation: A user with no grants has balance 0, cannot consume credits, and cannot refund anything.
Solution
def solution(operations):
import heapq
from collections import defaultdict
class UserState:
__slots__ = ('heap', 'total', 'history')
def __init__(self):
self.heap = [] # (expiresAt, grant_id) for grants with remaining > 0
self.total = 0 # total unexpired remaining credits
self.history = [] # stack of [grant_id, consumed_amount_still_not_refunded]
users = defaultdict(UserState)
grants = {} # grant_id -> [expiresAt, remaining]
next_grant_id = 0
def expire_user(user, now):
while user.heap and user.heap[0][0] <= now:
expires_at, grant_id = heapq.heappop(user.heap)
grant = grants[grant_id]
remaining = grant[1]
if remaining > 0:
user.total -= remaining
grant[1] = 0
results = []
for op in operations:
kind = op[0]
if kind == 'grant':
_, user_id, amount, expires_at = op
user = users[user_id]
grant_id = next_grant_id
next_grant_id += 1
grants[grant_id] = [expires_at, amount]
user.total += amount
heapq.heappush(user.heap, (expires_at, grant_id))
elif kind == 'balance':
_, user_id, at_time = op
user = users[user_id]
expire_user(user, at_time)
results.append(user.total)
elif kind == 'consume':
_, user_id, amount, now = op
user = users[user_id]
expire_user(user, now)
if user.total < amount:
results.append(False)
continue
need = amount
while need > 0:
expires_at, grant_id = heapq.heappop(user.heap)
grant = grants[grant_id]
remaining = grant[1]
if remaining == 0:
continue
take = remaining if remaining < need else need
grant[1] -= take
user.total -= take
user.history.append([grant_id, take])
need -= take
if grant[1] > 0:
heapq.heappush(user.heap, (expires_at, grant_id))
results.append(True)
elif kind == 'refund':
_, user_id, amount, now = op
user = users[user_id]
expire_user(user, now)
need = amount
restored = 0
while need > 0 and user.history:
grant_id, consumed_left = user.history[-1]
grant = grants[grant_id]
expires_at = grant[0]
if consumed_left == 0:
user.history.pop()
continue
if expires_at <= now:
user.history.pop()
continue
give = consumed_left if consumed_left < need else need
before = grant[1]
grant[1] += give
user.total += give
restored += give
need -= give
user.history[-1][1] -= give
if before == 0 and grant[1] > 0:
heapq.heappush(user.heap, (expires_at, grant_id))
if user.history[-1][1] == 0:
user.history.pop()
results.append(restored)
return resultsTime complexity: O(n log n) total, where n is the number of operations and grant/refund chunks processed. Space complexity: O(n).
Hints
- For each user, keep grants ordered by expiration so the earliest-expiring grant is always chosen first during consume.
- A stack of consumption chunks is a natural fit for refund, because refund must undo the most recent successful consumptions first.