Welcome to Subscribe On Youtube

2502. Design Memory Allocator

Description

You are given an integer n representing the size of a 0-indexed memory array. All memory units are initially free.

You have a memory allocator with the following functionalities:

  1. Allocate a block of size consecutive free memory units and assign it the id mID.
  2. Free all memory units with the given id mID.

Note that:

  • Multiple blocks can be allocated to the same mID.
  • You should free all the memory units with mID, even if they were allocated in different blocks.

Implement the Allocator class:

  • Allocator(int n) Initializes an Allocator object with a memory array of size n.
  • int allocate(int size, int mID) Find the leftmost block of size consecutive free memory units and allocate it with the id mID. Return the block's first index. If such a block does not exist, return -1.
  • int free(int mID) Free all memory units with the id mID. Return the number of memory units you have freed.

 

Example 1:

 Input ["Allocator", "allocate", "allocate", "allocate", "free", "allocate", "allocate", "allocate", "free", "allocate", "free"] [[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] 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.free(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.free(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.free(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.

 

Constraints:

  • 1 <= n, size, mID <= 1000
  • At most 1000 calls will be made to allocate and free.

Solutions

  • class Allocator { private int[] m; public Allocator(int n) { m = new int[n]; } public int allocate(int size, int mID) { int cnt = 0; for (int i = 0; i < m.length; ++i) { if (m[i] > 0) { cnt = 0; } else if (++cnt == size) { Arrays.fill(m, i - size + 1, i + 1, mID); return i - size + 1; } } return -1; } public int free(int mID) { int ans = 0; for (int i = 0; i < m.length; ++i) { if (m[i] == mID) { m[i] = 0; ++ans; } } return ans; } } /** * Your Allocator object will be instantiated and called as such: * Allocator obj = new Allocator(n); * int param_1 = obj.allocate(size,mID); * int param_2 = obj.free(mID); */ 
  • class Allocator { public: Allocator(int n) { m = vector<int>(n); } int allocate(int size, int mID) { int cnt = 0; for (int i = 0; i < m.size(); ++i) { if (m[i]) { cnt = 0; } else if (++cnt == size) { fill(i - size + 1, i + 1, mID); return i - size + 1; } } return -1; } int free(int mID) { int ans = 0; for (int i = 0; i < m.size(); ++i) { if (m[i] == mID) { m[i] = 0; ++ans; } } return ans; } private: vector<int> m; void fill(int from, int to, int val) { for (int i = from; i < to; ++i) { m[i] = val; } } }; /** * Your Allocator object will be instantiated and called as such: * Allocator* obj = new Allocator(n); * int param_1 = obj->allocate(size,mID); * int param_2 = obj->free(mID); */ 
  • class Allocator: def __init__(self, n: int): self.m = [0] * n def allocate(self, size: int, mID: int) -> int: cnt = 0 for i, v in enumerate(self.m): if v: cnt = 0 else: cnt += 1 if cnt == size: self.m[i - size + 1 : i + 1] = [mID] * size return i - size + 1 return -1 def free(self, mID: int) -> int: ans = 0 for i, v in enumerate(self.m): if v == mID: self.m[i] = 0 ans += 1 return ans # Your Allocator object will be instantiated and called as such: # obj = Allocator(n) # param_1 = obj.allocate(size,mID) # param_2 = obj.free(mID)  
  • type Allocator struct { m []int } func Constructor(n int) Allocator { return Allocator{make([]int, n)} } func (this *Allocator) Allocate(size int, mID int) int { cnt := 0 for i, v := range this.m { if v > 0 { cnt = 0 } else { cnt++ if cnt == size { for j := i - size + 1; j <= i; j++ { this.m[j] = mID } return i - size + 1 } } } return -1 } func (this *Allocator) Free(mID int) (ans int) { for i, v := range this.m { if v == mID { this.m[i] = 0 ans++ } } return } /** * Your Allocator object will be instantiated and called as such: * obj := Constructor(n); * param_1 := obj.Allocate(size,mID); * param_2 := obj.Free(mID); */ 
  • class Allocator { private m: number[]; constructor(n: number) { this.m = Array(n).fill(0); } allocate(size: number, mID: number): number { let cnt = 0; for (let i = 0; i < this.m.length; i++) { if (this.m[i] > 0) { cnt = 0; } else if (++cnt === size) { for (let j = i - size + 1; j <= i; j++) { this.m[j] = mID; } return i - size + 1; } } return -1; } freeMemory(mID: number): number { let ans = 0; for (let i = 0; i < this.m.length; i++) { if (this.m[i] === mID) { this.m[i] = 0; ans++; } } return ans; } } /** * Your Allocator object will be instantiated and called as such: * var obj = new Allocator(n) * var param_1 = obj.allocate(size,mID) * var param_2 = obj.freeMemory(mID) */

All Problems

All Solutions