Implement a memory allocator with malloc/free

Problem

You are implementing a simplified memory allocator over a contiguous memory region.

Initialize the allocator with a fixed total size:

• allocator(totalSize) creates an allocator that manages bytes indexed from 0 to totalSize-1.

Implement two operations:

• malloc(size) -> pointer

  • Allocates a contiguous block of size bytes.
  • Returns a pointer representing the allocated block (you may define this as an integer start index, or an opaque handle that can later be passed to free).
  • If no contiguous block of at least size bytes is available, return a null/invalid pointer (e.g., -1 or null).

• free(pointer) -> bool

  • Frees the block previously returned by malloc.
  • Returns true if the pointer was valid and the block was freed, otherwise returns false (e.g., double-free or unknown pointer).

Requirements / Clarifications

• The allocator must support many interleaved malloc and free calls.
• Freed space should become available for future allocations.
• You must correctly handle merging/coalescing of adjacent free blocks to reduce fragmentation.
• Discuss (and aim for) better-than-linear performance per operation if possible (e.g., around $O(\log n)$ for finding a suitable free block).

Example (one possible interpretation)

• allocator(10)
• p1 = malloc(3) might return 0 (allocates [0..2])
• p2 = malloc(4) might return 3 (allocates [3..6])
• free(p1) frees [0..2]
• p3 = malloc(2) might return 0 (reuses part of [0..2])

What to deliver

Explain and implement the data structures and algorithms needed to support malloc and free efficiently, including coalescing and pointer validation.

Implement a Memory Allocator with malloc/free

Constraints

• 1 <= totalSize <= 10^9
• 1 <= len(operations) <= 2 * 10^5
• For ('malloc', size): 1 <= size <= 10^9
• Pointers passed to free may be invalid or already freed
• Memory blocks returned by malloc are always contiguous and non-overlapping

Approach

The allocator models memory as a sorted list of free intervals free_list, each stored as [start, end) (half-open) and kept ordered by start. Initially the whole region is one free interval [0, totalSize). A dict allocated maps each live pointer to its block size.

malloc(size) — uses first-fit: scan free_list left to right for the first interval [s, e) with e - s >= size. Allocate from its front: the returned pointer is s. If the interval is exactly size, remove it; otherwise shrink it in place to [s + size, e). Record allocated[s] = size. If no interval fits, return -1.

free(pointer) — if pointer isn't a key in allocated, it's invalid or a double-free, so return False. Otherwise pop its size and form the freed interval [ns, ne) = [ptr, ptr + size). A binary search (lower_bound_free) finds insertion index i, the first interval whose start is >= ns. Then coalesce with neighbors:

• merged_left if the interval at i-1 ends exactly at ns;
• merged_right if the interval at i starts exactly at ne.

If both, the three pieces fuse: extend free_list[i-1]'s end to free_list[i]'s end and delete i. If only left, extend [i-1]'s end to ne. If only right, pull [i]'s start back to ns. If neither, insert [ns, ne) at i. Return True.

Correctness: intervals stay sorted, disjoint, and maximally merged, so adjacency checks against only the two neighbors at i-1/i suffice to keep fragmentation minimal. The allocated dict guarantees only genuinely live pointers can be freed, correctly rejecting invalid and double-frees.

• Space complexity: O(n + a), where n is the number of free intervals held in free_list and a is the number of currently allocated blocks tracked in the allocated dict. The outputs list adds O(m) for m operations.