Quick Overview

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.

Implement an expiring GPU-credit manager

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an expiring GPU-credit manager for a cloud provider. Each user receives credit grants with an amount and an expiration timestamp. Support: ( 1) grant(userId, amount, expiresAt) to add a new grant; ( 2) consume(userId, amount) to atomically deduct credits using earliest-expiring-first semantics and return true/false; ( 3) balance(userId, atTime=now) to report total unexpired credits; and ( 4) optional refund(userId, amount) that restores most-recently-consumed credits before expiration. Requirements: O(log n) per operation where n is the number of active grants for that user; expired grants must not be consumable; partial consumption across multiple grants must be handled; insufficient balance must not change state. Discuss data structures (e.g., heaps/trees), concurrency control for parallel consume calls, time handling, and include unit tests for edge cases (exact expiry boundaries, large amounts, empty state).

Overview: 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.

You are given a chronologically valid list of operations for a cloud provider's GPU-credit manager. Each credit grant belongs to a user, has an amount, and expires at an integer timestamp. Implement a function that processes these operations in order: 1. ("grant", userId, amount, expiresAt): add a new credit grant for the user. 2. ("consume", userId, amount, now): atomically deduct exactly amount credits using earliest-expiring-first semantics. Return True if successful, otherwise False. If the user does not have enough unexpired credits at time now, the state of unexpired credits must remain unchanged. 3. ("balance", userId, atTime): return the total unexpired credits for the user at time atTime. 4. ("refund", userId, amount, now): undo up to amount credits by restoring the most recently consumed credits first, but only if their original grant is still unexpired at time now. Return the number of credits actually restored. Important rules: - A grant with expiresAt = t is already expired at time t, so it is usable only when currentTime < expiresAt. - A consume may span multiple grants. - Expired grants must never be consumed or refunded. - Return a list containing the result of every non-grant operation, in order. Follow-up discussion (not required for the code): explain which data structures you would choose for O(log n) access per user, how to handle exact time boundaries, and how to make parallel consume calls safe with per-user locking or transactional updates.

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]

Input: ([('grant', 'bob', 5, 3), ('consume', 'bob', 5, 1), ('refund', 'bob', 5, 3), ('balance', 'bob', 3)],)

Expected Output: [True, 0, 0]

Hints

  1. For each user, keep grants ordered by expiration so the earliest-expiring grant is always chosen first during consume.
  2. A stack of consumption chunks is a natural fit for refund, because refund must undo the most recent successful consumptions first.

Loading coding console...

Show the approach

Approach

The solution keeps per-user state in a UserState: a min-heap of (expiresAt, grant_id), a running total of unexpired remaining credits, and a history stack of consumed chunks. A global grants dict maps grant_id -> [expiresAt, remaining] so every chunk references shared, mutable grant data.

Lazy expiry. expire_user(user, now) pops heap entries whose expiresAt <= now (matching the rule "expired when currentTime >= expiresAt"), subtracting any still-remaining credits from total and zeroing them. Every timed op calls this first, so total is always the true unexpired balance.

grant assigns a fresh id, records [expiresAt, amount], adds to total, and pushes onto the heap.

balance expires, then returns total.

consume expires, then short-circuits to False if total < amount — guaranteeing the state stays unchanged on failure. Otherwise it pops earliest-expiring grants, takes min(remaining, need) from each, logs [grant_id, take] to history, decrements total, and re-pushes a grant only if it still has credits. Because total >= amount was checked, the drain always succeeds atomically.

refund expires, then walks history LIFO (most-recent-first). It skips chunks whose grant is now expired (expiresAt <= now) or already fully refunded, restores min(consumed_left, need) back to the grant and total, and re-pushes the grant onto the heap if it had previously dropped to 0 (before == 0). It returns the credits actually restored.

Correctness rests on: shared grant objects keeping heap/history/total consistent, lazy expiry never resurrecting expired credits, and the LIFO history precisely reversing the most recent consumes.

Time complexity:
O(n log n)
Space complexity:
O(n)