Openai·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026

Summary

OpenAI SWE interview with a pretty meaty coding problem around GPU credit management. The core question had real design depth to it and a follow-up variant that apparently gets even messier with tiers and preemption.

Questions Asked (1)

Design a GPU credit system for a stream of transactions. Implement grant(user_id, amount, timestamp, expires_at), consume(user_id, amount, timestamp), and balance(user_id, timestamp). Consume should prefer credits expiring soonest, and balance should exclude expired credits.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This took me a minute to internalize.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify requirements and constraints, then propose a data structure that efficiently supports the operations. For consume, use a min-heap keyed by expiration time to always consume the soonest-expiring credits first. For balance, lazily remove expired credits from the heap and sum the remaining amounts.

Pro tip: Discuss trade-offs between eager and lazy expiration handling, and mention that lazy deletion with a heap is often more efficient for high-throughput streams. Also, consider concurrency and idempotency if the system is distributed.

1. Clarify Requirements and Constraints

Ask about expected scale, concurrency, persistence, and whether timestamps are monotonic. Clarify if consume should partially consume credits and if balance should be O(1) or can be O(log n).

2. Choose Data Structures

Propose a per-user min-heap of credits keyed by expires_at, with each credit storing amount and expiration. Optionally maintain a total balance for O(1) balance queries, updating it on grant and consume.

3. Implement Operations

For grant, push a new credit onto the heap and update total. For consume, pop expired credits, then consume from the soonest-expiring credits, updating total. For balance, pop expired credits and return total.

4. Handle Edge Cases and Optimizations

Discuss partial consumption, insufficient credits, and lazy vs eager expiration. Consider using a balanced BST or segment tree if frequent balance queries are needed without lazy deletion.

5. Analyze Complexity and Trade-offs

Analyze time complexity: grant O(log n), consume O(k log n) where k is number of credits consumed, balance O(m log n) where m is expired credits. Discuss trade-offs between eager and lazy expiration, and memory vs speed.

Key Points to Mention

Use a min-heap keyed by expiration time to ensure soonest-expiring credits are consumed first.
Lazy deletion of expired credits: only remove them when needed (during consume or balance) to avoid unnecessary work.
Maintain a running total balance to allow O(1) balance queries after cleaning expired credits.
Handle partial consumption of a credit by reducing its amount and keeping it in the heap if not fully consumed.
Consider concurrency and atomicity if multiple transactions can occur simultaneously; use locks or optimistic concurrency.
Discuss trade-offs: eager expiration (e.g., using a timer) vs lazy expiration, and heap vs balanced BST for different query patterns.

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