Design a contiguous segment allocator
Company: Tesla
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: This question evaluates a candidate's competency in designing and implementing efficient data structures for interval management, contiguous memory allocation, fragmentation handling, tag-based resource tracking, and algorithmic complexity analysis.
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
Input: (10, [["allocate", 3, "a"], ["allocate", 2, "b"], ["release", "a"], ["allocate", 4, "c"], ["allocate", 3, "d"]])
Expected 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.
Input: (5, [["allocate", 6, "x"], ["allocate", 0, "y"], ["allocate", 5, "z"], ["allocate", 1, "w"], ["release", "missing"]])
Expected 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
- allocate must return the lowest index where `len` consecutive cells are all free — think 'first fit', not 'best fit'.
- Guard len <= 0 and len > n up front: both return -1 with no state change.
- 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).
- 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.