Implement a Contiguous Memory Manager
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are asked to implement a contiguous memory manager for an array of `n` memory cells indexed from `0` to `n - 1`, where all cells are initially free.
Support the following operations:
1. `allocate(size, id) -> int`
- Find the **leftmost** free contiguous segment whose length is at least `size`.
- Allocate the first `size` cells of that segment and label them with allocation ID `id`.
- Return the starting index of the allocated segment.
- If no such segment exists, return `-1`.
2. `release(id) -> int`
- Free **all** cells currently allocated with allocation ID `id`.
- After freeing memory, merge any adjacent free segments into a single larger segment.
- Return the total number of cells released.
Additional notes:
- Multiple allocations may share the same `id`.
- The number of operations is `m`, and `n` may be much larger than `m` (for example, `n` can be up to `10^9`).
- A solution that scans the entire memory array for every operation is too slow.
Design the data structure and implement both operations efficiently.
Quick Answer: This question evaluates competence in designing efficient data structures and algorithms for interval management, contiguous allocation and deallocation over large sparse arrays, emphasizing complexity analysis and handling of large address spaces.