[面经] NVIDIA Coding：LRU 磁盘空间管理器（按容量淘汰）高频题
冷目灼灼的扁豆
[面经] NVIDIA Coding：LRU 磁盘空间管理器（按容量淘汰）
最近面了 NVIDIA，分享一下技术电面里的一道题。表面上看就是 LRU 缓存，但有个关键区别：容量限制的是总大小，不是条数。这一点同时影响淘汰逻辑和更新路径，很适合检验 LRU 的基本功到底是真的扎实还是背下来的。面试官一开始没有限定淘汰策略（合理的策略都可以，比如 LRU），后来为了让结果确定，固定用 LRU，操作也以批量形式给出、按顺序处理。
题目
实现一个内存里的磁盘空间管理器，总容量固定。数据集用
例题走一遍
容量 10，操作序列：put A 4, put B 3, get A, put C 5, get B, get A, get C。
最容易错的一步在第 4 步：被淘汰的是 B 不是 A，因为第 3 步的 get 刷新了 A。
核心思路
需要同时做到两件事：按
方法 B：哈希表 + 双向链表
同样的设计，但不用库来维护顺序：一个从
复杂度
觉得有帮助的话欢迎收藏、加米。也欢迎讨论变体，比如把 LRU 换成 LFU，或者给数据集加 TTL。
最近面了 NVIDIA，分享一下技术电面里的一道题。表面上看就是 LRU 缓存，但有个关键区别：容量限制的是总大小，不是条数。这一点同时影响淘汰逻辑和更新路径，很适合检验 LRU 的基本功到底是真的扎实还是背下来的。面试官一开始没有限定淘汰策略（合理的策略都可以，比如 LRU），后来为了让结果确定，固定用 LRU，操作也以批量形式给出、按顺序处理。
题目
实现一个内存里的磁盘空间管理器，总容量固定。数据集用
datasetId 标识，每个有一个整数 size。put(datasetId, size)：存入一个数据集。空闲空间不够时，淘汰最久未使用的数据集，直到能放下为止。如果size > totalCapacity，这次 put 失败，并且状态必须保持原样。get(datasetId)：返回存的大小，不存在返回 -1。
- 每次成功的
get和每次成功的put（包括更新）都让该数据集变为最近使用。 put一个已存在的datasetId是替换它的大小。先释放旧大小，再决定要不要淘汰别人。- 为了可测试，操作以批量形式给出：
solution(total_capacity, operations)按顺序返回每个操作的结果。put 成功返回"ok"，失败返回"error"，get 返回大小或 -1。
total_capacity 最大 1e9，操作数最多 2e5，size 在 1 到 1e9 之间，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
['ok', 'ok', 4, 'ok', -1, 4, 5]最容易错的一步在第 4 步：被淘汰的是 B 不是 A，因为第 3 步的 get 刷新了 A。
核心思路
需要同时做到两件事：按
datasetId O(1) 查找，以及 O(1) 拿到最久未使用的数据集。这就是 LRU 缓存经典的哈希表 + 有序结构组合。和教科书版 LRU 缓存的区别有三点：- 淘汰是一个循环，不是一次弹出：一次 put 可能淘汰多个数据集。
used的记账要经得起更新：先减掉旧大小再淘汰，否则会淘汰不必要的数据集，更糟的是可能把正在更新的数据集自己淘汰掉。- put 只有一种失败方式：
size > capacity。只要它本身能放进总容量，把其他都淘汰掉总能腾出地方，没有第二种失败路径。
from collections import OrderedDict
class DiskSpaceManager:
def __init__(self, total_capacity):
self.capacity = total_capacity
self.used = 0
self.store = OrderedDict() # datasetId -> size, LRU first
def get(self, dataset_id):
if dataset_id not in self.store:
return -1
self.store.move_to_end(dataset_id) # now most recently used
return self.store[dataset_id]
def put(self, dataset_id, size):
if size > self.capacity:
return "error" # can never fit; state untouched
if dataset_id in self.store:
# Update: free the old size before evicting anyone else.
self.used -= self.store.pop(dataset_id)
while self.used + size > self.capacity:
_, evicted_size = self.store.popitem(last=False) # LRU end
self.used -= evicted_size
self.store[dataset_id] = size
self.used += size
return "ok"
def solution(total_capacity, operations):
mgr = DiskSpaceManager(total_capacity)
out = []
for op in operations:
if op[0] == "put":
out.append(mgr.put(op[1], op[2]))
else:
out.append(mgr.get(op[1]))
return out
class DiskSpaceManager:
def __init__(self, total_capacity):
self.capacity = total_capacity
self.used = 0
self.store = OrderedDict() # datasetId -> size, LRU first
def get(self, dataset_id):
if dataset_id not in self.store:
return -1
self.store.move_to_end(dataset_id) # now most recently used
return self.store[dataset_id]
def put(self, dataset_id, size):
if size > self.capacity:
return "error" # can never fit; state untouched
if dataset_id in self.store:
# Update: free the old size before evicting anyone else.
self.used -= self.store.pop(dataset_id)
while self.used + size > self.capacity:
_, evicted_size = self.store.popitem(last=False) # LRU end
self.used -= evicted_size
self.store[dataset_id] = size
self.used += size
return "ok"
def solution(total_capacity, operations):
mgr = DiskSpaceManager(total_capacity)
out = []
for op in operations:
if op[0] == "put":
out.append(mgr.put(op[1], op[2]))
else:
out.append(mgr.get(op[1]))
return out
方法 B：哈希表 + 双向链表
同样的设计，但不用库来维护顺序：一个从
datasetId 到节点的字典，再加一条带头尾哨兵的双向链表保存新旧顺序（靠近头的是最久未使用，靠近尾的是最近使用）。适合 Java 里没有 access-order LinkedHashMap 的情况，或者面试官想看链表本身实现的时候。class _Node:
__slots__ = ("key", "size", "prev", "next")
def __init__(self, key=None, size=0):
self.key = key
self.size = size
self.prev = None
self.next = None
class DiskSpaceManagerDLL:
def __init__(self, total_capacity):
self.capacity = total_capacity
self.used = 0
self.map = {}
self.head = _Node() # sentinel: head.next is the LRU dataset
self.tail = _Node() # sentinel: tail.prev is the MRU dataset
self.head.next = self.tail
self.tail.prev = self.head
def _unlink(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _append_mru(self, node):
last = self.tail.prev
last.next = node
node.prev = last
node.next = self.tail
self.tail.prev = node
def get(self, dataset_id):
node = self.map.get(dataset_id)
if node is None:
return -1
self._unlink(node)
self._append_mru(node)
return node.size
def put(self, dataset_id, size):
if size > self.capacity:
return "error"
old = self.map.pop(dataset_id, None)
if old is not None:
self._unlink(old)
self.used -= old.size
while self.used + size > self.capacity:
lru = self.head.next
self._unlink(lru)
del self.map[lru.key]
self.used -= lru.size
node = _Node(dataset_id, size)
self.map[dataset_id] = node
self._append_mru(node)
self.used += size
return "ok"
__slots__ = ("key", "size", "prev", "next")
def __init__(self, key=None, size=0):
self.key = key
self.size = size
self.prev = None
self.next = None
class DiskSpaceManagerDLL:
def __init__(self, total_capacity):
self.capacity = total_capacity
self.used = 0
self.map = {}
self.head = _Node() # sentinel: head.next is the LRU dataset
self.tail = _Node() # sentinel: tail.prev is the MRU dataset
self.head.next = self.tail
self.tail.prev = self.head
def _unlink(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _append_mru(self, node):
last = self.tail.prev
last.next = node
node.prev = last
node.next = self.tail
self.tail.prev = node
def get(self, dataset_id):
node = self.map.get(dataset_id)
if node is None:
return -1
self._unlink(node)
self._append_mru(node)
return node.size
def put(self, dataset_id, size):
if size > self.capacity:
return "error"
old = self.map.pop(dataset_id, None)
if old is not None:
self._unlink(old)
self.used -= old.size
while self.used + size > self.capacity:
lru = self.head.next
self._unlink(lru)
del self.map[lru.key]
self.used -= lru.size
node = _Node(dataset_id, size)
self.map[dataset_id] = node
self._append_mru(node)
self.used += size
return "ok"
复杂度
get：平均 O(1)。put：平均 O(1) 加上淘汰的开销。每个数据集每次插入后最多被淘汰一次，所以 n 个操作总共是 O(n)；淘汰循环是均摊的，不会变成每个 put 都二次方。- 空间：O(当前存着的数据集数量）。
- 失败的 put 什么都不能改。
size > capacity时不要淘汰、不要插入、不要动新旧顺序。更新的情况也一样：超大的更新要让旧数据集保留旧大小和旧位置。 - 先释放旧大小，再淘汰。更新时如果先淘汰后记账，会多淘汰不必要的数据集，还可能把正在更新的数据集自己淘汰掉。
- get 未命中不算一次使用。返回 -1 时不能创建条目，也不能改新旧顺序。
- 一旦新数据集能放下就停止淘汰。多淘汰一个是最常见的 off-by-one；上面的例题能抓到它（第 4 步如果连 A 一起淘汰，put 照样成功，但第 6 步就会错误地返回 -1）。
觉得有帮助的话欢迎收藏、加米。也欢迎讨论变体，比如把 LRU 换成 LFU，或者给数据集加 TTL。
已获得 1 大米
共1条回复
