Implement a Contiguous Memory Allocator with Primitive Lists
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Implement a Contiguous Memory Allocator with Primitive Lists
Simulate an allocator over the contiguous address range `[0, capacity)`, initially one free block. Process two kinds of operation:
- `("alloc", size)` chooses the smallest free block whose size is at least `size`; ties go to the lower starting address. Split any unused suffix and return the allocated block's starting address. Return `-1` if no block fits.
- `("free", pointer)` releases the currently allocated block that begins exactly at `pointer`, coalesces it with adjacent free blocks, and returns `1`. Return `0` for an unknown pointer, an interior pointer, or a double free.
## Function Contract
```python
def run_allocator(
capacity: int,
operations: list[tuple],
) -> list[int]:
...
```
Return one integer result for every operation in order.
## Constraints
- `1 <= capacity <= 10_000`
- `1 <= len(operations) <= 10_000`
- An allocation size is an integer in `[1, capacity]`.
- A free pointer is an integer in `[0, capacity - 1]`.
- Use primitive Python lists and scalar variables for allocator state; do not use a tree, heap, hash map, ordered-map package, or `bisect`.
- If you maintain a size-ordered free list, implement its binary search and insertion directly.
- Block boundaries and coalescing must be derived from allocator-owned list state.
## Example
```text
capacity = 8
operations = [
("alloc", 3),
("alloc", 2),
("free", 0),
("alloc", 4),
]
result = [0, 3, 1, -1]
```
Overview: Simulate best-fit allocation across a contiguous address range using only primitive lists and scalar state. Support splitting, exact-pointer frees, double-free rejection, deterministic tie-breaking, and coalescing adjacent free blocks across up to 10,000 operations.
Implement run_allocator(capacity, operations). Each operation is ["alloc", size] or ["free", pointer], with numeric fields encoded as decimal strings. Allocation chooses the smallest fitting free block, breaking ties by lower address, splits its suffix, and returns the start or -1. Free succeeds only for an allocated block's exact start, coalesces adjacent free blocks, and returns 1; invalid frees return 0. Use primitive sequential containers for allocator state.
Constraints
- 1 <= capacity <= 10,000 and 1 <= len(operations) <= 10,000.
- Allocation sizes are between 1 and capacity; free pointers are between 0 and capacity - 1.
- Allocator state must use primitive sequential lists and scalars: do not use a map, tree, heap, ordered-map package, or a built-in binary-search insertion helper.
Examples
Input: (8, [["alloc","3"],["alloc","2"],["free","0"],["alloc","4"]])
Expected Output: [0, 3, 1, -1]
Explanation: The final free blocks are too small for four units.
Input: (1, [["alloc","1"],["free","0"],["alloc","1"]])
Expected Output: [0, 1, 0]
Explanation: A freed full-capacity block is reusable.
Hints
- Keep free blocks in address order and scan for the best fit.
- After insertion, a freed block can merge with its left neighbor, right neighbor, or both.