PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates event-replay and time-window accounting skills, including temporal data structures, priority-based consumption, out-of-order event processing, and resource/debt tracking within the Coding & Algorithms domain for a Machine Learning Engineer role.

  • medium
  • OpenAI
  • Coding & Algorithms
  • Machine Learning Engineer

Track Expiring GPU Credits

Company: OpenAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement a GPU credit tracking system that processes time-stamped events arriving out of order. Operations: - `add_credit(amount, start_time, duration)`: create a credit grant that is valid for every integer timestamp in the inclusive interval `[start_time, start_time + duration]` - `subtract(amount, timestamp)`: record usage at a timestamp - `get_balance(timestamp)`: return the effective balance at that time Rules: - Events may be inserted in any order, so queries must behave as if all events were replayed in timestamp order. - When subtracting, consume only credits that are active at that timestamp. - If multiple active grants are available, consume the one that expires soonest first. - If expiration times tie, consume the grant with earlier start time first. - If usage exceeds the active balance, keep the remainder as debt. - For a query, return `None` if there is no active credit history at that timestamp or if the effective balance is negative. Return `0` only when grants existed and were exactly exhausted. Common follow-ups: 1. Produce an audit log showing which credit grants funded each subtraction and by how much. 2. Refactor the solution into event, grant, and audit record classes. 3. Scale to about `1e5` events and frequent queries using sorted event storage, replay optimizations, or periodic snapshots. This question tests event replay, time-window logic, priority selection, out-of-order processing, and engineering trade-offs.

Quick Answer: This question evaluates event-replay and time-window accounting skills, including temporal data structures, priority-based consumption, out-of-order event processing, and resource/debt tracking within the Coding & Algorithms domain for a Machine Learning Engineer role.

Part 1: GPU Credits I - Basic Addition and Inclusive Expiration

You are given out-of-order GPU credit add events. Each add event is a tuple (amount, timestamp, duration). A credit becomes active at time timestamp and stays active for every integer time t in the inclusive interval [timestamp, timestamp + duration]. For each query time, return the total active balance. There is no subtraction in this part.

Constraints

  • 0 <= len(add_events), len(queries) <= 200000
  • 1 <= amount <= 10^9
  • 0 <= timestamp, duration <= 10^9
  • Queries may be unsorted and may repeat

Examples

Input: ([], [0, 10])

Expected Output: [0, 0]

Explanation: Edge case: no credits were ever added.

Input: ([(5, 10, 2), (3, 4, 0), (7, 8, 5)], [3, 4, 10, 12, 14])

Expected Output: [0, 3, 12, 12, 0]

Explanation: Events arrive out of order; query results depend only on timestamps.

Input: ([(4, 2, 3)], [1, 2, 5, 6])

Expected Output: [0, 4, 4, 0]

Explanation: The credit is active at times 2, 3, 4, 5 and expires before time 6.

Input: ([(2, 0, 0), (3, 0, 2)], [0, 1, 2, 3])

Expected Output: [5, 3, 3, 0]

Explanation: Two grants start at the same time; one lasts only for a single timestamp.

Hints

  1. A credit active on [start, end] can be represented as +amount at start and -amount at end + 1.
  2. Sort query times with their original indices, then sweep once through all balance changes.

Part 2: GPU Credits II - Subtraction with Expire-Soonest Priority

Now the system supports both add and subtract events. An add event is ('add', amount, timestamp, duration), active on the inclusive interval [timestamp, timestamp + duration]. A subtract event is ('sub', amount, timestamp). To answer a query at time t, replay all events with timestamp <= t in chronological order; if multiple events share the same timestamp, all adds happen before all subtracts. A subtraction always consumes currently active credits that expire soonest first; if expirations tie, consume the earlier-starting grant first, then earlier input order. If a subtraction cannot be fully covered, the uncovered part becomes debt. When a later add arrives, it pays down debt first, and only the leftover becomes a usable grant. Query rule: return None if debt is still positive, or if there is no active grant window at that time. Otherwise return the total remaining active amount. Active grants with 0 remaining still count as active until they expire, so a query can legally return 0.

Constraints

  • 0 <= len(events), len(queries) <= 2000
  • 1 <= amount <= 10^9
  • 0 <= timestamp, duration <= 10^9
  • Correctness is more important than optimization in this baseline version

Examples

Input: ([('add', 10, 0, 10), ('add', 5, 0, 2), ('sub', 8, 1)], [1, 3])

Expected Output: [7, 7]

Explanation: At time 1, the 5-credit grant expires sooner, so it is consumed first.

Input: ([('add', 5, 2, 3), ('sub', 5, 1)], [1, 2, 5, 6])

Expected Output: [None, 0, 0, None]

Explanation: The subtraction creates debt at time 1. The later add pays it off exactly, leaving an active zero-remaining grant until it expires.

Input: ([('add', 4, 1, 10), ('add', 2, 2, 10), ('sub', 7, 3)], [3, 4])

Expected Output: [None, None]

Explanation: Only 6 active credits exist at time 3, so debt remains positive afterward.

Input: ([('add', 5, 1, 1)], [0, 1, 2, 3])

Expected Output: [None, 5, 5, None]

Explanation: Inclusive expiration means the credit is still active at time 2.

Input: ([], [0])

Expected Output: [None]

Explanation: Edge case: no grants means no active credit window.

Hints

  1. For each query, simulate events in timestamp order rather than input order.
  2. Keep each grant's remaining amount, and when subtracting, always consume the active grant with the smallest expiration time first.

Part 3: GPU Credits III - Audit Trail for Grant Consumption

Build an audit log for every subtraction. Add events now include a grant id and are written as ('add', grant_id, amount, timestamp, duration). Subtract events are ('sub', amount, timestamp). Events may arrive out of order, but you must process them by timestamp; if multiple events share a timestamp, adds happen before subtracts. During a subtraction, consume currently active grants using expire-soonest priority; if expirations tie, consume the earlier-starting grant first, then earlier input order. If a subtraction is not fully covered, the uncovered part becomes debt. Later adds pay down debt first, and only leftover credit becomes available for future subtracts. Your function should return an audit log in chronological subtraction order. For each subtraction, output a tuple (timestamp, requested_amount, consumed_list, uncovered_amount), where consumed_list is a list of (grant_id, amount_used) pairs. Important: the log records what was consumed immediately at that subtraction time; later debt repayment does not rewrite old log rows.

Constraints

  • 0 <= len(events) <= 50000
  • Each add event has a unique grant_id
  • 1 <= amount <= 10^9
  • 0 <= timestamp, duration <= 10^9

Examples

Input: ([('add', 'A', 5, 0, 5), ('add', 'B', 4, 1, 4), ('sub', 6, 2)],)

Expected Output: [(2, 6, [('A', 5), ('B', 1)], 0)]

Explanation: Both grants expire at time 5, so the earlier-starting grant A is consumed first.

Input: ([('sub', 7, 3), ('add', 'g1', 4, 1, 10), ('add', 'g2', 2, 2, 10)],)

Expected Output: [(3, 7, [('g1', 4), ('g2', 2)], 1)]

Explanation: Only 6 credits are active at time 3, so the audit row shows uncovered amount 1.

Input: ([('sub', 5, 1), ('add', 'x', 3, 2, 5), ('add', 'y', 4, 3, 5), ('sub', 2, 3)],)

Expected Output: [(1, 5, [], 5), (3, 2, [('y', 2)], 0)]

Explanation: The first subtraction creates debt. Later adds pay debt first, leaving only 2 usable credits in grant y by time 3.

Input: ([('sub', 4, 5), ('add', 'g1', 10, 5, 5)],)

Expected Output: [(5, 4, [('g1', 4)], 0)]

Explanation: Same-timestamp ordering matters: adds happen before subtracts.

Input: ([],)

Expected Output: []

Explanation: Edge case: no events means no audit rows.

Hints

  1. A min-heap is a natural fit for 'consume the active grant that expires soonest'.
  2. You only need to log what a subtraction consumed right then; debt can be carried as a single number.

Part 4: GPU Credits IV - High-Volume Offline Queries

Use the same rules as Part 2, but now len(events) and len(queries) can both be as large as 100000. A replay-from-scratch solution is too slow. Add events are ('add', amount, timestamp, duration), active on [timestamp, timestamp + duration]. Subtract events are ('sub', amount, timestamp). Process events by timestamp, with all adds before all subtracts at the same timestamp. A subtraction consumes active grants that expire soonest first; ties break by earlier start time, then earlier input order. If a subtraction cannot be fully covered, the remainder becomes debt. Later adds pay down debt first. A query at time q observes the state after all events at timestamp q are processed. Return None if debt is positive or if no grant window is active at q; otherwise return the total remaining active amount. Active zero-remaining grants still count as active until they expire.

Constraints

  • 0 <= len(events), len(queries) <= 100000
  • 1 <= amount <= 10^9
  • 0 <= timestamp, duration <= 10^9
  • An O(len(events) * len(queries)) approach will time out

Examples

Input: ([('add', 10, 0, 10), ('add', 5, 0, 2), ('sub', 8, 1)], [0, 1, 2, 3, 11])

Expected Output: [15, 7, 7, 7, None]

Explanation: This checks overlapping grants, expire-soonest subtraction, and expiry after the window ends.

Input: ([('sub', 5, 1), ('add', 2, 2, 3), ('add', 3, 3, 3)], [1, 2, 3, 4, 7])

Expected Output: [None, None, 0, 0, None]

Explanation: Later adds exactly repay earlier debt, so the balance becomes 0 while grant windows are still active.

Input: ([('sub', 4, 5), ('add', 10, 5, 5), ('add', 3, 1, 10)], [5, 6])

Expected Output: [9, 9]

Explanation: Queries at time 5 must observe both same-timestamp events, with the add processed before the subtract.

Input: ([], [0, 10])

Expected Output: [None, None]

Explanation: Edge case: no active grants at any time.

Hints

  1. Sort queries offline with their original indices, and sweep forward in time only once.
  2. You may want one structure for grant-window expiration and another for choosing the next spendable grant.
Last updated: Apr 19, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Infection Spread Simulation with Death Threshold - OpenAI (medium)
  • Spreading Contagion on a Grid - OpenAI (medium)
  • Streaming Entropy with Numerical Stability - OpenAI (hard)
  • Implement a Distributed Rate Limiter - OpenAI (medium)
  • Compute Plant Infection Time - OpenAI (medium)