OpenAI VO #1 – Memory Manager – Implement malloc and free

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

• malloc(k) — Allocates a contiguous block of k bytes and returns a pointer to the beginning of the block.
• free(ptr) — Frees the block of memory that was previously allocated at pointer ptr.

Restrictions:

• Each allocated block must be contiguous.
• Once a block is assigned, it cannot be moved (no compaction).
• Freeing memory restores that segment to available space, but other allocations remain fixed.

Example (in Python):

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

Example usage and expected behavior:

m = MemoryManager(1000)
a = m.malloc(100)   # returns 0 → uses cells 0–99
b = m.malloc(500)   # returns 100 → uses 100–599
c = m.malloc(950)   # error: not enough space
m.free(b)           # frees 100–599
m.free(a)           # frees 0–99
m.free(a)           # error: already freed
c = m.malloc(950)   # succeeds → uses 0–949

总结

这题要求模拟内存分配器，核心是维护 一维连续区间的空闲块。

思路：

1. 用一个 列表或有序区间表 记录所有空闲块 (start, end)；
2. malloc(k) 时，从左到右找到第一个长度 ≥ k 的空闲区间；
3. 分配后更新区间（若被占部分切割，剩余部分仍留在空闲表中）；
4. free(ptr) 时，将该区间重新插入并与相邻空闲块 合并；
5. 若重复释放或指针无效 → 抛错。

考察点：

• 区间合并与切割逻辑
• 边界处理（分配、释放）
• 模拟系统内存管理思维

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 OpenAI、Google、Amazon、Citadel、SIG 等，提供实时语音助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Stripe 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。