Design First-Fit and Best-Fit Memory Allocation

Problem Statement

Implement an in-memory allocator managing a single contiguous address space of size total_size bytes (with addresses ranging from 0 to total_size - 1). Your allocator must support dynamic block splitting, immediate coalescing of neighboring free blocks, and robust handle validation.

Requirements

1. Allocation Strategies:
   • First-Fit ("FIRST_FIT"): Allocate from the free block with the lowest starting address that is large enough (size >= requested_size).
   • Best-Fit ("BEST_FIT"): Allocate from the smallest free block that satisfies size >= requested_size. Break ties by selecting the block with the lowest starting address.
2. Splitting: When an allocated block is strictly larger than the requested size, split the block: the lower address portion becomes the allocated block, and the remainder remains free.
3. Coalescing: When an allocated block is freed, immediately merge it with physically adjacent free blocks (both predecessor and successor, if free).
4. Handle Safety: allocate returns an opaque handle identifier. free must reject invalid or stale handles (e.g., handles that were never issued, already freed, or where the underlying byte range was reallocated to a new request) by returning False without modifying any allocator state.

Class Interface

class Allocator:
    def __init__(self, total_size: int, strategy: str = "FIRST_FIT"):
        """
        Initialize memory of total_size with strategy in {"FIRST_FIT", "BEST_FIT"}.
        """
        pass

    def allocate(self, size: int) -> int | None:
        """
        Allocates `size` bytes. Returns an opaque integer handle on success,
        or None if insufficient contiguous memory exists.
        """
        pass

    def free(self, handle: int) -> bool:
        """
        Frees memory associated with `handle`. 
        Returns True on success, or False if the handle is invalid or stale.
        """
        pass

Constraints

• 1 <= total_size <= 10^9
• 1 <= size <= total_size
• At most 10,000 total calls to allocate and free.
• strategy is either "FIRST_FIT" or "BEST_FIT".

Example

alloc = Allocator(total_size=100, strategy="FIRST_FIT")

h1 = alloc.allocate(30)  # Allocated [0, 30), remaining free [30, 100)
h2 = alloc.allocate(20)  # Allocated [30, 50), remaining free [50, 100)
h3 = alloc.allocate(20)  # Allocated [50, 70), remaining free [70, 100)

alloc.free(h2)           # Block [30, 50) is now free; returns True
alloc.free(h2)           # Returns False (stale / double-free)
alloc.free(99999)        # Returns False (forged handle)

h4 = alloc.allocate(15)  # Under FIRST_FIT, takes [30, 45); free [45, 50)
alloc.free(h1)           # Free [0, 30)
alloc.free(h4)           # Free [30, 45); coalesces [0, 30), [30, 45), [45, 50) into [0, 50)