Implement A Contiguous Memory Allocator With Free-Block Coalescing

Problem Statement

Design a contiguous memory allocator for a memory pool of fixed size total_size bytes (addressed from 0 to total_size - 1). Implement the MemoryAllocator class with the following methods:

• __init__(total_size: int): Initializes the allocator with a single contiguous block of free memory of size total_size starting at address 0.
• allocate(size: int) -> int: Finds the first available free block with a size of at least size using a first-fit strategy (i.e., the one with the smallest starting address). If found, allocates size bytes from the beginning of that block and returns its starting address. If no single contiguous block can accommodate size, return -1.
• free(address: int) -> bool: Frees the previously allocated block that begins precisely at address. If address is valid and currently allocated, free it, merge (coalesce) it with any physically adjacent free blocks (left, right, or both), and return True. If address does not correspond to the start of an actively allocated block, return False without modifying state.

Class Interface

class MemoryAllocator:
    def __init__(self, total_size: int):
        pass

    def allocate(self, size: int) -> int:
        pass

    def free(self, address: int) -> bool:
        pass

Examples

Example 1

allocator = MemoryAllocator(100)

allocator.allocate(20)  # returns 0   (Allocated [0, 19], remaining free [20, 99])
allocator.allocate(30)  # returns 20  (Allocated [20, 49], remaining free [50, 99])
allocator.allocate(40)  # returns 50  (Allocated [50, 89], remaining free [90, 99])

allocator.free(20)      # returns True (Block [20, 49] freed; free blocks: [20, 49], [90, 99])
allocator.allocate(25)  # returns 20  (Fits in [20, 49]; allocated [20, 44], remaining [45, 49])

allocator.free(0)       # returns True (Block [0, 19] freed)
allocator.free(20)      # returns True (Block [20, 44] freed; coalesces with [0, 19] and [45, 49] -> [0, 49])
allocator.free(20)      # returns False (Address 20 is no longer an active allocation start)

Constraints

• 1 <= total_size <= 10^9
• 1 <= size <= 10^9
• Up to 10^4 calls to allocate and free in total.
• Memory addresses are 0-indexed integers.

Edge Cases to Consider

• Requesting an allocation larger than total_size or larger than any available contiguous segment.
• Requesting allocation when memory is fragmented (sum of free memory >= size, but no single chunk is large enough).
• Freeing with coalescing on both sides simultaneously (left neighbor and right neighbor are both free).
• Freeing an address that points into the middle of an allocated block (should return False).