How does a fixed-size pool allocator achieve O(1) allocation and zero per-slot memory overhead using an intrusive free list?

A strong answer

A general-purpose heap allocator must store a metadata header (block size, flags) next to every allocation and search variable-sized bins. When every object has the exact same size and alignment (such as tree nodes, graph edges, or order-book entries), a fixed-size pool allocator eliminates both costs.

The pool allocates a large contiguous slab of N slots upfront. While a slot is unallocated, the caller is not using its bytes—so the pool reuses the first 8 bytes of the free slot itself to store a FreeNode* next pointer to the next free slot (intrusive free list).

• allocate() is 3 instructions ($O(1)$): read head = free_head_, advance free_head_ = head->next, and return head (constructing T via placement new).
• deallocate(T* p) is also $O(1)$: call p->~T(), cast p to FreeNode*, set node->next = free_head_, and set free_head_ = node.

Because the next pointer lives inside the free slot and is overwritten by T while allocated, the per-object memory overhead is 0 bytes, and objects allocated sequentially from a fresh slab sit in adjacent cache lines. To stay well-defined on all types T, each slot's stride and alignment must be std::max(sizeof(T), sizeof(FreeNode*)) and std::max(alignof(T), alignof(FreeNode*)).

What the interviewer is listening for

• Explains the intrusive free-list trick: overlaying FreeNode* inside unused slot storage so there is zero external metadata overhead.
• Correctly handles sizeof(T) < sizeof(void*) and alignof(T) constraints, plus placement new and explicit destructor calls p->~T().
• Names the trade-offs: a single-threaded pool is not thread-safe without a thread-local cache or atomic/mutex wrapper, and memory tied to a pool slab is not returned to the OS until the entire slab is freed.

Common mistakes

• Forgetting alignof(T) when carving a raw char[] buffer, causing unaligned access UB on SIMD or 16-byte aligned types.
• Returning raw memory without calling constructors/destructors, or leaking the underlying slab buffers when the pool is destroyed.