2502. Design Memory Allocator Medium

1/**
2 * [2502] Design Memory Allocator
3 *
4 * You are given an integer n representing the size of a 0-indexed memory array. All memory units are initially free.
5 * You have a memory allocator with the following functionalities:
6 * <ol>
7 * 	Allocate a block of size consecutive free memory units and assign it the id mID.
8 * 	Free all memory units with the given id mID.
9 * </ol>
10 * Note that:
11 * 
12 * 	Multiple blocks can be allocated to the same mID.
13 * 	You should free all the memory units with mID, even if they were allocated in different blocks.
14 * 
15 * Implement the Allocator class:
16 * 
17 * 	Allocator(int n) Initializes an Allocator object with a memory array of size n.
18 * 	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.
19 * 	int free(int mID) Free all memory units with the id mID. Return the number of memory units you have freed.
20 * 
21 *  
22 * <strong class="example">Example 1:
23 * 
24 * Input
25 * ["Allocator", "allocate", "allocate", "allocate", "free", "allocate", "allocate", "allocate", "free", "allocate", "free"]
26 * [[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]
27 * Output
28 * [null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]
29 * Explanation
30 * Allocator loc = new Allocator(10); // Initialize a memory array of size 10. All memory units are initially free.
31 * loc.allocate(1, 1); // The leftmost block's first index is 0. The memory array becomes [1,_,_,_,_,_,_,_,_,_]. We return 0.
32 * loc.allocate(1, 2); // The leftmost block's first index is 1. The memory array becomes [1,2,_,_,_,_,_,_,_,_]. We return 1.
33 * loc.allocate(1, 3); // The leftmost block's first index is 2. The memory array becomes [1,2,3,_,_,_,_,_,_,_]. We return 2.
34 * 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.
35 * loc.allocate(3, 4); // The leftmost block's first index is 3. The memory array becomes [1,_,3,4,4,4,_,_,_,_]. We return 3.
36 * 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.
37 * 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.
38 * 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.
39 * loc.allocate(10, 2); // We can not find any free block with 10 consecutive free memory units, so we return -1.
40 * 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.
41 * 
42 *  
43 * Constraints:
44 * 
45 * 	1 <= n, size, mID <= 1000
46 * 	At most 1000 calls will be made to allocate and free.
47 * 
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/design-memory-allocator/
52// discuss: https://leetcode.com/problems/design-memory-allocator/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55
56struct Allocator {
57        false
58    }
59
60
61/** 
62 * `&self` means the method takes an immutable reference.
63 * If you need a mutable reference, change it to `&mut self` instead.
64 */
65impl Allocator {
66
67    fn new(n: i32) -> Self {
68        
69    }
70    
71    fn allocate(&self, size: i32, m_id: i32) -> i32 {
72        
73    }
74    
75    fn free(&self, m_id: i32) -> i32 {
76        
77    }
78}
79
80/**
81 * Your Allocator object will be instantiated and called as such:
82 * let obj = Allocator::new(n);
83 * let ret_1: i32 = obj.allocate(size, mID);
84 * let ret_2: i32 = obj.free(mID);
85 */
86
87// submission codes end
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92
93    #[test]
94    fn test_2502() {
95    }
96}
97