Openai·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Got a system design coding question at OpenAI for a software engineering role. The problem was about building a GPU credit manager with out-of-order operation support, which sounds manageable until you actually sit down and think through the edge cases.

Questions Asked (1)

Design and implement a GPU credit manager that supports out-of-order operations. It needs three operations: adding credits with an ID, amount, timestamp, and expiration window; charging credits at a given timestamp (always consuming soonest-expiring credits first); and querying total unexpired balance at a given timestamp. Calls can arrive in arbitrary time order, and the whole thing should run at O(log n) per operation for around 100k total calls.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The expiration-first ordering for charge() is where I spent most of my time.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the requirements and constraints first, then propose a data structure that supports efficient insertion, deletion, and querying under out-of-order timestamps. Design a min-heap keyed by expiration time for charging and a balanced BST or Fenwick tree for balance queries, ensuring O(log n) per operation. Discuss trade-offs between different approaches and handle edge cases like expired credits and timestamp ordering.

Pro tip: Explicitly discuss how you handle out-of-order timestamps by using expiration time as the key rather than arrival time, and mention lazy deletion to avoid O(n) cleanup. This shows you understand the core challenge and can optimize for the given constraints.

1. Clarify Requirements and Constraints

Ask about the expected number of operations, memory limits, and whether timestamps are unique or can be equal. Confirm that credits expire after the expiration window from their timestamp, and that charging consumes soonest-expiring credits first.

2. Choose Data Structures

Select a min-heap (priority queue) keyed by expiration time for charging, and a balanced BST (e.g., TreeMap) or Fenwick tree over expiration times to maintain total unexpired balance. Consider using a hash map for ID lookup if needed.

3. Design Operations

For add: insert into heap and update balance structure. For charge: pop expired credits lazily, then consume from heap until amount is met, updating balance. For query: compute total balance minus expired credits using the balance structure and current timestamp.

4. Handle Out-of-Order and Expiration

Since calls can arrive in any order, always use the timestamp parameter to determine expiration. Use lazy deletion: when charging or querying, remove credits that have expired relative to the given timestamp. Ensure the balance structure supports range deletions.

5. Analyze Complexity and Trade-offs

Explain that each operation is O(log n) due to heap and tree operations. Discuss alternatives like using a segment tree or skip list, and trade-offs between memory and speed. Mention that lazy deletion may cause occasional O(k) cleanup but amortizes to O(log n).

Key Points to Mention

Use expiration time as the key for ordering, not arrival time, to handle out-of-order calls.
Min-heap for charging ensures soonest-expiring credits are consumed first.
Balanced BST or Fenwick tree for O(log n) balance queries and updates.
Lazy deletion of expired credits to avoid O(n) scans on every operation.
Amortized O(log n) per operation with careful handling of expired credits.
Edge cases: charging more than available balance, credits expiring at the same timestamp, and negative timestamps.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.