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 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

Expected behavior:

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

如果用 Python，可以直接把内存下标当作 pointer。例如 malloc(100) 返回 0，表示分配了 0 ~ 99 这段连续空间。

这题最重要的限制是：分配出去的内存必须连续，而且一旦分配后不能移动。也就是说，不能像整理数组一样把已经分配的块挪到一起。这就引出了核心考点：memory fragmentation。

一个错误思路是只记录剩余内存总量。比如释放了两块内存后，总空闲空间可能很多，但如果它们分散在不同位置，仍然无法满足一个大块连续内存申请。所以这题必须维护“空闲区间”，而不是只维护一个 remaining counter。

比较直接的设计是两个结构：

allocated: ptr -> size
free_blocks: list of [start, size]

allocated 用来记录已经分配出去的内存。因为 free(ptr) 只给一个起始位置，如果不记录大小，就不知道应该释放多少 byte。

free_blocks 用来记录当前所有空闲区间。初始化时只有一段：

free_blocks = [[0, N]]
allocated = {}

malloc(k) 时，从 free_blocks 里找第一段 size >= k 的连续空间。找到后返回它的 start，并把这段空间从空闲区间里扣掉。

例如：

free_blocks = [[0, 1000]]
malloc(100) -> 0
free_blocks = [[100, 900]]

malloc(500) -> 100
free_blocks = [[600, 400]]

此时再申请 malloc(950) 会失败，因为当前最大连续空间只有 400。

free(ptr) 时，先检查 ptr 是否存在于 allocated。如果不存在，说明这个 pointer 没有被分配过，或者已经被释放过，需要报错。比如题目里的第二次 free(a) 就应该失败。

如果合法释放，就从 allocated 里拿到对应大小，生成一个新的空闲区间 [ptr, size]，插回 free_blocks。

这里最关键的一步是合并相邻区间。比如：

free_blocks = [[600, 400]]
free(100) 释放 [100, 500]

插入后变成：

[[100, 500], [600, 400]]

因为 100 + 500 = 600，这两段是连续的，所以必须合并成：

[[100, 900]]

再释放 a = [0, 100] 后：

[[0, 100], [100, 900]]

继续合并，得到：

[[0, 1000]]

所以最后 malloc(950) 可以成功。

面试中可以先和面试官确认几个点：

Can I use the starting index as the mock pointer?
Should malloc use first-fit strategy?
Should free throw an error for invalid or double-free pointers?
Can I assume the memory size N is fixed?

通常第一版用 first-fit 就够了，也就是从左到右找第一段足够大的空闲区间。实现简单，逻辑也清楚。

复杂度方面，如果用普通 list 存 free_blocks，malloc 最坏需要扫描所有空闲区间，时间复杂度是 O(F)，其中 F 是 free block 数量。free 可以插入后排序并合并，简单实现是 O(F log F)；如果一直保持 free_blocks 按 start 有序，则可以做到 O(F)。

这题如果有 follow-up，可能会问如何优化。可以回答：如果想让 malloc 更快，可以用按 size 组织的平衡树或堆来查找足够大的 block；如果想让 free 合并更快，可以用按 start 排序的 TreeMap，释放时只检查前后两个相邻区间。

不过在面试第一版里，hashmap + sorted free list 已经足够。重点不是数据结构炫技，而是讲清楚四个核心点：连续内存分配、碎片问题、ptr -> size 记录、释放后的区间合并。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~