面试题：缓存设计之中等难度：LRU 缓存策略实现

Question

请用你熟悉的编程语言实现一个简单的 LRU（最近最少使用）缓存。要求缓存具备固定大小，当缓存满时，添加新元素会移除最久未使用的元素。你可以假设缓存操作只有 get 和 put 两种。

Answer 1

以Python语言为例，使用collections.OrderedDict可以方便地实现LRU缓存：

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

你可以使用以下方式测试代码：

# 示例用法
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))  # 返回 1
cache.put(3, 3)  # 移除键 2
print(cache.get(2))  # 返回 -1 (未找到)
cache.put(4, 4)  # 移除键 1
print(cache.get(1))  # 返回 -1 (未找到)
print(cache.get(3))  # 返回 3
print(cache.get(4))  # 返回 4

解释：

1. __init__ 方法初始化缓存容量和有序字典 cache。
2. get 方法检查键是否存在于缓存中。如果存在，将其移动到字典末尾（表示最近使用），并返回对应的值；如果不存在，返回 -1。
3. put 方法首先检查键是否已存在。如果存在，更新值并将其移动到字典末尾。如果不存在，添加键值对。如果缓存已满，移除字典最前面的元素（最久未使用）。