Openai·Software Engineer·Onsite - System Design / Architecture·Senior

Senior

Jun 2026

Summary

Went through a system design round at OpenAI for a software engineer role. The problem was a memory allocator, which sounds like a classic OS topic until they want you to actually spec out the data structures and hit O(m log m) total runtime. Pretty intense.

Questions Asked (1)

Design a memory allocator that supports allocate(size) and free(addr) operations over a contiguous region of size n, handling up to m operations. allocate should find the leftmost free block of sufficient size and split it if needed. free should mark the block free and coalesce with adjacent free neighbors. Target O(m log m) total runtime independent of n.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This one took me a while to get traction on.

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 like a balanced BST or segment tree to manage free blocks, explaining how allocate and free operations achieve O(log m) each. Discuss trade-offs between different approaches and how to handle edge cases like coalescing and fragmentation.

Pro tip: Emphasize that the O(m log m) bound is independent of n, so the solution must not iterate over the entire memory region; instead, use a data structure that scales with the number of operations. Also, mention that using a balanced BST keyed by address allows efficient leftmost-fit search and neighbor coalescing.

1. Clarify Requirements and Constraints

Confirm the interface, expected operation counts, and performance goals. Ask about alignment, thread safety, and whether memory can be over-allocated.

2. Choose Data Structure

Select a data structure that supports efficient search, insertion, and deletion of free blocks, such as a balanced BST (e.g., red-black tree) keyed by block address, or a segment tree over the operation indices.

3. Design allocate(size)

Find the leftmost free block with size >= requested size using the data structure. Split the block if larger, update the structure, and return the address.

4. Design free(addr)

Locate the block containing addr, mark it free, and coalesce with adjacent free blocks by checking neighbors via the data structure. Update the structure accordingly.

5. Analyze Complexity and Trade-offs

Show that each operation takes O(log m) time, leading to O(m log m) total. Discuss trade-offs: BST vs. segment tree, memory overhead, and handling fragmentation.

Key Points to Mention

Use a balanced BST keyed by block start address to store free blocks, enabling O(log m) search, insert, and delete.
For allocate, find the leftmost block with size >= requested size; if none, return failure. Split the block if larger.
For free, locate the block, mark it free, and coalesce with adjacent free blocks by checking predecessor and successor in the BST.
Maintain a separate map from allocated address to block size for O(1) lookup during free.
The total runtime is O(m log m) because each operation does O(log m) work and there are at most m operations.
Discuss edge cases: freeing invalid addresses, double free, and memory exhaustion.

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