Design a contiguous segment allocator

Q: Design a contiguous segment allocator

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

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

Overview

Comments (0)