Openai·Machine Learning Engineer·Onsite - System Design / Architecture·Senior

Senior

Apr 2026

Summary

OpenAI MLE interview with a system design question focused on building an in-memory GPU credit tracking system. Pretty deep technically, they wanted actual implementation decisions not just handwaving about data structures.

Questions Asked (1)

Design and implement an in-memory GPU credit tracking system with operations to add credits (with expiry timestamps), consume credits (expiring stale ones first and consuming oldest-expiring credits first), and check a user's current balance. Discuss your data structure choice and the time complexity of each operation.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

I went with a min-heap keyed on expiry timestamp pretty quickly, which felt right, but then they pushed on the trade-offs versus a sorted list or a sorted container from something like sortedcontainers.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a data structure that efficiently supports add, consume, and balance operations. Explain how to handle expiry and ordering, and analyze time complexity for each operation. Finally, discuss trade-offs and potential optimizations.

Pro tip: Mention that in a real system, you'd likely use a combination of a hash map for user balances and a min-heap or balanced BST for expiry ordering, but also consider lazy deletion to avoid frequent cleanups.

1. Clarify Requirements

Ask about expected scale, concurrency needs, and whether credits can be negative. Confirm that consume should remove expired credits first and then consume from the earliest expiring credits.

2. Choose Data Structures

Propose using a hash map to store per-user credit batches, and a min-heap (priority queue) keyed by expiry timestamp for each user to efficiently retrieve the earliest expiring credits. Alternatively, consider a balanced BST or a sorted list if frequent updates are expected.

3. Design Operations

For add: insert a new credit batch into the user's heap and update total balance. For consume: first remove expired batches from the heap (lazy deletion), then consume from the earliest expiring batches until the requested amount is met or credits are exhausted. For balance: return the current total balance, which can be maintained as a separate counter.

4. Analyze Time Complexity

Add: O(log n) for heap insertion. Consume: O(k log n) where k is the number of batches consumed, plus amortized O(log n) for cleanup. Balance: O(1) if maintained separately. Discuss that lazy deletion avoids O(n) cleanup on every operation.

5. Discuss Trade-offs and Optimizations

Compare with alternative approaches like using a balanced BST (e.g., TreeMap) which allows O(log n) for all operations and easier range deletions. Mention that for high concurrency, locking or lock-free data structures may be needed. Also consider memory overhead and whether to periodically compact expired credits.

Key Points to Mention

Use of min-heap (priority queue) for efficient retrieval of earliest expiring credits.
Lazy deletion of expired credits to avoid frequent O(n) cleanups.
Maintaining a separate total balance counter for O(1) balance queries.
Time complexity analysis: O(log n) for add, O(k log n) for consume, O(1) for balance.
Trade-offs between heap and balanced BST (e.g., TreeMap) for different operation patterns.
Considerations for concurrency and thread safety in a real system.

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