Contiguous Memory Allocator II

hard

CodingReported Jul 2026 · Medium frequency

Memory Allocator

CodingPhone, Onsite Software Engineer, Machine Learning Engineer — reported March 2026 — medium frequency

Problem Overview

Create a memory-manager class that controls a single contiguous address range. It should offer allocation and release behavior comparable to C's malloc() and free() operations.

Your allocator must:

Begin with a fixed amount of usable memory.
Reserve contiguous regions on request.
Return previously reserved regions to the free pool.
Continue operating correctly when free space is fragmented.
Reject invalid requests and requests that cannot be satisfied by one contiguous region.

Requirements

Build a MemoryAllocator class exposing the interface below.

Constructor

def __init__(self, total_capacity: int)

total_capacity gives the total number of bytes or abstract memory units managed by the allocator.
At construction time, the entire address range must be free.

Methods

1. `allocate(size: int) -> int`

Reserve one contiguous region containing size units.

Parameters:

size: The requested amount; it must be greater than zero.

Returns:

The address, represented as an index, at which the reserved region begins.

Behavior:

Examine free regions in address order and choose the first one large enough for the request.
Mark the selected range as occupied.
Return its starting address.

Errors:

Throw an exception when size is zero or negative.
Throw an exception when no single free region is large enough.

2. `free(address: int, size: int) -> None`

Return an earlier allocated region to the free memory pool.

Parameters:

address: The first address in the region being released.
size: The region's length.

Behavior:

Mark the indicated range as available again.
Combine neighboring free regions whenever they touch, limiting fragmentation.

Errors:

Throw an exception when address lies outside the managed address range.
Throw an exception when the requested range was not allocated.
Throw an exception when size is invalid.

Use a doubly linked list of free regions to implement the allocator.

Data Structure

Each list node represents one currently available range and contains:

start: The first address in the free range.
size: The number of free units in that range.
next: A link to the following free-range node.
prev: A link to the preceding free-range node.

Important: Keep the free list sorted by starting address. This ordering makes it possible to identify and combine adjacent ranges during free().

Allocation Strategy

Use first-fit search: scan from the lowest address toward the highest and stop at the first fitting node.
If the node exactly matches the requested length, unlink that node.
If the node is larger, move its start forward by the allocated length and reduce its size accordingly.

Deallocation Strategy

When inserting a released range, account for these four possibilities:

No merge: Neither neighboring free range touches the released range.
- Create and insert a separate node.
Merge with previous block: The preceding free range ends exactly where the released range begins.
- Increase the preceding node's size.
Merge with next block: The released range ends exactly where the following free range begins.
- Expand the following node backward and increase its size.
Merge with both: Free ranges exist immediately on both sides.
- Replace all three ranges with one combined range.

Example

# Create an allocator containing 80 units.
allocator = MemoryAllocator(80)

# Reserve 15 units.
a = allocator.allocate(15)  # Returns 0
# Memory: [Allocated(0-14)] [Free(15-79)]

# Reserve 25 units.
b = allocator.allocate(25)  # Returns 15
# Memory: [Allocated(0-14)] [Allocated(15-39)] [Free(40-79)]

# Reserve 20 units.
c = allocator.allocate(20)  # Returns 40
# Memory: [Allocated(0-14)] [Allocated(15-39)] [Allocated(40-59)] [Free(60-79)]

# Release the middle allocation.
allocator.free(15, 25)
# Memory: [Allocated(0-14)] [Free(15-39)] [Allocated(40-59)] [Free(60-79)]

# This request fits at the beginning of the first available range.
d = allocator.allocate(18)  # Returns 15
# Memory: [Allocated(0-14)] [Allocated(15-32)] [Free(33-39)] [Allocated(40-59)] [Free(60-79)]

# Release the first allocation.
allocator.free(0, 15)
# Memory: [Free(0-14)] [Allocated(15-32)] [Free(33-39)] [Allocated(40-59)] [Free(60-79)]

# Releasing the second allocation joins the free ranges on both sides.
allocator.free(15, 18)
# Memory: [Free(0-39)] [Allocated(40-59)] [Free(60-79)]

The final merge occurs because the released range [15-32] touches [0-14] on its left and [33-39] on its right.

Once the basic allocator is complete, be ready to explain its performance and possible alternatives.

Time Complexity

Allocation: O(n), with n representing the number of free-list nodes.
- In the worst case, the scan visits every free range before finding a fit or failing.
Deallocation: O(n) in the worst case.
- The list may need to be traversed to locate the released range's position and its potential neighbors.

Space Complexity

O(m), where m is the number of free ranges.
Alternating occupied and available regions can produce many free-list nodes.
Thus, the auxiliary space is driven by the allocation history and fragmentation pattern, not directly by total capacity.

Drawbacks and Limitations

External fragmentation: Repeated operations can divide available memory into many small pieces.
- A large request can fail even when the sum of all free pieces is sufficient.
- For example, 60 free units split into six ranges of 10 cannot satisfy a request for 50 contiguous units.
Linear search: First-fit allocation may inspect every free node.
No compaction: The allocator does not move live allocations to make one larger free range.

Optimization Strategies

Reducing Fragmentation:

Segregated free lists: Keep separate lists for distinct size categories.
- For instance, requests below 32 bytes could use a dedicated pool.
- This can protect the main address space from many tiny allocations.
- It may also improve cache locality.
Best-fit selection: Choose the smallest free range that can hold the request rather than the first suitable range.
- This can reduce the leftover space from an individual allocation.
- The trade-off is that a full scan is generally required, so allocation remains O(n).
Buddy allocation: Divide memory into blocks whose sizes are powers of two.
- Matching buddy blocks can be combined using predictable addresses.
- This often simplifies coalescing and can reduce external fragmentation.
- Rounding requests upward causes additional internal fragmentation.

Improving Time Complexity:

Balanced binary search trees: Index free ranges by both address and size.
- A size-ordered tree can locate a best-fit range in O(log n).
- An address-ordered tree can find neighboring ranges for merging in O(log n).
- Two indexes, or one augmented tree with a secondary index, can provide O(log n) allocation and release operations.
- Red-black trees and AVL trees are possible implementations.
- Production allocators such as glibc's ptmalloc2 use red-black trees for some free-block management.
Bitmap with an index: Represent fixed-size units with bits and maintain an index over available units.
- Bit operations can provide O(1) allocation for uniform-size blocks.
- This approach requires all allocatable blocks to have the same size.

Achieving Constant Space Complexity:

To use O(1) auxiliary space, place allocator metadata inside the managed memory itself.

Implicit free list: Store each block's length and occupancy flag in a header located at the block's beginning.
- Free blocks may also use their payload area for next and previous links.
- No separate collection of metadata nodes is required.
- This is the general strategy used by many practical malloc implementations.
- The minimum block size must fit the header and pointer metadata, commonly around 16–24 bytes.
Boundary tags: Pair the implicit-list headers with size information at each block's end.
- The footer allows the allocator to find the preceding block in constant time.
- It therefore enables O(1) backward coalescing, while forward coalescing is already constant time.
- A header and footer require 2 * sizeof(size_t) bytes of metadata per block.
- Boundary tags refine an implicit free list rather than constituting a separate allocation strategy.

Follow-up Questions

Be prepared to discuss the following extensions:

How would you enforce alignment, such as requiring every address to be divisible by 8?
How would you record live allocations so that invalid free() requests can be detected?
What design changes would be needed to support realloc() for resizing an existing allocation?
How would you make the allocator safe for concurrent callers?
Which aspects would differ between a real hardware-backed allocator and this abstract model?

Implementation Tips

Edge Cases to Handle

A request to allocate zero or a negative number of units.
A release whose address is outside the managed range.
A second release of an already freed range.
A release whose supplied size does not match the original allocation.
A request larger than the allocator's total capacity.
A request that fails because free space exists only in separated fragments.

Testing Strategy

Include tests for:

Ordinary allocation followed by release.
Running out of memory.
Requests affected by fragmentation.
Coalescing with the previous range, the next range, both ranges, and neither range.
Boundary allocations beginning at address 0 or ending at the final address.
Invalid operations such as double release and out-of-range addresses.

BackBack to problems

Contiguous Memory Allocator II

hard

CodingReported Jul 2026 · Medium frequency

Memory Allocator

CodingPhone, Onsite Software Engineer, Machine Learning Engineer — reported March 2026 — medium frequency

Problem Overview

Create a memory-manager class that controls a single contiguous address range. It should offer allocation and release behavior comparable to C's malloc() and free() operations.

Your allocator must:

Begin with a fixed amount of usable memory.
Reserve contiguous regions on request.
Return previously reserved regions to the free pool.
Continue operating correctly when free space is fragmented.
Reject invalid requests and requests that cannot be satisfied by one contiguous region.

Requirements

Build a MemoryAllocator class exposing the interface below.

Constructor

def __init__(self, total_capacity: int)

total_capacity gives the total number of bytes or abstract memory units managed by the allocator.
At construction time, the entire address range must be free.

Methods

1. `allocate(size: int) -> int`

Reserve one contiguous region containing size units.

Parameters:

size: The requested amount; it must be greater than zero.

Returns:

The address, represented as an index, at which the reserved region begins.

Behavior:

Examine free regions in address order and choose the first one large enough for the request.
Mark the selected range as occupied.
Return its starting address.

Errors:

Throw an exception when size is zero or negative.
Throw an exception when no single free region is large enough.

2. `free(address: int, size: int) -> None`

Return an earlier allocated region to the free memory pool.

Parameters:

address: The first address in the region being released.
size: The region's length.

Behavior:

Mark the indicated range as available again.
Combine neighboring free regions whenever they touch, limiting fragmentation.

Errors:

Throw an exception when address lies outside the managed address range.
Throw an exception when the requested range was not allocated.
Throw an exception when size is invalid.

Use a doubly linked list of free regions to implement the allocator.

Data Structure

Each list node represents one currently available range and contains:

start: The first address in the free range.
size: The number of free units in that range.
next: A link to the following free-range node.
prev: A link to the preceding free-range node.

Important: Keep the free list sorted by starting address. This ordering makes it possible to identify and combine adjacent ranges during free().

Allocation Strategy

Use first-fit search: scan from the lowest address toward the highest and stop at the first fitting node.
If the node exactly matches the requested length, unlink that node.
If the node is larger, move its start forward by the allocated length and reduce its size accordingly.

Deallocation Strategy

When inserting a released range, account for these four possibilities:

No merge: Neither neighboring free range touches the released range.
- Create and insert a separate node.
Merge with previous block: The preceding free range ends exactly where the released range begins.
- Increase the preceding node's size.
Merge with next block: The released range ends exactly where the following free range begins.
- Expand the following node backward and increase its size.
Merge with both: Free ranges exist immediately on both sides.
- Replace all three ranges with one combined range.

Example

# Create an allocator containing 80 units.
allocator = MemoryAllocator(80)

# Reserve 15 units.
a = allocator.allocate(15)  # Returns 0
# Memory: [Allocated(0-14)] [Free(15-79)]

# Reserve 25 units.
b = allocator.allocate(25)  # Returns 15
# Memory: [Allocated(0-14)] [Allocated(15-39)] [Free(40-79)]

# Reserve 20 units.
c = allocator.allocate(20)  # Returns 40
# Memory: [Allocated(0-14)] [Allocated(15-39)] [Allocated(40-59)] [Free(60-79)]

# Release the middle allocation.
allocator.free(15, 25)
# Memory: [Allocated(0-14)] [Free(15-39)] [Allocated(40-59)] [Free(60-79)]

# This request fits at the beginning of the first available range.
d = allocator.allocate(18)  # Returns 15
# Memory: [Allocated(0-14)] [Allocated(15-32)] [Free(33-39)] [Allocated(40-59)] [Free(60-79)]

# Release the first allocation.
allocator.free(0, 15)
# Memory: [Free(0-14)] [Allocated(15-32)] [Free(33-39)] [Allocated(40-59)] [Free(60-79)]

# Releasing the second allocation joins the free ranges on both sides.
allocator.free(15, 18)
# Memory: [Free(0-39)] [Allocated(40-59)] [Free(60-79)]

The final merge occurs because the released range [15-32] touches [0-14] on its left and [33-39] on its right.

Once the basic allocator is complete, be ready to explain its performance and possible alternatives.

Time Complexity

Allocation: O(n), with n representing the number of free-list nodes.
- In the worst case, the scan visits every free range before finding a fit or failing.
Deallocation: O(n) in the worst case.
- The list may need to be traversed to locate the released range's position and its potential neighbors.

Space Complexity

O(m), where m is the number of free ranges.
Alternating occupied and available regions can produce many free-list nodes.
Thus, the auxiliary space is driven by the allocation history and fragmentation pattern, not directly by total capacity.

Drawbacks and Limitations

External fragmentation: Repeated operations can divide available memory into many small pieces.
- A large request can fail even when the sum of all free pieces is sufficient.
- For example, 60 free units split into six ranges of 10 cannot satisfy a request for 50 contiguous units.
Linear search: First-fit allocation may inspect every free node.
No compaction: The allocator does not move live allocations to make one larger free range.

Optimization Strategies

Reducing Fragmentation:

Segregated free lists: Keep separate lists for distinct size categories.
- For instance, requests below 32 bytes could use a dedicated pool.
- This can protect the main address space from many tiny allocations.
- It may also improve cache locality.
Best-fit selection: Choose the smallest free range that can hold the request rather than the first suitable range.
- This can reduce the leftover space from an individual allocation.
- The trade-off is that a full scan is generally required, so allocation remains O(n).
Buddy allocation: Divide memory into blocks whose sizes are powers of two.
- Matching buddy blocks can be combined using predictable addresses.
- This often simplifies coalescing and can reduce external fragmentation.
- Rounding requests upward causes additional internal fragmentation.

Improving Time Complexity:

Balanced binary search trees: Index free ranges by both address and size.
- A size-ordered tree can locate a best-fit range in O(log n).
- An address-ordered tree can find neighboring ranges for merging in O(log n).
- Two indexes, or one augmented tree with a secondary index, can provide O(log n) allocation and release operations.
- Red-black trees and AVL trees are possible implementations.
- Production allocators such as glibc's ptmalloc2 use red-black trees for some free-block management.
Bitmap with an index: Represent fixed-size units with bits and maintain an index over available units.
- Bit operations can provide O(1) allocation for uniform-size blocks.
- This approach requires all allocatable blocks to have the same size.

Achieving Constant Space Complexity:

To use O(1) auxiliary space, place allocator metadata inside the managed memory itself.

Implicit free list: Store each block's length and occupancy flag in a header located at the block's beginning.
- Free blocks may also use their payload area for next and previous links.
- No separate collection of metadata nodes is required.
- This is the general strategy used by many practical malloc implementations.
- The minimum block size must fit the header and pointer metadata, commonly around 16–24 bytes.
Boundary tags: Pair the implicit-list headers with size information at each block's end.
- The footer allows the allocator to find the preceding block in constant time.
- It therefore enables O(1) backward coalescing, while forward coalescing is already constant time.
- A header and footer require 2 * sizeof(size_t) bytes of metadata per block.
- Boundary tags refine an implicit free list rather than constituting a separate allocation strategy.

Follow-up Questions

Be prepared to discuss the following extensions:

How would you enforce alignment, such as requiring every address to be divisible by 8?
How would you record live allocations so that invalid free() requests can be detected?
What design changes would be needed to support realloc() for resizing an existing allocation?
How would you make the allocator safe for concurrent callers?
Which aspects would differ between a real hardware-backed allocator and this abstract model?

Implementation Tips

Edge Cases to Handle

A request to allocate zero or a negative number of units.
A release whose address is outside the managed range.
A second release of an already freed range.
A release whose supplied size does not match the original allocation.
A request larger than the allocator's total capacity.
A request that fails because free space exists only in separated fragments.

Testing Strategy

Include tests for:

Ordinary allocation followed by release.
Running out of memory.
Requests affected by fragmentation.
Coalescing with the previous range, the next range, both ranges, and neither range.
Boundary allocations beginning at address 0 or ending at the final address.
Invalid operations such as double release and out-of-range addresses.

Contiguous Memory Allocator II

Memory Allocator

Problem Overview

Requirements

Constructor

Methods

1. allocate(size: int) -> int

2. free(address: int, size: int) -> None

Part 1: Basic Implementation

Data Structure

Allocation Strategy

Deallocation Strategy

Example

Part 2: Complexity Analysis and Optimization Discussion

Time Complexity

Space Complexity

Drawbacks and Limitations

Optimization Strategies

Follow-up Questions

Implementation Tips

Edge Cases to Handle

Testing Strategy

Contiguous Memory Allocator II

Memory Allocator

Problem Overview

Requirements

Constructor

Methods

1. allocate(size: int) -> int

2. free(address: int, size: int) -> None

Part 1: Basic Implementation

Data Structure

Allocation Strategy

Deallocation Strategy

Example

Part 2: Complexity Analysis and Optimization Discussion

Time Complexity

Space Complexity

Drawbacks and Limitations

Optimization Strategies

Follow-up Questions

Implementation Tips

Edge Cases to Handle

Testing Strategy

1. `allocate(size: int) -> int`

2. `free(address: int, size: int) -> None`

1. `allocate(size: int) -> int`

2. `free(address: int, size: int) -> None`