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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Design Memory Allocator

Number: 2587

Difficulty: Medium

Paid? No

Companies: Uber, Two Sigma, Microsoft, Amazon

Problem Description

Design a memory allocator that simulates allocation and freeing operations on a 0-indexed memory array of size n. Initially, all memory units are free. The allocator supports two functions:

  1. allocate(size, mID): Find the leftmost contiguous block of "size" free memory units and allocate them with the id mID. Return the starting index if successful or -1 if no suitable block exists.
  2. freeMemory(mID): Free all memory units allocated with id mID and return the count of memory units freed.

Key Insights

  • Use a simple simulation with an array representing memory, where 0 indicates a free memory unit.
  • For the allocate operation, traverse the array to find a contiguous block of free units of the required size.
  • For the freeMemory operation, scan the entire memory array and reset units with the specified mID to 0.
  • Given the problem constraints (n, size, mID <= 1000 and at most 1000 operations), an O(n) scan for each operation is efficient enough.

Space and Time Complexity

Time Complexity:

  • allocate: O(n) per call in the worst case.
  • freeMemory: O(n) per call. Space Complexity:
  • O(n) for maintaining the memory array.

Solution

We simulate the memory using an array of length n. For the allocate operation, we iterate through the array to search for a contiguous sequence of free slots (i.e., slots with value 0) of the required size. Once found, we mark those slots with the given mID and return the starting index. If no such block exists, we return -1.

For the freeMemory operation, we iterate over the entire array and whenever we find a slot marked with the given mID, we reset it to 0 (free it) and count the number of slots freed. This count is then returned.

This straightforward simulation approach leverages the small constraint sizes and keeps the implementation simple and easy to understand.

Code Solutions

# Python solution for the Design Memory Allocator problem

class Allocator:
    def __init__(self, n: int):
        # Initialize memory array of size n with all slots free (0 indicates free)
        self.memory = [0] * n

    def allocate(self, size: int, mID: int) -> int:
        n = len(self.memory)
        consecutive_free = 0  # count of consecutive free slots
        # iterate over memory array
        for i in range(n):
            if self.memory[i] == 0:
                consecutive_free += 1
            else:
                consecutive_free = 0

            # if a block of 'size' consecutive free slots is found
            if consecutive_free == size:
                start = i - size + 1
                # allocate memory: assign mID to these slots
                for j in range(start, start + size):
                    self.memory[j] = mID
                return start
        # no suitable block found
        return -1

    def freeMemory(self, mID: int) -> int:
        freed_count = 0
        # iterate over the entire memory
        for i in range(len(self.memory)):
            # if memory unit has the mID, free it
            if self.memory[i] == mID:
                self.memory[i] = 0
                freed_count += 1
        return freed_count

# Example usage:
# allocator = Allocator(10)
# print(allocator.allocate(1, 1))  # allocates first block
# print(allocator.freeMemory(1))   # frees blocks with mID=1
← Back to All Questions