Design Memory Allocator

Free with account Updated Nov 19, 2026 · 7 min read
On this page

    Problem statement

    Simulate a memory of n units, all free at the start. allocate(size, id) finds the leftmost run of size consecutive free units, marks them as owned by id and returns the start index, or −1 if no such run exists. free(id) releases every unit owned by id and returns how many units it freed. The same id may own several separate blocks. Follow-up: make it fast when n is 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

    Seven calls on 10 units. After free(2) there are 3 free units in total but no 3 in a row, so allocate(3, 3) fails.
    Seven calls on 10 units. After free(2) there are 3 free units in total but no 3 in a row, so allocate(3, 3) fails.
    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

    1. Leftmost fit, best fit, or any fit? (Here: leftmost, also called first fit.)
    2. Can one id own several blocks? (Here: yes, and free(id) frees all of them.)
    3. What does free return for an unknown id? (Here: 0.)
    4. How large is n compared with the number of calls? That decides between a unit array and a free list.