We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Memory Allocator

Difficulty: Medium

Problem Description

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 functionalities to allocate a block of size consecutive free memory units with a specified id and free all memory units with a given id.

Key Insights

  • The allocator manages memory as an array, where each index represents a memory unit.
  • Allocation requires finding the leftmost block of consecutive free units.
  • Freeing memory must handle multiple allocations with the same id and restore those units back to free.
  • Efficient tracking of allocated memory is essential to minimize time complexity for both allocation and freeing operations.

Space and Time Complexity

Time Complexity: O(n) for allocation and free operations in the worst case, where n is the size of the memory array.
Space Complexity: O(n) for storing the memory state and mapping ids to their allocated memory blocks.

Solution

The solution involves using an array to represent the memory and a hashmap to keep track of which indices are associated with which ids. The allocate function searches for the first segment of free memory that can accommodate the requested size, while the freeMemory function iterates through the memory array to free all segments associated with the specified id.

Code Solutions

class Allocator:
    def __init__(self, n: int):
        self.memory = [0] * n  # Initialize memory array
        self.id_map = {}  # Map to track allocations by id

    def allocate(self, size: int, mID: int) -> int:
        # Search for a block of 'size' consecutive free memory units
        for i in range(len(self.memory) - size + 1):
            if all(self.memory[j] == 0 for j in range(i, i + size)):
                # Allocate memory
                for j in range(i, i + size):
                    self.memory[j] = mID
                # Update id_map
                if mID not in self.id_map:
                    self.id_map[mID] = []
                self.id_map[mID].append((i, size))  # Save the starting index and size
                return i  # Return the starting index
        return -1  # Not enough memory

    def freeMemory(self, mID: int) -> int:
        if mID not in self.id_map:
            return 0  # No memory allocated with this ID
        freed_units = 0
        for start, size in self.id_map[mID]:
            # Free the allocated memory
            for j in range(start, start + size):
                if self.memory[j] == mID:  # Only free if it matches mID
                    self.memory[j] = 0
                    freed_units += 1
        # Remove from id_map
        del self.id_map[mID]
        return freed_units
← Back to All Questions