Design a contiguous segment allocator

Q: Design a contiguous segment allocator

This is a Coding & Algorithms interview question from Tesla for Software Engineer roles. View the full question and solution on PracHub.

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

Comments (0)