Implement a Simulated Memory Allocator

Implement a simulated memory allocator that supports allocate(size) and free(ptr) operations analogous to malloc and free. Treat memory as a contiguous byte array of capacity N provided at initialization and return identifiers for allocated blocks. Achieve low-latency operations under heavy workloads; justify your choice of data structures (e.g., segregated free lists, interval/balanced trees, buddy system). Handle alignment and external/internal fragmentation, and support coalescing of adjacent free blocks. Provide time and space complexity analysis, discuss trade-offs among first-fit/best-fit/next-fit strategies, and describe tests and benchmarks you would write to validate correctness and performance.

Implement a Simulated Memory Allocator

Implement a simulated memory allocator over a contiguous byte array spanning offsets [0, capacity). For deterministic judging, use a buddy allocator.

Task

Write a function:

solution(capacity, alignment, operations)

• capacity — total size of the arena (a power of two).
• alignment — the minimum block size, also used as the alignment unit (a power of two).
• operations — a list of operations, each a pair (op, value):
  • ('alloc', size) — request a block of size bytes.
  • ('free', ptr) — release the block that starts at offset ptr.

Process every operation in order and return a list of integers — one result per operation, in the same order.

alloc(size)

1. If size <= 0, append -1 (failure) and stop processing this operation.
2. Compute the required block size as max(alignment, p), where p is the smallest power of two that is >= size.
3. If that block size is greater than capacity, append -1.
4. Otherwise, locate a free block to satisfy the request:
   • Starting from the required order, scan upward through the free blocks for the smallest available block size that is >= the required size.
   • If no free block can satisfy the request, append -1.
   • Otherwise, take that block. If it is larger than needed, split it in half repeatedly: each split discards the block and keeps its left half, returning the right half to the pool of free blocks. Continue splitting until the block is exactly the required size.
   • Append the starting offset of the allocated block.

When more than one free block of the required size is available, allocation is deterministic: the block with the lowest starting offset is chosen.

free(ptr)

1. If ptr is not the exact starting offset of a currently allocated block, append 0 (no-op). This covers freeing an offset that was never allocated, an offset that is currently free, or an offset that is the interior of a larger block.
2. Otherwise, release the block and coalesce it with its free buddy of the same size whenever that buddy is also free, merging repeatedly up the chain. Append 1.

Buddy invariant

A block of size 2^k always starts at an offset that is a multiple of 2^k. Its buddy is the adjacent same-size block obtained by flipping bit k of the start offset — so splits and merges always stay aligned and each block has a unique sibling.

Constraints

• 1 <= alignment <= capacity <= 2^20.
• capacity and alignment are powers of two.
• 1 <= len(operations) <= 2 * 10^5.
• Each operation is either ('alloc', size) with 0 <= size <= capacity, or ('free', ptr) with 0 <= ptr < capacity.

Example

capacity = 16, alignment = 4
operations = [
  ('alloc', 3),   # -> 0   (rounds up to size 4, placed at offset 0)
  ('alloc', 5),   # -> 8   (rounds up to size 8)
  ('free', 0),    # -> 1   (offset 0 was allocated; freed)
  ('alloc', 4),   # -> 0   (reuses the lowest free 4-byte slot)
  ('free', 8),    # -> 1
  ('free', 0),    # -> 1
  ('alloc', 12)   # -> 0   (rounds up to 16, the whole arena)
]
# returns [0, 8, 1, 0, 1, 1, 0]

Discussion (interview context)

This models a low-latency allocator. Buddy allocation gives predictable split/coalesce behavior and reduces external fragmentation, but it can waste memory internally because requests are rounded up to a power of two. Be prepared to compare it with first-fit, best-fit, and next-fit interval allocators, and to discuss tests such as double-free, full-capacity allocation, alignment checks, long random workloads, and coalescing chains.

Hints

1. Think in powers of two: each allocation belongs to a size class, and larger blocks can be split until the needed class is reached.
2. When freeing a block of size S at address ptr, its buddy's address is ptr XOR S. If that buddy is also free, they can be merged.

Approach

This is a buddy allocator. Capacity is a power of two, so every block size is a power of two too. An "order" k means a block of size 2^k; max_order = log2(capacity) is the whole arena.

Free-block bookkeeping. For each order the code keeps two parallel structures: a set (free_sets[order]) for O(1) membership tests, and a min-heap (free_heaps[order]) so that among equal-size free blocks the one with the lowest start offset is chosen — this makes results deterministic. Deletion from the heap is lazy: pop_free discards heap entries no longer in the set before returning the smallest live start. Initially the single block (max_order, 0) covers everything.

alloc(size). Reject size <= 0 with -1. Round up to block_size = max(alignment, next_power_of_two(size)); if that exceeds capacity, return -1. The needed order is target_order = log2(block_size). Scan upward from target_order for the first non-empty order; if none, return -1. Pop that block, then split down: each step halves the order, and the right half start + 2^order is pushed back as free while we keep the left half. Record allocated[start] = target_order and return start.

free(ptr). If ptr isn't the exact start of a live allocation, return 0. Otherwise pop it and coalesce: the buddy of a block at start is start ^ (1 << order) (flip the order-th bit). While that buddy is free at the same order, remove it, move start to min(start, buddy), and bump the order. Insert the merged block and return 1.

Correctness rests on the buddy invariant: a block of size 2^k always starts at a multiple of 2^k, so XOR pinpoints its unique sibling and splits/merges stay aligned.

• Time complexity: O(log capacity * log F) amortized per operation (F = tracked free blocks); split/coalesce/order-scan are each O(log capacity) steps and each heap push/pop is O(log F). Over m operations: O(m * log capacity * log F).
• Space complexity: O(A + F), where A is the number of live allocations stored in the dict and F is the total free entries across the per-order sets and heaps (heaps may hold extra stale entries lazily until popped).