How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at OpenAI during technical interviews.

Track Expiring GPU Credits | OpenAI Coding Question

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.

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.

Loading coding console...

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

For each query, simulate events in timestamp order rather than input order.
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

A min-heap is a natural fit for 'consume the active grant that expires soonest'.
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

Sort queries offline with their original indices, and sweep forward in time only once.
You may want one structure for grant-window expiration and another for choosing the next spendable grant.