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.