[面经] NVIDIA Coding：LRU 磁盘空间管理器（按容量淘汰）

[面经] NVIDIA Coding：LRU 磁盘空间管理器（按容量淘汰）
最近面了 NVIDIA，分享一下技术电面里的一道题。表面上看就是 LRU 缓存，但有个关键区别：容量限制的是总大小，不是条数。这一点同时影响淘汰逻辑和更新路径，很适合检验 LRU 的基本功到底是真的扎实还是背下来的。面试官一开始没有限定淘汰策略（合理的策略都可以，比如 LRU），后来为了让结果确定，固定用 LRU，操作也以批量形式给出、按顺序处理。
题目
实现一个内存里的磁盘空间管理器，总容量固定。数据集用

1. datasetId

复制代码

标识，每个有一个整数

1. size

复制代码

。

• 1. put(datasetId, size)

  复制代码
  ：存入一个数据集。空闲空间不够时，淘汰最久未使用的数据集，直到能放下为止。如果
  1. size > totalCapacity

  复制代码
  ，这次 put 失败，并且状态必须保持原样。
• 1. get(datasetId)

  复制代码
  ：返回存的大小，不存在返回 -1。

细节规则：

• 每次成功的
  1. get

  复制代码
  和每次成功的
  1. put

  复制代码
  （包括更新）都让该数据集变为最近使用。
• 1. put

  复制代码
  一个已存在的
  1. datasetId

  复制代码
  是替换它的大小。先释放旧大小，再决定要不要淘汰别人。
• 为了可测试，操作以批量形式给出：
  1. solution(total_capacity, operations)

  复制代码
  按顺序返回每个操作的结果。put 成功返回
  1. "ok"

  复制代码
  ，失败返回
  1. "error"

  复制代码
  ，get 返回大小或 -1。

约束：

1. total_capacity

复制代码

最大 1e9，操作数最多 2e5，

1. size

复制代码

在 1 到 1e9 之间，

1. datasetId

复制代码

是非空字符串。
例题走一遍
容量 10，操作序列：put A 4, put B 3, get A, put C 5, get B, get A, get C。

• put A (4)：放得下。used = 4。新旧顺序：A
• put B (3)：放得下。used = 7。顺序：A, B
• get A：返回 4，A 变为最近使用。顺序：B, A
• put C (5)：空闲只有 3，不够。B 是最久未使用的，先淘汰 B（used = 4），再放入 C（used = 9）。顺序：A, C
• get B：-1，B 已经被淘汰了
• get A：4
• get C：5

输出：

1. ['ok', 'ok', 4, 'ok', -1, 4, 5]

复制代码

最容易错的一步在第 4 步：被淘汰的是 B 不是 A，因为第 3 步的 get 刷新了 A。
核心思路
需要同时做到两件事：按

1. datasetId

复制代码

O(1) 查找，以及 O(1) 拿到最久未使用的数据集。这就是 LRU 缓存经典的哈希表 + 有序结构组合。和教科书版 LRU 缓存的区别有三点：

• 淘汰是一个循环，不是一次弹出：一次 put 可能淘汰多个数据集。
• 1. used

  复制代码
  的记账要经得起更新：先减掉旧大小再淘汰，否则会淘汰不必要的数据集，更糟的是可能把正在更新的数据集自己淘汰掉。
• put 只有一种失败方式：
  1. size > capacity

  复制代码
  。只要它本身能放进总容量，把其他都淘汰掉总能腾出地方，没有第二种失败路径。

方法 A：OrderedDict

1. from collections import OrderedDict
3. class DiskSpaceManager:
4.     def __init__(self, total_capacity):
5.         self.capacity = total_capacity
6.         self.used = 0
7.         self.store = OrderedDict()  # datasetId -> size, LRU first
9.     def get(self, dataset_id):
10.         if dataset_id not in self.store:
11.             return -1
12.         self.store.move_to_end(dataset_id)  # now most recently used
13.         return self.store[dataset_id]
15.     def put(self, dataset_id, size):
16.         if size > self.capacity:
17.             return "error"  # can never fit; state untouched
18.         if dataset_id in self.store:
19.             # Update: free the old size before evicting anyone else.
20.             self.used -= self.store.pop(dataset_id)
21.         while self.used + size > self.capacity:
22.             _, evicted_size = self.store.popitem(last=False)  # LRU end
23.             self.used -= evicted_size
24.         self.store[dataset_id] = size
25.         self.used += size
26.         return "ok"
28. def solution(total_capacity, operations):
29.     mgr = DiskSpaceManager(total_capacity)
30.     out = []
31.     for op in operations:
32.         if op[0] == "put":
33.             out.append(mgr.put(op[1], op[2]))
34.         else:
35.             out.append(mgr.get(op[1]))
36.     return out

复制代码

方法 B：哈希表 + 双向链表
同样的设计，但不用库来维护顺序：一个从

1. datasetId

复制代码

到节点的字典，再加一条带头尾哨兵的双向链表保存新旧顺序（靠近头的是最久未使用，靠近尾的是最近使用）。适合 Java 里没有 access-order

1. LinkedHashMap

复制代码

的情况，或者面试官想看链表本身实现的时候。

1. class _Node:
2.     __slots__ = ("key", "size", "prev", "next")
4.     def __init__(self, key=None, size=0):
5.         self.key = key
6.         self.size = size
7.         self.prev = None
8.         self.next = None
10. class DiskSpaceManagerDLL:
11.     def __init__(self, total_capacity):
12.         self.capacity = total_capacity
13.         self.used = 0
14.         self.map = {}
15.         self.head = _Node()  # sentinel: head.next is the LRU dataset
16.         self.tail = _Node()  # sentinel: tail.prev is the MRU dataset
17.         self.head.next = self.tail
18.         self.tail.prev = self.head
20.     def _unlink(self, node):
21.         node.prev.next = node.next
22.         node.next.prev = node.prev
24.     def _append_mru(self, node):
25.         last = self.tail.prev
26.         last.next = node
27.         node.prev = last
28.         node.next = self.tail
29.         self.tail.prev = node
31.     def get(self, dataset_id):
32.         node = self.map.get(dataset_id)
33.         if node is None:
34.             return -1
35.         self._unlink(node)
36.         self._append_mru(node)
37.         return node.size
39.     def put(self, dataset_id, size):
40.         if size > self.capacity:
41.             return "error"
42.         old = self.map.pop(dataset_id, None)
43.         if old is not None:
44.             self._unlink(old)
45.             self.used -= old.size
46.         while self.used + size > self.capacity:
47.             lru = self.head.next
48.             self._unlink(lru)
49.             del self.map[lru.key]
50.             self.used -= lru.size
51.         node = _Node(dataset_id, size)
52.         self.map[dataset_id] = node
53.         self._append_mru(node)
54.         self.used += size
55.         return "ok"

复制代码

复杂度

• 1. get

  复制代码
  ：平均 O(1)。
• 1. put

  复制代码
  ：平均 O(1) 加上淘汰的开销。每个数据集每次插入后最多被淘汰一次，所以 n 个操作总共是 O(n)；淘汰循环是均摊的，不会变成每个 put 都二次方。
• 空间：O(当前存着的数据集数量）。

易错点

• 失败的 put 什么都不能改。
  1. size > capacity

  复制代码
  时不要淘汰、不要插入、不要动新旧顺序。更新的情况也一样：超大的更新要让旧数据集保留旧大小和旧位置。
• 先释放旧大小，再淘汰。更新时如果先淘汰后记账，会多淘汰不必要的数据集，还可能把正在更新的数据集自己淘汰掉。
• get 未命中不算一次使用。返回 -1 时不能创建条目，也不能改新旧顺序。
• 一旦新数据集能放下就停止淘汰。多淘汰一个是最常见的 off-by-one；上面的例题能抓到它（第 4 步如果连 A 一起淘汰，put 照样成功，但第 6 步就会错误地返回 -1）。

验证：除了上面的例题，还用 500 组随机操作序列和一个朴素 O(n) 参考实现做了对拍，两种方法全部一致。
觉得有帮助的话欢迎收藏、加米。也欢迎讨论变体，比如把 LRU 换成 LFU，或者给数据集加 TTL。

谢谢