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).

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.

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