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.

Manage GPU Credits with Expiration | OpenAI Coding Question

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.

Input: ([('add', 'x', 3, 0, 2), ('charge', 3, 2), ('balance', 1), ('charge', 2, 1), ('balance', 1)],)

Expected Output: [False, 3, True, 1]

Explanation: Batch 'x' is active only at times 0 and 1. Charging at time 2 fails because 2 is the exclusive end. The later charge at time 1 succeeds and leaves 1 credit.

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

Expected Output: [4, 6, True, 5]

Explanation: After adding 'b', a future operation may ask about earlier time 7 and correctly sees 'b' as active. At time 12, 'b' expires before 'a', so the charge consumes from 'b' first.

Input: ([],)

Expected Output: []

Explanation: With no operations, there are no non-add results to return.

Solution

def solution(operations):
    batches = []  # [remaining, start, end, add_order]
    results = []
    add_order = 0

    for op in operations:
        kind = op[0]

        if kind == 'add':
            _, _batch_id, amount, timestamp, expiration = op
            end = timestamp + expiration
            batches.append([amount, timestamp, end, add_order])
            add_order += 1

        elif kind == 'balance':
            _, timestamp = op
            total = 0
            for remaining, start, end, _ in batches:
                if remaining > 0 and start <= timestamp < end:
                    total += remaining
            results.append(total)

        elif kind == 'charge':
            _, amount, timestamp = op
            active = []
            total = 0

            for i, (remaining, start, end, order) in enumerate(batches):
                if remaining > 0 and start <= timestamp < end:
                    total += remaining
                    active.append((end, order, i))

            if total < amount:
                results.append(False)
                continue

            active.sort()
            need = amount
            for _, _, i in active:
                if need == 0:
                    break
                take = min(need, batches[i][0])
                batches[i][0] -= take
                need -= take

            results.append(True)

        else:
            raise ValueError('Unknown operation type')

    return results

Time complexity: Worst-case O(n^2 log n), where n is the number of operations. Space complexity: O(n).

Hints

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

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.