2502. Design Memory Allocator
Problem Description
The problem defines an Allocator for managing a block of memory indexed from 0. The memory space is represented as an array with a given size n
. The Allocator has two main functionalities: allocate and free. The allocate function has to find a contiguous block of memory of a requested size and mark it with an mID
. The free function is responsible for releasing all memory units associated with an mID
.
When allocating, it is important to find the leftmost block that fits the requirement to keep the solution efficient and fair (by using memory units in order). Also, if a block cannot be found because the memory is too fragmented or there isn't enough free space, the allocate function should return -1
.
When freeing memory, every block with the given mID
is released, even if the blocks were allocated at different times. The function should return the number of memory units that were freed.
Intuition
To keep track of the free memory units, a sorted list can be quite efficient. It allows us to quickly find consecutive free blocks by keeping the start and end indices of these blocks and sorting them. This makes it easy to find blocks that are big enough for the allocation and also allows us to add new blocks when releasing memory.
For the solution provided, the allocator uses a sorted list (self.sl
) that initially contains the entire memory as one large block. When allocating memory, we look for a gap between blocks that is large enough to fit the requested size; if found, we register the block in the sorted list and map its mID
to the newly allocated block in a dictionary that keeps all blocks per mID
. While freeing memory, we simply look up all blocks with a given mID
, remove them from the sorted list, and count the freed memory units to return the result. The use of the SortedList
from the sortedcontainers
package ensures efficient operations necessary for this purpose.
The intuition behind using a defaultdict(list)
is to map each mID
to a list of tuples representing the allocated blocks, allowing for easy freeing and tracking of all allocated blocks with the same mID
.
Additionally, the clever use of paired indices when iterating through potential free spaces with the pairwise
function simplifies the evaluation of blocks for allocation.
Solution Approach
The implementation of the Allocator leans on a couple of key data structures and algorithms:
-
SortedList: This data structure from
sortedcontainers
module maintains a sorted sequence of elements, which allows for fast insertion, deletion, and look-up operations. For our allocator, each element in theSortedList
represents a range of memory units in the form of a tuple(start_index, end_index)
. These elements denote the currently allocated blocks of memory. -
DefaultDict: A
defaultdict(list)
is used to associate eachmID
with a list of allocated memory unit ranges. The dictionary is keyed bymID
and the values are lists of tuples, with each tuple representing an allocated block.
The algorithms used in the implementation are detailed as follows:
Allocator Initialization
- The constructor method
__init__
initializes theSortedList
with a pair of sentinel values to represent the ends of the memory that are never allocated. These sentinels help simplify the logic needed in theallocate
method to check for available blocks. - It also initializes the
defaultdict(list)
for tracking the memory blocks allocated to eachmID
.
Allocating Memory
- In the
allocate
method, the memory is allocated by searching for a gap between two consecutive allocated blocks that is large enough to accommodate the requestedsize
. The search is performed thanks to theSortedList
, where the elements represent the ends of already-allocated blocks. - The
pairwise
helper function is used to iterate through theSortedList
in adjacent pairs. This function is not shown in the provided code snippet, but assuming it behaves likeitertools.pairwise
, it yields consecutive overlapping pairs of elements from the input. - The search starts from the leftmost block to find the first fit for the required size. When the spot is found, a tuple representing the new block range
(start, end)
is added to the sorted list and thedefaultdict
under the givenmID
. - If the suitable block is found, the starting index of the allocated block is returned. If no block can fit the request,
-1
is returned.
Freeing Memory
- The
free
method retrieves all the blocks associated with the givenmID
from thedefaultdict
, removes them from theSortedList
(thereby de-allocating them), and then calculates the total number of memory units freed. - After dealing with the blocks, it deletes the entry for the
mID
from the dictionary since all its associated blocks have been freed. - It returns the count of memory units that were freed.
The Allocator thereby allows for efficient allocation and deallocation of memory units while keeping a simple interface for the user of the class.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Consider an Allocator managing an array of 10 memory units indexed from 0 to 9. Following the solution approach, we'll look at how the Allocator would work with the allocate and free functions.
Allocator Initialization
- First, the Allocator is initialized with a
SortedList
containing[(0, 9)]
, representing the entire free memory range from index 0 to 9. - A
defaultdict(list)
is also initialized to keep track of the memory blocks allocated via theirmID
.
Allocating Memory
- Imagine we want to allocate a block of 3 units for the memory ID
mID=1
. The Allocator's allocate method seeks the first fitting spot from the left. - The allocate method finds that
(0, 9)
is a large enough block. It reserves indices0, 1, 2
formID=1
. - The
SortedList
updates to[(3, 9)]
, indicating that only the block from index 3 to 9 is available, and thedefaultdict
mapsmID=1
to the list[(0, 2)]
. - The Allocator returns the starting index
0
.
Allocating More Memory
- Another allocate request arrives for 4 units for a new
mID=2
. The Allocator checks theSortedList
and sees that the current free block(3, 9)
is large enough. - It allocates indices
3, 4, 5, 6
formID=2
, updates theSortedList
to[(7, 9)]
, and adds[(3, 6)]
to thedefaultdict
formID=2
. - The starting index
3
is returned as the result of the allocation.
Attempting Further Allocation
- A request is made to allocate 5 units for
mID=3
. The Allocator checks theSortedList
and realizes there's only a block of 3 units free(7, 9)
, which is not enough. - The Allocator returns
-1
to indicate the allocation request cannot be met.
Freeing Memory
- To free the memory allocated for
mID=1
, the free method is called. - It retrieves the blocks from the
defaultdict
formID=1
, which is[(0, 2)]
, and removes this range from theSortedList
. - The
SortedList
then is updated to[(0, 2), (7, 9)]
, indicating that these ranges are now available. The Allocator also removesmID=1
entries from thedefaultdict
. - It returns
3
as the number of units freed.
The example illustrates the Allocator efficiently managing the memory space, allocating and freeing memory as per the requests using the data structures and algorithms described.
Solution Implementation
1from sortedcontainers import SortedList
2from collections import defaultdict
3from itertools import pairwise
4
5class Allocator:
6 def __init__(self, n: int):
7 # Initialize a sorted list with two sentinel nodes to manage memory allocation.
8 # These represent the start and end bounds of the memory.
9 self.sorted_list = SortedList([(-1, -1), (n, n)])
10 # A dictionary to keep track of allocated blocks by memory ID (mID).
11 self.allocations = defaultdict(list)
12
13 def allocate(self, size: int, mID: int) -> int:
14 # Iterate over gaps between allocated blocks to find a suitable spot.
15 for (_, start), (end, _) in pairwise(self.sorted_list):
16 # Adjust the start and end pointers taking into account the exclusive end points.
17 start, end = start + 1, end - 1
18 if end - start + 1 >= size: # Check if the gap is big enough.
19 # If there's sufficient space, allocate the memory and add it to the sorted list.
20 self.sorted_list.add((start, start + size - 1))
21 # Record the allocation with its corresponding mID.
22 self.allocations[mID].append((start, start + size - 1))
23 return start # Return the starting address.
24 return -1 # If no suitable space is found, return -1.
25
26 def free(self, mID: int) -> int:
27 # This method frees the allocated memory linked to a specific memory ID.
28 total_freed = 0 # Initialize the total memory freed count.
29 # Remove each block allocated to the mID from the sorted list.
30 for block in self.allocations[mID]:
31 self.sorted_list.remove(block)
32 total_freed += block[1] - block[0] + 1 # Calculate the size of the freed block.
33 # Remove all records of the mID from the allocations dictionary.
34 del self.allocations[mID]
35 return total_freed # Return the total amount of memory freed.
36
37# Example usage:
38# obj = Allocator(n)
39# param_1 = obj.allocate(size, mID)
40# param_2 = obj.free(mID)
41
1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.HashMap;
4import java.util.List;
5import java.util.Map;
6import java.util.TreeMap;
7
8class Allocator {
9 // TreeMap to keep track of allocated and free segments with key as start and value as end of segment
10 private TreeMap<Integer, Integer> segmentsTreeMap = new TreeMap<>();
11
12 // HashMap where key is the memory ID and value is a list of starting addresses of allocated segments
13 private Map<Integer, List<Integer>> allocations = new HashMap<>();
14
15 // Constructor to initialize the Allocator with given memory size
16 public Allocator(int memorySize) {
17 // Setting the initial boundaries of the free memory
18 // -1 is a sentinel value to handle the start of memory
19 segmentsTreeMap.put(-1, -1);
20 // 'n' is the end boundary and is considered free
21 segmentsTreeMap.put(memorySize, memorySize);
22 }
23
24 // Method to allocate memory of a certain size for a given memory ID
25 public int allocate(int size, int memoryID) {
26 int start = -1;
27 // Iterate through the TreeMap to find a free segment of required size
28 for (var entry : segmentsTreeMap.entrySet()) {
29 int value = entry.getKey();
30 if (start != -1) {
31 // End of the current free segment
32 int end = value - 1;
33 // Check if the segment is large enough
34 if (end - start + 1 >= size) {
35 // Allocate the segment and update TreeMap
36 segmentsTreeMap.put(start, start + size - 1);
37 // Record the allocation against the memory ID
38 allocations.computeIfAbsent(memoryID, k -> new ArrayList<>()).add(start);
39 return start; // Return the start address of the allocated segment
40 }
41 }
42 // Move to the start of the next segment
43 start = entry.getValue() + 1;
44 }
45 return -1; // Allocation failed: no segment large enough
46 }
47
48 // Method to free the memory associated with a given memory ID
49 public int free(int memoryID) {
50 int totalFreed = 0;
51 // Retrieve the list of allocated segments for given memory ID
52 List<Integer> segmentsToFree = allocations.getOrDefault(memoryID, Collections.emptyList());
53 for (int start : segmentsToFree) {
54 // Remove the segment from TreeMap and get its end
55 int end = segmentsTreeMap.remove(start);
56 // Increase the total freed memory size
57 totalFreed += end - start + 1;
58 }
59 // Remove the record of the allocations for this memory ID
60 allocations.remove(memoryID);
61 return totalFreed; // Return the total amount of memory freed
62 }
63}
64
65/**
66 * Usage of Allocator class:
67 * Allocator allocator = new Allocator(memorySize);
68 * int allocationAddress = allocator.allocate(size, memoryID);
69 * int freedMemorySize = allocator.free(memoryID);
70 */
71
1#include <map>
2#include <unordered_map>
3#include <vector>
4
5class Allocator {
6public:
7 // Constructor initializes the memory allocation tree with boundaries
8 Allocator(int n) {
9 memoryTree[-1] = -1; // Set start boundary
10 memoryTree[n] = n; // Set end boundary
11 }
12
13 // Allocates a block of memory of given size, associated with a mID, and returns
14 // the start index of the allocated block. Returns -1 if allocation is not possible.
15 int allocate(int size, int mID) {
16 int start = -1; // Starting index for allocation
17
18 // Iterate over the memory blocks (end_points , start_points)
19 for (auto& [endPoint, startPoint] : memoryTree) {
20 if (start != -1) {
21 // If there is a previous block, calculate the potential end of the new block
22 int potentialEnd = endPoint - 1;
23 // Check if the block is large enough for the requested size
24 if (potentialEnd - start + 1 >= size) {
25 // Set the end of the new block in the tree
26 memoryTree[start] = start + size - 1;
27 // Record the allocation start point associated with mID
28 allocations[mID].emplace_back(start);
29 // Return the starting index of allocated block
30 return start;
31 }
32 }
33 // Update start to be the next possible index after current block
34 start = startPoint + 1;
35 }
36 // If no suitable block found, return -1
37 return -1;
38 }
39
40 // Frees all blocks of memory associated with a mID, returns total size of freed memory
41 int free(int mID) {
42 int totalFreedSize = 0; // Counter for total freed memory size
43
44 // Iterate over all start points of blocks associated with mID
45 for (int& start : allocations[mID]) {
46 int end = memoryTree[start]; // Fetch the corresponding end point
47 // Calculate size of the current block to increment the total freed size
48 totalFreedSize += end - start + 1;
49 // Remove the block from the memory allocation tree
50 memoryTree.erase(start);
51 }
52 // Remove mID from the allocation record
53 allocations.erase(mID);
54
55 // Return the total size of all freed blocks
56 return totalFreedSize;
57 }
58
59private:
60 // Map to track start and end points of allocated memory blocks
61 std::map<int, int> memoryTree;
62 // Unordered map to track allocations by mID, containing the start indexes of blocks
63 std::unordered_map<int, std::vector<int>> allocations;
64};
65
66/**
67 * Your Allocator object will be instantiated and called as such:
68 * Allocator* obj = new Allocator(n);
69 * int param_1 = obj->allocate(size, mID);
70 * int param_2 = obj->free(mID);
71 */
72
1interface MemoryBlock {
2 [endpoint: number]: number;
3}
4
5interface AllocationRecord {
6 [mID: number]: number[];
7}
8
9// Create memoryTree as a global variable to track start and end points of allocated memory blocks
10let memoryTree: MemoryBlock = {};
11
12// Create allocations as a global variable to record allocations by mID
13let allocations: AllocationRecord = {};
14
15// Initialize the memory allocation tree with boundaries
16function initializeAllocator(n: number): void {
17 memoryTree[-1] = -1; // Set start boundary
18 memoryTree[n] = n; // Set end boundary
19}
20
21// Allocates a block of memory of given size and returns the start index of the allocated block.
22// Returns -1 if allocation is not possible.
23function allocate(size: number, mID: number): number {
24 let start: number = -1; // Starting index for allocation
25
26 // Iterate over the memory blocks (end points, start points)
27 for (let endPoint in memoryTree) {
28 let startPoint = memoryTree[endPoint];
29 if (start !== -1) {
30 // If there is a previous block, calculate the potential end of the new block
31 let potentialEnd = parseInt(endPoint) - 1;
32 // Check if the block is large enough for the requested size
33 if (potentialEnd - start + 1 >= size) {
34 // Set the end of the new block in the tree
35 memoryTree[start] = start + size - 1;
36 // Record the allocation start point associated with mID
37 if (!allocations[mID]) allocations[mID] = [];
38 allocations[mID].push(start);
39 // Return the starting index of allocated block
40 return start;
41 }
42 }
43 // Update start to be the next possible index after current block
44 start = startPoint + 1;
45 }
46 // If no suitable block found, return -1
47 return -1;
48}
49
50// Frees all blocks of memory associated with a mID, returns total size of freed memory.
51function free(mID: number): number {
52 let totalFreedSize: number = 0; // Counter for total freed memory size
53
54 // Check if there are allocations for the given mID
55 if (allocations[mID]) {
56 // Iterate over all start points of blocks associated with mID
57 for (let start of allocations[mID]) {
58 let end = memoryTree[start]; // Fetch the corresponding end point
59 // Calculate size of the current block to increment the total freed size
60 totalFreedSize += end - start + 1;
61 // Remove the block from the memory allocation tree
62 delete memoryTree[start];
63 }
64 // Remove mID from the allocation record
65 delete allocations[mID];
66 }
67
68 // Return the total size of all freed blocks
69 return totalFreedSize;
70}
71
Time and Space Complexity
The provided code defines an Allocator class which handles memory allocation with methods for allocating and freeing memory blocks based on their size and an associated mID (memory ID). It uses a SortedList data structure from the sortedcontainers
module, which maintains a sorted list of memory blocks. A defaultdict
is used to keep track of memory blocks allocated to specific mIDs.
Time Complexity
The time complexity of each method is as follows:
-
__init__(n: int)
: The initialization of the Allocator class isO(1)
because it involves initializing a SortedList with two elements and a defaultdict which are both constant time operations. -
allocate(size: int, mID: int) -> int
:- Iterating through pairs of elements in the SortedList
self.sl
to find a suitable block has a worst-case time complexity ofO(N)
whereN
is the number of elements in the SortedList. - Inserting an element into the SortedList has a time complexity of
O(log N)
because the list needs to maintain its sorted order. This is typically done with a binary search followed by insertion. Therefore, the time complexity of theallocate
method isO(N + log N)
simplifying toO(N)
, as logarithmic factors are dominated by the linear term for largeN
.
- Iterating through pairs of elements in the SortedList
-
free(mID: int) -> int
:- For each block associated with
mID
, removing an element from the SortedList has a time complexity ofO(log N)
whereN
is the number of elements in the SortedList prior to removal. - If there are
M
blocks to be removed formID
, the time complexity isO(M * log N)
. SinceM
can be at mostN
, the worst-case time complexity isO(N log N)
.
- For each block associated with
Space Complexity
- The space complexity is
O(N + M)
:O(N)
for storing memory blocks in the SortedList, whereN
is the number of allocated blocks.O(M)
for storing the mapping of mIDs to memory blocks in thedefaultdict
, whereM
is the count of distinct mIDs with allocated blocks. WhileN
denotes the number of individual blocks allocated andM
denotes the number of mIDs, in the worst case, eachmID
could refer to a different block leading to a space complexity ofO(2N)
, which simplifies toO(N)
.
In summary, the time complexity of the allocate
method is O(N)
, and the time complexity of the free
method is O(N log N)
. The space complexity of the entire Allocator class is O(N)
assuming a worst-case scenario where each memory block is associated with a unique mID.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement recursion?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.