复习日 / Review Day — Day 90

🔄 复习日 / Review Day

今天是第 90 天，也是第 18 个复习日！回顾过去4天的内容 (Day 86-89)。

回顾主题 / Topics Covered:

• Day 86: Design Twitter (Heap) · Configuration Management (pydantic-settings, 12-Factor)
• Day 87: Find Median from Data Stream (Two Heaps) · Logging Best Practices (structlog, Correlation IDs)
• Day 88: Subsets (Backtracking #1/9) · Feature Flags (Simple → LaunchDarkly)
• Day 89: Combination Sum (Backtracking #2/9) · Mocking (unittest.mock)

📝 Quick Quiz — 3 Mini-Reviews

Q1: [💻 Algorithms — 回溯模式 Backtracking]

Combination Sum 和 Subsets 都用回溯模板，但有两个关键区别。说出这两个区别，并解释为什么 Combination Sum 递归时用 backtrack(i, ...) 而不是 backtrack(i+1, ...)。

Both Combination Sum and Subsets use the backtracking template, but they differ in two key ways. Name them, and explain why Combination Sum uses backtrack(i, ...) instead of backtrack(i+1, ...).

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

两个关键区别 / Two Key Differences:

1. 终止条件不同 / Different base cases:

- Subsets: 每个节点都加入结果（遍历完所有选项）

- Combination Sum: 只有 remaining == 0 时才加入结果；remaining < 0 时剪枝

1. 是否允许重复 / Element reuse:

- Subsets: backtrack(i+1, ...) — 每个元素只用一次，不回头

- Combination Sum: backtrack(i, ...) — 同一个元素可以重复选，i 不往后移

为什么 i 不后移？/ Why not advance i?

因为题目允许同一个数字无限次使用（candidates 可重复选）。用 i 而非 i+1 表示：下次递归时我还可以再选这个数字。

核心洞察：start 的移动方向控制了"去重"的方式：

• i+1 → 不重用（Subsets, Permutations with dedup）
• i → 允许重用（Combination Sum）
• 0 + visited → 全排列（Permutations）

</details>

Q2: [🐍 Python Craft — Mocking]

以下代码有一个常见的 mocking 错误。指出问题并给出修复方案。

The following code has a common mocking mistake. Identify the issue and fix it.

# myapp/payment.py
import stripe

class PaymentService:
    def charge(self, amount):
        return stripe.Charge.create(amount=amount)

# test_payment.py
from unittest.mock import patch
from myapp.payment import PaymentService

@patch("stripe.Charge.create")  # ← Is this correct?
def test_charge(mock_create):
    mock_create.return_value = {"id": "ch_123"}
    svc = PaymentService()
    result = svc.charge(1000)
    assert result == {"id": "ch_123"}

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

问题 / The Bug:

@patch("stripe.Charge.create") patches the object in the stripe module, but myapp/payment.py has already imported stripe and holds a reference to it. For this specific case it happens to work because stripe.Charge.create is accessed via attribute lookup at call time — but the best practice is to always patch where the name is used, not where it's defined.

修复 / Fix:

# Patch in the module under test
@patch("myapp.payment.stripe.Charge.create")
def test_charge(mock_create):
    mock_create.return_value = {"id": "ch_123"}
    svc = PaymentService()
    result = svc.charge(1000)
    assert result == {"id": "ch_123"}
    mock_create.assert_called_once_with(amount=1000)

黄金规则 / Golden Rule:

Patch where the name is looked up, not where it's defined.

如果代码用 from stripe import Charge，那 patch 路径就是 myapp.payment.Charge.create，不是 stripe.Charge.create。

附加测试 / Bonus — side_effect for error testing:

@patch("myapp.payment.stripe.Charge.create")
def test_charge_declined(mock_create):
    mock_create.side_effect = stripe.error.CardError("Declined", "card_declined", 402)
    with pytest.raises(stripe.error.CardError):
        PaymentService().charge(1000)

</details>

Q3: [🏗️ System Design — Design Twitter / Heap]

在 Design Twitter 题目（LeetCode #355）中，getNewsFeed() 需要从每个关注对象中获取最近的推文并合并为全局 Top 10。用什么数据结构最高效？时间复杂度是多少？

In Design Twitter (LeetCode #355), getNewsFeed() must merge recent tweets from all followed users into a global Top 10. Which data structure is most efficient, and what's the time complexity?

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

最优解：最小堆 (Min-Heap) / Optimal: Min-Heap

思路 / Approach:

• 每个用户维护一个推文列表（按时间戳倒序）
• getNewsFeed 时：把所有关注者（含自己）的最新推文放入最小堆
• 堆按时间戳维护，堆顶是"最小（最旧）"的候选推文
• Pop 10 次 = 全局最近 10 条

import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.timestamp = 0
        self.tweets = defaultdict(list)   # userId → [(ts, tweetId), ...]
        self.following = defaultdict(set)

    def postTweet(self, userId, tweetId):
        self.tweets[userId].append((self.timestamp, tweetId))
        self.timestamp += 1

    def getNewsFeed(self, userId):
        heap = []  # min-heap: (-timestamp, tweetId, userId, index)
        candidates = self.following[userId] | {userId}

        for uid in candidates:
            tweets = self.tweets[uid]
            if tweets:
                idx = len(tweets) - 1
                ts, tid = tweets[idx]
                heapq.heappush(heap, (-ts, tid, uid, idx))

        result = []
        while heap and len(result) < 10:
            neg_ts, tid, uid, idx = heapq.heappop(heap)
            result.append(tid)
            if idx > 0:  # more tweets from this user
                ts, ntid = self.tweets[uid][idx - 1]
                heapq.heappush(heap, (-ts, ntid, uid, idx - 1))
        return result

复杂度 / Complexity:

• postTweet: O(1)
• getNewsFeed: O(F·log F) where F = # followed users (heap ops)
• Space: O(F) for the heap at any time

为什么用最小堆而非最大堆？/ Why min-heap with negated timestamp?

Python's heapq is a min-heap. We negate timestamps so the "largest" (most recent) timestamp is treated as the smallest value in the heap.

</details>

💡 复习巩固记忆，螺旋式上升。回溯模板 + Mocking 黄金规则 + 堆的多路合并 — 三个高频考点，掌握了面试无敌！

Spaced repetition builds mastery. Backtracking templates + mocking rules + heap-based merge — three high-frequency interview patterns, nail these and you're unstoppable!

📅 明天继续新内容！Day 91 starts tomorrow!