K
🐍Python 常用容器与迭代

手撕题：LRU 与常见设计

难度：⭐⭐ | 高频指数：🔥🔥🔥

面试回答

常见问法

  • 手写一个 LRU Cache
  • 怎么实现带过期时间的缓存？
  • 写一个重试装饰器（带指数退避）
  • 实现一个简单的限流器
  • 这些题面试时怎么讲思路？

回答

Python 面试中最常见的”手撕设计题”集中在几个方向：缓存（LRU/TTL）、重试机制、限流器。这些题考察的不是算法难度，而是工程设计能力 + Python 语言熟练度。

面试时的讲解策略：先说数据结构选型和时间复杂度，写出核心代码，主动提出可优化的点。

追问

1）LRU Cache — OrderedDict 版（推荐先写这个）

from collections import OrderedDict

class LRUCache:
    """
    get/put 均为 O(1)
    核心思路：OrderedDict 维护访问顺序，最近访问的移到末尾
    """
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    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)

# 测试
lru = LRUCache(2)
lru.put("a", 1)
lru.put("b", 2)
print(lru.get("a"))   # 1
lru.put("c", 3)       # 淘汰 "b"
print(lru.get("b"))   # -1

面试时先写这个版本，然后主动说：“如果面试官要求不用 OrderedDict，我可以用双向链表 + 哈希表实现。“

2）LRU Cache — 双向链表 + 哈希表版

class Node:
    __slots__ = ('key', 'value', 'prev', 'next')
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = self.next = None

class LRUCacheManual:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        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) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_tail(node)
        return node.value

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_tail(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self._add_to_tail(node)
            if len(self.cache) > self.capacity:
                lru_node = self.head.next
                self._remove(lru_node)
                del self.cache[lru_node.key]

3）带过期时间的缓存（TTL Cache）思路

在 LRU 基础上，存储 (value, expire_time)，get 时惰性检查是否过期。核心改动：put 时记录 time.time() + ttl，get 时比较当前时间，过期则删除返回 None。可额外加 cleanup() 方法定期清理。

4）重试装饰器（带指数退避）

import time
import functools
import random

def retry(max_retries=3, base_delay=1.0, backoff=2.0, exceptions=(Exception,)):
    """delay = base_delay * backoff^attempt + jitter"""
    def decorator(func):
        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            for attempt in range(max_retries + 1):
                try:
                    return func(*args, **kwargs)
                except exceptions as e:
                    if attempt == max_retries:
                        raise
                    delay = base_delay * (backoff ** attempt)
                    jitter = random.uniform(0, delay * 0.1)
                    time.sleep(delay + jitter)
        return wrapper
    return decorator

@retry(max_retries=3, base_delay=0.5, exceptions=(ConnectionError,))
def fetch_api(url):
    ...

要点：指数退避避免雪崩，jitter 避免多客户端同时重试，functools.wraps 保留元信息。

5）限流器 — 滑动窗口

import time
from collections import deque

class SlidingWindowLimiter:
    def __init__(self, max_requests: int, window_size: float):
        self.max_requests = max_requests
        self.window_size = window_size
        self.requests = deque()

    def allow(self) -> bool:
        now = time.time()
        while self.requests and self.requests[0] <= now - self.window_size:
            self.requests.popleft()
        if len(self.requests) < self.max_requests:
            self.requests.append(now)
            return True
        return False

# 每秒最多 3 次
limiter = SlidingWindowLimiter(max_requests=3, window_size=1.0)
for i in range(5):
    print(f"请求 {i+1}: {'允许' if limiter.allow() else '拒绝'}")

6）限流器 — 令牌桶

import time

class TokenBucket:
    """以固定速率生成令牌，请求消耗令牌，允许突发流量"""
    def __init__(self, rate: float, capacity: int):
        self.rate = rate
        self.capacity = capacity
        self.tokens = capacity
        self.last_time = time.time()

    def allow(self, tokens=1) -> bool:
        now = time.time()
        self.tokens = min(self.capacity, self.tokens + (now - self.last_time) * self.rate)
        self.last_time = now
        if self.tokens >= tokens:
            self.tokens -= tokens
            return True
        return False

原理展开

1. LRU 的时间复杂度分析

操作OrderedDict 版双向链表+哈希表版
getO(1)O(1)
putO(1)O(1)
淘汰O(1) popitemO(1) 删头节点

两个版本时间复杂度相同，但面试官可能要求手写链表版来考察数据结构基本功。

2. 为什么用哨兵节点？

哨兵节点消除了空链表和边界条件的特殊处理，所有插入/删除操作统一，不需要判断 head/tail 是否为空。

3. 滑动窗口 vs 令牌桶对比

维度滑动窗口令牌桶
突发流量不允许超过窗口限制允许（桶满时可突发）
实现复杂度简单（deque）中等（需计算令牌）
内存存储每个请求时间戳只存几个数值
适用场景严格限流允许短时突发

4. 面试时怎么讲思路

  1. 明确需求：“LRU 需要 O(1) 的 get 和 put，超过容量淘汰最久未使用的”
  2. 选型：“哈希表保证 O(1) 查找，双向链表保证 O(1) 的移动和删除”
  3. 写代码：先写数据结构，再写核心方法
  4. 测试：给一两个用例验证
  5. 扩展：“如果要线程安全，可以加锁；如果要分布式，可以用 Redis”

易错点

  • LRU 的 put 忘记处理 key 已存在的情况 已存在时要更新值并移到末尾，不能直接插入新节点。

  • 双向链表删除节点后忘记从哈希表中删除 链表和哈希表必须同步操作。

  • 重试装饰器忘记 functools.wraps 不加的话原函数的 __name__、__doc__ 会丢失。

  • 限流器在多线程下不安全 len() 检查 + append 不是原子操作，需要加锁。

  • 指数退避没有上限 要设 max_delay，否则等待时间会爆炸。

  • 令牌桶的 tokens 可能变成负数 先 _refill 再检查，不要先扣再补。

记忆技巧

  • LRU = 淘汰最老的：链表头是最老的，尾是最新的。
  • 哨兵节点 = 虚拟边界：不存数据，只为让代码统一。
  • 指数退避 = 越失败等越久：1s → 2s → 4s → 8s…
  • 令牌桶 = 水龙头匀速滴水：桶满了溢出（拒绝），有水就能用（允许）。
  • 面试手撕三步走：说思路 → 写核心 → 提扩展。

面试速答版

LRU Cache 的核心是 O(1) 的 get/put + 淘汰最久未使用。最快的实现方式是 OrderedDict（move_to_end + popitem），底层原理是双向链表 + 哈希表。面试时先写 OrderedDict 版展示思路清晰，再补充手写链表版展示基本功。重试装饰器的关键是指数退避 + jitter 防雪崩。限流器常见两种：滑动窗口（严格限流）和令牌桶（允许突发）。这些题的共同点是：数据结构选型要对、时间复杂度要清楚、边界条件要处理好，然后主动提出线程安全和分布式扩展方向。

Related · 常用容器与迭代
dict底层与哈希手撕题：LRU 与常见设计迭代器生成器与yield