How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Tesla.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Tesla during technical interviews.

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.

Input: (8, [["allocate", 2, "t"], ["allocate", 2, "t"], ["release", "t"]])

Expected Output: [0, 2, 4]

Explanation: Repeated tag: first t -> [0,1] (index 0), second t -> [2,3] (index 2). release t frees all 4 cells carrying 't'.

Input: (4, [["allocate", 2, "a"], ["allocate", 1, "b"], ["allocate", 1, "c"], ["release", "b"], ["allocate", 1, "d"]])

Expected Output: [0, 2, 3, 1, 2]

Explanation: a=[0,1], b=[2], c=[3]. release b frees 1 cell (index 2). allocate 1 'd' takes the now-free lowest cell -> index 2.

Input: (0, [["allocate", 1, "a"], ["release", "a"]])

Expected Output: [-1, 0]

Explanation: Empty array (n=0): any allocate of positive length has len > n -> -1. release of absent tag -> 0.

Input: (6, [["allocate", 6, "full"], ["allocate", 1, "x"], ["release", "full"], ["allocate", 6, "again"]])

Expected Output: [0, -1, 6, 0]

Explanation: full occupies all 6 cells -> 0. x can't fit -> -1. release full frees all 6. allocate 6 'again' now fits the whole array -> 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.

Quick Overview

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.