Design a Fixed-Size Memory Allocator with Correct Alignment
Hudson River TradingSoftware Engineer · Onsite
Last updated
Design a slab-backed fixed-size allocator with constant-time free-list operations, correct stride and alignment, separate object lifetime, corruption defenses, concurrency choices, and efficient handling of nine-byte payloads.
Design a fixed-size memory allocator backed by slabs and a linked free list. Explain allocation, deallocation, alignment, lifetime, corruption defenses, and how you would store objects whose payload size is 9 bytes efficiently.
Constraints & Assumptions
- Every slot in one size class has the same stride.
- Allocation and deallocation should be constant time in the common case.
- The allocator manages raw storage; object construction and destruction are separate operations.
- The design must not return pointers that violate the requested alignment.
Clarifying Questions to Ask
- What maximum alignment and number of simultaneous allocations are required?
- May empty slabs be returned to the operating system?
- Is the allocator used by one thread or many?
Follow-up questions
- Where can free-list metadata live when a slot is allocated?
- How would you make the allocator thread-safe without one global lock?
- What are the consequences of returning an empty slab too aggressively?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.