Given N free bytes in memory, implement the following two functions:
- malloc(k) — Allocates a contiguous block of
kbytes 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–949Summary
Core idea: manage free memory as a list of intervals.
Approach:
- Track all free ranges as
(start, end)pairs. - For
malloc(k), find the first range large enough and split it. - For
free(ptr), insert the block back and merge with adjacent ranges. - Handle invalid or double frees properly.
This problem mainly tests interval manipulation, state consistency, and low-level resource management logic.
The VOprep team has long accompanied candidates through various major company OAs and VOs, including OpenAI, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Stripe or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
