Design a contiguous segment allocator

Design an in-memory contiguous segment allocator over an array of n cells (indexed 0..n- 1), all initially free. Support two operations:

1. allocate(len, tag): find the lowest index i such that cells [i, i+len-1] are all free, mark those cells with identifier tag, and return i; if no such block exists, return -1.
2. release(tag): free every cell currently marked with tag and return the total number of cells released. Specify and implement data structures to achieve efficient performance for large n (aim for O(log n) per operation). Handle edge cases such as repeated tags, releasing a non-existent tag, fragmentation after arbitrary allocate/release sequences, len <= 0, and len > n. Provide complexity analysis and brief tests demonstrating correctness.

Design a Contiguous Segment Allocator

Design an in-memory contiguous segment allocator over an array of n cells indexed 0..n-1, all initially free. You must support two operations replayed in order, and return the result of each:

1. allocate(len, tag) — find the lowest index i such that cells [i, i+len-1] are all free, mark every one of those cells with the identifier tag, and return i. If no such block exists, return -1. If len <= 0 or len > n, no allocation happens and you return -1.
2. release(tag) — free every cell currently marked with tag and return the total number of cells released. Releasing a tag that is not present returns 0.

Tags may repeat: calling allocate twice with the same tag marks two (possibly non-adjacent) blocks with that tag, and a single release(tag) frees all cells carrying it.

Implementation contract for this console: implement solution(n, ops) where ops is a list of operations. Each operation is a list: ["allocate", len, tag] or ["release", tag]. Return a list with one result per operation (the returned index for allocate, the count freed for release).

Discuss how you would achieve O(log n) per operation for large n (e.g. a balanced BST / segment tree over maximal free intervals, plus a tag -> list of [start, len] map for release). The console accepts a correct simulation; the complexity discussion is the design portion of the answer.

Constraints

• 0 <= n (n may be 0, an empty array)
• Each op is ["allocate", len, tag] or ["release", tag]
• allocate with len <= 0 or len > n returns -1 and allocates nothing
• Tags may repeat across allocate calls; release(tag) frees every cell carrying that tag
• release of an absent tag returns 0
• allocate returns the LOWEST feasible start index

Examples

Example 1

Input: (10, [["allocate", 3, "a"], ["allocate", 2, "b"], ["release", "a"], ["allocate", 4, "c"], ["allocate", 3, "d"]])
Output: [0, 3, 3, 5, 0]

Explanation: a takes [0,2], b takes [3,4]. release a frees 3 cells. allocate 4 'c': [0,3] is blocked by b at 3, so lowest fit is [5,8] -> 5. allocate 3 'd': cells 0,1,2 are free -> 0.

Example 2

Input: (5, [["allocate", 6, "x"], ["allocate", 0, "y"], ["allocate", 5, "z"], ["allocate", 1, "w"], ["release", "missing"]])
Output: [-1, -1, 0, -1, 0]

Explanation: len 6 > n=5 -> -1. len 0 <= 0 -> -1. z fills [0,4] -> 0. w can't fit (array full) -> -1. releasing a tag that was never allocated -> 0.

Hints

1. allocate must return the lowest index where len consecutive cells are all free — think 'first fit', not 'best fit'.
2. Guard len <= 0 and len > n up front: both return -1 with no state change.
3. Because tags can repeat, releasing must free EVERY cell carrying the tag, not just the most recent block — a tag -> segments map makes release O(segments).
4. For O(log n) per op, keep the maximal free intervals in a balanced/ordered structure so you can find the lowest interval of sufficient length, and merge neighbors on release.