Best-Fit Memory Pool
Implement a class MemoryPool that hands out blocks of consecutive cells from size cells numbered 0 to size - 1. A free run is a stretch of free cells that cannot be made any longer. Write these methods:
MemoryPool(size)starts with every cell free.alloc(n)looks at the free runs with at leastncells and picks the shortest one, or the lowest-numbered one among equally short runs. It uses the firstncells of that run as a new block and returns the first cell of the block. Returns-1if no free run is long enough.release(start)frees the block whose first cell isstartand returns its length, or returns-1if no block starts atstart.largest_free()returns the length of the longest free run, or0if every cell is used.list_blocks()returns the blocks as[start, length]pairs, sorted by start.
The tests call the methods in sequence and compare every return value. The expected list holds null for the constructor.
Example 1
MemoryPool(10)
alloc(3) returns 0
alloc(2) returns 3
alloc(4) returns 5
release(3) returns 2
alloc(1) returns 9
list_blocks() returns [[0,3],[5,4],[9,1]]
largest_free() returns 2
After the block at 3 is released there are two free runs: cells 3 and 4, and cell 9. A request for one cell takes the shorter run, so it gets cell 9.
Constraints
1 <= size <= 301 <= n <= 300 <= start < size- Each test makes
1to40method calls after the constructor.
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.