系统设计中的算法应用

4.3 系统设计中的算法应用

本节摘要：面试的最后一问常是"这个算法工业界怎么用"。本节把全册的进化产物挂到真实组件上：LRU 缓存是哈希表加双向链表的合体，排行榜与调度是堆的主场，社交关系合并是并查集的领地，海量数据统计则靠分治与近似结构变形——完成从做题者到工程师的映射训练。

刷题与工程之间隔着一张映射表

系统设计题考察的不是新知识，而是映射能力：面试官描述个业务组件，你能否当场指出"它的核心操作是哪种瓶颈、全册哪个结构恰好治这个瓶颈"。本节按组件逐张映射，每个案例都沿用全册的老传统：先给朴素方案，指出它在真实负载下的痛点，再完成进化。

一、LRU 缓存：两个结构的合体

缓存容量有限，满了要淘汰"最久未使用"的条目。需求拆成两个操作：按键读写（要求 O(1)，否则缓存失去意义）、以及维护访问时间顺序并快速摘除最旧条目。哈希表管读写是天然的，但它没有顺序概念；链表有顺序且摘插都是 O(1)，但定位慢。两个短板恰好互补——哈希表存"键到链表节点"的映射，双向链表按访问时间排列。读缓存时命中即把节点摘下搬到链表头；写缓存时插入链表头，超容则删链表尾。每个操作都是常数时间。

class DNode:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                       # 键到节点
        self.head, self.tail = DNode(), DNode()   # 哑头哑尾
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)               # 刚用过，提到最前
        return node.val

    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = DNode(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            last = self.tail.prev
            self._remove(last)
            del self.map[last.key]          # 淘汰最久未用

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
​

这段代码正是 LeetCode 第 146 题，同时也是 Redis 等真实缓存的简化原型——面试里说出这句话，刷题与工程的桥就搭起来了。变式 LFU（淘汰最不常用）在顺序维度上再加频次维度，用堆或频次桶实现，是标准的进阶追问。

二、调度与排行榜：堆的主场

任务调度器的核心操作是"随时取出优先级最高的任务"——这正是第三章堆的存在理由。操作系统调度、消息队列的延迟投递（按执行时间组织的小顶堆）、订单簿撮合（按价格与时间的双堆），全是同一模式。实时排行榜则是 TopK 的流式版本：热度值不断更新，随时要前 k 名，小顶堆维护候选区，命中淘汰线才替换。设计题的答题模板由此成型：先问清楚核心操作的频率与延迟要求，再报出"这个操作我准备用什么结构、代价多少"，最后讨论数据量超内存时怎么办。

三、海量数据：装不下就变形

数据量大到单机内存装不下时，精确解让位于变形与近似。经典追问"十亿个查询词找频率前十"：单机放不下计数表，先哈希分片把相同词路由到同一分片（保证计数完整），各分片各自堆式 TopK，再汇总归并——分治思想在系统尺度的重演。判断"某元素是否见过"且允许极小误判时，布隆过滤器用位数组加多重哈希，以近似的代价把空间压到标量的几十分之一，典型落点是缓存穿透防护。判断"两组用户是否有关联"时，并查集在线合并关系；离线批量场景则常换成图遍历。这些变形的共同哲学：数据规模突破内存时，要么分片保持精确，要么牺牲精度换取空间，选择权在业务对错误的容忍度。

刷题结构到系统组件的映射表

四、答题节奏的进化

系统设计环节的加分动作可以总结成套话术：先复述需求并问清规模（每秒多少请求、数据多大、延迟要求多少）；再给出核心操作的抽象（这本质是取最值、是前缀匹配、还是连通判断）；然后报结构选型与复杂度；最后主动讨论规模突破内存时的变形。你会发现这套话术就是全册进化链的口语版——找到瓶颈、匹配结构、说清代价。面试官要听的从来不是你背过多少题，而是你脑子里有没有这条链。

本节要点回顾

• LRU 等于哈希表加双向链表：定位与顺序各取所长，第 146 题即其原型；
• 调度与排行榜是堆的领地：核心操作是动态最值，堆是唯一对数级答案；
• 海量数据两条路：哈希分片保精确，近似结构（布隆过滤器）省空间；
• 答题模板四步：问规模、抽象操作、报结构与复杂度、讨论超内存变形；
• 映射能力是最后一跃：面试官要听推导过程，不是名词背诵。

全册四条进化链到此汇合：度量衡、策略、专用结构、工程映射。愿你带着"暴力解、找瓶颈、换洞察、达最优"的链式思维，走进任何一场面试。