2502. Design Memory Allocator
Asked at Apple, OpenAI, Ripple, Capital One and 1 more
Difficulty
Medium
Time
O(n) per allocate, O(n) per free
Space
O(n)
Pattern
Array
Companies
5
Problem
Design a class Allocator that manages a memory array of n units. Every unit is free at the start. Each unit can hold one id, or be free.
Implement two methods. allocate(size, mID) looks for the leftmost run of size consecutive free units. If it finds one, it marks all those units with mID and returns the index of the first unit in the run. If no such run exists, it returns -1. freeMemory(mID) releases every unit that currently holds mID and returns how many units were released.
The tricky part: the same mID can be used by several separate allocations. A single freeMemory(mID) call must clear all of them, not just one block. Also, allocate must pick the leftmost valid run, not any run.
Leftmost run wins
Constraints
- ●
1 <= n, size, mID <= 1000 - ●
At most 1000 calls will be made to allocate and freeMemory
Examples
["Allocator", "allocate", "allocate", "allocate", "freeMemory", "allocate", "allocate", "allocate", "freeMemory", "allocate", "freeMemory"]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]["Allocator", "allocate", "allocate", "freeMemory", "allocate"]
[[5], [2, 1], [2, 2], [1], [2, 3]][null, 0, 2, 2, 0]Asked At
5 companies| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| OpenAI | Medium | View all OpenAI questions → |
| Ripple | Medium | View all Ripple questions → |
| Capital One | Medium | View all Capital One questions → |
| Roblox | Medium | View all Roblox 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.
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.
Scan, fill, then clear by id
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
O(n) per allocate, O(n) per free timeclass 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 runs in O(n) per allocate, O(n) per free time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Design Memory Allocator?
Design Memory Allocator is asked at Apple, OpenAI, Ripple, Capital One, Roblox. 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.