InterviewLegend

Design a Memory Allocator

Frequently asked
Alex Chen24 min readGuide updated
In this lesson
  • Lay out a fixed buffer as blocks with headers, and say where the bookkeeping lives
  • Choose a free list and a placement policy, and explain the fragmentation each one causes
  • Get free right: coalescing, bad and double frees, alignment, and the tests that prove it

Understanding the problem

The prompt

Something like this: you are given a fixed block of memory, modelled as an array of bytes. Write malloc, which hands back the start of a free region of at least the requested size, and free, which takes that region back. You can't call the real allocator.

Among Two Sigma's design-and-code prompts, only the order matching engine comes up more often, and a Premium question comes up as often. Six candidates got the allocator between 2022 and 2026. The newest, from October 2026, is an intern's first technical interview: a few questions about past experience, then "design a memory allocator." That candidate couldn't finish in time. Earlier candidates describe malloc "using an array" in an intern technical round in New York (2024) and "creating slotted memory and storing data in C" in another intern round (2024). It was also the one "design type" question in a 2024 technical loop, the "implementation/OOD question" in a 2023 onsite round two, and part of a 2022 phone screen that also covered process communication. Only one of those falls in the last twelve months. So treat it as a prompt that keeps coming back across 2022 to 2026, and don't read it as this year's favourite.

Nobody draws boxes and arrows here. You write a working allocator in the interview pad. The design lives in the choices you make before and while you type. Where the bookkeeping goes is the first of them. After that come finding a free block, handling the leftover piece, and putting the pieces back together on free. None of the reports describes a follow-up question, so this lesson teaches the whole shape of the problem and doesn't pretend to know the order an interviewer will push in.

The Two Sigma angle
Two Sigma's careers page says the technical interviews are 60 minutes in a shared codepair environment, in C, C++, Java or Python. It lists testing and design/architecture among the areas graded. An allocator touches both. Your code has to run, and your tests have to show it works.

Requirements

Functional requirements

Pin the surface down in the first few minutes. The allocator owns one buffer of a fixed size, chosen up front. A request for some number of bytes gets back an offset into that buffer, or a clear failure value when nothing fits. A free call gives a region back so later requests can reuse it. Ask what free should do with an offset it never handed out, or one it already took back. Crashing quietly is the worst answer, so propose returning an error. Then ask the question that decides how you spend the next fifty minutes: may the bookkeeping live outside the array? If yes, a sorted list or a dictionary of blocks does the job and you spend your time on policy and tests. If the bookkeeping has to live inside the buffer, which is the natural reading in C, every block carries a small header and the code gets fiddlier.

In scope

  • Allocate some bytes and return an offset, or a failure value
  • Free a region so later requests can reuse the space
  • Reject a double free or an offset that isn't a block start
  • Merge free neighbours so big requests can still fit
  • A way to inspect the state, so tests can check it

Below the line (call it out, then skip)

  • Growing the buffer when it fills up
  • realloc and calloc, unless there's time at the end
  • Threads and locking, unless the interviewer brings them up
  • Virtual memory, paging and garbage collection

Non-functional requirements

Correctness comes first. A request must never get a region that overlaps a live one, and a freed region must become usable again. Every bug in an allocator shows up later as somebody else's corrupted data, which is why it's worth being strict at the boundary. Memory efficiency comes next, and it has two parts. Overhead is the bookkeeping you spend per block. Fragmentation is free space you can't use, either because it's split into pieces too small for the request or because a block was rounded up past what the caller asked for. Speed matters less in an interview than people think. A malloc that walks every block is fine for a first version, as long as you can say what it costs and how you'd make it faster. If the interviewer gives no numbers, propose some. A 64 KB buffer, an 8-byte header and an 8-byte footer on each block, and every block size a multiple of 8.

  • Buffer: 64 KB. 65,536 bytes. Small enough to reason about, big enough that walking every block starts to cost something.
  • Bookkeeping: 16 bytes per block. An 8-byte header in front of the payload and an 8-byte copy of it at the end, the footer.
  • Alignment: 8 bytes. Every block starts on a multiple of 8, so any 8-byte number stored in it is aligned.
  • Smallest block: 24 bytes. A freed block must hold an 8-byte header, two 4-byte free-list links and an 8-byte footer, 24 bytes in all. A 1-byte request costs 24.

The set-up

Core entities

1

The buffer

One array of bytes that the allocator owns from start to end. Nothing outside it gets handed out, and nothing in it is ever moved, because a caller holds an offset and expects its data to stay put.

2

A block

A stretch of the buffer that is either in use or free. Blocks sit next to each other in address order and cover the whole buffer with no gaps, so the end of one block is always the start of the next.

3

The header

A few bytes at the front of each block holding its size and whether it's in use. The caller never sees it. With the in-band layout, malloc returns the offset just past the header.

4

The free list

An index of the free blocks only, so a search can skip everything in use. In the in-band layout it costs nothing extra, because each free block stores the links in its own unused payload.

When the bookkeeping lives inside the buffer, a block looks like the table below. Sizes are multiples of 8, so the lowest three bits of a size are always zero. The in-use flag goes in the lowest bit, which saves a separate field.

What a block holds, inside the buffer
PartFields
Header (8 bytes, at the block start)size · in-use bit
Payload (what the caller gets)the caller's data, or two free-list links when free
Footer (8 bytes, at the block end)size · in-use bit, a copy of the header
The footer looks redundant until free needs to find the block on its left. The coalescing deep dive shows why it earns its 8 bytes.

API

Two calls do the real work and a third makes testing easy. The real free returns nothing, but returning the size freed here turns a double free into something a test can assert on.

The interface
Request
CallerAllocatorreserve a region
allocate(size)
offset of the region, or -1 if nothing fits
CallerAllocatorgive a region back
release(offset)
bytes freed, or -1 for a bad or repeated free
Only an offset that allocate returned, and that is still live, is accepted.
TestAllocatorinspect fragmentation
largest()
size of the biggest free block

High-level design

There isn't much to draw. A caller, two calls, a policy that picks a block, and the buffer itself laid out in address order. In the diagram, blue is the code calling us, violet is logic we write, amber is the free list that links free blocks together, and green is the memory itself.

Loading diagram...

1) Start with one free block. The constructor writes a single header at byte 0 and a footer at the last 8 bytes, marking the whole 64 KB as one free block, and makes it the only entry on the Free list. That's the entire setup. The invariant from here on is that blocks tile the buffer with no gaps, so walking from byte 0 by each block's size always lands on the next header.

2) Allocate. A request for 13 bytes is rounded up to 16 for alignment, plus 16 bytes of header and footer, so it needs a 32-byte block. The Allocator asks the Placement policy, which walks the free list and picks a free block of at least 32 bytes. If the block is much bigger, it gets split. The front 32 bytes become the new block in use, and the rest becomes a smaller free block that stays on the list. If the leftover would be under 24 bytes, too small to ever hold its own header, footer and links, hand the caller the whole block instead. That wastes a few bytes inside the block and keeps unusable slivers out of the list. Walking the whole list is the naive part, and the first deep dive fixes it.

3) Release. The offset goes through the Free check first. It must sit inside the buffer, point at a payload the allocator handed out, and belong to a block that is still in use. Then the block's header and footer flip to free, and it looks at both neighbours. If the block to the right is free, the two merge. If the block on the left is free, they merge too. Releasing In use, bytes 120 to 143 in the diagram would join it with both free blocks around it into one. Without that merge, the buffer slowly turns into small free pieces, which the coalescing deep dive works through.

4) Inspect. largest() walks the free list and returns the biggest free block. It does nothing for a real caller, but it lets a test say "after these frees, a 64-byte block exists," which is the clearest way to prove coalescing works. Add it early. It also gives you something to print when a test fails with a minute left.

Data structure choices

  • The Fixed buffer, in address order is a bytearray in Python or a static array in C. Ask for the size up front and never grow it.
  • In Python or Java, keep blocks in a list sorted by start offset. Neighbours sit next to each other in it, so merging is cheap.
  • In C, put the Allocator bookkeeping in headers inside the buffer. A side table would need memory from somewhere, and malloc is off limits.
  • Make the Free list doubly linked. With a previous link, unlinking a block during a merge takes constant time.
  • Start the Placement policy as first fit. Switch only when you can name the fragmentation pattern it causes.

Say which layout you're building before you write a line. A side table in Python gets you to working tests fastest. Headers in the buffer are the more faithful answer and take longer. Either is defensible if you say why.

The Two Sigma angle
The 2024 C round talked about "slotted memory," and C is one of the four languages Two Sigma lists. If you pick C, plan for headers inside the buffer and pointer arithmetic on offsets. In Python, a side table is the normal choice, and the time it saves goes into tests.

Potential deep dives

How does malloc find a free block quickly?

Put a number on the search first. With a 24-byte smallest block, 64 KB holds at most 65,536 / 24, about 2,700 blocks. If 90 percent of them are in use, there are around 270 free ones. A search that looks at every block does ten times the work of one that looks only at free blocks, on every single malloc.

BadMark every byte and scan for a run

Approach

Keep a second array with one flag per byte of the buffer, set when the byte is in use. To allocate n bytes, scan for n free flags in a row. To free, clear the flags again.

Challenges

Every allocate can touch all 65,536 flags. Free doesn't know how long the block was unless you store the size somewhere else, so you end up building a block table anyway. The flags also cost a full extra buffer of memory. It's a reasonable thing to say in the first minute and drop in the second.

GoodImplicit list: walk the blocks by their headers

Approach

Give each block a header with its size and in-use bit. The next block always starts at the current start plus its size, so the headers form a list with no pointers at all. Allocate walks from byte 0, header by header, and stops at the first free block big enough. Free flips the bit and merges with the block to its right.

Challenges

Search time grows with every block, used or free, so about 2,700 header reads in the worst case. That's fine for the interview and slow for a real program that allocates millions of times a second. Merging left is the other gap: from a block you can step right, but stepping left needs a walk from the start.

GreatExplicit free list, then size classes

Approach

Thread a doubly linked list through the free blocks, storing the next and previous free offsets in each free block's payload. A search now visits free blocks only, around 270 instead of 2,700 in the example. Freeing pushes the block on the front, a constant-time step. For speed beyond that, keep separate lists by size class, one per power of two from 32 bytes to 64 KB, which is a dozen lists, and search only the class that can hold the request.

Challenges

The links are why the smallest block is 24 bytes, so tiny requests waste more. A list ordered by most recently freed is fast but tends to fragment more than one kept in address order, which costs a walk on every free. Size classes add code and an edge case: a block that splits or merges moves to a different list.

The explicit list earns its extra code once the search cost shows up in a profile, and in an interview you'll rarely get that far. Building the implicit list and then explaining the explicit one is a solid hour. Most production allocators, glibc's malloc among them, keep many free lists binned by size, so that's where the explanation should land.

First fit, next fit or best fit?

When two free blocks are both big enough, the choice matters later. Take a buffer with a free 48-byte block near the start and a free 24-byte block further along. A 24-byte request arrives. First fit takes the 48-byte block, splits it, and leaves 24 bytes there. Best fit takes the exact 24-byte block and leaves the 48 alone. Now a 48-byte request arrives. Under best fit it succeeds. Under first fit, if nothing else is free, it fails, even though 48 free bytes exist in total. Same free space, different outcome.

Placement policies side by side
PolicyPicksSearch costFragmentation
First fitthe first free block big enoughstops early, usually shortsmall slivers pile up near the start of the buffer
Next fitthe first fit after where the last search stoppedshortest on averageoften worse than first fit, because it spreads slivers everywhere
Best fitthe smallest free block big enougha full scan, unless lists are sorted by sizekeeps big blocks whole, but leaves tiny leftovers

Start with first fit. It's the easiest to code and to reason about in a test. When the interviewer asks what you'd change, best fit is the usual answer. Its full scan stops costing much once you have the size-class lists from the previous dive, because searching one class already gets you close to the best fit. Point out that link, because it ties the two dives into one design.

What does free do with its neighbours?

Fill the 64 KB buffer with 1,024 blocks of 64 bytes, then free all of them. Without merging, the free list holds 1,024 separate 64-byte blocks. A request for 100 bytes now fails, with the entire buffer free. That's external fragmentation in its purest form. A test that frees a few neighbours and then asks for a bigger block catches it at once.

BadMark the block free and stop

Approach

Flip the in-use bit and push the block onto the free list. Each call does one write.

Challenges

It fails the 1,024-block test above. Free space only ever gets cut into smaller pieces, never put back together, so a long-running program sees larger and larger requests fail over time.

GoodMerge with the right neighbour, walk to find the left

Approach

The block to the right starts at this block's start plus its size, so check its header and, if it's free, unlink it and add its size to ours. For the left side, walk from byte 0 until the next block would be this one. With a side table kept in address order, the left neighbour is simply the entry before this one.

Challenges

In the in-band layout, the left walk costs up to 2,700 header reads per free, which turns a cheap call into the slowest one. A list ordered by free time doesn't help, because it says nothing about which block sits to the left in memory.

GreatBoundary tags, with a footer on every block

Approach

Copy the header into the last 8 bytes of every block. To free a block, read the 8 bytes just before its start. That's the left neighbour's footer, holding its size and in-use bit. If it's free, the neighbour starts that many bytes back, so merging left takes one read, the same as merging right. Free then handles four cases in constant time: no free neighbour, free right only, free left only, or both, which collapses three blocks into one.

Challenges

Every block pays 8 more bytes, which is a third of a 24-byte block. The footer must be rewritten whenever a block splits or merges, and forgetting one stale footer corrupts the next free on the left.

The left neighbour's footer sits right before your header, so merging left starts with a single read.

python
left_footer = read_word(start - 8) # left neighbour's size and in-use bit
if not left_footer & IN_USE:
left_start = start - (left_footer & ~IN_USE)
unlink(left_start) # take it off the free list
start, size = left_start, size + (left_footer & ~IN_USE)

There's a known refinement if the interviewer asks about the footer's cost. Only free blocks really need one, because only a free left neighbour is ever merged. Keep a second bit in each header that says whether the block before it is free, and drop footers from blocks in use. Mention it once you have the four cases working. It's the kind of detail that's easy to break with a minute left.

How does the allocator fail safely?

An allocator is trusted by everything above it, so its edge cases are where the interviewer can probe hardest. Four of them apply to any version of this problem.

1

Rounding and alignment

Round every request up to a multiple of 8 before adding the 16 bytes of header and footer, then apply the 24-byte minimum. A 1-byte request becomes a 24-byte block and a 13-byte request becomes 32. Rounding keeps every payload aligned, and it's what frees the low bits of the size for the in-use flag.

2

Zero and oversized requests

Decide what a request for 0 bytes does and write it down. Returning the failure value is the simplest rule to test. A request larger than the buffer, or larger than the biggest free block, fails without touching any state.

3

Double free

Releasing a block that's already free must be refused. If it isn't, the block lands on the free list twice, two later requests get the same memory, and the bug surfaces far away. The in-use bit catches it. Check it before changing anything.

4

An offset that was never handed out

An offset in the middle of a block, or past the end of the buffer, must also be refused. With a side table that's one dictionary lookup. In the in-band layout you can't trust a header you haven't verified, so either walk the blocks to confirm the offset is a real start, or keep a small magic number in each header and check it.

The rounding is one line, and it's worth writing as a named helper so the tests can call it directly.

python
def block_size(request):
payload = (request + 7) & ~7 # round up to a multiple of 8
return max(payload + 16, 24) # header + footer, never under 24

What if every slot is the same size?

The 2024 C round asked for "creating slotted memory and storing data." Ask whether your version fixes the slot size, because if it does, the design gets much simpler. Split 64 KB into 64-byte slots and you have 1,024 of them. No block ever splits or merges, so there's no placement policy and no fragmentation between slots.

GoodA pool with a free stack

Approach

Keep a stack of free slot indices. Allocate pops one and returns its offset, slot index times 64. Release pushes the index back. Both are constant time. The stack can even live inside the slots: each free slot stores the index of the next free slot in its first 4 bytes, so the only extra memory is one head index.

Challenges

A double free pushes the same slot twice. A bitmap of 1,024 bits, 128 bytes in all, records which slots are in use and catches it. Waste moves inside the slot: a 10-byte item still takes 64 bytes. If item sizes vary, the answer is several pools, one per size, which is the size-class idea from the first dive again.

Keep this version ready even for the general prompt. It answers "what if most requests are the same size," and it's a working fallback if the general allocator runs long.

Which tests prove the allocator works?

Write the tests as you build, one per behaviour, and run them as each part lands. A suite written in the last five minutes rarely gets run. These cover the shape of the problem in about the order you'd build it.

  • Fill the buffer exactly, then show one more byte fails.
  • Allocate two blocks and check their regions don't overlap.
  • Free a block, then allocate the same size and get the same offset back.
  • Free a middle block, then its neighbours, and check one big free block remains.
  • Release the same offset twice and check the second call fails.
  • Release an offset inside a block, and one past the end.
  • Request 0 bytes, and more than the buffer holds.
  • Recreate the first fit versus best fit example and assert the policy you chose.

If time allows, add a random test. Run a few thousand random allocates and releases against both your allocator and a dumb model, such as a list of one flag per byte, and compare after every step. It finds the stale footer and the off-by-one split that hand-written cases miss.

The Two Sigma angle
Two Sigma grades testing as its own area, and the newest allocator candidate, in October 2026, ran out of time. Get allocate and release passing simple tests within the first half hour. Merging and policy can follow.

Practice the core in code

The problem below is the side-table version of the allocator. Bookkeeping lives outside the array, and sizes are plain units with no headers or rounding, so the code is all about splitting, merging and refusing bad frees. Once it passes, redo it in C with headers inside the buffer. Same logic, harder plumbing.

1

Memory allocator over a fixed array

Medium
Problem
You manage a fixed array of capacity memory units, all free at the start. Write a class Allocator with three methods.

allocate(size) finds the lowest-addressed free run of at least size consecutive units and takes its first size units, leaving the rest of the run free. It returns the start offset, or -1 if size is not positive or no free run is long enough.

release(offset) frees the block that allocate returned at offset and returns its size. Freed space joins any free space next to it. If offset is not the start of a block that is currently allocated, it returns -1 and changes nothing. largest() returns the length of the longest run of free units, or 0 if none.

Input encoding. A test case is a JSON array of operations. The first entry is ["Allocator", [capacity]] and each later entry is [method, [args]]. The expected array holds each operation's return, with null for the constructor.
  1. Allocator(10)
  2. allocate(3)→ 0
  3. allocate(4)→ 3
  4. allocate(4)→ -1
  5. largest()→ 3
  6. release(0)→ 3
  7. allocate(2)→ 0
  8. largest()→ 3

After two allocations only units 7 to 9 are free, so a request for 4 fails. Releasing offset 0 frees units 0 to 2, and a request for 2 takes the lowest free run, leaving units 2 and 7 to 9 free.

How this uses the pattern

Keep the blocks in a list sorted by start offset, each with its length and whether it is in use. Allocate splits the first free block that fits. Release merges the freed block with a free neighbour on either side.

Write it here, or go full screen with the problem, hints and solution beside the editor.

Memory allocator over a fixed array

Loading...
Click "Run" to execute your code
The Two Sigma angle
This is the core of the memory allocator prompt Two Sigma candidates describe, without the header bookkeeping. Most bugs are in release: forgetting to merge on one side, or accepting an offset twice. Say the invariant before coding: the blocks tile the array in order with no gaps, and no two free blocks are ever next to each other.
Take it further
Bring the design back in. Switch to best fit and write a test where it gives a different answer. Then move the bookkeeping into the array itself, with a header in front of each block and a footer at its end, so release can find its left neighbour in one step. Finally, add a pool for one fixed size and route small requests to it.

Extensions worth having an answer for

These are the natural next steps, worth an answer in case one comes up.

realloc. Growing a block in place works when the block to its right is free and big enough: merge, then split off whatever is left. Otherwise allocate a new block, copy the payload and free the old one. Shrinking is a split. Threads. One lock around allocate and release is correct and simple, and it becomes the bottleneck as soon as several threads allocate at once. Allocators such as tcmalloc and jemalloc keep a small cache of free blocks per thread or per CPU and only take a shared lock when a cache runs dry or fills up. Running out. A real allocator asks the operating system for more memory when the buffer is full, with sbrk or mmap. In this prompt the buffer is fixed, so failure is the answer. Say that you'd make it visible to the caller and never return memory you don't have.

What is expected at each level

Intern and new grad

Three of the six were intern rounds. At this level, most of the hour should go into working code. Set the scope, pick a layout and say why in a sentence or two, then get a correct allocate and release running with merging on both sides. You don't need boundary tags or size classes, but you should be able to say what each would fix. The bar: a working first-fit allocator with splitting, merging and refused double frees, plus tests you wrote and ran yourself, inside the hour.

The Two Sigma angle
A Blind poster tagged as a Two Sigma employee wrote in April 2025 that new grads don't get system design. For an intern or new grad, a prompt like this one is the design part of the loop, judged on working code and tests.

Experienced engineers

With a few years behind you, expect more of the hour to go on the reasoning around the code. Build the in-band layout, or explain it well if a side table saved time. Raise fragmentation before being asked and defend the placement policy with an example. The four free cases should all be handled, along with the refinement that drops footers from blocks in use. Bring up threads and realloc yourself, before the interviewer has to. The bar: a tested allocator plus a clear account of overhead, fragmentation and search cost, and what you'd change for a real workload.

Key Takeaways

  • ✓Ask first whether bookkeeping may live outside the array. It decides how the hour goes.
  • ✓Blocks tile the buffer in address order. Allocate splits a free block, release merges it with free neighbours.
  • ✓Boundary tags let free read its left neighbour in one step. Without merging, a fully free buffer can still fail.
  • ✓Refuse double frees and bad offsets, and write tests as you build, since Two Sigma grades testing.
Two Sigma interview guide

Know what Two Sigma asks before you walk in.

21 coding · 4 system design · 13 behavioral questions

Get Premium$49 a year · Instant access
Or start freeNo card.

Get their questions first.

The System Design InterviewHad your Two Sigma interview?How we research

InterviewLegend is independent and not affiliated with or endorsed by any company it covers.