Katkat
Back

Design a contiguous segment allocator

TeslaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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. 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.