Implement A Contiguous Memory Allocator With Free-Block Coalescing
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a memory manager for a contiguous block of `N` bytes.
The memory manager starts with all bytes free and must support:
```python
malloc(k: int) -> int
free(ptr: int) -> None
```
`malloc(k)` allocates one physically contiguous block of `k` bytes and returns the starting offset of the allocated block. If no contiguous free block can fit `k` bytes, return `-1`.
`free(ptr)` frees the block that starts at `ptr`. The caller only provides the starting offset, so your allocator must remember the size of each allocated block. When adjacent free blocks become neighbors after a free, merge them into one larger free block.
Start with a first-fit allocator. Then describe how you would change the design to support best-fit allocation efficiently.
Function signature:
```python
class MemoryAllocator:
def __init__(self, n: int):
pass
def malloc(self, k: int) -> int:
pass
def free(self, ptr: int) -> None:
pass
```
Constraints:
- Allocations must be contiguous.
- Allocated blocks cannot be moved after `malloc` returns.
- `free(ptr)` is called only for currently allocated block starts unless the interviewer asks for defensive handling.
- The first-fit version may keep free blocks ordered by start offset.
- The best-fit follow-up should explain a secondary index ordered by block size.
Examples:
```text
allocator = MemoryAllocator(10)
allocator.malloc(3) -> 0
allocator.malloc(4) -> 3
allocator.free(0)
allocator.malloc(2) -> 0
allocator.free(3)
At this point the free ranges should be coalesced where adjacent.
```
Quick Answer: Review a contiguous memory allocator coding prompt with malloc, free, first-fit allocation, block coalescing, and a best-fit follow-up. The interview topic emphasizes interval management, allocated-block maps, fragmentation, secondary indexes, and complexity trade-offs.