Implement malloc and free over Fixed Memory, Then Make Both Logarithmic

Implement a simple memory allocator with malloc and free operations in Python. The interviewer provides test cases that allocate blocks, free some of them, and allocate again. First write a working version that keeps its blocks in a plain Python list, then optimize it.

The exact interface is left open. Assume the following and confirm it with the interviewer:

class Allocator:
 def __init__(self, capacity: int):
 """Manage addresses 0 to capacity - 1, all free at the start."""

 def malloc(self, size: int) -> int:
 """Reserve `size` contiguous free units and return the first address, or -1 if no free block is large enough."""

 def free(self, address: int) -> None:
 """Release the block that an earlier malloc call returned at this address."""

Clarifying Questions

• Which placement policy should malloc use: the lowest address that fits (first fit), the smallest free block that fits (best fit), or any block that fits?
• What should malloc do for a size of zero or less?
• What should free do for an address that malloc never returned, or one that was already freed?
• Should adjacent free blocks merge, so that a later request larger than either of them can succeed?

Part 1 — A list-based allocator

Implement malloc and free, tracking blocks in a plain list (in effect, a linked list of blocks simulated with a Python list). The implementation must pass tests such as: allocate several blocks, free one in the middle, and allocate into the freed space.

What This Part Should Cover

• Data structures for free space and for allocated blocks
• Splitting a free block on allocation, and merging neighbors on free
• Behavior for failed allocations and invalid frees
• The running time of each operation

Part 2 — Logarithmic malloc and free

Can you make both operations faster? Design a version in which malloc and free each run in $O(\log n)$ time, where $n$ is the number of blocks, and implement it. Python has no built-in balanced binary search tree; you may use a third-party sorted-container library.

Clarifying Questions for this Part

• Must the fast version keep the placement policy of Part 1, or may it change?

What This Part Should Cover

• The ordered structures that index the free blocks, and the query each one answers
• How allocation finds a block and how freeing finds its neighbors, with the cost of each step
• Consistency between the structures through splits and merges
• How the placement policy affects what can be made logarithmic