Watch 10 video solutions for Design Memory Allocator, a medium level problem involving Array, Hash Table, Design. This walkthrough by Algorithms Casts has 2,256 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
size consecutive free memory units and assign it the id mID.mID.Note that:
mID.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 freeMemory(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", "freeMemory", "allocate", "allocate", "allocate", "freeMemory", "allocate", "freeMemory"] [[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.freeMemory(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.freeMemory(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.freeMemory(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 <= 10001000 calls will be made to allocate and freeMemory.Problem Overview: You need to simulate a memory allocator that manages n memory slots. The allocate(size, mID) operation finds the leftmost contiguous block of free slots of length size and marks them with mID. The free(mID) operation releases all slots assigned to that ID and returns the number of freed cells.
Approach 1: Array-Based Simulation (O(n) allocate, O(n) free)
The simplest design uses a fixed array of size n where each index stores the current mID occupying that memory slot or 0 if the slot is free. For allocate, iterate through the array and look for the first contiguous window of size empty cells. Once found, fill those cells with mID and return the starting index. If no such window exists, return -1. For free(mID), scan the entire array and reset every cell that equals mID back to 0, counting how many slots were released.
This approach works because the constraints allow a straightforward simulation. The main operations are sequential scans and updates, making the logic easy to implement and debug. It fits well with problems tagged under simulation and design, where the goal is to mirror the real-world system behavior directly. Time complexity for both operations is O(n), while space complexity is O(n) for the memory array.
Approach 2: Linked List of Free Blocks (O(k) allocate, O(k) free)
A more structured design keeps track of free memory segments using a linked list of intervals. Each node stores a free block represented by [start, length]. During allocate, traverse the list and pick the first block whose length is at least size. Allocate from its start, shrink the interval, and remove the node if the block becomes empty. To support efficient free operations, maintain a hash table mapping mID to the segments allocated to that ID.
When freeing memory, retrieve all segments associated with mID, insert them back into the free list, and merge adjacent intervals to prevent fragmentation. The complexity depends on the number of tracked blocks k. Allocation and freeing both run in roughly O(k), and the additional storage for the mapping and interval list results in O(n) space overall.
Recommended for interviews: The array-based simulation is usually expected first because it directly models the allocator and demonstrates clear reasoning. After presenting it, discussing the linked list interval design shows deeper system design thinking and awareness of fragmentation and memory management trade‑offs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Array-Based Simulation | O(n) allocate, O(n) free | O(n) | Best for simple implementation and typical interview solutions |
| Linked List Free Block Tracking | O(k) allocate, O(k) free | O(n) | Useful when tracking memory segments and reducing fragmentation |