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 a GPU credit manager | OpenAI Coding Question

Quick Overview

This question evaluates understanding of concurrent resource management, advanced data structures for top-K and per-user queries, enforcement of caps and expirations, and algorithmic complexity guarantees while maintaining atomicity under concurrent operations.

Implement a GPU credit manager

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a GPU credit manager for a compute cluster. Each user has a nonnegative credit balance that can be increased (grantCredits(user, amount)), consumed when scheduling jobs (consume(user, amount) -> boolean), and refunded when jobs finish (refund(user, amount)). Support querying a user’s remaining credits (get(user) -> int) and retrieving the top K users by balance (topK(k) -> list). Enforce per-user maximum caps, optional per-organization aggregate caps, and optional credit expirations. Prevent balances from going negative and ensure atomicity under concurrent calls. Target O(log n) time per operation and near-linear space. Describe the data structures, provide pseudocode for each API, and analyze time and space complexity.

Quick Answer: This question evaluates understanding of concurrent resource management, advanced data structures for top-K and per-user queries, enforcement of caps and expirations, and algorithmic complexity guarantees while maintaining atomicity under concurrent operations.

Process a sequence of timestamped operations for a single-threaded GPU credit manager. Rules: - Every user starts with 0 credits. - `user_caps[user]` is that user's maximum balance. If a user is missing from `user_caps`, their cap is unlimited. - `user_org[user]` gives the user's organization. If a user is missing from `user_org`, they have no organization. - `org_caps[org]` is the maximum total active balance across all users in that organization. If an organization is missing from `org_caps`, its cap is unlimited. - Operations are given in nondecreasing timestamp order and are processed atomically. - Credits are stored in lots. A granted lot may expire at a specific timestamp. Before processing any operation at time `t`, all remaining credits from lots with `expire_time <= t` disappear. - When consuming credits, always consume from the earliest-expiring active lots first. Non-expiring lots are treated as expiring last. - `grant` and `refund` are partially applied if necessary: add as many credits as possible without violating the user cap or the organization cap. - Balances can never go negative. - `topK(k)` returns up to `k` users with positive balances, sorted by balance descending, then by user name ascending. Implement `solution(user_caps, user_org, org_caps, operations)` and return a list containing the result of every operation in order. Operation formats: - `('grant', t, user, amount, expire_time)` -> return the integer amount actually added. `expire_time` is an integer timestamp or `None`. - `('refund', t, user, amount)` -> return the integer amount actually added. Refunded credits never expire. - `('consume', t, user, amount)` -> return `True` if the full amount was consumed, otherwise `False`. - `('get', t, user)` -> return the user's current active balance. - `('topK', t, k)` -> return a list of `[user, balance]` pairs.

Constraints

0 <= len(operations) <= 2 * 10^5
Operation timestamps are in nondecreasing order
0 <= amount, cap <= 10^9
User and organization names are non-empty strings
If `expire_time` is not `None`, it is an integer timestamp; a lot with `expire_time <= t` is considered expired before time `t` operations run

Examples

Input: ({}, {}, {}, [])

Expected Output: []

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

Input: ({'alice': 10, 'bob': 7}, {'alice': 'org1', 'bob': 'org1', 'carol': 'org2'}, {'org1': 12, 'org2': 20}, [('grant', 1, 'alice', 8, 5), ('grant', 2, 'bob', 7, None), ('consume', 3, 'alice', 3), ('refund', 4, 'bob', 5), ('get', 4, 'bob'), ('topK', 4, 2), ('get', 5, 'alice'), ('topK', 6, 3)])

Expected Output: [8, 4, True, 3, 7, [['bob', 7], ['alice', 5]], 0, [['bob', 7]]]

Explanation: Bob's first grant is limited by the organization cap, Bob's refund is also capped, and Alice's remaining expiring credits disappear at time 5.

Input: ({'u': 20}, {}, {}, [('grant', 1, 'u', 5, 10), ('grant', 2, 'u', 7, 6), ('consume', 3, 'u', 6), ('get', 5, 'u'), ('get', 6, 'u'), ('topK', 6, 1)])

Expected Output: [5, 7, True, 6, 5, [['u', 5]]]

Explanation: Consumption uses the earliest-expiring lot first, leaving 1 credit in the lot expiring at time 6, which then expires before the `get` at time 6.

Input: ({'a': 10, 'b': 10, 'c': 10}, {'a': 'o', 'b': 'o', 'c': 'o2'}, {'o': 9, 'o2': 10}, [('grant', 1, 'a', 5, None), ('grant', 1, 'b', 5, None), ('grant', 1, 'c', 5, None), ('topK', 1, 3), ('consume', 2, 'a', 2), ('refund', 3, 'b', 10), ('topK', 3, 3)])

Expected Output: [5, 4, 5, [['a', 5], ['c', 5], ['b', 4]], True, 2, [['b', 6], ['c', 5], ['a', 3]]]

Explanation: User `b` is limited by the organization cap both on the initial grant and on the later refund. In the first `topK`, `a` and `c` tie at 5, so `a` comes first lexicographically.

Input: ({'x': 5}, {}, {}, [('topK', 0, 2), ('consume', 1, 'x', 1), ('refund', 2, 'x', 4), ('grant', 3, 'x', 3, None), ('consume', 4, 'x', 5), ('get', 5, 'x')])

Expected Output: [[], False, 4, 1, True, 0]

Explanation: This covers an empty `topK`, a failed consume on a zero balance, and a grant that is partially applied because user `x` is already near the cap.

Hints

You need two different orderings at once: earliest expiration for consuming/expiring lots, and largest current balance for `topK`. Heaps plus hash maps are a strong fit.
For `topK`, avoid updating heap entries in place. Push new balance entries and skip stale ones later with lazy deletion.

Quick Overview