2502. Design Memory Allocator - Detailed Explanation

Problem Statement

You are tasked with designing a memory allocator that manages a contiguous block of memory of a given size. The allocator must support two operations:

1. allocate(size, mID):
   Allocate a contiguous block of free memory of the given size and mark it with the memory ID (mID). The allocation should use the first available block (i.e., with the smallest starting index). If a suitable block is found, return its starting index (0-indexed). Otherwise, return -1.

2. free(mID):
   Free all memory units that have been allocated with the specified mID, making those units available for future allocations. Return the total number of memory units that were freed.

Initially, all memory units are free.

Hints

1. Memory Representation:
   Represent the memory as an array where each element holds 0 if it is free or a positive integer representing the mID if it is allocated.

2. Allocation Strategy:
   To maximize usage, iterate over the memory array to find the first contiguous sequence of free cells that is long enough to satisfy the allocation request.

3. Freeing Memory:
   When freeing, simply scan through the memory array, resetting any cell with the given mID to 0 and counting how many cells were freed.

Approaches

Brute Force Approach

• Idea:
  Use a simple array to model the memory. For allocation, scan from the beginning and check each possible starting position to see if a block of the required size is available. For freeing, iterate through the entire array and reset cells that match the given mID.

• Steps for allocate:

  1. Initialize a counter for free contiguous cells.
  2. Iterate through the memory array.
  3. Increase the counter when a free cell (value 0) is found.
  4. When the counter reaches the requested size, mark those cells with mID and return the starting index.
  5. If the block is interrupted by an allocated cell, reset the counter.

• Steps for free:

  1. Iterate through the memory array.
  2. For each cell matching mID, set it to 0 and increment a freed counter.
  3. Return the total freed counter.

• Complexity:

  • Time:
    • allocate: O(n) per call (n is the total memory size) in the worst case.
    • free: O(n) per call.
  • Space: O(n) for the memory array.

Optimized Considerations

While the brute force approach is straightforward, further optimization (such as using interval trees or segment trees) could improve performance for a very large memory space and frequent operations. However, for many practical cases and interview settings, the brute force method is acceptable and simpler to implement.

Complexity Analysis

• Time Complexity:

  • allocate: O(n) in the worst case if the allocator needs to scan the entire memory.
  • free: O(n) in the worst case.

• Space Complexity:

  • O(n) to store the memory representation.

Python Code

Java Code