Design Memory Allocator
On this page
Problem statement
Simulate a memory of
nunits, all free at the start.allocate(size, id)finds the leftmost run ofsizeconsecutive free units, marks them as owned byidand returns the start index, or −1 if no such run exists.free(id)releases every unit owned byidand returns how many units it freed. The sameidmay own several separate blocks. Follow-up: make it fast whennis large and blocks are few, by tracking free blocks instead of individual units.
A small systems-flavoured design question: first-fit allocation, the kind a C runtime or a GPU memory pool does. The simple array version is enough to pass; the follow-up (a free list with merging) is where interviewers see whether you think about fragmentation. Original problem: LeetCode 2502.
Example

Allocator(10)
allocate(3, 1) -> 0
allocate(2, 2) -> 3
allocate(4, 1) -> 5 # id 1 now owns two separate blocks
free(2) -> 2
allocate(3, 3) -> -1 # free units: 3, 4 and 9; no run of 3
allocate(2, 3) -> 3
free(1) -> 7 # 3 + 4 units
Constraints (assumed)
- 1 ≤ n, size ≤ 1,000; up to 1,000 calls (the simple version is fine).
- Follow-up: n up to 10⁹, with at most 10⁵ live blocks.
What this question tests
- A clear first-fit rule and its loop, with correct start index.
- Bookkeeping per owner, since one id can own many blocks.
- For the follow-up: representing free space as intervals and merging neighbours on free, the same skill as Merge Intervals.
Questions to ask first
- Leftmost fit, best fit, or any fit? (Here: leftmost, also called first fit.)
- Can one id own several blocks? (Here: yes, and
free(id)frees all of them.) - What does
freereturn for an unknown id? (Here: 0.) - How large is
ncompared with the number of calls? That decides between a unit array and a free list.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.