Scale Engineer

Design Memory Allocator

Med
#2283Time: - **`allocate(size, mID)`**: O(n * size). In the worst-case scenario (e.g., memory is `[1, 0, 1, 0, ...]` and we search for `size=2`), the outer loop iterates up to `n` times, and the inner loop runs `size` times for each outer iteration. - **`freeMemory(mID)`**: O(n). We must scan the entire memory array to find all units associated with the given `mID`.Space: O(n) - We only need an array of size `n` to store the state of the memory.5 companies
Patterns
Design
Data structures
ArrayHash Table
Companies
ByteDanceQualcommRubrikTwo Sigma

Prompt

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:

  1. Allocate a block of size consecutive free memory units and assign it the id mID.
  2. 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 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 <= 1000
  • At most 1000 calls will be made to allocate and freeMemory.

Approaches

3 approaches with complexity analysis and trade-offs.

This is the most straightforward brute-force approach. It uses an array to represent memory and performs linear scans for both allocation and freeing. Allocation involves a nested loop to find a contiguous free block, which is inefficient.

Algorithm

  • Allocator(n):
    1. Initialize an integer array memory of size n with all zeros.
  • allocate(size, mID):
    1. Iterate with an index i from 0 to n - size.
    2. For each i, assume a block is found (isBlockFree = true).
    3. Start a nested loop with an index j from i to i + size - 1.
    4. If memory[j] is not 0, set isBlockFree = false and break the inner loop.
    5. If the inner loop completes and isBlockFree is still true: a. Fill memory[i] to memory[i + size - 1] with mID. b. Return i.
    6. If the outer loop completes without finding a suitable block, return -1.
  • freeMemory(mID):
    1. Initialize freedCount = 0.
    2. Iterate with an index i from 0 to n - 1.
    3. If memory[i] == mID: a. Set memory[i] = 0. b. Increment freedCount.
    4. Return freedCount.

Walkthrough

A simple integer array memory of size n is used. A value of 0 indicates a free unit, while a non-zero value represents the mID of the occupying block.

  • allocate(size, mID): To find the leftmost free block, we iterate from the first possible start index i = 0 up to n - size. For each i, a second loop checks if the block of memory from i to i + size - 1 is entirely free. If it is, we've found our spot. We then fill this block with the given mID and return the start index i. If the outer loop finishes without success, it means no suitable block exists, and we return -1.

  • freeMemory(mID): This operation requires a full scan of the memory array. We iterate from 0 to n-1, and for each unit memory[i] that matches the mID, we reset it to 0 and count it. The total count of freed units is returned.

class Allocator {    private int[] memory;    private int n;     public Allocator(int n) {        this.n = n;        this.memory = new int[n];    }     public int allocate(int size, int mID) {        for (int i = 0; i <= n - size; i++) {            boolean isFree = true;            for (int j = 0; j < size; j++) {                if (memory[i + j] != 0) {                    isFree = false;                    i = i + j; // Optimization to jump past the occupied block                    break;                }            }            if (isFree) {                for (int j = i; j < i + size; j++) {                    memory[j] = mID;                }                return i;            }        }        return -1;    }     public int freeMemory(int mID) {        int freedCount = 0;        for (int i = 0; i < n; i++) {            if (memory[i] == mID) {                memory[i] = 0;                freedCount++;            }        }        return freedCount;    }}

Complexity

Time

- **`allocate(size, mID)`**: O(n * size). In the worst-case scenario (e.g., memory is `[1, 0, 1, 0, ...]` and we search for `size=2`), the outer loop iterates up to `n` times, and the inner loop runs `size` times for each outer iteration. - **`freeMemory(mID)`**: O(n). We must scan the entire memory array to find all units associated with the given `mID`.

Space

O(n) - We only need an array of size `n` to store the state of the memory.

Trade-offs

Pros

  • Simple to understand and implement.

  • Uses minimal space, just the memory array itself.

Cons

  • allocate operation is very slow due to the nested loop structure, making it likely to exceed time limits for larger inputs.

Solutions

class Allocator { private int [] m ; public Allocator ( int n ) { m = new int [ n ]; } public int allocate ( int size , int mID ) { int cnt = 0 ; for ( int i = 0 ; i < m . length ; ++ i ) { if ( m [ i ] > 0 ) { cnt = 0 ; } else if (++ cnt == size ) { Arrays . fill ( m , i - size + 1 , i + 1 , mID ); return i - size + 1 ; } } return - 1 ; } public int free ( int mID ) { int ans = 0 ; for ( int i = 0 ; i < m . length ; ++ i ) { if ( m [ i ] == mID ) { m [ i ] = 0 ; ++ ans ; } } return ans ; } } /** * 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); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem