0) Problem Restatement
Visa asked a variant of LeetCode 2502 ("Design Memory Allocator"). You have memory of n units (all free at first):
allocate(size, mID): find the leftmost block ofsizeconsecutive free units, mark them as belonging tomID, and return the start index (or −1 if none).free(mID): free all units that belong tomID(an ID may have several blocks), and return how many units were freed.
1) Simple Version (clear and correct)
class Allocator:
def __init__(self, n):
self.mem = [0] * n # 0 = free, otherwise the owner id
def allocate(self, size, mid):
run = 0
for i, owner in enumerate(self.mem):
run = run + 1 if owner == 0 else 0
if run == size:
start = i - size + 1
for j in range(start, i + 1):
self.mem[j] = mid
return start
return -1
def free(self, mid):
count = 0
for i, owner in enumerate(self.mem):
if owner == mid:
self.mem[i] = 0
count += 1
return count2) Faster Version: Track Free Blocks
For large memory, scanning every unit is slow. Instead track blocks:
- Free list: free blocks as
(start, length), sorted by start (a balanced tree / sorted list). - Owner map:
mID → list of (start, length)allocated blocks.
length ≥ size (first fit). Split it: the allocated part goes to the owner map, and the remainder stays free.
free(mID): for each block of that ID, insert it back into the free list and merge (coalesce) with the neighbors if they're adjacent, so free space doesn't get chopped into tiny pieces.
To find the leftmost block that's big enough in O(log n) instead of scanning the free list, use a segment tree over memory that stores, for each segment, the longest free run (plus the prefix and suffix free lengths). Then descend left-first to the first position where a run of size fits.
Architecture Diagram
flowchart LR
A["allocate(size)"] --> FL["Free blocks sorted by start"]
FL -->|"first fit, split"| OM["Owner map: id to blocks"]
F["free(id)"] --> OM
OM -->|"return blocks"| FL
FL -->|"merge adjacent"| FL3) Fragmentation (explain simply)
Over time, memory can have lots of small free gaps between used blocks. Then a large request fails even though the total free space is enough. That's external fragmentation. Mitigations:
- Coalescing on free (merge neighbors), which is essential.
- Allocation policy: first fit (fast), best fit (the smallest block that fits, which leaves bigger blocks intact but creates tiny leftovers), buddy system (power-of-two blocks that merge easily).
- Real systems also have internal fragmentation (rounding sizes up wastes space inside blocks).
4) How Real Allocators Do It
- Size classes (malloc, jemalloc, tcmalloc): small requests are rounded to fixed sizes (16, 32, 48 bytes...) and served from per-size free lists, which is very fast.
- Buddy system (Linux page allocator): split blocks in halves, and merge "buddies" back when both are free.
- Per-thread caches avoid lock contention. Large allocations go directly to the OS (mmap).
- Concurrency for our allocator: a lock around the free structures, or per-region locks.
5) Wrap-Up
The simple solution keeps an array of owners, scanning for the leftmost run of free units on allocate and clearing an ID's units on free, both O(n). To scale, track free blocks sorted by start (with a segment tree of longest free runs for O(log n) leftmost-fit search) and an owner map of blocks, splitting on allocate and coalescing neighbors on free. Explain fragmentation and how real allocators use size classes, buddy systems and per-thread caches.