Design Memory Allocator
Asked at Apple, OpenAI, Ripple
Problem
Design a memory allocator that supports allocate(size, mID) and free(size, mID) operations. allocate finds the leftmost block of contiguous free memory of at least size and assigns it to mID. free releases all memory assigned to mID. This tests simulation and data structure design skills.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| OpenAI | Medium | View all OpenAI questions → |
| Ripple | Medium | View all Ripple questions → |
How to Think About It
Array simulation: maintain an array of size n where each cell stores the mID of the block occupying it (0 = free). For allocate(size, mID), scan left to right for the first contiguous block of size size free cells. For free(size, mID), find and clear up to size cells assigned to mID.
Visual walkthrough for Allocator(10) then allocate(1,1), allocate(2,2), free(1,1), allocate(2,3):
Initial: [0,0,0,0,0,0,0,0,0,0]
allocate(1,1): [1,0,0,0,0,0,0,0,0,0] -> return 0
allocate(2,2): [1,2,2,0,0,0,0,0,0,0] -> return 1
free(1,1): [0,2,2,0,0,0,0,0,0,0] -> return 1
allocate(2,3): [3,3,2,0,0,0,0,0,0,0] -> return 0
Note: allocate(2,3) finds 2 free cells starting at index 0.
Optimization: instead of scanning the entire array, use a hash map to track which cells belong to each mID. For free, iterate only the cells of that mID. For allocate, still scan for free space but skip allocated cells faster.
A more efficient approach uses a sorted set of free intervals. Allocate merges/splits intervals. Free adds intervals back. This gives O(log n) per operation but is more complex to implement.
Complexity: naive array scan is O(n) per operation. Optimized with interval tracking is O(n) worst case but faster in practice. The sorted interval approach is O(log n) but harder to code under interview pressure.
Optimal Approach
Use an array memory of size n where memory[i] = mID (0 = free).
Allocate(size, mID): scan from left. For each starting position, check if the next size cells are free. If found, assign mID to those cells and return the start index. If no block found, return -1.
Free(size, mID): count how many cells belong to mID. Free up to size of them (from left to right). Return the number freed.
Walkthrough with Allocator(5), allocate(2,1), free(1,1), allocate(1,2):
- Initial: [0,0,0,0,0]
- allocate(2,1): find 2 free cells at index 0. [1,1,0,0,0]. Return 0.
- free(1,1): free 1 cell with mID=1. [0,1,0,0,0]. Return 1.
- allocate(1,2): find 1 free cell at index 0. [2,1,0,0,0]. Return 0.
Time: allocate is O(n) worst case. Free is O(n) worst case. Space: O(n) for the memory array.
What Trips People Up in Real Interviews
Allocate must find the LEFTMOST free block, not any free block. Scanning from index 0 ensures this. If you use a different data structure, you must maintain ordering.
Free releases all memory for mID up to size cells, not just one cell. The problem says "free size units of memory assigned to mID." You may need to free multiple cells.
Forgetting to return -1 when allocation is impossible. If no contiguous block of the requested size exists, return -1. Check after scanning the entire array.
Not handling the edge case where mID has less than size cells allocated. Free as many as available (up to size) and return the actual number freed.
Double-free: if you free memory that was already freed, it should be a no-op (return 0). Track what is actually allocated to avoid freeing unallocated memory.
Solution Code
class Allocator:
def __init__(self, n):
self.memory = [0] * n
self.size = n
def allocate(self, size, mID):
count = 0
start = -1
for i in range(self.size):
if self.memory[i] == 0:
if start == -1:
start = i
count += 1
if count == size:
for j in range(start, start + size):
self.memory[j] = mID
return start
else:
count = 0
start = -1
return -1
def free(self, size, mID):
freed = 0
for i in range(self.size):
if freed >= size:
break
if self.memory[i] == mID:
self.memory[i] = 0
freed += 1
return freedFrequently Asked Questions
What is the Design Memory Allocator problem?
Design a memory allocator that supports allocate(size, mID) and free(size, mID) operations. allocate finds the leftmost block of contiguous free memory of at least size and assigns it to mID. free releases all memory assigned to mID. This tests simulation and data structure design skills.
How do you solve Design Memory Allocator?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Design Memory Allocator?
Design Memory Allocator is asked at Apple, OpenAI, Ripple. It is a medium difficulty problem.
What are common mistakes on Design Memory Allocator?
- Allocate must find the LEFTMOST free block, not any free block. Scanning from index 0 ensures this. If you use a different data structure, you must maintain ordering.
- Free releases all memory for mID up to `size` cells, not just one cell. The problem says "free size units of memory assigned to mID." You may need to free multiple cells.
- Forgetting to return -1 when allocation is impossible. If no contiguous block of the requested size exists, return -1. Check after scanning the entire array.
- Not handling the edge case where mID has less than `size` cells allocated. Free as many as available (up to `size`) and return the actual number freed.
- Double-free: if you free memory that was already freed, it should be a no-op (return 0). Track what is actually allocated to avoid freeing unallocated memory.