LRU缓存、最小栈、LFU缓存——面试中设计题是区分度最高的题型
设计题考察的不是算法难度，而是数据结构的组合与权衡。每种数据结构都有优劣，设计题要求你根据操作需求，选择合适的组合，达到所有操作的高效。
# OrderedDict 模拟 LRU（Python 3.7+）
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # 移到末尾=最近使用
return self.cache[key]
def put(self, key, value):
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) # 删除最久未用OrderedDict 快速实现 LRU，但要能从头手写哈希表+双向链表的版本。面试官可能会要求不使用内置 OrderedDict。题目描述：设计一个满足 LRU（最近最少使用）缓存约束的数据结构，实现 get 和 put 操作，均需 O(1) 时间。
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # key → value
self.order = [] # 简化版: 用列表维护顺序
def get(self, key: int) -> int:
if key in self.cache:
self.order.remove(key) # O(n) 简化
self.order.append(key)
return self.cache[key]
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.order.remove(key)
elif len(self.cache) >= self.capacity:
lru = self.order.pop(0) # O(n) 简化
del self.cache[lru]
self.cache[key] = value
self.order.append(key)# O(1) 版本: 手写双向链表 + 哨兵节点
class Node:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = {} # key → Node
# 哨兵节点: head(最久) ↔ tail(最近)
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_tail(self, node):
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_to_tail(node)
return node.val
def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])
node = Node(key, value)
self.cache[key] = node
self._add_to_tail(node)
if len(self.cache) > self.cap:
lru = self.head.next
self._remove(lru)
del self.cache[lru.key]题目描述：设计一个栈，支持 push、pop、top 和 getMin 操作，且都是 O(1) 时间。
min(当前值, 辅助栈顶)；pop 时两个栈同步弹出。辅助栈顶永远是当前最小值。
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
self.min_stack.append(
min(val, self.min_stack[-1] if self.min_stack else val)
)
def pop(self) -> None:
self.stack.pop()
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]所有操作：O(1)
空间复杂度：O(n)
题目描述：设计 LFU（最不经常使用）缓存，实现 get 和 put。当缓存满时，淘汰使用频率最低的 key；如果有多个频率相同的，淘汰最久未使用的。
key_to_val_freq：哈希表，key → (value, frequency)，O(1) 查找freq_to_keys：哈希表，freq → OrderedDict of keys，同一频率的 key 按使用时间排序min_freq：当前最小频率，用于淘汰时快速定位import collections
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.min_freq = 0
self.key_to_val_freq = {} # key → (val, freq)
self.freq_to_keys = collections.defaultdict(
collections.OrderedDict
) # freq → OrderedDict of keys
def get(self, key: int) -> int:
if key not in self.key_to_val_freq:
return -1
val, freq = self.key_to_val_freq[key]
# 从旧频率桶中移除
del self.freq_to_keys[freq][key]
if not self.freq_to_keys[freq]:
del self.freq_to_keys[freq]
if self.min_freq == freq:
self.min_freq += 1
# 加入新频率桶
self.freq_to_keys[freq + 1][key] = None
self.key_to_val_freq[key] = (val, freq + 1)
return val
def put(self, key: int, value: int) -> None:
if self.capacity <= 0:
return
if key in self.key_to_val_freq:
_, freq = self.key_to_val_freq[key]
self.key_to_val_freq[key] = (value, freq)
self.get(key) # 借用get更新频率
return
# 新key，需要淘汰
if len(self.key_to_val_freq) >= self.capacity:
# 淘汰min_freq桶中最久未用的
evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
del self.key_to_val_freq[evict_key]
self.key_to_val_freq[key] = (value, 1)
self.freq_to_keys[1][key] = None
self.min_freq = 1get：O(1)，put：O(1)
空间复杂度：O(capacity)
数据结构设计题是面试中区分度最高的题型之一，以下是应对策略：
# 先定义好类的方法签名
class MyDataStructure:
def __init__(self, ...):
pass
def operation1(self, ...):
pass
def operation2(self, ...):
pass
# 然后逐个实现，边写边解释复杂度# O(1) 随机访问 + O(1) 删除: 数组 + 哈希表
# 数组存元素，哈希表存元素→索引
# 删除时: 用末尾元素覆盖，O(1)
# O(1) 查找 + 有序: 哈希表 + 平衡树/跳表
# Java: HashMap + TreeMap
# Python: dict + SortedList (from sortedcontainers)
# O(1) 最值 + 栈操作: 主栈 + 辅助栈
# O(1) 中位数: 最大堆 + 最小堆(1) 确认所有操作及其复杂度要求
(2) 分析每个操作需要什么数据结构支持
(3) 设计组合方案，画图说明数据流转
(4) 先写简化版（可能不是最优），再优化
(5) 处理边界情况：空容器、容量为0等