First-Fit Allocator

Implementing a first-fit memory allocator in C++

This hard coding problem asks you to build a working memory allocator from scratch—a core systems-programming skill tested at firms that care about low-level performance. You must manage a flat buffer of memory by tracking free and allocated blocks, handle fragmentation through coalescing, and correctly implement the classic first-fit search strategy.

The challenge sits at the intersection of correctness and pointer arithmetic. Your solution must walk a linked block structure by hand, split blocks when they are too large, merge adjacent free blocks when deallocating, and track metadata (size, allocation status) in fixed-size headers. Edge cases include deciding when a remainder is too small to split, correctly identifying adjacent blocks, and ensuring coalescing works in both directions without double-counting.

• Header-based block management and pointer traversal
• Fragmentation and coalescing strategies
• Edge cases in block splitting and merging
• Time complexity trade-offs (O(n) allocation cost; O(1) deallocation with metadata)