Design the core of a heap allocator over one contiguous managed region. Blocks have an address, size, and free/allocated state. Allocation requests specify a positive byte count; free requests identify a previously allocated block. Adjacent free blocks must be coalesced. ### Part 1: First-Fit Allocation Implement or describe first-fit allocation. Explain the data structures used to find a block, split excess space, insert a newly freed block by address, and merge with both neighbors. #### What This Part Should Cover - Address-ordered block metadata - Split and exact-fit cases - Left and right coalescing - Invalid and duplicate free detection - Time and space complexity ### Part 2: Best-Fit Optimization Add best-fit allocation using an extra index ordered by free-block size. Explain how every split, allocation, free, and merge updates both the address index and size index atomically. #### What This Part Should Cover - Lower-bound search by requested size - Stable handling of equal-size blocks - Cross-links or IDs shared by both indexes - Complexity and fragmentation trade-offs ### Part 3: Testing Design tests that would expose metadata corruption and subtle coalescing bugs, not only successful allocations. #### What This Part Should Cover - Conservation of total managed bytes - Nonoverlap and address ordering - Double-free, unknown pointer, and exhaustion cases - Sequences that merge left, right, and both sides ### What a Strong Answer Covers A strong answer makes the invariants of both indexes explicit and recognizes that best-fit changes search cost but does not guarantee low fragmentation. ### Follow-up Questions - Add alignment requirements. - Make allocation thread-safe. - Compare boundary tags with an external metadata tree.