← Back to companies
[ OK ] Loaded —
[ INFO ]
$ cd
$ ls -lt
01
02
03
04
05
$ ls -lt
01
02
03
04
05
user@intervues:~/$
Practice/OpenAI/Memory Allocator
CodingMust
Design and implement a memory allocator that manages a contiguous block of memory, similar to malloc() and free() in C. The allocator must support dynamic allocation and deallocation with proper fragmentation handling.
This problem tests your understanding of linked list manipulation, memory management fundamentals, and edge case handling -- all critical skills for systems and ML infrastructure roles.
` class MemoryAllocator: def init(self, total_capacity: int): ...
def allocate(self, size: int) -> int:
"""First-fit allocation. Returns starting address."""
def free(self, address: int, size: int) -> None:
"""Free block and merge with adjacent free blocks."""
def get_free_memory(self) -> int:
"""Total free memory across all free blocks."""
def get_largest_free_block(self) -> int:
"""Size of the largest contiguous free block."""
`
Use a doubly-linked list where each node represents a free memory block. The list is maintained in address order to enable efficient merging during deallocation.
class FreeBlock: def __init__(self, start: int, size: int): self.start = start self.size = size self.next = None # Next free block (higher address) self.prev = None # Previous free block (lower address)
Traverse the free list from the beginning and use the first block that can satisfy the request:
When freeing memory, check for four cases:
` allocator = MemoryAllocator(100)
addr1 = allocator.allocate(20) # 0 -> [Alloc 0-19][Free 20-99] addr2 = allocator.allocate(30) # 20 -> [Alloc 0-19][Alloc 20-49][Free 50-99] addr3 = allocator.allocate(40) # 50 -> [Alloc 0-19][Alloc 20-49][Alloc 50-89][Free 90-99]
allocator.free(20, 30)
addr4 = allocator.allocate(25) # 20 -> reuses freed space
allocator.free(0, 20)
allocator.free(20, 25) # Merges with both neighbors!
`
allocator.allocate(0) # ValueError: size must be positive allocator.allocate(-5) # ValueError: size must be positive allocator.free(999, 10) # ValueError: address out of bounds allocator.free(0, 10) # ValueError: not allocated (double-free) allocator.allocate(200) # MemoryError: insufficient contiguous memory
After implementing Part 1, be prepared to discuss:
Current ComplexityOperationTimeSpaceallocateO(n)O(1)freeO(n)O(1)
Where n is the number of free blocks in the list.
External fragmentation occurs when total free memory is sufficient but no single contiguous block is large enough:
Total: 100 units, Free: 60 units Layout: [Alloc 10][Free 10][Alloc 10][Free 10][Alloc 10][Free 10]... Cannot allocate 50 units despite 60 units free!
Reducing fragmentation:
Improving time complexity to O(log n):
Achieving O(1) space:
malloc implementations work