OpenAI OA 面试真题解析：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!

这道题要求设计一个简单的内存管理器，实现连续内存块的分配与释放：`malloc(k)` 必须找到一段长度为 `k` 的连续空闲区间并返回起始位置，`free(ptr)` 则释放对应区间。核心难点在于，已分配的块不能移动，也不能在分配后做碎片整理，所以不能只靠一个总空闲数来判断，必须维护空闲区间信息。常见做法是用有序结构记录所有空闲段，并在分配时从前往后寻找足够长的连续区间，在释放时与相邻空闲段合并，避免碎片不断累积。