How do I handle allocation failures in the Design Memory Allocator problem?

You need to return -1 if there isn't enough free memory for the requested size. Efficient scanning of the memory array helps ensure this condition is checked early in the process.

What is the time complexity of the `allocate` operation in this problem?

The time complexity of the `allocate` operation is O(n) in the worst case, as you may need to scan the entire memory array to find a suitable free block.

How do I efficiently free memory in the Design Memory Allocator?

Use a hash table to track the memory blocks by `mID`. When freeing memory, simply look up the `mID` in the hash table to quickly access and deallocate the corresponding memory units.

Can I use other data structures apart from arrays and hash tables for the allocator?

While arrays and hash tables are the most straightforward and efficient for this problem, alternative data structures like linked lists or segment trees could be used for more complex scenarios, such as handling dynamic memory resizing or fragmentation.

What edge cases should I consider when implementing the Design Memory Allocator?

Edge cases include insufficient memory for allocation requests, invalid `mID` values for `freeMemory` operations, and handling deallocation of memory blocks that were never allocated.

#2502

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

设计内存分配器

给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。请你设计一个具备以下功能的内存分配器：分配一块大小为 size 的连续空闲内存单元并赋 id mID 。释放给定 id mID 对应的所有内存单元。注意：多个块可以被分配到同一个 mID 。你必须释…

数组哈希表设计模拟

题目描述

给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。

请你设计一个具备以下功能的内存分配器：

分配一块大小为 size 的连续空闲内存单元并赋 id mID 。
释放给定 id mID 对应的所有内存单元。

注意：

多个块可以被分配到同一个 mID 。
你必须释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。

实现 Allocator 类：

Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。
int allocate(int size, int mID) 找出大小为 size 个连续空闲内存单元且位于 最左侧 的块，分配并赋 id mID 。返回块的第一个下标。如果不存在这样的块，返回 -1 。
int freeMemory(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。

示例：

输入
["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]]
输出
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

解释
Allocator loc = new Allocator(10); // 初始化一个大小为 10 的内存数组，所有内存单元都是空闲的。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 0 。内存数组变为 [1, , , , , , , , , ]。返回 0 。
loc.allocate(1, 2); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,2, , , , , , , , ]。返回 1 。
loc.allocate(1, 3); // 最左侧的块的第一个下标是 2 。内存数组变为 [1,2,3, , , , , , , ]。返回 2 。
loc.freeMemory(2); // 释放 mID 为 2 的所有内存单元。内存数组变为 [1, ,3, , , , , , , ] 。返回 1 ，因为只有 1 个 mID 为 2 的内存单元。
loc.allocate(3, 4); // 最左侧的块的第一个下标是 3 。内存数组变为 [1, ,3,4,4,4, , , , ]。返回 3 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,1,3,4,4,4, , , , ]。返回 1 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 6 。内存数组变为 [1,1,3,4,4,4,1, , , ]。返回 6 。
loc.freeMemory(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4, , , , ] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。
loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块，所有返回 -1 。
loc.freeMemory(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状，因为不存在 mID 为 7 的内存单元。返回 0 。

提示：

1 <= n, size, mID <= 1000
最多调用 allocate 和 free 方法 1000 次

lightbulb

解题思路

方法一：模拟

题目数据范围不大，可以直接用数组模拟内存空间。

初始化时，将数组中的每个元素置为 $0$ ，表示空闲。

当调用 allocate 方法时，遍历数组，找到连续的 size 个空闲内存单元，将其置为 mID，并返回第一个下标。

当调用 free 方法时，遍历数组，将所有等于 mID 的内存单元置为 $0$ ，表示空闲。

时间复杂度 $O(n \times q)$ ，空间复杂度 $O(n)$ ，其中 $n$ 和 $q$ 分别为内存空间的大小和方法调用的次数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class Allocator:

    def __init__(self, n: int):
        self.m = [0] * n

    def allocate(self, size: int, mID: int) -> int:
        cnt = 0
        for i, v in enumerate(self.m):
            if v:
                cnt = 0
            else:
                cnt += 1
                if cnt == size:
                    self.m[i - size + 1 : i + 1] = [mID] * size
                    return i - size + 1
        return -1

    def freeMemory(self, mID: int) -> int:
        ans = 0
        for i, v in enumerate(self.m):
            if v == mID:
                self.m[i] = 0
                ans += 1
        return ans


# Your Allocator object will be instantiated and called as such:
# obj = Allocator(n)
# param_1 = obj.allocate(size,mID)
# param_2 = obj.freeMemory(mID)

speed

复杂度分析

指标	值
时间	complexity depends on the allocation and scanning approach. Array scanning has a worst-case time complexity of O(n) for each allocation, while hash table lookups for freeing memory are O(1). The space complexity is O(n) for storing the memory array and hash table entries for `mID` tracking.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of memory management in an array and hash-based tracking.
question_mark
Test if the candidate can optimize the allocation search with efficient techniques.
question_mark
Gauge ability to handle edge cases such as memory exhaustion or invalid memory deallocation.

warning

常见陷阱

外企场景

error
Not handling cases where memory blocks cannot be allocated due to insufficient consecutive free memory.
error
Failing to correctly manage and track `mID` values, leading to incorrect deallocations.
error
Inefficient allocation logic causing performance issues with large memory sizes or frequent operations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increase memory array size or handle dynamic resizing of the allocator.
arrow_right_alt
Introduce memory fragmentation, requiring more complex memory allocation strategies.
arrow_right_alt
Add additional operations such as querying memory usage or checking for the largest free block.

help

常见问题

外企场景

继续练习

#2043 简易银行系统 #3242 设计相邻元素求和服务 #2549 统计桌面上的不同数字