#2502

Design Memory Allocator

specialist · 900 · lc medium +31 · 49.7% accepted · 358 likes · top 37%

Description

Design an Allocator class to manage a 0-indexed memory array of size n (initially all free):

- Allocator(int n) — initializes the memory array.

- int allocate(int size, int mID) — finds the leftmost run of size consecutive free units, marks them with id mID, and returns the starting index. Returns -1 if no such run exists. Multiple blocks may share the same mID.

- int freeMemory(int mID) — releases all units tagged mID and returns the count freed.

Example 1:

Input

["Allocator", "allocate", "allocate", "allocate", "freeMemory", "allocate", "allocate", "allocate", "freeMemory", "allocate", "freeMemory"]

[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]

Output

[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

Example 2:

Explanation

Allocator loc = new Allocator(10); // Initialize a memory array of size 10. All memory units are initially free.

loc.allocate(1, 1); // The leftmost block's first index is 0. The memory array becomes [1,_,_,_,_,_,_,_,_,_]. We return 0.

loc.allocate(1, 2); // The leftmost block's first index is 1. The memory array becomes [1,2,_,_,_,_,_,_,_,_]. We return 1.

loc.allocate(1, 3); // The leftmost block's first index is 2. The memory array becomes [1,2,3,_,_,_,_,_,_,_]. We return 2.

loc.freeMemory(2); // Free all memory units with mID 2. The memory array becomes [1,_, 3,_,_,_,_,_,_,_]. We return 1 since there is only 1 unit with mID 2.

loc.allocate(3, 4); // The leftmost block's first index is 3. The memory array becomes [1,_,3,4,4,4,_,_,_,_]. We return 3.

loc.allocate(1, 1); // The leftmost block's first index is 1. The memory array becomes [1,1,3,4,4,4,_,_,_,_]. We return 1.

loc.allocate(1, 1); // The leftmost block's first index is 6. The memory array becomes [1,1,3,4,4,4,1,_,_,_]. We return 6.

loc.freeMemory(1); // Free all memory units with mID 1. The memory array becomes [_,_,3,4,4,4,_,_,_,_]. We return 3 since there are 3 units with mID 1.

loc.allocate(10, 2); // We can not find any free block with 10 consecutive free memory units, so we return -1.

loc.freeMemory(7); // Free all memory units with mID 7. The memory array remains the same since there is no memory unit with mID 7. We return 0.

Code

class Allocator:

    def __init__(self, n: int):
        

    def allocate(self, size: int, mID: int) -> int:
        

    def freeMemory(self, mID: int) -> int:
        


# Your Allocator object will be instantiated and called as such:
# obj = Allocator(n)
# param_1 = obj.allocate(size,mID)
# param_2 = obj.freeMemory(mID)

class Allocator:

    def __init__(self, n: int):
        

    def allocate(self, size: int, mID: int) -> int:
        

    def freeMemory(self, mID: int) -> int:
        


# Your Allocator object will be instantiated and called as such:
# obj = Allocator(n)
# param_1 = obj.allocate(size,mID)
# param_2 = obj.freeMemory(mID)