1. Design Memory Allocator (LeetCode)
Model answer
The task
Design a fixed-size memory allocator that assigns contiguous free cells to an allocation ID and releases every cell belonging to a given ID. An allocation should use the first available contiguous region large enough, or report failure.
Key idea
Store each cell’s allocation ID in an array, using 0 to represent a free cell. Scan from left to right to find the first sufficiently long free run; freeing an ID is a single pass over the array.
Approach
- Initialize an array of
nzeroes. - For an allocation, scan for a run of
sizeconsecutive zeroes. - When found, fill that run with
mIDand return its starting index. - If no such run exists, return
-1. - To free an ID, replace every matching cell with zero and return how many cells were released.
class Allocator:
def __init__(self, n: int):
# Zero denotes an unallocated cell.
self.memory = [0] * n
def allocate(self, size: int, mID: int) -> int:
run_start = -1
run_length = 0
for index, owner in enumerate(self.memory):
if owner == 0:
if run_length == 0:
run_start = index
run_length += 1
if run_length == size:
for cell in range(run_start, run_start + size):
self.memory[cell] = mID
return run_start
else:
run_length = 0
return -1
def free(self, mID: int) -> int:
released = 0
for index, owner in enumerate(self.memory):
if owner == mID:
self.memory[index] = 0
released += 1
return released
Complexity:
- Time:
O(n)per operation; allocation scans the array and may mark the selected cells, while freeing scans the entire array. - Space:
O(n)for the memory array.
Common follow-ups
- How could allocation be faster for frequent requests? Track free intervals in an ordered structure, merging adjacent intervals when memory is freed.
- What if a request can span noncontiguous cells? Scan for any
sizefree cells rather than requiring a consecutive run. - How would you handle very large memory spaces? Use interval-based storage so work depends more on the number of allocated regions than on total capacity.