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:
Allocate a block of size consecutive free memory units and assign it the id mID.
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 sizeconsecutive 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
Solution 1: Brute Force Simulation
The data range of the problem is not large, so we can directly use an array to simulate the memory space.
During initialization, set each element in the array to $0$, indicating it's free.
When the allocate method is called, traverse the array, find size consecutive free memory units, set them to mID, and return the first index.
When the free method is called, traverse the array, set all memory units equal to mID to $0$, indicating they are free.
The time complexity is $O(n \times q)$, and the space complexity is $O(n)$, where $n$ and $q$ are the size of the memory space and the number of method calls, respectively.
classAllocator:def__init__(self,n:int):self.m=[0]*ndefallocate(self,size:int,mID:int)->int:cnt=0fori,vinenumerate(self.m):ifv:cnt=0else:cnt+=1ifcnt==size:self.m[i-size+1:i+1]=[mID]*sizereturni-size+1return-1deffree(self,mID:int)->int:ans=0fori,vinenumerate(self.m):ifv==mID:self.m[i]=0ans+=1returnans# Your Allocator object will be instantiated and called as such:# obj = Allocator(n)# param_1 = obj.allocate(size,mID)# param_2 = obj.free(mID)
classAllocator{privateint[]m;publicAllocator(intn){m=newint[n];}publicintallocate(intsize,intmID){intcnt=0;for(inti=0;i<m.length;++i){if(m[i]>0){cnt=0;}elseif(++cnt==size){Arrays.fill(m,i-size+1,i+1,mID);returni-size+1;}}return-1;}publicintfree(intmID){intans=0;for(inti=0;i<m.length;++i){if(m[i]==mID){m[i]=0;++ans;}}returnans;}}/** * 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); */
classAllocator{public:Allocator(intn){m=vector<int>(n);}intallocate(intsize,intmID){intcnt=0;for(inti=0;i<m.size();++i){if(m[i]){cnt=0;}elseif(++cnt==size){fill(i-size+1,i+1,mID);returni-size+1;}}return-1;}intfree(intmID){intans=0;for(inti=0;i<m.size();++i){if(m[i]==mID){m[i]=0;++ans;}}returnans;}private:vector<int>m;voidfill(intfrom,intto,intval){for(inti=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); */
typeAllocatorstruct{m[]int}funcConstructor(nint)Allocator{returnAllocator{make([]int,n)}}func(this*Allocator)Allocate(sizeint,mIDint)int{cnt:=0fori,v:=rangethis.m{ifv>0{cnt=0}else{cnt++ifcnt==size{forj:=i-size+1;j<=i;j++{this.m[j]=mID}returni-size+1}}}return-1}func(this*Allocator)Free(mIDint)(ansint){fori,v:=rangethis.m{ifv==mID{this.m[i]=0ans++}}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); */
Solution 2: Hash Table + Ordered Set
We can use an ordered set to maintain the start and end indices of all allocated memory units, where the start index is the key and the end index is the value. Additionally, we use a hash table to maintain the mID and its corresponding start index of the memory unit.
When the allocate method is called, we traverse the ordered set, find the first free interval with a length greater than or equal to size, allocate it to mID, and update the ordered set. Then we add the mID and its corresponding start index of the memory unit to the hash table.
When the free method is called, we find the start index of the memory unit corresponding to mID from the hash table, then delete it from the ordered set, and then delete mID from the hash table.
The time complexity is $O(q \log n)$, and the space complexity is $O(n)$, where $n$ and $q$ are the size of the memory space and the number of method calls, respectively.
fromsortedcontainersimportSortedListclassAllocator:def__init__(self,n:int):self.sl=SortedList([(-1,-1),(n,n)])self.d=defaultdict(list)defallocate(self,size:int,mID:int)->int:for(_,s),(e,_)inpairwise(self.sl):s,e=s+1,e-1ife-s+1>=size:self.sl.add((s,s+size-1))self.d[mID].append((s,s+size-1))returnsreturn-1deffree(self,mID:int)->int:ans=0forblockinself.d[mID]:self.sl.remove(block)ans+=block[1]-block[0]+1delself.d[mID]returnans# Your Allocator object will be instantiated and called as such:# obj = Allocator(n)# param_1 = obj.allocate(size,mID)# param_2 = obj.free(mID)
classAllocator{privateTreeMap<Integer,Integer>tm=newTreeMap<>();privateMap<Integer,List<Integer>>d=newHashMap<>();publicAllocator(intn){tm.put(-1,-1);tm.put(n,n);}publicintallocate(intsize,intmID){ints=-1;for(varentry:tm.entrySet()){intv=entry.getKey();if(s!=-1){inte=v-1;if(e-s+1>=size){tm.put(s,s+size-1);d.computeIfAbsent(mID,k->newArrayList<>()).add(s);returns;}}s=entry.getValue()+1;}return-1;}publicintfree(intmID){intans=0;for(ints:d.getOrDefault(mID,Collections.emptyList())){inte=tm.remove(s);ans+=e-s+1;}d.remove(mID);returnans;}}/** * 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); */
classAllocator{public:Allocator(intn){tm[-1]=-1;tm[n]=n;}intallocate(intsize,intmID){ints=-1;for(auto&[v,c]:tm){if(s!=-1){inte=v-1;if(e-s+1>=size){tm[s]=s+size-1;d[mID].emplace_back(s);returns;}}s=c+1;}return-1;}intfree(intmID){intans=0;for(int&s:d[mID]){inte=tm[s];tm.erase(s);ans+=e-s+1;}d.erase(mID);returnans;}private:map<int,int>tm;unordered_map<int,vector<int>>d;};/** * 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); */
typeAllocatorstruct{rbt*redblacktree.Treedmap[int][]int}funcConstructor(nint)Allocator{rbt:=redblacktree.NewWithIntComparator()rbt.Put(-1,-1)rbt.Put(n,n)returnAllocator{rbt,map[int][]int{}}}func(this*Allocator)Allocate(sizeint,mIDint)int{s:=-1it:=this.rbt.Iterator()forit.Next(){v:=it.Key().(int)ifs!=-1{e:=v-1ife-s+1>=size{this.rbt.Put(s,s+size-1)this.d[mID]=append(this.d[mID],s)returns}}s=it.Value().(int)+1}return-1}func(this*Allocator)Free(mIDint)int{ans:=0for_,s:=rangethis.d[mID]{ife,ok:=this.rbt.Get(s);ok{this.rbt.Remove(s)ans+=e.(int)-s+1}}this.d[mID]=[]int{}returnans}/** * Your Allocator object will be instantiated and called as such: * obj := Constructor(n); * param_1 := obj.Allocate(size,mID); * param_2 := obj.Free(mID); */