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: ```python 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. ```hint What to store Decide what you keep for free space and what you keep for allocated blocks, and which lookup each operation needs from them. ``` ```hint Freeing between free blocks When a block is freed right between two free blocks, picture what the free space should look like afterwards, and how a later large request would see it. ``` #### 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. ```hint Two questions, two orders `malloc` and `free` ask different questions about the free blocks. Think about which ordering of the free blocks answers each question quickly. ``` ```hint Keep the indexes in step Every split and merge changes free blocks that more than one structure indexes. Decide how you keep those structures identical in content. ``` #### 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 ### What a Strong Answer Covers - A correct allocator that passes allocate, free and reallocate tests, including merges on both sides - Clear invariants for the free blocks: ordered, non-overlapping, and never two adjacent free blocks - A logarithmic design whose indexes answer exactly the queries that `malloc` and `free` need - Consistent key order and boundary comparisons in the sorted structures - An honest account of the library's operation costs, and tests or assertions that expose mistakes quickly ### Follow-up Questions - How would you keep first-fit placement and still allocate in logarithmic time? - How does fragmentation arise under your policy, and how would you measure it? - How would you add `realloc`, growing a block in place when the memory after it is free? - How would you make the allocator safe to call from multiple threads?