🔄 复习日 Day 55 / Review Day 55

📊 NeetCode: 46/150 · SysDesign: 45/40 · Behavioral: 45/40 · Frontend: 37/50 · AI: 22/30

🔥 54-day streak!

今天是复习日！回顾 Day 51–54 的内容。

Today is a review day! Let's revisit Days 51–54.

📝 Quick Quiz — 3 Mini-Reviews

Q1: [🏗️ System Design] From Day 51 — Distributed File System (HDFS/GFS)

HDFS 把一个大文件分成多个 chunk 存在不同 DataNode 上。NameNode 挂掉了，会发生什么？Google GFS 是怎么处理这个单点故障问题的？

HDFS splits files into chunks across DataNodes. The NameNode goes down — what happens? How does GFS address this single point of failure?

<details>

<summary>显示答案 / Show Answer</summary>

NameNode 是 HDFS 的元数据中心，挂掉后整个集群无法读写（因为没人知道数据在哪）。

• HDFS 方案: Secondary NameNode 定期做 checkpoint，但它不是热备，故障恢复需要时间。HDFS HA 方案用两个 NameNode (Active/Standby) + ZooKeeper 自动切换。
• GFS 方案: GFS 也是单 Master，但通过 operation log + checkpoint 到多副本持久化来减少恢复时间；同时 chunk lease 机制允许 chunk server 之间直接传输数据，降低 Master 压力。
• 核心洞察: 元数据服务的高可用比数据服务更难，因为元数据必须强一致。

</details>

Q2: [⚙️ Algorithms] From Day 53 — Reverse Nodes in K-Group

给你一个链表和整数 K，每 K 个节点翻转一组，不足 K 个的保持原样。这道题和"翻转整个链表"有什么关键区别？空间复杂度能做到 O(1) 吗？

Given a linked list and integer K, reverse every K-group; leave the tail as-is if fewer than K nodes remain. What's the key difference from reversing the whole list? Can you achieve O(1) space?

<details>

<summary>显示答案 / Show Answer</summary>

关键区别：需要先"看前方"确认剩余节点 ≥ K 才翻转，否则保留。

核心步骤：
1. 先检查从当前位置往后是否还有 K 个节点（不够就停止）
2. 翻转这 K 个节点（标准链表翻转）
3. 将翻转后的头接到上一组的尾部
4. 将这组的尾部（原头部）连到下一组
5. 前进到下一组起点，重复

空间复杂度: 迭代实现可以做到 O(1)；递归实现是 O(N/K) 栈空间。面试中首选迭代。

最容易出 bug 的地方: 翻转前忘记断开与后续节点的连接，导致成环。

</details>

Q3: [🐍 Python Craft] From Day 54 — GIL Deep Dive

Python 的 GIL 到底保护的是什么？为什么 I/O 密集型任务用多线程有效，而 CPU 密集型任务无效？什么时候应该用 multiprocessing 代替 threading？

What exactly does Python's GIL protect? Why does multi-threading work for I/O-bound but not CPU-bound tasks? When should you reach for multiprocessing instead?

<details>

<summary>显示答案 / Show Answer</summary>

GIL (Global Interpreter Lock) 保护的是 CPython 解释器内部的引用计数机制，防止多线程同时修改对象引用计数导致内存损坏。

• I/O 密集型有效的原因: 线程在等待 I/O（网络、磁盘）时会主动释放 GIL，让其他线程运行。所以 10 个线程各自等待网络请求，总体吞吐量是单线程的 ~10x。
• CPU 密集型无效的原因: 纯计算不需要等待外部，GIL 每隔 ~5ms 才强制切换一次。多线程 Python 在 CPU 密集任务上实际上是串行的，切换开销反而更慢。
• 什么时候用 multiprocessing: 需要并行 CPU 计算时——每个进程有独立的 GIL，可以真正并行。代价是进程间通信开销 + 内存不共享（需要序列化）。
• 实用规则: I/O 密集 → threading 或 asyncio；CPU 密集 → multiprocessing 或 C 扩展。

</details>

🎯 本周主题 / This Week's Theme

Days 51–54 深入 Expert 阶段的核心挑战：分布式系统的边界情况（多区域、分布式文件系统）、链表的高级操作（K 组翻转、合并 K 个链表）、以及 Python 并发的底层原理。

这些话题的共同点是：答案不只是"怎么做"，而是"为什么这样做，有什么代价"——这正是 Senior/Staff 面试的核心考查维度。

Days 51–54 pushed deep into Expert-level territory: distributed systems edge cases (multi-region, distributed file systems), advanced linked list ops (K-group reversal, K-way merge), and Python concurrency internals. The common thread: the answer isn't just "how" but "why this approach, and at what cost" — that's the Senior/Staff interview lens.

🔬 Saturday Deep Dive: Merge K Sorted Lists（合并 K 个排序链表）(18 min read)

📊 NeetCode: 46/150 · SysDesign: 45/40 · Behavioral: 45/40 · Frontend: 37/50 · AI: 22/30

🔥 54-day streak!

Overview / 概述

中文：

合并 K 个排序链表是一道经典的 Hard 难度题，频繁出现在 Google、Meta、Amazon 等大厂面试中。它考察你能否将多个已排序的序列高效地合并成一个。表面上看是道链表题，核心却是优先队列（最小堆）的应用——这是面试官真正想看到的思维跳跃。掌握这道题，你同时掌握了堆、链表操作、分治三种核心模式。

English：

Merge K Sorted Lists is a canonical Hard problem that shows up constantly at FAANG. It asks: given K sorted linked lists, produce one sorted linked list. On the surface it's a linked list problem; at its core it's about min-heap / priority queue — that's the insight interviewers are really probing for. Solving this deeply means you also internalize heap operations, linked list pointer manipulation, and divide-and-conquer.

🔗 LeetCode: https://leetcode.com/problems/merge-k-sorted-lists/

📹 NeetCode: https://www.youtube.com/watch?v=q5a5OiGbT6Q

Part 1: Theory / 理论基础 (5 min)

为什么这道题难？/ Why is this hard?

中文：

合并 2 个排序链表很简单：两个指针，谁小移谁。但 K 个链表的问题在于——每次你要从 K 个"候选头节点"中找最小值。如果 K = 1000，每次线性扫描是 O(K)，整体就是 O(NK)，太慢了。

核心洞察：我们只关心每条链表当前的头节点。维护一个大小为 K 的最小堆，每次 pop 出最小节点，append 到结果链表，再把该节点的 next（如果有）push 回堆中。

English：

Merging 2 sorted lists is easy — two pointers, advance the smaller one. But with K lists the problem is: every step you need the minimum among K candidate heads. Naive linear scan per step = O(NK) total. Too slow.

The key insight: we only care about the current head of each list. Keep a min-heap of size K. Each iteration: pop the global minimum, append it to the result, push that node's .next back into the heap (if it exists).

心智模型 / Mental Model

想象 K 条赛道上各有一队运动员按速度排好队，每次你要找出所有"队首"中跑得最慢的（最小值），让他出列加入总排名，然后他让出位置给下一个队友。最小堆就是这个"找最小值"操作的数据结构。

Imagine K running lanes, each sorted by speed. Each round you pick the slowest among all K front-runners, add them to the final ranking, and let the next runner step up in their lane. The min-heap is this "find the minimum among K elements" operation.

复杂度分析 / Complexity

中文： 堆的大小始终是 K，每次 push/pop 是 O(log K)，总共 N 个节点，所以是 O(N log K)。当 K << N 时，这比 O(N log N) 快得多。

English: Heap size stays K; each push/pop is O(log K); we process N nodes total → O(N log K). When K << N, this is substantially faster than O(N log N).

Part 2: Step-by-Step Implementation / 一步一步实现 (8 min)

Approach 1: Brute Force — 暴力解法

中文： 把所有节点值收集到数组，排序，重建链表。简单但浪费空间，面试中用来建立 baseline。

from typing import Optional, List

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_brute(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    """
    Brute force: collect all values, sort, rebuild.
    Time: O(N log N)  Space: O(N)
    """
    all_vals = []
    
    # Step 1: Collect all node values into a flat list
    for head in lists:
        while head:
            all_vals.append(head.val)
            head = head.next
    
    # Step 2: Sort
    all_vals.sort()
    
    # Step 3: Rebuild linked list using a dummy head
    dummy = ListNode(0)
    curr = dummy
    for val in all_vals:
        curr.next = ListNode(val)
        curr = curr.next
    
    return dummy.next

Approach 2: Sequential Merge — 逐一合并

中文： 先合并 list[0] 和 list[1]，结果再和 list[2] 合并……直到处理完所有链表。代码简单，但最坏情况是 O(NK)（当每次合并的结果越来越长时）。

def merge_two(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    """
    Classic two-pointer merge of two sorted linked lists.
    Time: O(m + n)  Space: O(1)
    """
    dummy = ListNode(0)
    curr = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    
    # Attach remaining nodes (at most one of l1/l2 is non-null)
    curr.next = l1 if l1 else l2
    return dummy.next

def merge_k_sequential(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    """
    Merge lists one by one. Time: O(NK)  Space: O(1)
    """
    if not lists:
        return None
    
    result = lists[0]
    for i in range(1, len(lists)):
        result = merge_two(result, lists[i])
    
    return result

Approach 3: Min-Heap — 最优解法 ✅

中文： 用 Python 的 heapq 维护一个大小为 K 的最小堆，堆中每个元素是 (node.val, index, node) 三元组。index 是为了打破 val 相同时的平局（ListNode 对象不支持直接比较）。

import heapq

def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    """
    Min-heap approach.
    Time: O(N log K)  Space: O(K) for the heap
    
    Key trick: store (val, index, node) in heap.
    - val: for comparison (heapq is a min-heap by default)
    - index: tiebreaker when two nodes have equal val (ListNode isn't comparable)
    - node: the actual ListNode we need
    """
    dummy = ListNode(0)
    curr = dummy
    
    heap = []
    
    # Step 1: Initialize heap with the head of each list
    for i, node in enumerate(lists):
        if node:
            # Push (value, unique_index, actual_node)
            heapq.heappush(heap, (node.val, i, node))
    
    # Step 2: Process until heap is empty
    while heap:
        val, i, node = heapq.heappop(heap)  # Get global minimum
        
        curr.next = node          # Append to result list
        curr = curr.next
        
        if node.next:
            # Push the next node from the same list back into the heap
            heapq.heappush(heap, (node.next.val, i, node.next))
    
    return dummy.next


# ─── Test it ───────────────────────────────────────────────────────────────
def build_list(vals):
    """Helper: build a linked list from a Python list."""
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next

def to_python_list(head):
    """Helper: convert linked list back to Python list for easy assertion."""
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

if __name__ == "__main__":
    # Test case 1: standard case
    lists = [
        build_list([1, 4, 5]),
        build_list([1, 3, 4]),
        build_list([2, 6]),
    ]
    result = merge_k_lists(lists)
    assert to_python_list(result) == [1, 1, 2, 3, 4, 4, 5, 6]
    print("Test 1 passed:", to_python_list(result))
    
    # Test case 2: empty input
    assert merge_k_lists([]) is None
    print("Test 2 passed: empty input returns None")
    
    # Test case 3: single empty list
    assert merge_k_lists([None]) is None
    print("Test 3 passed: [None] returns None")
    
    # Test case 4: single list
    single = [build_list([1, 2, 3])]
    result = merge_k_lists(single)
    assert to_python_list(result) == [1, 2, 3]
    print("Test 4 passed:", to_python_list(result))

Approach 4: Divide & Conquer — 分治法

中文： 和归并排序一样，把 K 个链表分成两组，各自递归合并，再合并两组的结果。时间复杂度和堆相同，但空间复杂度更好（只有 O(log K) 的递归栈）。

def merge_k_divide_conquer(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    """
    Divide & conquer — like merge sort on lists.
    Time: O(N log K)  Space: O(log K) recursion stack
    
    Round 1: merge pairs  [0+1, 2+3, 4+5, ...]  → K/2 lists
    Round 2: merge pairs  [0+1, 2+3, ...]        → K/4 lists
    ...
    log2(K) rounds total, each round processes N nodes → O(N log K)
    """
    if not lists:
        return None
    
    def helper(left: int, right: int) -> Optional[ListNode]:
        if left == right:
            return lists[left]         # Base case: single list
        if left + 1 == right:
            return merge_two(lists[left], lists[right])  # Base: merge pair
        
        mid = (left + right) // 2
        l = helper(left, mid)          # Recurse on left half
        r = helper(mid + 1, right)     # Recurse on right half
        return merge_two(l, r)         # Merge results
    
    return helper(0, len(lists) - 1)

代码执行追踪 / Execution Trace (Min-Heap)

Input: [[1,4,5], [1,3,4], [2,6]]

Part 3: Edge Cases & Gotchas / 边界情况 (2 min)

中文：

1. 空输入 lists = [] → 直接返回 None。忘记这个会导致堆初始化空循环或越界。

1. lists 中有 None 元素 → 初始化堆时跳过 None（if node: 保护）。常见错误：直接 push None。

1. 重复值 → Python 的 heapq 比较元组时，如果第一个元素相等会比较第二个。(val, i, node) 中 i 是唯一的，所以不会尝试比较 ListNode 对象（ListNode 没有实现 lt，会报 TypeError）。这是最经典的面试 bug！

1. K = 1 → 直接返回该链表，代码应该自然处理。

1. 所有链表只有一个节点 → 堆操作正常，只是每次 push 后 node.next 为 None，不会再 push。

English:

1. Empty input → guard at start, return None.

1. None nodes in lists → skip with if node: during init; don't push None to heap.

1. Duplicate values → this is the most common bug: you must use (val, i, node) not (val, node). Python will try to compare ListNode objects as a tiebreaker when values are equal, raising TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'. The index i breaks ties safely.

1. Single list → handled naturally, no special case needed.

1. Very large K with short lists → heap overhead dominates; divide & conquer may be more cache-friendly in practice.

Part 4: Real-World Application / 实际应用 (2 min)

中文：

这个模式在生产系统中无处不在：

1. 日志聚合 (Log Aggregation): Elasticsearch、Splunk 在合并来自多个分片的有序搜索结果时，底层就是 K-way merge。每个分片返回按分数排序的结果，merge 出全局 top-K。

1. 数据库外排序 (External Sort): MySQL/PostgreSQL 在内存不够时，会把数据分成 K 个已排序的"run"写到磁盘，最终用 K-way merge 合并。这就是 SORT 操作慢的本质原因之一。

1. 时间序列数据库 (Time-Series DB): InfluxDB、Prometheus 在查询跨多个时间分区的数据时，需要 merge K 个按时间戳排序的序列——完全相同的问题。

1. 流处理 (Stream Processing): Kafka consumer 从多个 partition 读取消息，如果需要全局有序处理，底层也是 K-way merge。

English:

This exact pattern appears constantly in production:

1. Log aggregation: Elasticsearch merges per-shard sorted results via K-way merge to produce global top-K hits.

1. External sort: When DB sort operations spill to disk, K sorted "runs" are merged back — this is the root cause of slow ORDER BY on large tables.

1. Time-series DBs: InfluxDB and Prometheus merge K time-ordered segments when querying across partitions.

1. Stream processing: Global ordering across Kafka partitions requires K-way merge of per-partition ordered streams.

The key abstraction: anytime you have K pre-sorted streams and need one globally sorted output, min-heap K-way merge is your tool.

Part 5: Interview Simulation / 面试模拟 (3 min)

以下是面试官最常追问的 5 个问题，每题附简短答案。/ These are the 5 most common follow-up questions with brief answers.

Q1: 你为什么在堆里存 (val, i, node) 而不是 (val, node)？

Why store (val, i, node) and not (val, node)?

A: Python's tuple comparison is lexicographic. When two vals are equal, Python tries to compare the next element. ListNode doesn't implement lt, so it raises TypeError. The unique index i ensures the comparison stops there and never reaches the node object.

Q2: 能不能不用 dummy head，直接操作 curr？

Can you avoid the dummy head node?

A: Technically yes, but it requires special-casing the first node (check if curr is None before assigning curr.next). The dummy head pattern eliminates that branch and is idiomatic. In interviews, mentioning this tradeoff shows maturity.

Q3: 堆方案和分治方案，你在生产中更倾向哪个？

Heap vs divide & conquer — which do you prefer in production?

A: Same asymptotic complexity. Heap is simpler to implement iteratively and uses O(K) space. Divide & conquer uses O(log K) stack space and may have better cache behavior for large K. In practice, I'd use the heap for clarity and D&C if K is enormous and memory is tight. The real answer: measure it.

Q4: 如果链表本身是无限流（比如从 Kafka 实时消费），怎么处理？

What if the lists are infinite streams (e.g., Kafka partitions)?

A: The heap approach generalizes perfectly — you never need to hold all N nodes in memory. Just hold K nodes (one per stream) in the heap. As each is consumed, fetch the next element from that stream. This is exactly how stream processors implement ordered merge. Space remains O(K) regardless of stream length.

Q5: 如果要合并 K 个降序链表怎么改？

How would you handle K lists sorted in descending order?

A: Two options: (1) Use a max-heap by negating values heapq.heappush(heap, (-node.val, i, node)). (2) Reverse each list first (O(N) total), merge ascending, reverse result. Option 1 is cleaner. In an interview, mention both and note that Python's heapq is always a min-heap, so negation is the idiomatic workaround.

总结 / Summary

一句话记住： 堆让你在 O(log K) 时间内找到 K 个已知候选中的最小值——这是 K-way merge 一切变体的核心。

One-liner: The heap gives you O(log K) minimum extraction among K known candidates — that's the core of every K-way merge variant you'll ever see.