Openai·Software Engineer·Onsite - Coding / Algorithms·Senior

Senior

Jun 2026

Summary

OpenAI SWE coding round, one meaty problem the whole time. It was basically a mini scheduling system for GPU credits and they wanted the full thing: implementation, complexity analysis, and tests.

Questions Asked (1)

Design and implement a GPU credit accounting system with three operations: grant credits to a user with an expiration timestamp, consume credits using a soonest-expiry-first policy, and query a user's non-expired balance at a given time. Use a per-user min-heap with lazy expiration, discuss time complexity, and write tests covering partial consumption across grants and fully expired credits.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This looked manageable at first glance and then I realized how many edge cases were quietly hiding in it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and constraints, then propose a per-user min-heap keyed by expiration time, with lazy deletion of expired credits during consume and query operations. Explain the time complexity of each operation and how lazy expiration avoids eager cleanup overhead. Finally, outline test cases covering partial consumption across grants and fully expired credits.

Pro tip: Mention that lazy expiration is a trade-off: it keeps operations fast but may leave stale entries in the heap, so you should periodically compact or rebuild the heap if memory becomes a concern. Also, emphasize that using a heap ensures soonest-expiry-first consumption in O(log n) time per operation.

1. Clarify requirements and constraints

Ask about expected scale (number of users, grants per user), concurrency needs, and whether credits can be negative or have other constraints. Confirm that expiration timestamps are in the future and that consume should fail if insufficient credits.

2. Design data structures

Propose a dictionary mapping user IDs to a min-heap of credit grants, where each grant stores amount and expiration time. Explain that the heap is ordered by expiration to support soonest-expiry-first consumption.

3. Implement operations with lazy expiration

For grant, push a new entry onto the user's heap. For consume, pop expired entries from the top until a valid grant is found, then deduct from it (and possibly multiple grants if partial consumption is needed). For query, similarly pop expired entries and sum the remaining valid grants.

4. Analyze time complexity

Grant is O(log n) for heap insertion. Consume and query are O(k log n) where k is the number of expired entries removed plus the number of grants touched; amortized over many operations, each expired entry is removed once, so total cost is O(m log n) for m operations.

5. Write tests

Cover: (1) partial consumption across multiple grants, ensuring the soonest-expiring grant is used first; (2) fully expired credits, verifying they are ignored in balance and consumption; (3) edge cases like consuming exactly the available balance, consuming more than available, and querying at a time when all credits are expired.

Key Points to Mention

Per-user min-heap keyed by expiration timestamp for soonest-expiry-first consumption.
Lazy expiration: expired entries are removed only when encountered during consume or query, avoiding eager cleanup.
Time complexity: O(log n) for grant, O(k log n) for consume/query where k is the number of expired entries removed plus grants touched; amortized O(log n) per operation.
Partial consumption across grants: consume may need to deduct from multiple grants if the first grant has insufficient credits.
Handling fully expired credits: they are skipped and removed from the heap during operations.
Testing strategy: unit tests for partial consumption, expired credits, and edge cases like insufficient balance.

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