Quick Overview

This question evaluates data-structure design and algorithmic reasoning for time-based resource accounting, including handling expiring credits and out-of-order operations while maintaining efficient (logarithmic) performance constraints.

Manage GPU Credits with Expiration

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question Implement a GPU credit manager supporting out-of-order operations: API add_credit(id, amount, timestamp, expiration) // adds ‘amount’ credits usable in [timestamp, timestamp+expiration) charge(amount, timestamp) // consume ‘amount’ credits at ‘timestamp’; always draw from credits that expire soonest first (tie-break by any order) get_balance(timestamp) // return total unexpired credits available at ‘timestamp’ ##### Constraints add_credit and charge calls may arrive in arbitrary time order charge(…) must fail silently or partially apply only if enough total balance exists at that moment Design an efficient data structure to support ~10^5 operations with O(log n) per call.

Quick Answer: This question evaluates data-structure design and algorithmic reasoning for time-based resource accounting, including handling expiring credits and out-of-order operations while maintaining efficient (logarithmic) performance constraints.

You are given a list of GPU credit manager API calls in the order they arrive. Each credit batch has an amount, a start timestamp, and an expiration duration, so it is usable during the half-open interval [timestamp, timestamp + expiration). Calls may mention timestamps in any order. Process the operations in the given input order: - ("add", id, amount, timestamp, expiration): add a new credit batch. The id is unique metadata. - ("charge", amount, timestamp): try to consume amount credits at the given timestamp. - ("balance", timestamp): return the total currently remaining credits that are usable at that timestamp. Rules: 1. A successful charge may use only batches that are active at that timestamp. 2. It must always consume from the active batches that expire soonest first. If multiple batches expire at the same time, any order among them is acceptable. 3. If the total active balance at that timestamp is smaller than the requested amount, the charge fails and nothing changes. 4. Operations are processed in the order they appear in the input. A later operation may refer to an earlier timestamp, but it does not retroactively change results that were already returned earlier. Return a list containing the result of every non-add operation, in order: - For a charge, append True if it succeeds, otherwise False. - For a balance query, append the integer balance.

Constraints

  • 1 <= len(operations) <= 100000
  • 0 <= amount <= 10^9
  • -10^9 <= timestamp <= 10^9
  • 0 <= expiration <= 10^9
  • All add ids are unique
  • The answer for every balance fits in a 64-bit signed integer

Examples

Input: ([('balance', 5), ('add', 'a', 10, 5, 5), ('balance', 7), ('charge', 4, 8), ('balance', 8), ('balance', 10)],)

Expected Output: [0, 10, True, 6, 0]

Explanation: Initially there are no credits. Batch 'a' is active for times 5 through 9. Charging 4 at time 8 succeeds, leaving 6. At time 10 the batch is expired because the interval is half-open.

Input: ([('add', 'a', 5, 10, 10), ('add', 'b', 7, 5, 10), ('charge', 5, 12), ('balance', 12), ('balance', 17), ('charge', 6, 9), ('balance', 17)],)

Expected Output: [True, 7, 5, False, 5]

Explanation: At time 12 both batches are active, and batch 'b' expires first, so the charge uses 5 from 'b'. That leaves 2 in 'b' and 5 in 'a'. A later failed charge at earlier time 9 does not change the state.

Hints

  1. A credit batch contributes its remaining amount to every query timestamp inside its active interval, so add/remove actions can be modeled as range updates with point queries.
  2. To enforce 'expire soonest first' at one timestamp, think about an interval structure where each batch is stored on O(log n) nodes, and a point query inspects only one root-to-leaf path.

Loading coding console...