Design Memory Allocator Interview Question for Amazon

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:

Allocate a block of size consecutive free memory units and assign it the id mID.
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.

For example:

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.

How would you implement this Allocator class and what are the time and space complexities of your solution? Consider edge cases and provide a well-structured, efficient solution.

Solution to the Memory Allocator Problem

This problem requires implementing a memory allocator with allocate and freeMemory functionalities. Let's explore both a naive and an optimal solution.

1. Naive Solution

Approach

Use an array to represent the memory.

allocate(size, mID): Iterate through the memory array to find a contiguous block of size free units. If found, mark them with mID and return the starting index. Otherwise, return -1.

freeMemory(mID): Iterate through the memory array and set all units with the given mID to free (e.g., 0). Return the count of freed units.

Code (Python)

class Allocator: def __init__(self, n: int): self.memory = [0] * n def allocate(self, size: int, mID: int) -> int: count = 0 start = -1 for i in range(len(self.memory)): if self.memory[i] == 0: if count == 0: start = i count += 1 if count == size: for j in range(start, start + size): self.memory[j] = mID return start else: count = 0 start = -1 return -1 def freeMemory(self, mID: int) -> int: freed = 0 for i in range(len(self.memory)): if self.memory[i] == mID: self.memory[i] = 0 freed += 1 return freed

Big O Analysis

Time Complexity:

allocate: O(n) in the worst case (when iterating through the entire array).
freeMemory: O(n) as it iterates through the entire array.

Space Complexity: O(1) (excluding the memory array itself).

2. Optimal Solution

Approach

To optimize, we can maintain a list of available blocks. This can be done by tracking the start and end indices of free memory blocks. Then, when we allocate, we can quickly find a suitable block using a data structure like a heap or sorted list.

For this specific question, since the constraints are small (n <= 1000), the naive solution should be sufficient to solve it. If the problem required more performance, we could explore more efficient ways to track free blocks.

Edge Cases

Allocation Failure: When there is no block of sufficient size, return -1.

Freeing Non-existent ID: When freeMemory is called with an mID that doesn't exist, return 0.

Multiple Blocks with Same ID: Ensure all blocks with the given mID are freed.