Design a memory-safe collections library in C.

A strong answer

A strong candidate frames Design a memory-safe collections library in C. around the exact memory layout, compiler semantics, and hardware execution model covered in Project: Memory-Safe Collections with Slab and Arena Allocators. Discuss API design, ownership semantics, error handling without exceptions, and testing strategies for a C collections library.

General-purpose heap allocators like malloc() and free() are engineered to handle arbitrary sizes, unpredictable lifetimes, and multi-threaded synchronization. To support this generality, they introduce structural overhead:

1. Per-Allocation Header Overhead: Every malloc chunk carries 8 to 16 bytes of metadata overhead (chunk size, in-use flags, bin pointers). Allocating millions of small 24-byte nodes wastes up to 40% of physical RAM on allocator metadata.
2. External Fragmentation: Unpredictable interleaving of allocations and deallocations fragments heap pages into disjointed free blocks. Eventually, malloc fails or triggers expensive page consolidation even when total free memory is ample.
3. Cache Inefficiency: Linked nodes allocated through malloc end up scattered across non-contiguous virtual memory pages. Traversal stalls the CPU pipeline on DRAM latency (~60 ns per pointer dereference).
4. Synchronization and Lock Contention: Calling malloc from concurrent worker threads contends on global arena mutexes, introducing scheduling jitter.

Systems software (such as compilers, database query executors, game engines, and network proxies) exhibits distinct allocation patterns:

• Phase-Based Lifetimes: Many objects are created during a discrete operation (e.g., parsing an AST, evaluating a SQL query, servicing an HTTP request) and can be discarded simultaneously.
• Uniform Object Sizes: Data structures like hash tables, search trees, and event queues allocate thousands of identical-sized nodes.

In a production interview, always connect the specification rule to its concrete runtime consequence: state what lives on the stack versus the heap or static storage segment, how the compiler or operating system validates alignments, lifetimes, and error codes, and what happens under adversarial or boundary inputs (such as zero-length buffers, integer overflow, concurrent mutation, or partial I/O). Backing your explanation with a small trace of register/memory state transitions immediately separates senior systems engineers from candidates who only memorized syntax.

What the interviewer is listening for

• Mastery of core invariant: Construct an aligned bump arena allocator with instant O(1) bulk lifecycle resets.
• Mastery of core invariant: Build an intrusive free-list slab allocator to eliminate external heap fragmentation.
• Mastery of core invariant: Implement an abstract Allocator vtable interface decoupling containers from libc malloc.
• Hardware and ABI awareness: Explaining how sizes, alignments, calling conventions, or kernel boundaries behave on real 64-bit targets rather than relying on implementation-defined assumptions.
• Defensive engineering: Naming the exact compiler flags (-Wall -Wextra -Werror), static analyzers, or runtime sanitizers (-fsanitize=address,undefined,thread) that verify correctness in CI.

Common mistakes

• Explaining only surface syntax without tracing the underlying memory addresses, ownership lifetime, or kernel/user-space state transitions.
• Assuming undefined behavior (such as signed overflow, uninitialized reads, strict-aliasing violations, or dangling pointers) will "just work" because it passed an unoptimized -O0 debug build.
• Ignoring return codes, partial reads/writes, alignment padding, or cleanup paths when an allocation or syscall fails midway through a function.