OpenAI OA Interview Question: Design a Memory Manager

Given N free bytes in the memory, implement the following two functions.

• malloc(k): allocates a block of k bytes of memory and returns a pointer to the beginning of the block. The assigned memory should be one contiguous space in the memory.
• free(ptr): frees the memory that is pointed to by the input pointer.

If using languages without pointers, we can mock the pointer with other designs.

A couple of restrictions:

• The assigned memory block has to be a contiguous sequence of bytes.
• Once a memory block is assigned, you cannot move it and thus you cannot do fragmentation cleanup after malloc.

For example, in Python, we can use the memory block ID as the pointer:

self._mem = range(N)  # free memory with N bytes w/ ids 0,...,N-1

Here is the expected output for a test case:

m = MemoryManager(1000)
a = m.malloc(100)  # returns 0; a takes memory cells 0-99
b = m.malloc(500)  # returns 100; b takes memory cells 100-599
c = m.malloc(950)  # throw an error; not enough space.
m.free(b)          # memory cells 100-599 are freed.
m.free(a)          # memory cells 0-99 are freed.
m.free(a)          # throw an error.
c = m.malloc(950)  # succeeds!

This problem asks you to build a memory manager that supports contiguous allocation and freeing. The key challenge is that allocated blocks cannot be moved, so you need to track free intervals carefully rather than just counting total free space. A typical solution uses an ordered map or interval list to store free segments, scans for a large enough contiguous block during `malloc`, and merges neighboring segments during `free` to reduce fragmentation.