Memory Allocator Design

What's being tested

These problems test designing a contiguous memory allocator: managing a linear address space with best-fit allocation, splitting, and coalescing of free blocks. Interviewers probe data-structure choices, correctness for malloc/free semantics (including double-free detection and pointer validation), and deterministic tie-breaking under equal-fit scenarios.

Patterns & templates

• Free-list as ordered list — maintain a list of (start, size, free) blocks; scan for best-fit in O(b) time where b = number of blocks.

• Block header layout — store metadata (size, free flag) adjacent to block; use pointer arithmetic for successor/predecessor.

• Split on allocation — when a free block > requested, carve prefix/suffix and update headers; watch minimum block size to avoid tiny fragments.

• Coalesce on free — merge adjacent free neighbors by checking neighboring headers in O(1) if doubly-linked, O(b) otherwise.

• Exact-pointer validation — accept frees only when pointer matches a block's payload start; reject interior or null frees deterministically.

• Deterministic tie-breaking — prefer earliest-start or lowest-index block on equal sizes to make behavior testable and reproducible.

• Optional optimizations — use segregated free lists or balanced tree (interval tree / ordered set) to reduce allocation/search to O(log b) at space cost.

Common pitfalls

Pitfall: Returning an interior pointer or allowing frees of non-exact pointers — always validate pointer equals the block’s payload start.

Pitfall: Forgetting to prevent double-free — track a free flag or remove freed block from free-list before coalescing.

Pitfall: Splitting without enforcing minimum block/header size — leads to unusable tiny fragments and incorrect pointer arithmetic.