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 Technical Screen rounds at OpenAI.

What role is this question designed for?

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

Implement Time-Aware GPU Credit Ledger

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an in-memory GPU credit ledger with three operations: - `create_grant(amount, start_time, expire_time)`: add a credit grant. The grant is active for times `t` such that `start_time <= t < expire_time`. - `subtract(amount, at_time)`: consume `amount` credits at time `at_time`. A subtraction permanently changes future balances, because consumed credits are no longer available later. Only grants active at `at_time` may be used, and credits must be deducted from the active grants with the earliest expiration time first. - `get_balance(at_time)`: return the total remaining active credits at time `at_time`. Assume times are integers, grants may overlap, and multiple grants can share the same expiration time. If `subtract` requests more credits than are available at `at_time`, the operation should fail without changing state. Design the data structures and implement these operations.

Quick Answer: This question evaluates the ability to design efficient data structures and algorithms for time-aware resource accounting, including handling overlapping grants, ordering by expiration, and maintaining atomic state changes across time.

You are given a sequence of operations for an in-memory GPU credit ledger. Process the operations from left to right. Each credit grant has an amount, a start time, and an expiration time. A grant is active exactly for times t where start_time <= t < expire_time. Operations: - ('create', amount, start_time, expire_time): add a new grant. This operation has no direct output. - ('subtract', amount, at_time): try to consume amount credits at time at_time. You may use only grants that are active at at_time. If multiple grants are active, you must deduct from the grant with the earliest expiration time first. If there are not enough active credits, the subtraction fails and the ledger must remain unchanged. Output True for success and False for failure. - ('balance', at_time): output the total remaining active credits at time at_time. Important assumptions for this task: - Operations affect only later operations in the given sequence. - All times used by 'subtract' and 'balance' operations are non-decreasing through the input. - A grant only exists after its 'create' operation is processed. If it is created after its start_time but before its expire_time, it becomes immediately active.

Constraints

0 <= len(operations) <= 2 * 10^5
1 <= amount <= 10^9
0 <= start_time < expire_time <= 10^9
0 <= at_time <= 10^9
Times in all 'subtract' and 'balance' operations are non-decreasing across the list

Examples

Input: [('create', 10, 0, 10), ('create', 5, 0, 5), ('balance', 0), ('subtract', 7, 3), ('balance', 3), ('balance', 5), ('subtract', 9, 6), ('balance', 6)]

Expected Output: [15, True, 8, 8, False, 8]

Explanation: At time 0 both grants are active, so balance is 15. Subtracting 7 at time 3 must use the grant expiring at 5 first: consume 5 from that grant and 2 from the grant expiring at 10. The remaining active balance is 8. At time 6 only 8 credits remain active, so subtracting 9 fails and state stays unchanged.

Input: [('create', 4, 5, 10), ('balance', 4), ('balance', 5), ('subtract', 2, 7), ('balance', 9), ('balance', 10)]

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

Explanation: The grant is not active before time 5. It becomes active at time 5, 2 credits are consumed at time 7, 2 remain at time 9, and it is no longer active at time 10.

Input: [('balance', 2), ('create', 6, 1, 5), ('balance', 2), ('subtract', 4, 2), ('balance', 4), ('balance', 5)]

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

Explanation: The ledger is empty at the first query. When the grant is created, its time window already includes the current time 2, so it becomes immediately active. After subtracting 4, 2 credits remain until expiration at time 5.

Input: [('create', 3, 0, 10), ('create', 4, 0, 10), ('subtract', 8, 1), ('balance', 1), ('subtract', 7, 1), ('balance', 1), ('balance', 9)]

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

Explanation: Only 7 credits are active at time 1, so subtracting 8 fails and the ledger stays unchanged. The next subtraction of 7 succeeds, leaving no active credits.

Input: []

Expected Output: []

Explanation: No operations produce no results.

Hints

Because query times never go backward, you can sweep time forward. Each grant only moves from future -> active -> expired once.
Use a min-heap for active grants ordered by expiration time so subtraction always consumes the earliest-expiring credits first. Keep a running sum of active remaining credits for fast balance queries.

Quick Overview

This question evaluates the ability to design efficient data structures and algorithms for time-aware resource accounting, including handling overlapping grants, ordering by expiration, and maintaining atomic state changes across time.