2502. Design Memory Allocator

MediumDesignArrayHash TableSimulation
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Solution Approach

The implementation of the Allocator leans on a couple of key data structures and algorithms:

  1. 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 the SortedList 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.

  2. DefaultDict: A defaultdict(list) is used to associate each mID with a list of allocated memory unit ranges. The dictionary is keyed by mID 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 the SortedList 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 the allocate method to check for available blocks.
  • It also initializes the defaultdict(list) for tracking the memory blocks allocated to each mID.

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 requested size. The search is performed thanks to the SortedList, where the elements represent the ends of already-allocated blocks.
  • The pairwise helper function is used to iterate through the SortedList in adjacent pairs. This function is not shown in the provided code snippet, but assuming it behaves like itertools.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 the defaultdict under the given mID.
  • 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 given mID from the defaultdict, removes them from the SortedList (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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Example 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 their mID.

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 indices 0, 1, 2 for mID=1.
  • The SortedList updates to [(3, 9)], indicating that only the block from index 3 to 9 is available, and the defaultdict maps mID=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 the SortedList and sees that the current free block (3, 9) is large enough.
  • It allocates indices 3, 4, 5, 6 for mID=2, updates the SortedList to [(7, 9)], and adds [(3, 6)] to the defaultdict for mID=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 the SortedList 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 for mID=1, which is [(0, 2)], and removes this range from the SortedList.
  • The SortedList then is updated to [(0, 2), (7, 9)], indicating that these ranges are now available. The Allocator also removes mID=1 entries from the defaultdict.
  • 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
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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 is O(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 of O(N) where N 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 the allocate method is O(N + log N) simplifying to O(N), as logarithmic factors are dominated by the linear term for large N.

  • free(mID: int) -> int:

    • For each block associated with mID, removing an element from the SortedList has a time complexity of O(log N) where N is the number of elements in the SortedList prior to removal.
    • If there are M blocks to be removed for mID, the time complexity is O(M * log N). Since M can be at most N, the worst-case time complexity is O(N log N).

Space Complexity

  • The space complexity is O(N + M):
    • O(N) for storing memory blocks in the SortedList, where N is the number of allocated blocks.
    • O(M) for storing the mapping of mIDs to memory blocks in the defaultdict, where M is the count of distinct mIDs with allocated blocks. While N denotes the number of individual blocks allocated and M denotes the number of mIDs, in the worst case, each mID could refer to a different block leading to a space complexity of O(2N), which simplifies to O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫