演算法題型與 Appier 真題

準備策略：Appier coding 面試長什麼樣 高頻

綜合網路上的面試心得，Appier 後端（含實習轉正）的 coding 關卡有幾個明顯特徵：

• 難度落在 LeetCode easy–medium：Valid Parentheses（LC 20）、含 * 的版本（LC 678）、中等字串處理、graph DFS。很少出現需要冷門技巧的 hard 題。
• 題目常被「包裝」：不會直接說「這是 LC 56」，而是「廣告有多個投放時段，請算出實際有在投放的時間」；不說「hash map join」，而是「有兩個資料來源的 user attributes，請合併」。你要能把業務敘述翻譯成資料結構問題。
• 追問是主菜：寫出第一版只是開始。常見追問鏈是「DFS 寫完 → 能不能列出所有路徑（backtracking）→ 能不能用 DP 優化」、「遞迴能不能改掉」、「資料量到上億筆怎麼辦」。
• 重視工程品質：take-home（例如合併兩個 JSON 檔）會看程式結構、錯誤處理、測試、命名，而不只是「能跑」。
• 會延伸到系統面：合併兩份資料 → 「資料放不進記憶體怎麼辦」→ external sort / hash partition / Spark join，這部分在 第 12 章 詳談。

準備優先順序

1. 先把本章 Part B 的真題全部自己寫一遍（不看解答），寫完再對照追問。這些是「被問到機率最高」的題目。
2. 熟練 Python 工具箱：Counter、defaultdict、deque、heapq、bisect、functools.cache。白板題用對工具可以省一半程式碼，也顯示你精通 Python（職缺必備條件）。
3. 按模式刷題（Part C），每個模式先做 2–3 題代表題，抓住「看到什麼訊號就想到什麼模式」。
4. 練習口說：邊寫邊講，用計時器模擬 45 分鐘一輪（5 分鐘釐清、5 分鐘講思路、20 分鐘寫、10 分鐘測試與追問）。

時間複雜度速查：n 有多大、能接受多慢 基礎

看到輸入範圍的第一秒就應該推估目標複雜度。粗略經驗：C++ 每秒約可做 10⁸ 次簡單運算；CPython 慢上數十倍，粗估每秒 10⁷ 量級的簡單操作（迴圈內做加法、dict 查詢）。面試沒有 OJ 計時，但面試官會用 n 的大小暗示期待的解法。

Python 內建操作的複雜度（常被追問）

Python 面試必備工具箱 高頻

用對標準函式庫是「精通 Python」最直接的證明。以下每段程式碼都可直接執行（含 assert），建議自己在 REPL 打一次。

collections：Counter / defaultdict / deque / OrderedDict

from collections import Counter, OrderedDict, defaultdict, deque

# --- Counter：計數器（dict 的子類別） ---
c = Counter("abracadabra")
assert c["a"] == 5 and c["z"] == 0               # 不存在的 key 回傳 0，不會 KeyError
assert c.most_common(2) == [("a", 5), ("b", 2)]  # 同次數時依首次出現順序
assert Counter("aab") - Counter("ab") == Counter({"a": 1})   # 相減會丟掉 <= 0 的項目
assert (Counter("aab") & Counter("abb")) == Counter({"a": 1, "b": 1})  # 交集取 min
assert (Counter("aab") | Counter("abb")) == Counter({"a": 2, "b": 2})  # 聯集取 max
assert Counter("listen") == Counter("silent")    # 判斷 anagram
assert c.total() == 11                           # Python 3.10+

# --- defaultdict：自動初始化預設值 ---
graph: defaultdict[str, list[str]] = defaultdict(list)
for u, v in [("a", "b"), ("a", "c"), ("b", "c")]:
    graph[u].append(v)                           # 不用先判斷 key 是否存在
assert graph["a"] == ["b", "c"]
assert "z" not in graph                          # 用 in 檢查不會建立 key
_ = graph["z"]                                   # 但「讀取」不存在的 key 會建立它！
assert graph["z"] == [] and "z" in graph

nested = defaultdict(lambda: defaultdict(int))   # 兩層計數：campaign -> event -> count
nested["c1"]["click"] += 1
assert nested["c1"]["click"] == 1

# --- deque：雙端佇列，兩端操作皆 O(1) ---
q: deque[int] = deque([1, 2, 3])
q.appendleft(0)
q.append(4)
assert q.popleft() == 0 and q.pop() == 4
window = deque(maxlen=3)                         # 固定長度：超過自動丟掉最舊的
for x in range(5):
    window.append(x)
assert list(window) == [2, 3, 4]
q.rotate(1)                                      # 向右旋轉
assert list(q) == [3, 1, 2]

# --- OrderedDict：保留順序 + move_to_end / popitem(last=False) ---
od: OrderedDict[str, int] = OrderedDict(a=1, b=2, c=3)
od.move_to_end("a")                              # 移到最後（LRU 的「最近使用」）
assert list(od) == ["b", "c", "a"]
assert od.popitem(last=False) == ("b", 2)        # 彈出最舊的（LRU 淘汰）

heapq 與 bisect

import bisect
import heapq

# --- heapq：min-heap（Python 只有 min-heap） ---
nums = [5, 1, 8, 3, 2]
heapq.heapify(nums)                              # O(n) 原地建堆
assert nums[0] == 1                              # nums[0] 永遠是最小值
heapq.heappush(nums, 0)
assert heapq.heappop(nums) == 0

# max-heap：存負值
max_heap: list[int] = []
for x in [5, 1, 8]:
    heapq.heappush(max_heap, -x)
assert -max_heap[0] == 8

# tuple 會逐欄比較：(priority, 序號, payload)，加序號避免 payload 不可比較
tasks: list[tuple[int, int, dict]] = []
for seq, (prio, payload) in enumerate([(2, {"id": "b"}), (1, {"id": "a"}), (2, {"id": "c"})]):
    heapq.heappush(tasks, (prio, seq, payload))
assert [heapq.heappop(tasks)[2]["id"] for _ in range(3)] == ["a", "b", "c"]

assert heapq.nlargest(2, [4, 1, 7, 3]) == [7, 4]          # O(n log k)
assert heapq.nsmallest(2, ["bb", "a", "ccc"], key=len) == ["a", "bb"]
assert list(heapq.merge([1, 4, 7], [2, 5], [3])) == [1, 2, 3, 4, 5, 7]  # 合併已排序序列（惰性）

# --- bisect：已排序陣列上的二分搜尋 ---
a = [1, 2, 2, 2, 5]
assert bisect.bisect_left(a, 2) == 1     # 第一個 >= 2 的位置
assert bisect.bisect_right(a, 2) == 4    # 第一個 > 2 的位置
assert bisect.bisect_right(a, 2) - bisect.bisect_left(a, 2) == 3   # 2 出現次數
assert bisect.bisect_left(a, 3) == 4     # 3 不存在：回傳插入點
bisect.insort(a, 3)                      # 插入並維持排序（搬移是 O(n)）
assert a == [1, 2, 2, 2, 3, 5]

# Python 3.10+ 支援 key=：在依 ts 排序的事件中找第一個 ts >= 15 的事件
events = [(10, "imp"), (20, "click"), (30, "imp")]
i = bisect.bisect_left(events, 15, key=lambda e: e[0])
assert events[i] == (20, "click")

itertools、functools 與排序

import itertools
import operator
from functools import cache, cmp_to_key, lru_cache, reduce

assert list(itertools.accumulate([1, 2, 3, 4])) == [1, 3, 6, 10]               # prefix sum
assert list(itertools.accumulate([1, 2, 3], initial=0)) == [0, 1, 3, 6]        # 含前導 0
assert list(itertools.accumulate([3, 1, 4, 1], max)) == [3, 3, 4, 4]           # running max
assert list(itertools.combinations("abc", 2)) == [("a", "b"), ("a", "c"), ("b", "c")]
assert len(list(itertools.permutations(range(3)))) == 6
assert list(itertools.product([0, 1], repeat=2)) == [(0, 0), (0, 1), (1, 0), (1, 1)]
assert [(k, len(list(g))) for k, g in itertools.groupby("aaabbc")] == [("a", 3), ("b", 2), ("c", 1)]
assert list(itertools.pairwise([1, 2, 4])) == [(1, 2), (2, 4)]                 # 3.10+
assert list(itertools.chain([1], [2, 3])) == [1, 2, 3]
assert list(itertools.islice(itertools.count(10), 3)) == [10, 11, 12]
assert reduce(operator.mul, [1, 2, 3, 4]) == 24

@cache                     # 等同 lru_cache(maxsize=None)，3.9+
def fib(n: int) -> int:
    return n if n < 2 else fib(n - 1) + fib(n - 2)
assert fib(80) == 23416728348467685

@lru_cache(maxsize=1024)   # 有上限的快取，適合輸入空間大的情況
def square(x: int) -> int:
    return x * x
square(3)
assert square.cache_info().currsize == 1

# sorted + key：多欄位排序，數字欄位用負號做降冪
words = ["bb", "a", "ccc", "aa"]
assert sorted(words, key=lambda w: (-len(w), w)) == ["ccc", "aa", "bb", "a"]

# cmp_to_key：自訂比較函式（LC 179 Largest Number）
def largest_number(nums: list[int]) -> str:
    strs = [str(x) for x in nums]
    strs.sort(key=cmp_to_key(lambda a, b: -1 if a + b > b + a else (1 if a + b < b + a else 0)))
    out = "".join(strs)
    return "0" if out[0] == "0" else out
assert largest_number([3, 30, 34, 5, 9]) == "9534330"
assert largest_number([0, 0]) == "0"

字串與其他常用操作

s = "  Hello, Appier World  "
assert s.strip().lower() == "hello, appier world"
assert "a,b,,c".split(",") == ["a", "b", "", "c"]          # 指定分隔符會保留空字串
assert " a  b ".split() == ["a", "b"]                       # 不帶參數：依空白切且去掉空字串
assert "-".join(["2024", "05", "01"]) == "2024-05-01"
assert "abc"[::-1] == "cba"
assert ord("b") - ord("a") == 1 and chr(ord("a") + 2) == "c"
assert "a1".isalnum() and "12".isdigit() and "ab".isalpha()
key, sep, value = "campaign=c1".partition("=")             # 比 split 安全：一定回傳三段
assert (key, sep, value) == ("campaign", "=", "c1")
assert "key=a=b".split("=", 1) == ["key", "a=b"]           # maxsplit
assert "abcabc".find("c") == 2 and "abc".find("z") == -1   # find 找不到回 -1；index 會 raise
assert "ab".startswith(("x", "a"))                          # 可傳 tuple

# 組字串：用 list + join，不要在迴圈內 +=
parts: list[str] = []
for i in range(3):
    parts.append(str(i))
assert "".join(parts) == "012"

# 矩陣轉置、方向陣列
matrix = [[1, 2, 3], [4, 5, 6]]
assert [list(row) for row in zip(*matrix)] == [[1, 4], [2, 5], [3, 6]]
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))

# 整數除法陷阱：// 是向負無限大取整
assert -7 // 2 == -4 and int(-7 / 2) == -3 and divmod(7, 2) == (3, 1)
assert float("inf") > 10**18                                # 當作無限大
assert (10**30) + 1 > 10**30                                # Python int 沒有溢位

解題溝通流程：45 分鐘怎麼分配 高頻

演算法面試不是考試，是「和未來同事一起解決問題」的模擬。面試官評分通常包含：溝通、問題分析、程式正確性、程式品質、測試、複雜度分析。即使沒解出最佳解，流程完整也能拿到不錯的分數。

1. 釐清（3–5 分鐘）：輸入型別與規模？可以有重複嗎？空輸入回傳什麼？大小寫有分嗎？輸入是否已排序？可否修改輸入？包裝題要特別問「衝突時以誰為準」。
2. 暴力解先說：「最直覺的做法是兩層迴圈 O(n²)，我先確認這個方向對不對，再優化。」這能避免你悶頭寫錯題。
3. 優化：問自己「哪裡在重複計算？」（→ hash map / memo / prefix sum）、「排序後會不會變簡單？」（→ two pointers / binary search）、「只需要最大/最小的幾個？」（→ heap）、「需要最近的未匹配項？」（→ stack）。
4. 寫程式：變數命名清楚（left/right 而非 i/j 當語意重要時）；先寫函式簽名與型別提示；複雜邏輯拆 helper。
5. 測試：用題目範例 dry run；再測邊界。主動說「我來測幾個 case」，不要等面試官問。
6. 複雜度與延伸：說時間、空間；說還能怎麼改（串流、平行、記憶體受限）。

真題 1–2：Valid Parentheses（LC 20）與含 * 版本（LC 678） 高頻 基礎

這兩題在 Appier 面試心得中反覆出現，通常 LC 20 當暖身，接著直接追問 LC 678。關鍵是你能不能從「stack」自然地過渡到「只需要記錄可能的未配對數量範圍」的思路。

LC 20：Valid Parentheses

題目：給定只含 ()[]{} 的字串，判斷括號是否合法配對（每個左括號都被相同類型的右括號以正確順序關閉）。

思路：「最近一個尚未配對的左括號」必須先被關閉 → 後進先出 → stack。遇到左括號 push；遇到右括號時，stack 頂端必須是對應的左括號，否則不合法。最後 stack 必須為空（沒有多出來的左括號）。

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for ch in s:
        if ch in pairs:                       # 右括號
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        elif ch in "([{":                     # 左括號
            stack.append(ch)
        # 其他字元（若題目允許）直接忽略
    return not stack


assert is_valid("()[]{}")
assert is_valid("{[()]}")
assert is_valid("")
assert not is_valid("(]")
assert not is_valid("([)]")          # 交錯：類型對但順序錯
assert not is_valid("((")            # 剩下未關閉
assert not is_valid("))")            # stack 空時遇右括號
assert is_valid("f(a[0]) { return; }")

複雜度：時間 O(n)，空間 O(n)（最壞全是左括號）。小優化：字串長度為奇數可直接回傳 False。

LC 20 追問

只有一種括號？

不需要 stack，用一個計數器 balance：遇 ( +1、遇 ) −1，過程中不可小於 0，最後須為 0。空間 O(1)。這正是 LC 678 greedy 解的起點。

最少刪除幾個字元讓它合法？（LC 1249）

stack 記錄左括號的 index；遇到無法配對的右括號標記刪除；最後 stack 內剩下的左括號也刪除。

最長合法括號子字串？（LC 32）

stack 放 index，底部放一個「上一個不合法位置」當基準。

產生所有 n 對合法括號？（LC 22）

backtracking，維持 open ≤ n 且 close ≤ open。

def min_remove_to_make_valid(s: str) -> str:
    """LC 1249：刪除最少括號使字串合法。O(n) 時間、O(n) 空間。"""
    chars = list(s)
    open_idx: list[int] = []
    for i, ch in enumerate(chars):
        if ch == "(":
            open_idx.append(i)
        elif ch == ")":
            if open_idx:
                open_idx.pop()
            else:
                chars[i] = ""          # 多出來的右括號
    for i in open_idx:                 # 沒被關閉的左括號
        chars[i] = ""
    return "".join(chars)


def longest_valid_parentheses(s: str) -> int:
    """LC 32：stack 底部永遠是「最後一個無法配對的位置」。"""
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:              # 這個 ')' 無法配對，成為新的基準
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best


def generate_parentheses(n: int) -> list[str]:
    """LC 22：backtracking，輸出數量為 Catalan 數。"""
    res: list[str] = []
    path: list[str] = []

    def backtrack(open_cnt: int, close_cnt: int) -> None:
        if len(path) == 2 * n:
            res.append("".join(path))
            return
        if open_cnt < n:
            path.append("(")
            backtrack(open_cnt + 1, close_cnt)
            path.pop()
        if close_cnt < open_cnt:
            path.append(")")
            backtrack(open_cnt, close_cnt + 1)
            path.pop()

    backtrack(0, 0)
    return res


assert min_remove_to_make_valid("lee(t(c)o)de)") == "lee(t(c)o)de"
assert min_remove_to_make_valid("a)b(c)d") == "ab(c)d"
assert min_remove_to_make_valid("))((") == ""
assert longest_valid_parentheses(")()())") == 4
assert longest_valid_parentheses("(()") == 2
assert longest_valid_parentheses("") == 0
assert generate_parentheses(3) == ["((()))", "(()())", "(())()", "()(())", "()()()"]

LC 678：Valid Parenthesis String（含 *）

題目：字串只含 (、)、*，其中 * 可以當作 (、) 或空字串。判斷是否有某種解讀讓字串合法。

思路演進（面試時照這個順序講，展示你如何一步步優化）：

1. 暴力：每個 * 有 3 種選擇，枚舉 3ᵏ 種組合再用計數器檢查。k 可達 n，指數時間。
2. 記憶化 DFS：狀態只需要 (i, open_cnt)——走到第 i 個字元、目前未配對的左括號數。i 有 n 種、open_cnt 最多 n 種 → O(n²) 狀態，每個 O(1) 轉移 → O(n²)。
3. 狀態集合：把同一個 i 的所有可能 open_cnt 收成集合，逐字元推進。
4. 觀察：這個集合永遠是連續區間（每步都是 ±1 或 0 的擴張）→ 只需記錄區間 [lo, hi] → O(n) 時間、O(1) 空間的 greedy。

from functools import cache


def check_valid_string(s: str) -> bool:
    """Greedy：[lo, hi] 是「未配對左括號數」所有可能值的範圍。O(n) / O(1)。"""
    lo = hi = 0
    for ch in s:
        if ch == "(":
            lo += 1
            hi += 1
        elif ch == ")":
            lo -= 1
            hi -= 1
        else:              # '*'：可能是 ')'(-1)、''(0)、'('(+1)
            lo -= 1
            hi += 1
        if hi < 0:         # 就算所有 * 都當 '(' 仍不夠抵銷 ')'
            return False
        lo = max(lo, 0)    # 未配對數不可能為負：把讓它變負的 '*' 改當空字串
    return lo == 0         # 0 落在可能範圍內


def check_valid_string_dp(s: str) -> bool:
    """記憶化 DFS：狀態 (i, open_cnt)。O(n^2) 時間與空間。"""
    n = len(s)

    @cache
    def dfs(i: int, open_cnt: int) -> bool:
        if open_cnt < 0 or open_cnt > n - i:   # 剪枝：剩下字元不足以關閉
            return False
        if i == n:
            return open_cnt == 0
        ch = s[i]
        if ch == "(":
            return dfs(i + 1, open_cnt + 1)
        if ch == ")":
            return dfs(i + 1, open_cnt - 1)
        return dfs(i + 1, open_cnt + 1) or dfs(i + 1, open_cnt) or dfs(i + 1, open_cnt - 1)

    return dfs(0, 0)


def check_valid_string_states(s: str) -> bool:
    """bottom-up：逐字元維護「所有可能的未配對數」集合，是 DP 到 greedy 的橋樑。"""
    states = {0}
    for ch in s:
        nxt: set[int] = set()
        for k in states:
            if ch in "(*":
                nxt.add(k + 1)
            if ch in ")*" and k > 0:
                nxt.add(k - 1)
            if ch == "*":
                nxt.add(k)
        if not nxt:
            return False
        states = nxt
    return 0 in states


def check_valid_string_two_stacks(s: str) -> bool:
    """兩個 stack 存 index：右括號優先用 '(' 配，再用 '*'；最後 '*' 必須在 '(' 右邊。"""
    opens: list[int] = []
    stars: list[int] = []
    for i, ch in enumerate(s):
        if ch == "(":
            opens.append(i)
        elif ch == "*":
            stars.append(i)
        elif opens:
            opens.pop()
        elif stars:
            stars.pop()
        else:
            return False
    while opens and stars:
        if opens.pop() > stars.pop():   # '*' 在 '(' 左邊，無法當 ')' 關閉它
            return False
    return not opens


cases = {
    "": True, "()": True, "(*)": True, "(*))": True, "*)": True, "(*": True,
    ")(": False, "(((*)": False, "**((": False, "*()(": False, "(*)(": False,
    "((*)(*))((*": False, "(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())": False,
}
for text, expected in cases.items():
    for fn in (check_valid_string, check_valid_string_dp, check_valid_string_states, check_valid_string_two_stacks):
        assert fn(text) == expected, (fn.__name__, text)

真題 3：合併多個資料來源的 User Attributes 高頻 進階

這是 Appier 最具代表性的「包裝題」：表面上是合併兩個 List[dict]，實際上在考 hash join、衝突處理規則、資料不在記憶體時怎麼辦。面試心得提到後續會追問「資料量到上億筆怎麼辦」。

基本版：合併兩個 List[dict] 中相同 id 的資料

題目：給兩個 list，每個元素是含 id 的 dict（例如來自 CRM 與 App SDK 的使用者屬性）。請將相同 id 的資料合併成一筆，回傳合併後的 list。

先釐清（這幾題問出來就已經贏一半）：

• 同一個 list 內 id 會重複嗎？
• 兩邊同一欄位值不同時，以誰為準？（後者覆蓋？時間戳新的？某來源優先？非空優先？）
• 只出現在一邊的 id 要保留嗎？（outer join 還是 inner join）
• 輸出順序有要求嗎？可以修改輸入嗎？
• 資料量多大？放得進記憶體嗎？

from itertools import chain
from typing import Any, Hashable

Record = dict[str, Any]


def merge_by_id(*sources: list[Record], key: str = "id") -> list[Record]:
    """Full outer join by key；後出現的來源覆蓋前面的同名欄位。
    時間 O(總欄位數)，空間 O(合併後資料量)。輸出順序 = id 第一次出現的順序。
    """
    merged: dict[Hashable, Record] = {}
    for rec in chain.from_iterable(sources):
        k = rec[key]
        if k in merged:
            merged[k].update(rec)
        else:
            merged[k] = dict(rec)       # 複製一份，避免修改呼叫端的輸入
    return list(merged.values())


crm = [{"id": 1, "name": "Amy", "tier": "gold"}, {"id": 2, "name": "Bob"}]
sdk = [{"id": 2, "os": "iOS"}, {"id": 1, "os": "Android", "tier": "silver"}, {"id": 3, "os": "iOS"}]

result = merge_by_id(crm, sdk)
assert result == [
    {"id": 1, "name": "Amy", "tier": "silver", "os": "Android"},
    {"id": 2, "name": "Bob", "os": "iOS"},
    {"id": 3, "os": "iOS"},
]
assert crm[0] == {"id": 1, "name": "Amy", "tier": "gold"}   # 輸入沒被改到

為什麼用 dict 而不是雙層迴圈：雙層迴圈對每筆 a 去 b 裡找相同 id 是 O(|A|·|B|)；建 hash index 後是 O(|A| + |B|)。這就是資料庫的 hash join。Python 3.7+ dict 保證插入順序，所以輸出順序是「id 第一次出現的順序」，不需要額外的 OrderedDict。

延伸 1：衝突規則（時間戳、來源優先級、非空優先、集合聯集）

真實的 user profile 合併（例如 CDP / 受眾平台）很少是「後者覆蓋」這麼簡單。常見規則：

from collections import defaultdict
from dataclasses import dataclass
from typing import Any, Hashable, Iterable


@dataclass(frozen=True)
class SourceRecord:
    source: str              # 例如 "crm" / "sdk" / "3rd_party"
    updated_at: int          # epoch 秒
    data: dict[str, Any]


Rank = tuple[int, int]       # (來源優先級, 時間戳)，tuple 比較 = 先比優先級再比時間


def _is_empty(value: Any) -> bool:
    return value is None or (isinstance(value, (str, list, tuple, set, dict)) and len(value) == 0)


def merge_user_attributes(
    records: Iterable[SourceRecord],
    priority: dict[str, int],
    key: str = "user_id",
    union_fields: frozenset[str] = frozenset({"tags"}),
) -> dict[Hashable, dict[str, Any]]:
    """逐欄位（field-level）決定勝者：非空優先 → 來源優先級高者 → 時間較新者。
    union_fields 中的欄位做集合聯集。時間 O(總欄位數)。
    """
    best: dict[Hashable, dict[str, tuple[Rank, Any]]] = defaultdict(dict)
    unions: dict[Hashable, dict[str, set[Any]]] = defaultdict(lambda: defaultdict(set))

    for rec in records:
        uid = rec.data[key]
        rank: Rank = (priority.get(rec.source, 0), rec.updated_at)
        for field, value in rec.data.items():
            if _is_empty(value):
                continue                                   # 非空優先（注意 0 / False 不算空）
            if field in union_fields:
                unions[uid][field].update(value)
                continue
            current = best[uid].get(field)
            if current is None or rank > current[0]:       # 平手時保留先到的，結果可重現
                best[uid][field] = (rank, value)

    result: dict[Hashable, dict[str, Any]] = {}
    for uid, fields in best.items():
        profile = {field: value for field, (_, value) in fields.items()}
        for field, values in unions.get(uid, {}).items():
            profile[field] = sorted(values)                # 排序讓輸出穩定、好測試
        result[uid] = profile
    return result


records = [
    SourceRecord("sdk", 100, {"user_id": 1, "email": "a@x.com", "city": "Taipei", "tags": ["sports"]}),
    SourceRecord("crm", 50, {"user_id": 1, "email": "a@corp.com", "city": None, "tags": ["vip"]}),
    SourceRecord("sdk", 200, {"user_id": 1, "city": "Tokyo"}),
    SourceRecord("sdk", 10, {"user_id": 2, "email": "b@x.com", "tags": []}),
]
merged = merge_user_attributes(records, priority={"crm": 2, "sdk": 1})
assert merged[1] == {"user_id": 1, "email": "a@corp.com", "city": "Tokyo", "tags": ["sports", "vip"]}
assert merged[2] == {"user_id": 2, "email": "b@x.com"}

注意 city 的結果：CRM 的 None 被跳過（非空優先），兩筆 SDK 中 updated_at=200 較新，所以是 Tokyo；email 則因為 CRM 優先級較高，即使時間較舊仍勝出。規則要做成可設定（per-field strategy），面試時說出「我會把衝突規則抽成設定，而不是寫死在 if-else 裡」是工程成熟度的展現。

延伸 2：巢狀 dict 的 deep merge

import copy
from typing import Any


def deep_merge(base: dict[str, Any], override: dict[str, Any]) -> dict[str, Any]:
    """兩邊都是 dict 時遞迴合併，否則 override 勝。不修改輸入。"""
    out = dict(base)
    for k, v in override.items():
        if k in out and isinstance(out[k], dict) and isinstance(v, dict):
            out[k] = deep_merge(out[k], v)
        else:
            out[k] = v
    return out


a = {"id": 1, "device": {"os": "iOS", "ver": "17"}, "geo": {"country": "TW"}}
b = {"id": 1, "device": {"ver": "18", "model": "15 Pro"}}
m = deep_merge(a, b)
assert m == {"id": 1, "device": {"os": "iOS", "ver": "18", "model": "15 Pro"}, "geo": {"country": "TW"}}
assert a["device"]["ver"] == "17"               # 輸入未被修改
assert m["geo"] is a["geo"]                     # 但未合併的子物件是共享參考（淺複製）
safe = deep_merge(copy.deepcopy(a), b)          # 需要完全獨立時先 deepcopy
assert safe["geo"] is not a["geo"]

延伸 3：資料已排序 / 串流進來時的合併

若兩份資料都已依 id 排序（例如從 DB 用 ORDER BY id 讀出、或 Spark 輸出的排序檔），可以用 merge join：兩個指標同步前進，記憶體只需 O(1)，不用把任何一邊整個載入。k 份來源就用 heapq.merge（內部是大小 k 的 heap）。

import heapq
from itertools import groupby
from typing import Any, Iterable, Iterator

Record = dict[str, Any]


def merge_sorted_two(a: Iterable[Record], b: Iterable[Record], key: str = "id") -> Iterator[Record]:
    """兩路 merge join（full outer）。假設各自依 key 遞增且 key 唯一。記憶體 O(1)。"""
    ia, ib = iter(a), iter(b)
    ra, rb = next(ia, None), next(ib, None)
    while ra is not None and rb is not None:
        if ra[key] < rb[key]:
            yield ra
            ra = next(ia, None)
        elif ra[key] > rb[key]:
            yield rb
            rb = next(ib, None)
        else:
            yield {**ra, **rb}
            ra, rb = next(ia, None), next(ib, None)
    while ra is not None:
        yield ra
        ra = next(ia, None)
    while rb is not None:
        yield rb
        rb = next(ib, None)


def merge_sorted_k(sources: list[Iterable[Record]], key: str = "id") -> Iterator[Record]:
    """k 路合併：heapq.merge 在 key 相同時，較前面的來源先輸出（穩定），所以後面的來源覆蓋前面。
    時間 O(N log k)，記憶體 O(k + 同一 id 的紀錄數)。
    """
    stream = heapq.merge(*sources, key=lambda r: r[key])
    for _, group in groupby(stream, key=lambda r: r[key]):
        out: Record = {}
        for rec in group:
            out.update(rec)
        yield out


a = [{"id": 1, "x": 1}, {"id": 3, "x": 3}, {"id": 5, "x": 5}]
b = [{"id": 2, "y": 2}, {"id": 3, "y": 3}]
c = [{"id": 3, "x": 30}, {"id": 6, "z": 6}]
assert list(merge_sorted_two(a, b)) == [
    {"id": 1, "x": 1}, {"id": 2, "y": 2}, {"id": 3, "x": 3, "y": 3}, {"id": 5, "x": 5},
]
assert list(merge_sorted_k([a, b, c])) == [
    {"id": 1, "x": 1}, {"id": 2, "y": 2}, {"id": 3, "x": 30, "y": 3}, {"id": 5, "x": 5}, {"id": 6, "z": 6},
]

延伸 4：資料量上億筆、放不進記憶體怎麼辦

• Hash partition：用 hash(id) % P 把兩份資料各切成 P 個分片檔，同一個 id 一定落在同編號的分片；之後每對分片小到可以放進記憶體做 hash join。這就是 Grace hash join，也是 Spark shuffle join 的原理。
• External sort + merge join：各自外部排序（分塊排序寫檔 → k-way merge），再用上面的 merge_sorted_two 串流合併。
• 交給資料庫或分散式引擎：MySQL 用 INSERT ... ON DUPLICATE KEY UPDATE、MongoDB 用 upsert、Spark 用 df_a.join(df_b, "id", "full_outer") 再用 coalesce 處理欄位衝突。
• 資料傾斜（skew）：某些 id（例如匿名使用者的預設 id）量特別大會拖垮單一分片，需 salting 或先過濾。

詳細的分散式 join、external sort、資料傾斜處理請見 第 12 章 大數據處理。

真題 4：合併兩個 JSON 檔（take-home） 進階

這是面試心得中提到的 take-home 題（與「設計發送 LINE 訊息的 API」一起出）。題目通常很短：「寫一個程式合併兩個 JSON 檔」，但評分重點是規格的定義、邊界處理、程式結構與測試。

先定義合併規則

遞迴版本

import json
from typing import Any, Literal

ListStrategy = Literal["replace", "concat", "union", "by_id"]


def _fingerprint(item: Any) -> str:
    """把任意 JSON 值轉成可 hash 的字串（dict 不可 hash，不能直接放進 set）。"""
    return json.dumps(item, sort_keys=True, ensure_ascii=False)


def _union(base: list[Any], override: list[Any]) -> list[Any]:
    seen: set[str] = set()
    out: list[Any] = []
    for item in [*base, *override]:
        fp = _fingerprint(item)
        if fp not in seen:
            seen.add(fp)
            out.append(item)
    return out


def merge_json(base: Any, override: Any, strategy: ListStrategy = "by_id", id_key: str = "id") -> Any:
    if isinstance(base, dict) and isinstance(override, dict):
        out = dict(base)
        for k, v in override.items():
            out[k] = merge_json(base[k], v, strategy, id_key) if k in base else v
        return out
    if isinstance(base, list) and isinstance(override, list):
        return _merge_lists(base, override, strategy, id_key)
    return override


def _merge_lists(base: list[Any], override: list[Any], strategy: ListStrategy, id_key: str) -> list[Any]:
    if strategy == "replace":
        return list(override)
    if strategy == "concat":
        return [*base, *override]
    if strategy == "union":
        return _union(base, override)
    # by_id：含 id 的物件依 id 合併；其他元素去重後附加
    out = list(base)
    pos = {x[id_key]: i for i, x in enumerate(out) if isinstance(x, dict) and id_key in x}
    seen = {_fingerprint(x) for x in out}
    for item in override:
        if isinstance(item, dict) and id_key in item:
            if item[id_key] in pos:
                i = pos[item[id_key]]
                out[i] = merge_json(out[i], item, strategy, id_key)
            else:
                pos[item[id_key]] = len(out)
                out.append(item)
        elif (fp := _fingerprint(item)) not in seen:
            seen.add(fp)
            out.append(item)
    return out


def merge_json_files(path_a: str, path_b: str, out_path: str, strategy: ListStrategy = "by_id") -> None:
    with open(path_a, encoding="utf-8") as f:
        a = json.load(f)
    with open(path_b, encoding="utf-8") as f:
        b = json.load(f)
    with open(out_path, "w", encoding="utf-8") as f:
        json.dump(merge_json(a, b, strategy), f, ensure_ascii=False, indent=2)


A = {
    "name": "svc", "version": 1, "tags": ["a", "b"],
    "db": {"host": "localhost", "port": 3306, "opts": {"ssl": False}},
    "users": [{"id": 1, "name": "Amy"}, {"id": 2, "name": "Bob"}],
}
B = {
    "version": 2, "tags": ["b", "c"],
    "db": {"host": "db.prod", "opts": {"timeout": 5}},
    "users": [{"id": 2, "role": "admin"}, {"id": 3, "name": "Cat"}],
    "new": True,
}
EXPECTED = {
    "name": "svc", "version": 2, "tags": ["a", "b", "c"],
    "db": {"host": "db.prod", "port": 3306, "opts": {"ssl": False, "timeout": 5}},
    "users": [{"id": 1, "name": "Amy"}, {"id": 2, "name": "Bob", "role": "admin"}, {"id": 3, "name": "Cat"}],
    "new": True,
}
snapshot = json.dumps(A, sort_keys=True)
assert merge_json(A, B) == EXPECTED
assert json.dumps(A, sort_keys=True) == snapshot                       # 輸入未被修改
assert merge_json(A, B, "concat")["tags"] == ["a", "b", "b", "c"]
assert merge_json(A, B, "replace")["users"] == B["users"]
assert merge_json({"x": {"y": 1}}, {"x": 5}) == {"x": 5}               # 型別衝突：override 勝

複雜度：時間 O(N_a + N_b)（每個節點訪問一次；by_id 與 union 多了序列化指紋的成本，與元素大小成正比）；遞迴深度 = JSON 巢狀深度 d，空間 O(d) 堆疊 + 輸出大小。

追問：把遞迴改成迭代（explicit stack）

面試官可能追問「JSON 巢狀很深怎麼辦？」——Python 預設遞迴上限約 1000 層。改法：先 deepcopy base 當作輸出，stack 裡放「待辦工作」(parent 容器, key, 要合併進來的值)，每次 pop 一筆處理，遇到需要往下合併的子節點就 push，而不是遞迴呼叫。

import copy
import json
from typing import Any


def _fingerprint(item: Any) -> str:
    return json.dumps(item, sort_keys=True, ensure_ascii=False)


def merge_json_iterative(
    base: Any, override: Any, strategy: str = "by_id", id_key: str = "id", in_place: bool = False
) -> Any:
    """in_place=True 時直接修改 base 且不複製 override 的值，完全沒有遞迴（適合極深輸入）。"""
    dup = (lambda x: x) if in_place else copy.deepcopy     # deepcopy 本身是遞迴實作
    root = {"_": dup(base)}                                # 包一層，讓根節點也能被「替換」
    stack: list[tuple[Any, Any, Any]] = [(root, "_", override)]
    while stack:
        parent, k, new = stack.pop()
        old = parent[k]
        if isinstance(old, dict) and isinstance(new, dict):
            for nk, nv in new.items():
                if nk in old:
                    stack.append((old, nk, nv))            # 延後處理，取代遞迴呼叫
                else:
                    old[nk] = dup(nv)
        elif isinstance(old, list) and isinstance(new, list):
            if strategy == "replace":
                parent[k] = dup(new)
            elif strategy == "concat":
                old.extend(dup(new))
            elif strategy == "union":
                seen = {_fingerprint(x) for x in old}
                for item in new:
                    if (fp := _fingerprint(item)) not in seen:
                        seen.add(fp)
                        old.append(dup(item))
            else:  # by_id
                pos = {x[id_key]: i for i, x in enumerate(old) if isinstance(x, dict) and id_key in x}
                seen = {_fingerprint(x) for x in old}
                for item in new:
                    if isinstance(item, dict) and id_key in item:
                        if item[id_key] in pos:
                            stack.append((old, pos[item[id_key]], item))   # list 也能當 parent
                        else:
                            pos[item[id_key]] = len(old)
                            old.append(dup(item))
                    elif (fp := _fingerprint(item)) not in seen:
                        seen.add(fp)
                        old.append(dup(item))
        else:
            parent[k] = dup(new)
    return root["_"]


A = {"name": "svc", "version": 1, "tags": ["a", "b"],
     "db": {"host": "localhost", "port": 3306, "opts": {"ssl": False}},
     "users": [{"id": 1, "name": "Amy"}, {"id": 2, "name": "Bob"}]}
B = {"version": 2, "tags": ["b", "c"], "db": {"host": "db.prod", "opts": {"timeout": 5}},
     "users": [{"id": 2, "role": "admin"}, {"id": 3, "name": "Cat"}], "new": True}
assert merge_json_iterative(A, B) == {
    "name": "svc", "version": 2, "tags": ["a", "b", "c"],
    "db": {"host": "db.prod", "port": 3306, "opts": {"ssl": False, "timeout": 5}},
    "users": [{"id": 1, "name": "Amy"}, {"id": 2, "name": "Bob", "role": "admin"}, {"id": 3, "name": "Cat"}],
    "new": True,
}
assert A["db"]["host"] == "localhost"

# 深度 5000 的巢狀物件：遞迴版會 RecursionError，迭代版沒問題
deep_a: dict = {}
deep_b: dict = {}
cur_a, cur_b = deep_a, deep_b
for _ in range(5000):
    cur_a["n"], cur_b["n"] = {}, {}
    cur_a, cur_b = cur_a["n"], cur_b["n"]
cur_a["x"], cur_b["y"] = 1, 2
merged = merge_json_iterative(deep_a, deep_b, in_place=True)
node = merged
while "n" in node:
    node = node["n"]
assert node == {"x": 1, "y": 2}

Take-home 交付清單

• CLI：python merge_json.py a.json b.json -o out.json --list-strategy by_id，用 argparse，錯誤訊息清楚、exit code 正確（檔案不存在、JSON 格式錯誤）。
• 測試：pytest 參數化測試涵蓋每種型別組合、空物件、Unicode、輸入不被修改；可用 tmp_path fixture 測檔案 I/O。
• 大檔案：說明 json.load 會把整個檔案載入記憶體；若是 JSON Lines（每行一筆），可串流處理並用上一題的排序合併；巨大單一 JSON 可用 ijson 之類的串流 parser。
• README：寫清楚合併規則、假設、複雜度、可改進之處。評分者通常先看 README。
• 型別提示 + lint：mypy、ruff 通過；commit 歷史乾淨。

真題 5：Wordle 遊戲實作 高頻 進階

面試心得提到「實作 Wordle，用 hash map / counter」。這題的陷阱是重複字母：大多數人第一版會寫錯。之後常延伸成「設計遊戲類別」與「寫一個 solver」。

規則與題目

秘密單字與猜測都是 5 個字母。對猜測的每個位置回饋：

• G（綠）：字母正確且位置正確。
• Y（黃）：字母存在於秘密單字中但位置不對——但每個秘密字母只能被「用掉」一次。
• B（灰）：其他情況。

例：秘密 CRANE、猜 EERIE。最後一個 E 是綠；秘密裡只有一個 E 且已被綠色用掉，所以前兩個 E 都是灰（naive 解會錯標成黃）；R 在秘密中但位置不對 → 黃。正確答案 BBYBG。

兩趟演算法：先標綠，再用 Counter 標黃

from collections import Counter


def wordle_feedback(secret: str, guess: str) -> str:
    """回傳由 G/Y/B 組成的字串。O(L) 時間，O(字母表) 空間。"""
    if len(secret) != len(guess):
        raise ValueError("secret and guess must have the same length")
    result = ["B"] * len(guess)
    remaining: Counter[str] = Counter()

    # 第一趟：標出綠色；沒被綠色用掉的秘密字母放進 remaining
    for i, (s, g) in enumerate(zip(secret, guess)):
        if s == g:
            result[i] = "G"
        else:
            remaining[s] += 1

    # 第二趟：非綠色位置，若該字母還有剩餘額度就標黃並扣掉額度
    for i, g in enumerate(guess):
        if result[i] == "B" and remaining[g] > 0:
            result[i] = "Y"
            remaining[g] -= 1
    return "".join(result)


assert wordle_feedback("crane", "eerie") == "BBYBG"   # 重複字母：綠色優先佔用
assert wordle_feedback("apple", "allee") == "GYBBG"   # 第二個 l 沒有額度了
assert wordle_feedback("hello", "lolly") == "BYGGB"
assert wordle_feedback("abbey", "babes") == "YYGGB"
assert wordle_feedback("trace", "trace") == "GGGGG"
assert wordle_feedback("speed", "erase") == "YBBYY"

遊戲類別設計

from collections import Counter
from enum import Enum


def wordle_feedback(secret: str, guess: str) -> str:
    result = ["B"] * len(guess)
    remaining = Counter(s for s, g in zip(secret, guess) if s != g)
    for i, (s, g) in enumerate(zip(secret, guess)):
        if s == g:
            result[i] = "G"
        elif remaining[g] > 0:
            result[i] = "Y"
            remaining[g] -= 1
    return "".join(result)


class Status(Enum):
    IN_PROGRESS = "in_progress"
    WON = "won"
    LOST = "lost"


class WordleGame:
    RANK = {"B": 0, "Y": 1, "G": 2}

    def __init__(self, secret: str, dictionary: set[str], max_attempts: int = 6) -> None:
        self.dictionary = {w.lower() for w in dictionary}
        self.secret = secret.lower()
        if self.secret not in self.dictionary:
            raise ValueError("secret must be in dictionary")
        self.max_attempts = max_attempts
        self.history: list[tuple[str, str]] = []
        self.status = Status.IN_PROGRESS

    def guess(self, word: str) -> str:
        if self.status is not Status.IN_PROGRESS:
            raise RuntimeError("game is over")
        word = word.lower()
        if len(word) != len(self.secret):
            raise ValueError(f"word must have {len(self.secret)} letters")
        if word not in self.dictionary:          # 不合法的猜測不消耗次數
            raise ValueError("not in word list")
        fb = wordle_feedback(self.secret, word)
        self.history.append((word, fb))
        if fb == "G" * len(word):
            self.status = Status.WON
        elif len(self.history) >= self.max_attempts:
            self.status = Status.LOST
        return fb

    def keyboard(self) -> dict[str, str]:
        """每個字母目前已知的最佳狀態（G > Y > B），用來畫虛擬鍵盤。"""
        states: dict[str, str] = {}
        for word, fb in self.history:
            for ch, f in zip(word, fb):
                if ch not in states or self.RANK[f] > self.RANK[states[ch]]:
                    states[ch] = f
        return states


words = {"crane", "trace", "grace", "apple", "hello"}
game = WordleGame("trace", words)
assert game.guess("crane") == "YGGBG"
assert game.keyboard()["c"] == "Y" and game.keyboard()["n"] == "B"
try:
    game.guess("zzzzz")
except ValueError:
    pass
assert len(game.history) == 1                      # 不合法的猜測沒被計入
assert game.guess("TRACE") == "GGGGG" and game.status is Status.WON

注意第二版 wordle_feedback 用一行 Counter 生成式建 remaining，再用單一迴圈同時標綠與黃——之所以正確，是因為 remaining 在迴圈開始前就已經排除所有綠色位置的字母，黃色不會吃掉綠色的額度。

延伸：根據 feedback 篩選候選字的 Solver

關鍵洞察：與其手動推導「這個字母不能在位置 2、至少出現 1 次…」等複雜約束，不如直接利用 feedback 函式本身——候選字 w 與歷史一致，若且唯若 feedback(w, guess) == observed 對每一筆歷史都成立。這自動正確處理了重複字母。

from collections import Counter


def wordle_feedback(secret: str, guess: str) -> str:
    result = ["B"] * len(guess)
    remaining = Counter(s for s, g in zip(secret, guess) if s != g)
    for i, (s, g) in enumerate(zip(secret, guess)):
        if s == g:
            result[i] = "G"
        elif remaining[g] > 0:
            result[i] = "Y"
            remaining[g] -= 1
    return "".join(result)


def filter_candidates(candidates: list[str], guess: str, observed: str) -> list[str]:
    """O(|candidates| * L)"""
    return [w for w in candidates if wordle_feedback(w, guess) == observed]


def best_guess(candidates: list[str], pool: list[str]) -> str:
    """Minimax：選一個猜測，使「最壞情況剩下的候選數」最小。
    O(|pool| * |candidates| * L)。同分時優先選本身就是候選的字（有機會直接猜中）。
    """
    cand_set = set(candidates)

    def score(g: str) -> tuple[int, int]:
        buckets = Counter(wordle_feedback(c, g) for c in candidates)
        return (max(buckets.values()), 0 if g in cand_set else 1)

    return min(pool, key=score)


def solve(secret: str, words: list[str], max_turns: int = 6) -> list[str]:
    candidates = list(words)
    guesses: list[str] = []
    for _ in range(max_turns):
        g = candidates[0] if len(candidates) <= 2 else best_guess(candidates, words)
        guesses.append(g)
        fb = wordle_feedback(secret, g)
        if fb == "G" * len(secret):
            return guesses
        candidates = filter_candidates(candidates, g, fb)
    return guesses


words = ["crane", "crate", "trace", "grace", "react", "apple", "hello", "brace", "caret"]
assert filter_candidates(words, "crane", "YGGBG") == ["trace", "grace", "brace"]
for secret in words:
    path = solve(secret, words)
    assert path[-1] == secret and len(path) <= 6

複雜度與優化

官方字典約數千到一萬多字，每回合 best_guess 是 |pool|·|cand|·5，第一步最慢。可預先計算 feedback 矩陣（字數² 個 byte，用 numpy 存），或把第一步的最佳開局字快取起來。

更好的評分

Minimax 最小化最壞情況；改用 entropy（各 feedback bucket 機率的資訊量期望值）通常平均步數更少。

後端角度的追問

「做成線上服務」：秘密單字只存在 server、client 只拿 feedback（防作弊）；每日題目用 hash(date + salt) % N 決定；遊戲狀態存 Redis（key = user_id:date，設 TTL）；API 設計 POST /games/{id}/guesses 回傳 feedback 與狀態，詳見 第 7 章。

真題 6：Graph DFS → Backtracking → DP 優化 高頻 深入

面試心得原文是「graph 題用 DFS → 追問 backtracking → 追問能否用 DP 優化」。這是一條非常經典的追問鏈，面試官在看你是否理解三者的關係：

DFS

沿一條路走到底再回頭；用來判斷可達性、找連通分量、拓撲排序。每個節點訪問一次，O(V + E)。

Backtracking

DFS 的一種：在搜尋樹上「做選擇 → 遞迴 → 撤銷選擇」，用來列舉所有解。輸出本身可能是指數級，複雜度至少與輸出同階。

DP

當問題只要計數 / 最佳值 / 是否存在（而非列出所有解），且子問題的答案只依賴「目前狀態」而與「怎麼走到這裡」無關時，可以把重複的子問題結果存起來，從指數降到多項式。

何時 backtracking 可以轉成 DP？

1. 重疊子問題（overlapping subproblems）：搜尋樹中同一個狀態被重複走到。例如格子路徑中，(2,3) 可以從 (1,3) 或 (2,2) 到達，從 (2,3) 出發的答案是一樣的。
2. 最佳子結構（optimal substructure）：整體最佳解由子問題最佳解組成（求計數時則是「可加性」）。
3. 狀態不依賴路徑（無後效性）：從某狀態出發的答案只與狀態本身有關。若需要 visited 集合才能避免重複走（例如一般圖上的 simple path、word search），狀態就變成 (位置, visited 集合)，數量指數級，DP 沒有幫助。
4. 狀態空間夠小：狀態數 × 每個狀態的轉移成本要可接受。

範例 A：Word Search（LC 79）——純 backtracking，無法 DP

題目：在字母格子中，判斷 word 是否能由上下左右相鄰、且不重複使用同一格的字母組成。

from collections import Counter


def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    # 剪枝 1：格子裡的字母數量不夠，直接 False
    have = Counter(ch for row in board for ch in row)
    if any(have[ch] < cnt for ch, cnt in Counter(word).items()):
        return False
    # 剪枝 2：從較稀有的一端開始搜，能大幅減少起點
    if have[word[0]] > have[word[-1]]:
        word = word[::-1]

    def dfs(r: int, c: int, i: int) -> bool:
        if board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        saved, board[r][c] = board[r][c], "#"      # 做選擇：標記已使用（原地，省掉 visited set）
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
                board[r][c] = saved
                return True
        board[r][c] = saved                         # 撤銷選擇
        return False

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))


grid = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
assert exist(grid, "ABCCED")
assert exist(grid, "SEE")
assert not exist(grid, "ABCB")                      # 不能重複使用同一格
assert grid[0] == ["A", "B", "C", "E"]              # 結束後格子已還原

複雜度：O(R · C · 3ᴸ)（起點 R·C 個，之後每步最多 3 個方向，因為不能走回頭）；空間 O(L) 遞迴深度。為什麼不能 DP：從 (r, c) 匹配 word[i:] 的答案取決於「哪些格子已經用過」，狀態必須包含 visited，指數級。追問「多個單字」時改用 Trie + backtracking（LC 212）。

範例 B：所有從起點到終點的路徑（LC 797）→ 計數 DP

題目：給一個 DAG（以 adjacency list 表示，節點 0 到 n−1），列出所有從 0 到 n−1 的路徑。

from functools import cache


def all_paths_source_target(graph: list[list[int]]) -> list[list[int]]:
    """Backtracking。DAG 不會繞回，所以不需要 visited。"""
    target = len(graph) - 1
    res: list[list[int]] = []
    path = [0]

    def dfs(u: int) -> None:
        if u == target:
            res.append(path.copy())          # 一定要複製，否則之後 pop 會改到
            return
        for v in graph[u]:
            path.append(v)
            dfs(v)
            path.pop()

    dfs(0)
    return res


def all_paths_iterative(graph: list[list[int]]) -> list[list[int]]:
    """explicit stack 版本：stack 裡直接放「到目前為止的路徑」。"""
    target = len(graph) - 1
    res: list[list[int]] = []
    stack = [[0]]
    while stack:
        path = stack.pop()
        u = path[-1]
        if u == target:
            res.append(path)
            continue
        for v in reversed(graph[u]):        # 反向 push，讓輸出順序與遞迴版相同
            stack.append(path + [v])
    return res


def count_paths(graph: list[list[int]]) -> int:
    """只要「數量」時：count(u) = sum(count(v))，每個節點只算一次。O(V + E)。"""
    target = len(graph) - 1

    @cache
    def count(u: int) -> int:
        if u == target:
            return 1
        return sum(count(v) for v in graph[u])

    return count(0)


g = [[1, 2], [3], [3], []]
assert all_paths_source_target(g) == [[0, 1, 3], [0, 2, 3]]
assert all_paths_iterative(g) == [[0, 1, 3], [0, 2, 3]]
g2 = [[4, 3, 1], [3, 2, 4], [3], [4], []]
assert len(all_paths_source_target(g2)) == count_paths(g2) == 5

# 「菱形鏈」：路徑數 2^k，列舉是指數級，但 count_paths 是線性
k = 40
chain: list[list[int]] = []
for i in range(k):
    base = 3 * i
    chain += [[base + 1, base + 2], [base + 3], [base + 3]]
chain.append([])
assert count_paths(chain) == 2 ** k

重點對比：列出所有路徑的複雜度是 O(2ⁿ · n)（路徑數本身可能指數級，無法更好，因為輸出就這麼大）；但若只問路徑「數量」，memo 後每個節點與邊只處理一次 → O(V + E)。這就是「backtracking → DP」最清楚的例子：DP 能加速的前提是你不需要列出每個解。

範例 C：格子路徑數（LC 63 Unique Paths II）：暴力 → memo → bottom-up → 1D

題目：m×n 格子，1 代表障礙物，只能向右或向下走，求從左上到右下的路徑數。

from functools import cache


def unique_paths_brute(grid: list[list[int]]) -> int:
    """純 DFS：O(2^(m+n))。"""
    m, n = len(grid), len(grid[0])

    def dfs(r: int, c: int) -> int:
        if r >= m or c >= n or grid[r][c] == 1:
            return 0
        if (r, c) == (m - 1, n - 1):
            return 1
        return dfs(r + 1, c) + dfs(r, c + 1)

    return dfs(0, 0)


def unique_paths_memo(grid: list[list[int]]) -> int:
    """加上 @cache：狀態 (r, c) 只有 m*n 個 → O(mn) 時間、O(mn) 空間。"""
    m, n = len(grid), len(grid[0])

    @cache
    def dfs(r: int, c: int) -> int:
        if r >= m or c >= n or grid[r][c] == 1:
            return 0
        if (r, c) == (m - 1, n - 1):
            return 1
        return dfs(r + 1, c) + dfs(r, c + 1)

    return dfs(0, 0)


def unique_paths_dp(grid: list[list[int]]) -> int:
    """Bottom-up + 滾動陣列：dp[c] = 走到目前這一列第 c 格的路徑數。O(mn) 時間、O(n) 空間，無遞迴。"""
    n = len(grid[0])
    dp = [0] * n
    dp[0] = 1
    for row in grid:
        for c in range(n):
            if row[c] == 1:
                dp[c] = 0
            elif c > 0:
                dp[c] += dp[c - 1]       # dp[c]（上方，舊值）+ dp[c-1]（左方，新值）
    return dp[-1]


cases = [
    ([[0, 0, 0], [0, 1, 0], [0, 0, 0]], 2),
    ([[0, 1], [0, 0]], 1),
    ([[1]], 0),
    ([[0]], 1),
    ([[0, 0], [0, 1]], 0),
]
for grid, expected in cases:
    assert unique_paths_brute(grid) == unique_paths_memo(grid) == unique_paths_dp(grid) == expected
big = [[0] * 18 for _ in range(18)]
assert unique_paths_dp(big) == 2333606220        # C(34, 17)

範例 D：矩陣中最長遞增路徑（LC 329）——有 visited 卻可以 memo 的例子

題目：在整數矩陣中找最長的嚴格遞增路徑長度（上下左右移動）。

乍看像 word search 需要 visited，但嚴格遞增保證路徑不可能回到走過的格子（值只會變大）——等於在一個隱含的 DAG 上找最長路徑。所以 dfs(r, c) 的答案與路徑無關，可以 memo。

from collections import deque
from functools import cache

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def longest_increasing_path(matrix: list[list[int]]) -> int:
    """DFS + memo：每格只算一次，O(RC) 時間與空間（遞迴深度最壞 O(RC)）。"""
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])

    @cache
    def dfs(r: int, c: int) -> int:
        best = 1
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                best = max(best, 1 + dfs(nr, nc))
        return best

    return max(dfs(r, c) for r in range(rows) for c in range(cols))


def longest_increasing_path_topo(matrix: list[list[int]]) -> int:
    """無遞迴版：拓撲排序（Kahn）一層一層剝，層數 = 最長路徑長度。O(RC)。"""
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    indeg = [[0] * cols for _ in range(rows)]        # 入度 = 比自己小的鄰居數
    for r in range(rows):
        for c in range(cols):
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
                    indeg[r][c] += 1
    q = deque((r, c) for r in range(rows) for c in range(cols) if indeg[r][c] == 0)
    layers = 0
    while q:
        layers += 1
        for _ in range(len(q)):
            r, c = q.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    indeg[nr][nc] -= 1
                    if indeg[nr][nc] == 0:
                        q.append((nr, nc))
    return layers


for fn in (longest_increasing_path, longest_increasing_path_topo):
    assert fn([[9, 9, 4], [6, 6, 8], [2, 1, 1]]) == 4      # 1 → 2 → 6 → 9
    assert fn([[3, 4, 5], [3, 2, 6], [2, 2, 1]]) == 4      # 3 → 4 → 5 → 6
    assert fn([[1]]) == 1
    assert fn([]) == 0
snake = [list(range(i * 50, i * 50 + 50))[:: 1 if i % 2 == 0 else -1] for i in range(50)]
assert longest_increasing_path_topo(snake) == 2500           # 蛇形矩陣：整個矩陣是一條路

真題 7：遞迴改迭代 高頻 進階

「程式優化：能否把遞迴改掉」是 Appier 面試心得中明確提到的追問。你需要知道為什麼要改（Python 的限制）與怎麼改（explicit stack 的幾種模式）。

為什麼在 Python 要在意遞迴？

• 遞迴上限：sys.getrecursionlimit() 預設 1000。超過會丟 RecursionError。處理一條退化成鏈的樹（例如 10 萬個節點的 linked-list 狀樹）就會爆。
• 調高上限有風險：sys.setrecursionlimit(10**6) 只是解除 Python 層的檢查。在舊版 CPython，每層 Python 呼叫也會吃 C stack，太深會直接 segfault（整個 process 掛掉，而不是可捕捉的例外）。3.11 起純 Python 函式之間的呼叫不再遞迴使用 C stack，風險降低，但經過 C 實作的函式（例如 copy.deepcopy、某些 callback）仍會使用。常見的 workaround 是在 threading.stack_size() 調大的新 thread 中執行，但這是權宜之計。
• 沒有 tail call optimization（TCO）：即使是尾遞迴，CPython 也不會把它轉成迴圈。Guido 的理由是 TCO 會讓 traceback 失去中間 frame、不利除錯，且 Python 鼓勵用迴圈表達迭代。所以「改成尾遞迴」在 Python 不是解法。
• 函式呼叫成本：每次呼叫要建立 frame 物件，比迴圈內的一次迭代貴得多。熱點路徑上的遞迴改成迴圈常有可觀的加速（仍需 profiling 確認，見 第 8 章）。

import sys


def depth_recursive(n: int) -> int:
    return 0 if n == 0 else 1 + depth_recursive(n - 1)


def depth_tail(n: int, acc: int = 0) -> int:
    return acc if n == 0 else depth_tail(n - 1, acc + 1)   # 尾遞迴，但 Python 不優化


assert sys.getrecursionlimit() == 1000
assert depth_recursive(500) == 500
for fn in (depth_recursive, depth_tail):
    try:
        fn(5000)
        raise AssertionError("should not reach")
    except RecursionError:
        pass                                              # 兩者都爆：尾遞迴沒有被優化

模式 1：樹的前序 / 中序 / 後序迭代

from __future__ import annotations

from collections import deque
from dataclasses import dataclass
from typing import Optional


@dataclass
class TreeNode:
    val: int
    left: Optional[TreeNode] = None
    right: Optional[TreeNode] = None


def build(values: list[Optional[int]]) -> Optional[TreeNode]:
    """由 LeetCode 層序表示法建樹，例如 [1, None, 2, 3]。"""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    q = deque([root])
    i = 1
    while q and i < len(values):
        node = q.popleft()
        for side in ("left", "right"):
            if i < len(values) and values[i] is not None:
                child = TreeNode(values[i])
                setattr(node, side, child)
                q.append(child)
            i += 1
    return root


def preorder(root: Optional[TreeNode]) -> list[int]:
    """根 → 左 → 右：pop 後先 push 右再 push 左（stack 是 LIFO）。"""
    out: list[int] = []
    stack = [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out


def inorder(root: Optional[TreeNode]) -> list[int]:
    """左 → 根 → 右：一路往左 push，pop 時輸出，再轉向右子樹。"""
    out: list[int] = []
    stack: list[TreeNode] = []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out


def postorder(root: Optional[TreeNode]) -> list[int]:
    """通用技巧：stack 存 (node, visited)。第一次遇到時「展開」，第二次才輸出。
    改變 push 順序即可得到任何一種 traversal，是最容易背的模板。"""
    out: list[int] = []
    stack: list[tuple[TreeNode, bool]] = [(root, False)] if root else []
    while stack:
        node, visited = stack.pop()
        if visited:
            out.append(node.val)
            continue
        stack.append((node, True))          # 根最後輸出 → 最先 push
        if node.right:
            stack.append((node.right, False))
        if node.left:
            stack.append((node.left, False))
    return out


def max_depth_iterative(root: Optional[TreeNode]) -> int:
    """需要「子問題回傳值」時：stack 帶著深度走，或用 BFS 數層數。"""
    best = 0
    stack = [(root, 1)] if root else []
    while stack:
        node, d = stack.pop()
        best = max(best, d)
        for child in (node.left, node.right):
            if child:
                stack.append((child, d + 1))
    return best


t = build([4, 2, 6, 1, 3, 5, 7])
assert preorder(t) == [4, 2, 1, 3, 6, 5, 7]
assert inorder(t) == [1, 2, 3, 4, 5, 6, 7]
assert postorder(t) == [1, 3, 2, 5, 7, 6, 4]
assert max_depth_iterative(t) == 3
assert inorder(build([1, None, 2, 3])) == [1, 3, 2]

# 10 萬層的退化樹：遞迴版會爆，迭代版沒問題
root = cur = TreeNode(0)
for i in range(1, 100_000):
    cur.right = TreeNode(i)
    cur = cur.right
assert len(inorder(root)) == 100_000 and max_depth_iterative(root) == 100_000

模式 2：Flatten Nested List（含 LC 341 Iterator）

from typing import Any, Iterator


def flatten_recursive(nested: list[Any]) -> list[Any]:
    out: list[Any] = []
    for item in nested:
        if isinstance(item, list):
            out.extend(flatten_recursive(item))
        else:
            out.append(item)
    return out


def flatten(nested: list[Any]) -> list[Any]:
    """stack 裡放「iterator」而不是元素：保留順序、不需反轉、也不複製子 list。O(總元素數)。"""
    out: list[Any] = []
    stack: list[Iterator[Any]] = [iter(nested)]
    while stack:
        item = next(stack[-1], _SENTINEL)
        if item is _SENTINEL:
            stack.pop()                       # 這一層走完了
        elif isinstance(item, list):
            stack.append(iter(item))          # 進入下一層 = 取代遞迴呼叫
        else:
            out.append(item)
    return out


_SENTINEL = object()


class NestedIterator:
    """LC 341：惰性版本，next() / has_next() 攤銷 O(1)，記憶體 O(巢狀深度)。"""

    def __init__(self, nested: list[Any]) -> None:
        self._stack: list[Iterator[Any]] = [iter(nested)]
        self._peeked: Any = _SENTINEL

    def has_next(self) -> bool:
        while self._peeked is _SENTINEL and self._stack:
            item = next(self._stack[-1], _SENTINEL)
            if item is _SENTINEL:
                self._stack.pop()
            elif isinstance(item, list):
                self._stack.append(iter(item))
            else:
                self._peeked = item
        return self._peeked is not _SENTINEL

    def next(self) -> Any:
        if not self.has_next():
            raise StopIteration
        item, self._peeked = self._peeked, _SENTINEL
        return item


data = [1, [2, [3, [4]], 5], [], [[6]], 7]
assert flatten_recursive(data) == flatten(data) == [1, 2, 3, 4, 5, 6, 7]
it = NestedIterator(data)
got = []
while it.has_next():
    got.append(it.next())
assert got == [1, 2, 3, 4, 5, 6, 7]
assert flatten([[], [[]]]) == []

deep: list[Any] = [0]
for i in range(1, 50_000):
    deep = [deep, i]
assert flatten(deep) == list(range(50_000))   # flatten_recursive(deep) 會 RecursionError

模式 3：圖的 DFS 迭代與「模擬呼叫堆疊」

圖 DFS 改迭代有個細節：遞迴版在「進入節點時」標記 visited；簡單的 stack 版若在 push 時標記，訪問順序會和遞迴版不同（但仍是合法的 DFS，可達性/連通分量結果相同）。若需要完全等價的順序或 post-order 時間點（例如拓撲排序、偵測環），就要 stack 存 (node, neighbor iterator)，精確模擬呼叫堆疊。

def dfs_order_recursive(graph: dict[int, list[int]], start: int) -> list[int]:
    seen: set[int] = set()
    order: list[int] = []

    def visit(u: int) -> None:
        seen.add(u)
        order.append(u)
        for v in graph.get(u, []):
            if v not in seen:
                visit(v)

    visit(start)
    return order


def dfs_order_iterative(graph: dict[int, list[int]], start: int) -> list[int]:
    """stack 存 (node, 鄰居 iterator)：與遞迴版順序完全相同。"""
    seen = {start}
    order = [start]
    stack = [(start, iter(graph.get(start, [])))]
    while stack:
        u, it = stack[-1]
        for v in it:                          # 從上次停下的位置繼續
            if v not in seen:
                seen.add(v)
                order.append(v)
                stack.append((v, iter(graph.get(v, []))))
                break                         # 「遞迴呼叫」：先處理 v
        else:
            stack.pop()                       # 所有鄰居處理完 =「return」，post-order 時間點在此
    return order


def topo_sort_dfs(graph: dict[int, list[int]], nodes: list[int]) -> list[int]:
    """迭代式 DFS 拓撲排序 + 環偵測（三色標記）。"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {u: WHITE for u in nodes}
    post: list[int] = []
    for s in nodes:
        if color[s] != WHITE:
            continue
        color[s] = GRAY
        stack = [(s, iter(graph.get(s, [])))]
        while stack:
            u, it = stack[-1]
            for v in it:
                if color[v] == GRAY:
                    raise ValueError("cycle detected")
                if color[v] == WHITE:
                    color[v] = GRAY
                    stack.append((v, iter(graph.get(v, []))))
                    break
            else:
                color[u] = BLACK
                post.append(u)
                stack.pop()
    return post[::-1]


g = {1: [2, 3], 2: [4], 3: [4], 4: [], 5: [1]}
assert dfs_order_recursive(g, 1) == dfs_order_iterative(g, 1) == [1, 2, 4, 3]
order = topo_sort_dfs(g, [1, 2, 3, 4, 5])
pos = {u: i for i, u in enumerate(order)}
assert all(pos[u] < pos[v] for u, vs in g.items() for v in vs)
try:
    topo_sort_dfs({1: [2], 2: [1]}, [1, 2])
    raise AssertionError
except ValueError:
    pass

真題 8：中等字串處理題 高頻 進階

面試心得提到「中等難度字串處理白板題」。以下是最可能出現的類型：stack 解析（LC 394）、sliding window（LC 3）、hash 分組（LC 49）、字串壓縮（LC 443 / 經典面試題）、回文（LC 5）。

LC 394：Decode String

題目："3[a2[c]]" → "accaccacc"。k[...] 表示括號內字串重複 k 次，可巢狀，k 可能是多位數。

思路：巢狀結構 → stack。遇 [ 時把「目前累積的字串」與「重複次數」存進 stack，開始一個新的層；遇 ] 時把這層結果乘上次數，接回上一層。

def decode_string(s: str) -> str:
    stack: list[tuple[list[str], int]] = []
    cur: list[str] = []
    num = 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)              # 多位數
        elif ch == "[":
            stack.append((cur, num))
            cur, num = [], 0
        elif ch == "]":
            prev, k = stack.pop()
            prev.append("".join(cur) * k)
            cur = prev
        else:
            cur.append(ch)
    return "".join(cur)


assert decode_string("3[a]2[bc]") == "aaabcbc"
assert decode_string("3[a2[c]]") == "accaccacc"
assert decode_string("2[abc]3[cd]ef") == "abcabccdcdcdef"
assert decode_string("10[a]") == "a" * 10
assert decode_string("abc") == "abc"

複雜度：時間與空間 O(輸出長度)。用 list 累積再 join，避免字串反覆相加。追問：(1) 遞迴下降解析器版本（遇 [ 遞迴、遇 ] 回傳）；(2) 輸出可能非常大（"1000[1000[a]]"）→ 若只需第 k 個字元（LC 880 Decoded String at Index），不要真的展開，用長度倒推；(3) 輸入不合法（括號不配對）時如何報錯。

LC 3：Longest Substring Without Repeating Characters

def length_of_longest_substring(s: str) -> int:
    """sliding window：right 每步擴張；遇到重複就把 left 跳到「上次出現位置 + 1」。O(n) / O(字母表)。"""
    last: dict[str, int] = {}
    left = best = 0
    for right, ch in enumerate(s):
        if last.get(ch, -1) >= left:     # 重複字元在視窗內才需要移動 left
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best


assert length_of_longest_substring("abcabcbb") == 3
assert length_of_longest_substring("bbbbb") == 1
assert length_of_longest_substring("pwwkew") == 3
assert length_of_longest_substring("") == 0
assert length_of_longest_substring("abba") == 2      # 檢查 last[ch] >= left 的必要性
assert length_of_longest_substring("dvdf") == 3

LC 49：Group Anagrams

from collections import defaultdict


def group_anagrams(strs: list[str]) -> list[list[str]]:
    """key = 排序後的字串。O(n * k log k)，k = 平均字串長度。"""
    groups: defaultdict[str, list[str]] = defaultdict(list)
    for s in strs:
        groups["".join(sorted(s))].append(s)
    return list(groups.values())


def group_anagrams_count(strs: list[str]) -> list[list[str]]:
    """key = 26 個字母的計數 tuple。O(n * k)，k 很長時較快（只適用小寫英文字母）。"""
    groups: defaultdict[tuple[int, ...], list[str]] = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord("a")] += 1
        groups[tuple(count)].append(s)       # list 不可 hash，要轉 tuple
    return list(groups.values())


data = ["eat", "tea", "tan", "ate", "nat", "bat"]
expected = [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
assert group_anagrams(data) == expected
assert group_anagrams_count(data) == expected
assert group_anagrams([""]) == [[""]]

字串壓縮：Run-Length Encoding（經典面試題 + LC 443）

from itertools import groupby


def compress(s: str) -> str:
    """'aabcccccaaa' -> 'a2b1c5a3'；若沒有變短則回傳原字串。O(n)。"""
    encoded = "".join(f"{ch}{len(list(g))}" for ch, g in groupby(s))
    return encoded if len(encoded) < len(s) else s


def decompress(s: str) -> str:
    """'a2b1c5a3' -> 'aabcccccaaa'；支援多位數次數（'a12'）。"""
    out: list[str] = []
    i = 0
    while i < len(s):
        ch = s[i]
        j = i + 1
        while j < len(s) and s[j].isdigit():
            j += 1
        out.append(ch * int(s[i + 1:j]))
        i = j
    return "".join(out)


def compress_in_place(chars: list[str]) -> int:
    """LC 443：原地壓縮，次數為 1 時不寫；回傳新長度。O(n) 時間、O(1) 額外空間（two pointers）。"""
    write = read = 0
    while read < len(chars):
        ch = chars[read]
        start = read
        while read < len(chars) and chars[read] == ch:
            read += 1
        chars[write] = ch
        write += 1
        run = read - start
        if run > 1:
            for d in str(run):
                chars[write] = d
                write += 1
    return write


assert compress("aabcccccaaa") == "a2b1c5a3"
assert compress("abc") == "abc"                         # 壓縮後更長 → 回傳原字串
assert compress("") == ""
assert decompress("a2b1c5a3") == "aabcccccaaa"
assert decompress("a12") == "a" * 12
chars = list("aabbccc")
assert chars[: compress_in_place(chars)] == list("a2b2c3")
chars = list("abbbbbbbbbbbb")
assert chars[: compress_in_place(chars)] == list("ab12")

追問：原字串含數字時，a2 會有歧義（是 a 重複 2 次，還是字元 a 加字元 2？）→ 需要跳脫字元或固定長度編碼。實務上 RLE 適合重複多的資料（例如 bitmap、columnar storage 的 run-length encoding，Parquet 就有用）。

LC 5：Longest Palindromic Substring（中心擴展）

def longest_palindrome(s: str) -> str:
    """每個中心（2n-1 個，含字元之間）向外擴展。O(n^2) 時間、O(1) 空間。"""
    if not s:
        return ""
    start, end = 0, 0                            # 目前最佳 [start, end]

    def expand(lo: int, hi: int) -> tuple[int, int]:
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        return lo + 1, hi - 1

    for i in range(len(s)):
        for lo, hi in (expand(i, i), expand(i, i + 1)):   # 奇數長度、偶數長度
            if hi - lo > end - start:
                start, end = lo, hi
    return s[start:end + 1]


assert longest_palindrome("babad") in ("bab", "aba")
assert longest_palindrome("cbbd") == "bb"
assert longest_palindrome("a") == "a"
assert longest_palindrome("forgeeksskeegfor") == "geeksskeeg"

DP 解（dp[i][j] = s[i]==s[j] and dp[i+1][j-1]）同樣 O(n²) 但需要 O(n²) 空間，中心擴展較好；Manacher 演算法可 O(n)，面試通常只需要提到名字。

真題 9：與廣告業務相關的包裝題 高頻 深入

以下題目是依照 Appier 的業務（程式化廣告、行銷自動化）設計的「包裝題」，每題都對應一個經典演算法模式。練習時先別看解答，試著自己把業務敘述翻成資料結構問題。

題 9-1：Frequency Capping（過去 N 分鐘內的曝光次數）

題目：為了不讓使用者看到同一支廣告太多次，廣告主設定「每位使用者在任意 60 分鐘內最多看到 3 次」。請實作 try_serve(user_id, now)：若允許曝光則記錄並回傳 True，否則回傳 False。時間戳單調遞增。

思路：每位使用者一個 deque 存曝光時間；每次查詢先把「已滑出視窗」的舊時間戳從左邊 pop 掉，剩下的長度就是視窗內次數。每個時間戳最多進出 deque 各一次 → 攤銷 O(1)。

from collections import defaultdict, deque


class FrequencyCapper:
    """Sliding window log。視窗定義為 (now - window, now]。
    每次呼叫攤銷 O(1)；記憶體 O(活躍使用者數 × cap)。"""

    def __init__(self, max_impressions: int, window_seconds: float) -> None:
        self.cap = max_impressions
        self.window = window_seconds
        self._events: defaultdict[str, deque[float]] = defaultdict(deque)

    def _evict(self, q: deque[float], now: float) -> None:
        while q and q[0] <= now - self.window:
            q.popleft()

    def count(self, user_id: str, now: float) -> int:
        q = self._events.get(user_id)          # 用 get：查詢不該為新使用者建立空 deque
        if not q:
            return 0
        self._evict(q, now)
        return len(q)

    def try_serve(self, user_id: str, now: float) -> bool:
        q = self._events[user_id]
        self._evict(q, now)
        if len(q) >= self.cap:
            return False
        q.append(now)
        return True

    def cleanup(self, now: float) -> None:
        """定期清掉視窗內已無事件的使用者，避免記憶體無限成長。"""
        for uid in list(self._events):
            self._evict(self._events[uid], now)
            if not self._events[uid]:
                del self._events[uid]


fc = FrequencyCapper(max_impressions=3, window_seconds=60)
assert [fc.try_serve("u1", t) for t in (0, 10, 20, 30)] == [True, True, True, False]
assert fc.try_serve("u2", 30)                  # 使用者之間互不影響
assert fc.count("u1", 59) == 3
assert fc.try_serve("u1", 60)                  # t=0 已滑出 (0, 60] 視窗
assert not fc.try_serve("u1", 61)              # 視窗內有 10, 20, 60
assert fc.try_serve("u1", 70.5)                # 10 滑出
fc.cleanup(now=1000)
assert fc.count("u1", 1000) == 0 and not fc._events

離線變形：給一份依時間排序的曝光 log [(ts, user)]，對每筆事件計算「該使用者在過去 N 秒內（含本筆）的曝光次數」，或找出違反 cap 的事件。做法相同：per-user deque 一次掃描，O(n)。

題 9-2：Top K 熱門廣告（含串流版 Count-Min Sketch）

題目：給一串曝光事件（ad_id），回傳曝光次數最多的 K 支廣告。延伸：事件是無限串流、distinct ad 數量非常大，記憶體有限。

import heapq
from collections import Counter


def top_k_counter(events: list[str], k: int) -> list[str]:
    """Counter.most_common(k) 內部用 heapq.nlargest：O(n + m log k)，m = distinct 數。"""
    return [ad for ad, _ in Counter(events).most_common(k)]


def top_k_heap(events: list[str], k: int) -> list[str]:
    """手寫：大小為 k 的 min-heap，heap 頂端是「目前第 k 名」，比它大才替換。O(n + m log k)。"""
    counts = Counter(events)
    heap: list[tuple[int, str]] = []
    for ad, cnt in counts.items():
        if len(heap) < k:
            heapq.heappush(heap, (cnt, ad))
        elif cnt > heap[0][0]:
            heapq.heapreplace(heap, (cnt, ad))
    return [ad for _, ad in sorted(heap, key=lambda x: (-x[0], x[1]))]


def top_k_bucket(events: list[str], k: int) -> list[str]:
    """Bucket sort：次數最多 n，用 n+1 個桶。O(n)。"""
    counts = Counter(events)
    buckets: list[list[str]] = [[] for _ in range(len(events) + 1)]
    for ad, cnt in counts.items():
        buckets[cnt].append(ad)
    out: list[str] = []
    for cnt in range(len(buckets) - 1, 0, -1):
        for ad in sorted(buckets[cnt]):
            out.append(ad)
            if len(out) == k:
                return out
    return out


events = ["a"] * 5 + ["b"] * 3 + ["c"] * 4 + ["d"]
assert top_k_counter(events, 2) == ["a", "c"]
assert top_k_heap(events, 2) == ["a", "c"]
assert top_k_bucket(events, 3) == ["a", "c", "b"]

串流版：當 distinct 廣告/關鍵字數太多，連 Counter 都放不下時，用 Count-Min Sketch（CMS）估計頻率：d 列、每列 w 個計數器，每個元素用 d 個不同 hash 各加到一格；查詢時取 d 格中的最小值。它只會高估、不會低估；在 w = ⌈e/ε⌉、d = ⌈ln(1/δ)⌉ 時，估計值 ≤ 真實值 + εN 的機率至少 1 − δ（N 為總事件數）。搭配一個大小 k 的候選集合即可追蹤 heavy hitters。

import hashlib
import math


class CountMinSketch:
    def __init__(self, epsilon: float = 0.001, delta: float = 0.01) -> None:
        self.width = math.ceil(math.e / epsilon)
        self.depth = math.ceil(math.log(1 / delta))
        self.table = [[0] * self.width for _ in range(self.depth)]

    def _indexes(self, item: str) -> list[int]:
        idx = []
        for row in range(self.depth):
            digest = hashlib.blake2b(item.encode(), digest_size=8, salt=row.to_bytes(8, "big")).digest()
            idx.append(int.from_bytes(digest, "big") % self.width)
        return idx

    def add(self, item: str, count: int = 1) -> None:
        for row, col in enumerate(self._indexes(item)):
            self.table[row][col] += count

    def estimate(self, item: str) -> int:
        return min(self.table[row][col] for row, col in enumerate(self._indexes(item)))


class StreamingTopK:
    """CMS 估頻率 + 只保留 k 個候選。記憶體 O(w*d + k)，與 distinct 數無關。"""

    def __init__(self, k: int, epsilon: float = 0.001, delta: float = 0.01) -> None:
        self.k = k
        self.cms = CountMinSketch(epsilon, delta)
        self.candidates: dict[str, int] = {}

    def add(self, item: str) -> None:
        self.cms.add(item)
        est = self.cms.estimate(item)
        if item in self.candidates or len(self.candidates) < self.k:
            self.candidates[item] = est
            return
        weakest = min(self.candidates, key=self.candidates.__getitem__)   # k 小時 O(k) 即可
        if est > self.candidates[weakest]:
            del self.candidates[weakest]
            self.candidates[item] = est

    def top(self) -> list[tuple[str, int]]:
        return sorted(self.candidates.items(), key=lambda kv: (-kv[1], kv[0]))


stream = []
for i in range(200):                       # 交錯產生：熱門廣告 + 長尾
    stream.append("ad_hot")
    if i % 2 == 0:
        stream.append("ad_warm")
    if i % 4 == 0:
        stream.append("ad_mild")
    stream.append(f"ad_tail_{i % 50}")     # 50 支長尾廣告各 4 次
tk = StreamingTopK(k=3)
for ad in stream:
    tk.add(ad)
assert [ad for ad, _ in tk.top()] == ["ad_hot", "ad_warm", "ad_mild"]
cms = tk.cms
assert cms.estimate("ad_hot") >= 200 and cms.estimate("never_seen") >= 0

精確 vs 近似

計費、對帳要精確（離線批次用 Spark 精確計算）；即時儀表板、熱門排行、異常偵測可接受近似（CMS、HyperLogLog 算 UV）。

分散式

CMS 可合併：兩個相同參數的 sketch 逐格相加即為合併後的 sketch，非常適合「每台機器各自統計、再彙總」。

其他演算法

Misra-Gries、Space-Saving 直接維護 k 個計數器找 heavy hitters，也常被提到。

題 9-3：解析 log 統計每個 campaign 的 CTR

題目：log 每行格式如 2024-05-01T10:00:00Z event=impression campaign=c1 user=u1 req=r1。請統計每個 campaign 的曝光數、點擊數與 CTR，依 CTR 由高到低排序。需處理格式錯誤的行，並避免重複點擊（同一個 req 只算一次）。

from collections import Counter
from dataclasses import dataclass
from typing import Iterable, Optional


@dataclass(frozen=True)
class CampaignStats:
    campaign: str
    impressions: int
    clicks: int

    @property
    def ctr(self) -> float:
        return self.clicks / self.impressions if self.impressions else 0.0


def parse_line(line: str) -> Optional[dict[str, str]]:
    parts = line.split()
    if len(parts) < 2:
        return None
    fields = {"ts": parts[0]}
    for token in parts[1:]:
        key, sep, value = token.partition("=")
        if not sep or not key:
            return None
        fields[key] = value
    if "event" not in fields or "campaign" not in fields:
        return None
    return fields


def campaign_ctr(lines: Iterable[str], min_impressions: int = 1) -> tuple[list[CampaignStats], int]:
    """單次掃描、O(n) 時間；記憶體 O(campaign 數 + 去重用的 req 數)。回傳 (統計結果, 錯誤行數)。"""
    impressions: Counter[str] = Counter()
    clicks: Counter[str] = Counter()
    seen_click_reqs: set[str] = set()
    bad = 0
    for line in lines:
        rec = parse_line(line)
        if rec is None:
            bad += 1
            continue
        campaign, event = rec["campaign"], rec["event"]
        if event == "impression":
            impressions[campaign] += 1
        elif event == "click":
            req = rec.get("req")
            if req is not None:
                if req in seen_click_reqs:
                    continue                       # 重複點擊（使用者連點、SDK 重送）
                seen_click_reqs.add(req)
            clicks[campaign] += 1
    stats = [
        CampaignStats(c, impressions[c], clicks[c])
        for c in impressions
        if impressions[c] >= min_impressions       # 曝光太少的 CTR 沒有統計意義
    ]
    stats.sort(key=lambda s: (-s.ctr, -s.impressions, s.campaign))
    return stats, bad


logs = """2024-05-01T10:00:00Z event=impression campaign=c1 user=u1 req=r1
2024-05-01T10:00:01Z event=impression campaign=c1 user=u2 req=r2
2024-05-01T10:00:02Z event=click campaign=c1 user=u1 req=r1
2024-05-01T10:00:02Z event=click campaign=c1 user=u1 req=r1
2024-05-01T10:00:03Z event=impression campaign=c2 user=u3 req=r3
2024-05-01T10:00:04Z event=impression campaign=c2 user=u4 req=r4
2024-05-01T10:00:05Z event=impression campaign=c2 user=u5 req=r5
2024-05-01T10:00:05Z event=impression campaign=c2 user=u6 req=r6
2024-05-01T10:00:06Z event=click campaign=c2 user=u3 req=r3
garbage line
2024-05-01T10:00:07Z event=impression user=u7""".splitlines()
stats, bad = campaign_ctr(logs)
assert [(s.campaign, s.impressions, s.clicks) for s in stats] == [("c1", 2, 1), ("c2", 4, 1)]
assert stats[0].ctr == 0.5 and stats[1].ctr == 0.25
assert bad == 2

• 函式接受 Iterable[str]：可以直接傳入檔案物件（with open(...) as f: campaign_ctr(f)）逐行串流處理，不必整個檔案載入記憶體。
• 去重集合會無限成長：實務上用時間視窗（只在 N 分鐘內去重）、Bloom filter，或在上游以 request id 冪等寫入。
• 規模放大：這就是 MapReduce 的 word count 變形——map 輸出 (campaign, (imp, click))，reduce 加總。上億筆時用 Spark / Flink，詳見 第 12 章；報表系統設計見 第 13 章。
• 統計追問：CTR 在曝光少時變異很大，可以用 Bayesian smoothing（加上先驗的曝光與點擊數）讓排名更穩定。

題 9-4：合併廣告投放時段（Merge Intervals）

題目：一支廣告由多個投放設定組成，每個設定是一個時段 [start, end)（可能重疊）。請 (1) 合併成不重疊的時段；(2) 回答某時間點是否在投放；(3) 計算同時在投放的 campaign 最大數量（評估峰值預算/流量）。

import bisect


def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """LC 56：依 start 排序後一次掃描。半開區間 [s, e)：相接（e == 下一個 s）也合併。O(n log n)。"""
    merged: list[list[int]] = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return [(s, e) for s, e in merged]


def is_active(merged: list[tuple[int, int]], t: int) -> bool:
    """在合併後的區間上二分搜尋：O(log n)。"""
    i = bisect.bisect_right(merged, t, key=lambda iv: iv[0]) - 1   # 最後一個 start <= t 的區間
    return i >= 0 and t < merged[i][1]


def max_concurrent(intervals: list[tuple[int, int]]) -> int:
    """LC 253 Meeting Rooms II 的 sweep line：start +1、end -1，同一時間點先處理結束。O(n log n)。"""
    points = []
    for s, e in intervals:
        points.append((s, 1))
        points.append((e, -1))
    points.sort()                       # (t, -1) 排在 (t, 1) 前面：半開區間在 e 時已結束
    cur = best = 0
    for _, delta in points:
        cur += delta
        best = max(best, cur)
    return best


slots = [(9, 12), (14, 18), (11, 13), (18, 20), (1, 3)]
merged = merge_intervals(slots)
assert merged == [(1, 3), (9, 13), (14, 20)]
assert is_active(merged, 10) and is_active(merged, 14) and is_active(merged, 19)
assert not is_active(merged, 13) and not is_active(merged, 0) and not is_active(merged, 20)
assert max_concurrent(slots) == 2
assert max_concurrent([(0, 10), (5, 15), (8, 9), (10, 12)]) == 3
assert merge_intervals([]) == []

追問：(1) 時段頻繁新增時，每次重新排序是 O(n log n)——可以用 LC 57 Insert Interval 的 O(n) 插入，或用平衡樹 / sortedcontainers；(2) 每週重複的排程（每週一到五 9:00–18:00）→ 先展開到查詢範圍，或轉成「週內分鐘數」的區間；(3) 時區！投放時段通常以廣告主時區設定，儲存一律用 UTC。

題 9-5：Rate Limiter 類別設計（Token Bucket）

題目：設計一個 rate limiter，限制每個 API key 每秒平均 r 個請求，但允許最多 b 個的短暫突發（burst）。

思路：token bucket——桶容量 b，以速率 r 補充 token，每個請求消耗 1 個 token，沒 token 就拒絕。不需要背景執行緒補 token：每次請求時根據「距上次補充過了多久」惰性計算應補多少。

import threading
import time
from typing import Callable


class TokenBucket:
    def __init__(self, capacity: float, refill_per_sec: float,
                 clock: Callable[[], float] = time.monotonic) -> None:
        self.capacity = capacity
        self.rate = refill_per_sec
        self.clock = clock                     # 可注入假時鐘 → 測試不需要 sleep
        self.tokens = capacity
        self.last = clock()
        self._lock = threading.Lock()          # 多執行緒共用時保護 read-modify-write

    def allow(self, cost: float = 1.0) -> bool:
        with self._lock:
            now = self.clock()
            self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
            self.last = now
            if self.tokens >= cost:
                self.tokens -= cost
                return True
            return False


class RateLimiter:
    """每個 key 一個 bucket。O(1) / 請求；閒置 key 應定期清除（或用 LRU 限制數量）。"""

    def __init__(self, capacity: float, refill_per_sec: float,
                 clock: Callable[[], float] = time.monotonic) -> None:
        self._factory = lambda: TokenBucket(capacity, refill_per_sec, clock)
        self._buckets: dict[str, TokenBucket] = {}
        self._lock = threading.Lock()

    def allow(self, key: str) -> bool:
        with self._lock:
            bucket = self._buckets.get(key)
            if bucket is None:
                bucket = self._buckets[key] = self._factory()
        return bucket.allow()


class FakeClock:
    def __init__(self) -> None:
        self.t = 0.0

    def __call__(self) -> float:
        return self.t


clock = FakeClock()
rl = RateLimiter(capacity=2, refill_per_sec=1, clock=clock)
assert [rl.allow("k1") for _ in range(3)] == [True, True, False]   # burst 2 次後用完
assert rl.allow("k2")                                              # 不同 key 獨立
clock.t = 0.5
assert not rl.allow("k1")                                          # 只補了 0.5 個
clock.t = 1.0
assert rl.allow("k1")                                              # 累積到 1 個
clock.t = 100.0
assert [rl.allow("k1") for _ in range(3)] == [True, True, False]   # 補滿也只到容量 2

題 9-6：LRU Cache（OrderedDict 版與手寫雙向鏈結串列版）

題目（LC 146）：實作容量固定的快取，get 與 put 都要 O(1)；容量滿時淘汰最久未使用的項目。

思路：hash map 提供 O(1) 查找；雙向鏈結串列提供 O(1) 的「移到最前面」與「刪除最尾端」。兩者結合：dict 的 value 指向鏈結串列節點。

from __future__ import annotations

from collections import OrderedDict
from typing import Optional


class LRUCacheOD:
    """OrderedDict 版：面試時先寫這個，再被要求「不用 OrderedDict」時寫手刻版。"""

    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.data: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        self.data.move_to_end(key)             # 標記為最近使用
        return self.data[key]

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)      # 淘汰最舊的


class _Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key: int = 0, value: int = 0) -> None:
        self.key = key
        self.value = value
        self.prev: Optional[_Node] = None
        self.next: Optional[_Node] = None


class LRUCache:
    """dict + 雙向鏈結串列。head 與 tail 是 sentinel（哨兵）節點，省去所有 None 判斷。
    head.next 是最近使用，tail.prev 是最久未使用。"""

    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.map: dict[int, _Node] = {}
        self.head, self.tail = _Node(), _Node()
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node: _Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node: _Node) -> None:
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._remove(node)
        self._add_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._remove(node)
            self._add_front(node)
            return
        node = _Node(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]              # 節點要存 key，才能從 dict 刪掉


for cls in (LRUCacheOD, LRUCache):
    c = cls(2)
    c.put(1, 1)
    c.put(2, 2)
    assert c.get(1) == 1                       # 1 變成最近使用
    c.put(3, 3)                                # 淘汰 2
    assert c.get(2) == -1
    c.put(4, 4)                                # 淘汰 1
    assert c.get(1) == -1
    assert c.get(3) == 3 and c.get(4) == 4
    c.put(3, 30)                               # 更新既有 key 不淘汰
    assert c.get(3) == 30 and c.get(4) == 4

為什麼要雙向？

刪除任意節點需要知道它的前一個節點；單向串列要 O(n) 去找。

為什麼節點要存 key？

淘汰尾端節點時要同步從 dict 刪除，需要知道它的 key。

Thread-safety

上面都不是 thread-safe；多執行緒要加 threading.Lock。functools.lru_cache 本身是 thread-safe 的（內部有鎖），但只適合快取函式結果。

TTL

廣告場景的快取通常還要過期時間：節點多存 expire_at，get 時檢查過期就刪除（lazy expiration），與 Redis 的做法類似。

題型模式總覽：看到什麼訊號，想到什麼模式 高頻

刷題的目的不是背答案，而是建立「訊號 → 模式」的反射。以下決策圖是面對新題目時的第一個思考步驟，接著各節給出每個模式的訊號、模板與代表題。

模式：Two Pointers、Sliding Window、Hash Map 計數、Prefix Sum 基礎

Two Pointers

訊號：已排序陣列找配對、從兩端往中間收斂（回文、容器）、同向快慢指針（原地去重、linked list 找環/中點）。核心：每一步都能確定「某一端的元素不可能是答案」，所以可以安全地丟掉它，把 O(n²) 降到 O(n)。

def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    """LC 167：相向雙指針。和太小 → 左指針右移；太大 → 右指針左移。O(n) / O(1)。"""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return [lo + 1, hi + 1]
        if s < target:
            lo += 1
        else:
            hi -= 1
    return []


def three_sum(nums: list[int]) -> list[list[int]]:
    """LC 15：排序 + 固定一個 + 雙指針，注意三處去重。O(n^2)。"""
    nums = sorted(nums)
    res: list[list[int]] = []
    n = len(nums)
    for i in range(n - 2):
        if nums[i] > 0:
            break                                  # 最小的都 > 0，不可能和為 0
        if i > 0 and nums[i] == nums[i - 1]:
            continue                               # 去重 1：固定值重複
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1                        # 去重 2：左值重複（右側自然會被跳過）
    return res


def max_area(height: list[int]) -> int:
    """LC 11：移動較矮的那一邊——移動較高的那邊，寬度變小、高度不會超過矮邊，不可能更好。"""
    lo, hi = 0, len(height) - 1
    best = 0
    while lo < hi:
        best = max(best, (hi - lo) * min(height[lo], height[hi]))
        if height[lo] < height[hi]:
            lo += 1
        else:
            hi -= 1
    return best


def remove_duplicates(nums: list[int]) -> int:
    """LC 26：同向快慢指針，slow 指向下一個要寫入的位置。"""
    slow = 0
    for fast in range(len(nums)):
        if fast == 0 or nums[fast] != nums[fast - 1]:
            nums[slow] = nums[fast]
            slow += 1
    return slow


assert two_sum_sorted([2, 7, 11, 15], 9) == [1, 2]
assert three_sum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
assert three_sum([0, 0, 0, 0]) == [[0, 0, 0]]
assert max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
arr = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k = remove_duplicates(arr)
assert arr[:k] == [0, 1, 2, 3, 4]

Sliding Window

訊號：「連續」子陣列/子字串 + 最長/最短/計數 + 某種條件（至多 k 個不同、包含所有字元、和 ≥ target）。前提：條件要有單調性——視窗擴大只會讓它「更不合法」（或更合法），才能用「右擴、左縮」的方式。若陣列含負數且求和，單調性不成立，要改用 prefix sum。

from collections import Counter


def longest_with_at_most_k_distinct(s: str, k: int) -> int:
    """模板（LC 340 / LC 904 Fruit Into Baskets）：
    1) right 擴張並更新視窗狀態；2) while 不合法就收縮 left；3) 此時視窗合法，更新答案。O(n)。"""
    window: Counter[str] = Counter()
    left = best = 0
    for right, ch in enumerate(s):
        window[ch] += 1
        while len(window) > k:
            out = s[left]
            window[out] -= 1
            if window[out] == 0:
                del window[out]                  # 要刪掉，len(window) 才是 distinct 數
            left += 1
        best = max(best, right - left + 1)
    return best


def min_window(s: str, t: str) -> str:
    """LC 76：求最短 → 在「合法」時收縮並更新答案。missing = 還缺幾個字元。O(|s| + |t|)。"""
    need = Counter(t)
    missing = len(t)
    left = 0
    best_start, best_len = 0, float("inf")
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1                            # 可為負：代表視窗中多出來的
        while missing == 0:
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            need[s[left]] += 1
            if need[s[left]] > 0:                # 移出的是必要字元
                missing += 1
            left += 1
    return "" if best_len == float("inf") else s[best_start:best_start + int(best_len)]


def character_replacement(s: str, k: int) -> int:
    """LC 424：視窗長度 - 出現最多字元數 <= k 即合法。max_freq 不需要在收縮時遞減（只關心更大的答案）。"""
    count: Counter[str] = Counter()
    left = max_freq = best = 0
    for right, ch in enumerate(s):
        count[ch] += 1
        max_freq = max(max_freq, count[ch])
        while (right - left + 1) - max_freq > k:
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best


def find_anagrams(s: str, p: str) -> list[int]:
    """LC 438：固定長度視窗。"""
    k, need, window, res = len(p), Counter(p), Counter(), []
    for i, ch in enumerate(s):
        window[ch] += 1
        if i >= k:
            out = s[i - k]
            window[out] -= 1
            if window[out] == 0:
                del window[out]
        if window == need:
            res.append(i - k + 1)
    return res


assert longest_with_at_most_k_distinct("eceba", 2) == 3
assert longest_with_at_most_k_distinct("aa", 1) == 2
assert min_window("ADOBECODEBANC", "ABC") == "BANC"
assert min_window("a", "a") == "a" and min_window("a", "aa") == ""
assert character_replacement("ABAB", 2) == 4
assert character_replacement("AABABBA", 1) == 4
assert find_anagrams("cbaebabacd", "abc") == [0, 6]
assert find_anagrams("abab", "ab") == [0, 1, 2]

Hash Map 計數

訊號：「是否見過」、「出現幾次」、「找配對的另一半」、「分組」。用空間換時間，把 O(n) 的線性搜尋換成 O(1) 查詢。

def two_sum(nums: list[int], target: int) -> list[int]:
    """LC 1：邊走邊查「另一半是否見過」。O(n)。先查再存，避免同一元素用兩次。"""
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []


def longest_consecutive(nums: list[int]) -> int:
    """LC 128：只從序列起點（x-1 不存在）開始往上數 → 每個數最多被看兩次，O(n)。"""
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:
            y = x
            while y + 1 in s:
                y += 1
            best = max(best, y - x + 1)
    return best


def first_uniq_char(s: str) -> int:
    """LC 387"""
    from collections import Counter
    cnt = Counter(s)
    return next((i for i, ch in enumerate(s) if cnt[ch] == 1), -1)


assert two_sum([2, 7, 11, 15], 9) == [0, 1]
assert two_sum([3, 3], 6) == [0, 1]
assert longest_consecutive([100, 4, 200, 1, 3, 2]) == 4
assert longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) == 9
assert longest_consecutive([]) == 0
assert first_uniq_char("leetcode") == 0 and first_uniq_char("aabb") == -1

Prefix Sum（前綴和）

訊號：多次區間和查詢、「和為 k 的子陣列個數」（含負數時 sliding window 不適用）、「除了自己以外的乘積」。核心：sum(nums[i:j]) = P[j] - P[i]，其中 P[0] = 0。搭配 hash map 記錄「看過的前綴和出現次數」可以 O(n) 解計數問題。

from collections import Counter
from itertools import accumulate


def subarray_sum(nums: list[int], k: int) -> int:
    """LC 560：P[j] - P[i] == k  ⇔  P[i] == P[j] - k。O(n)。"""
    seen = Counter({0: 1})                  # 空前綴：讓「從頭開始的子陣列」也能被算到
    prefix = count = 0
    for x in nums:
        prefix += x
        count += seen[prefix - k]
        seen[prefix] += 1
    return count


def product_except_self(nums: list[int]) -> list[int]:
    """LC 238：左側乘積 × 右側乘積，不用除法。O(n) 時間、O(1) 額外空間（不計輸出）。"""
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out


class NumMatrix:
    """LC 304：2D 前綴和，O(RC) 預處理、O(1) 查詢（容斥原理）。"""

    def __init__(self, matrix: list[list[int]]) -> None:
        rows, cols = len(matrix), len(matrix[0]) if matrix else 0
        self.P = [[0] * (cols + 1) for _ in range(rows + 1)]
        for r in range(rows):
            for c in range(cols):
                self.P[r + 1][c + 1] = matrix[r][c] + self.P[r][c + 1] + self.P[r + 1][c] - self.P[r][c]

    def sum_region(self, r1: int, c1: int, r2: int, c2: int) -> int:
        P = self.P
        return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]


assert subarray_sum([1, 1, 1], 2) == 2
assert subarray_sum([1, 2, 3], 3) == 2
assert subarray_sum([1, -1, 0], 0) == 3
assert product_except_self([1, 2, 3, 4]) == [24, 12, 8, 6]
assert product_except_self([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]
nm = NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]])
assert (nm.sum_region(2, 1, 4, 3), nm.sum_region(1, 1, 2, 2), nm.sum_region(1, 2, 2, 4)) == (8, 11, 12)

# 業務應用：每小時曝光數的區間查詢
hourly = [120, 80, 95, 300, 410, 220]
P = [0, *accumulate(hourly)]
assert P[5] - P[2] == 95 + 300 + 410              # 第 2~4 小時的曝光總和，O(1)

模式：Binary Search（含 Search on Answer） 進階

訊號：已排序或部分有序（旋轉陣列）、「找第一個 / 最後一個滿足條件的位置」、「最小的 x 使得 ... 可行」。核心：找到一個單調的判定函式 pred(x)（F F F T T T），二分找第一個 T。

from typing import Callable


def first_true(lo: int, hi: int, pred: Callable[[int], bool]) -> int:
    """在 [lo, hi) 中找第一個 pred 為 True 的位置；全 False 則回傳 hi。pred 必須單調。"""
    while lo < hi:
        mid = (lo + hi) // 2          # Python 沒有溢位問題；其他語言寫 lo + (hi - lo) // 2
        if pred(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


def lower_bound(nums: list[int], target: int) -> int:
    return first_true(0, len(nums), lambda i: nums[i] >= target)


def search_rotated(nums: list[int], target: int) -> int:
    """LC 33：每次二分，左右至少有一半是有序的；判斷 target 是否落在有序的那一半。O(log n)。"""
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:                 # 左半有序
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                     # 右半有序
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1


def find_min_rotated(nums: list[int]) -> int:
    """LC 153：跟右端比較。nums[mid] > nums[hi] 代表最小值在右半。"""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]


assert lower_bound([1, 3, 3, 5], 3) == 1 and lower_bound([1, 3, 3, 5], 6) == 4
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 0) == 4
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 3) == -1
assert search_rotated([1], 0) == -1 and search_rotated([3, 1], 1) == 1
assert find_min_rotated([3, 4, 5, 1, 2]) == 1 and find_min_rotated([11, 13, 15, 17]) == 11

Search on Answer（對答案二分）

當題目問「最小的速度 / 容量 / 時間使得任務可完成」，且「x 可行 ⇒ 更大的 x 也可行」時，不要去想直接算出答案，而是二分答案並寫一個 O(n) 的可行性檢查。總複雜度 O(n log(range))。

def min_eating_speed(piles: list[int], h: int) -> int:
    """LC 875 Koko：速度 k 可行 ⇔ sum(ceil(p / k)) <= h。答案範圍 [1, max(piles)]。"""
    def hours(k: int) -> int:
        return sum((p + k - 1) // k for p in piles)   # 整數 ceil，避免浮點誤差

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo


def ship_within_days(weights: list[int], days: int) -> int:
    """LC 1011：容量下界 max(weights)（最重的要裝得下），上界 sum(weights)（一天運完）。"""
    def days_needed(cap: int) -> int:
        d, cur = 1, 0
        for w in weights:
            if cur + w > cap:
                d += 1
                cur = 0
            cur += w
        return d

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(mid) <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo


assert min_eating_speed([3, 6, 7, 11], 8) == 4
assert min_eating_speed([30, 11, 23, 4, 20], 5) == 30
assert min_eating_speed([30, 11, 23, 4, 20], 6) == 23
assert ship_within_days(list(range(1, 11)), 5) == 15
assert ship_within_days([3, 2, 2, 4, 1, 4], 3) == 6
assert ship_within_days([1, 2, 3, 1, 1], 4) == 3

模式：Stack / Monotonic Stack 與 Queue / BFS 進階

Stack 與 Monotonic Stack

訊號：括號配對、巢狀解析、運算式求值（stack）；「下一個更大/更小的元素」、「往左/右能延伸多遠」、直方圖最大矩形（monotonic stack）；滑動視窗最大值（monotonic deque）。核心：stack 裡維持單調性，每個元素最多 push、pop 各一次 → O(n)。元素被 pop 的那一刻，就是「找到它的答案」的時候。

from collections import deque


def daily_temperatures(temps: list[int]) -> list[int]:
    """LC 739：stack 存「還沒等到更暖天氣」的 index，溫度由底到頂遞減。"""
    res = [0] * len(temps)
    stack: list[int] = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j                       # j 的「下一個更大」就是 i
        stack.append(i)
    return res


def largest_rectangle_area(heights: list[int]) -> int:
    """LC 84：stack 存 (起點, 高度) 且高度遞增。被 pop 時，它能向右延伸到 i、向左延伸到 start。"""
    stack: list[tuple[int, int]] = []
    best = 0
    for i, h in enumerate([*heights, 0]):        # 尾端放 0 把 stack 全部清出
        start = i
        while stack and stack[-1][1] >= h:
            idx, height = stack.pop()
            best = max(best, height * (i - idx))
            start = idx                          # 新的矮柱子可以往左延伸到被 pop 者的起點
        stack.append((start, h))
    return best


def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """LC 239：monotonic deque 存 index，對應值遞減；隊首就是視窗最大值。O(n)。"""
    dq: deque[int] = deque()
    res: list[int] = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                             # 比 x 小又比 x 早離開的，永遠不會是最大值
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()                         # 滑出視窗
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res


def eval_rpn(tokens: list[str]) -> int:
    """LC 150：除法向 0 取整（Python 的 // 是向負無限大取整，要特別處理）。"""
    stack: list[int] = []
    for tok in tokens:
        if tok in {"+", "-", "*", "/"}:
            b, a = stack.pop(), stack.pop()      # 注意順序：先 pop 的是右運算元
            if tok == "+":
                stack.append(a + b)
            elif tok == "-":
                stack.append(a - b)
            elif tok == "*":
                stack.append(a * b)
            else:
                q = abs(a) // abs(b)
                stack.append(q if (a < 0) == (b < 0) else -q)
        else:
            stack.append(int(tok))
    return stack[0]


assert daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]) == [1, 1, 4, 2, 1, 1, 0, 0]
assert largest_rectangle_area([2, 1, 5, 6, 2, 3]) == 10
assert largest_rectangle_area([2, 4]) == 4
assert max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert eval_rpn(["2", "1", "+", "3", "*"]) == 9
assert eval_rpn(["4", "13", "5", "/", "+"]) == 6
assert eval_rpn(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]) == 22

Queue / BFS（最短路徑、多源 BFS）

訊號：無權重圖/格子上的「最少步數」、「最短轉換次數」、「同時擴散」、「層序」。核心：BFS 按距離由近到遠展開，第一次到達某節點時的距離就是最短距離。多源 BFS：把所有起點同時放進佇列（距離 0），等同於加一個超級源點。

from collections import defaultdict, deque

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def oranges_rotting(grid: list[list[int]]) -> int:
    """LC 994：多源 BFS，所有爛橘子同時是起點；每一「層」= 1 分鐘。O(RC)。"""
    rows, cols = len(grid), len(grid[0])
    q: deque[tuple[int, int]] = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while q and fresh:
        minutes += 1
        for _ in range(len(q)):                  # 一次處理一整層
            r, c = q.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2             # 入隊時就標記，避免重複入隊
                    fresh -= 1
                    q.append((nr, nc))
    return minutes if fresh == 0 else -1


def shortest_path_binary_matrix(grid: list[list[int]]) -> int:
    """LC 1091：8 方向 BFS，回傳路徑上的格子數。"""
    n = len(grid)
    if grid[0][0] or grid[n - 1][n - 1]:
        return -1
    q = deque([(0, 0, 1)])
    seen = {(0, 0)}
    while q:
        r, c, d = q.popleft()
        if (r, c) == (n - 1, n - 1):
            return d
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    q.append((nr, nc, d + 1))
    return -1


def ladder_length(begin: str, end: str, word_list: list[str]) -> int:
    """LC 127：每個單字是節點；用 'h*t' 這種萬用字元 pattern 分桶找鄰居，避免 O(N^2) 兩兩比較。"""
    words = set(word_list)
    if end not in words:
        return 0
    buckets: defaultdict[str, list[str]] = defaultdict(list)
    for w in words | {begin}:
        for i in range(len(w)):
            buckets[w[:i] + "*" + w[i + 1:]].append(w)
    q = deque([(begin, 1)])
    seen = {begin}
    while q:
        w, d = q.popleft()
        if w == end:
            return d
        for i in range(len(w)):
            key = w[:i] + "*" + w[i + 1:]
            for nxt in buckets[key]:
                if nxt not in seen:
                    seen.add(nxt)
                    q.append((nxt, d + 1))
            buckets[key] = []                    # 這個桶已展開過，清空省時間
    return 0


assert oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]) == 4
assert oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]) == -1
assert oranges_rotting([[0, 2]]) == 0
assert shortest_path_binary_matrix([[0, 1], [1, 0]]) == 2
assert shortest_path_binary_matrix([[0, 0, 0], [1, 1, 0], [1, 1, 0]]) == 4
assert shortest_path_binary_matrix([[1, 0, 0], [1, 1, 0], [1, 1, 0]]) == -1
assert ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) == 5
assert ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]) == 0

模式：DFS / Backtracking（Subsets、Permutations、Combination Sum） 進階

訊號：「列出所有」組合、排列、子集、分割方式、合法配置（N-Queens、數獨）。n 通常很小（≤ 20）。模板：path 存目前的選擇；每層「做選擇 → 遞迴 → 撤銷」；收集答案時要 path.copy()。三個決策點：(1) 何時收集答案；(2) 下一層從哪裡開始選（start 決定組合 vs 排列）；(3) 如何剪枝與去重。

def subsets(nums: list[int]) -> list[list[int]]:
    """LC 78：每個節點都是一個答案。O(n * 2^n)。"""
    res: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int) -> None:
        res.append(path.copy())
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)              # i + 1：每個元素只用一次，且不回頭 → 組合
            path.pop()

    backtrack(0)
    return res


def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    """LC 90：先排序；同一層中跳過相同的值（i > start 且與前一個相同）。"""
    nums = sorted(nums)
    res: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int) -> None:
        res.append(path.copy())
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return res


def permute(nums: list[int]) -> list[list[int]]:
    """LC 46：排列要從頭選，用 used 標記。O(n * n!)。"""
    res: list[list[int]] = []
    path: list[int] = []
    used = [False] * len(nums)

    def backtrack() -> None:
        if len(path) == len(nums):
            res.append(path.copy())
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return res


def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    """LC 39：元素可重複使用 → 下一層仍從 i 開始；排序後可在超過時 break 剪枝。"""
    candidates = sorted(candidates)
    res: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int, remain: int) -> None:
        if remain == 0:
            res.append(path.copy())
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remain:
                break                     # 後面更大，全部剪掉
            path.append(c)
            backtrack(i, remain - c)
            path.pop()

    backtrack(0, target)
    return res


assert subsets([1, 2, 3]) == [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
assert subsets_with_dup([2, 1, 2]) == [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
assert permute([1, 2, 3]) == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
assert combination_sum([2, 3, 6, 7], 7) == [[2, 2, 3], [7]]
assert combination_sum([2, 3, 5], 8) == [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

模式：Tree（Traversal、LCA、BST、Level Order） 基礎

訊號：二元樹、BST、祖先、深度、路徑和。思考框架：「這個節點需要從子樹拿到什麼資訊（後序，回傳值）？」或「需要從父節點傳下什麼資訊（前序，參數）？」大部分樹題是 O(n) 時間、O(h) 空間（h 為高度，最壞 O(n)）。

from __future__ import annotations

import math
from collections import deque
from dataclasses import dataclass
from typing import Optional


@dataclass(eq=False)                # eq=False：用 identity 比較節點，LCA 才能用 is
class TreeNode:
    val: int
    left: Optional[TreeNode] = None
    right: Optional[TreeNode] = None


def build(values: list[Optional[int]]) -> Optional[TreeNode]:
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    q, i = deque([root]), 1
    while q and i < len(values):
        node = q.popleft()
        for side in ("left", "right"):
            if i < len(values) and values[i] is not None:
                setattr(node, side, TreeNode(values[i]))
                q.append(getattr(node, side))
            i += 1
    return root


def find(root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if root is None or root.val == val:
        return root
    return find(root.left, val) or find(root.right, val)


def lowest_common_ancestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
    """LC 236：後序。左右子樹各找到一個 → 自己就是 LCA；只有一邊找到 → 往上傳。O(n)。"""
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left or right


def is_valid_bst(root: Optional[TreeNode], lo: float = -math.inf, hi: float = math.inf) -> bool:
    """LC 98：前序，往下傳「合法範圍」。只比較父子是錯的（見測試第三例）。"""
    if root is None:
        return True
    if not lo < root.val < hi:
        return False
    return is_valid_bst(root.left, lo, root.val) and is_valid_bst(root.right, root.val, hi)


def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    """LC 102：BFS，用 len(q) 切出每一層。"""
    res: list[list[int]] = []
    q = deque([root]) if root else deque()
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)
    return res


def diameter(root: Optional[TreeNode]) -> int:
    """LC 543：後序回傳高度，同時用左右高度更新「經過此節點的最長路徑」。"""
    best = 0

    def height(node: Optional[TreeNode]) -> int:
        nonlocal best
        if node is None:
            return 0
        lh, rh = height(node.left), height(node.right)
        best = max(best, lh + rh)
        return 1 + max(lh, rh)

    height(root)
    return best


t = build([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
assert lowest_common_ancestor(t, find(t, 5), find(t, 1)).val == 3
assert lowest_common_ancestor(t, find(t, 5), find(t, 4)).val == 5      # 節點可以是自己的祖先
assert is_valid_bst(build([2, 1, 3]))
assert not is_valid_bst(build([5, 1, 4, None, None, 3, 6]))
assert not is_valid_bst(build([5, 4, 6, None, None, 3, 7]))            # 3 在 5 的右子樹
assert level_order(build([3, 9, 20, None, None, 15, 7])) == [[3], [9, 20], [15, 7]]
assert diameter(build([1, 2, 3, 4, 5])) == 3

延伸：BST 的 LCA（LC 235）可利用大小關係 O(h) 迭代；BST 第 k 小（LC 230）用中序迭代第 k 個；序列化/反序列化（LC 297）用前序 + None 標記。

模式：Graph（Topological Sort、Union-Find、Dijkstra） 進階

import heapq
from collections import defaultdict, deque
from typing import Hashable


def find_order(n: int, prerequisites: list[list[int]]) -> list[int]:
    """LC 210 Kahn：入度 0 的先做；做完扣掉鄰居入度。輸出數量 < n 代表有環。"""
    graph: list[list[int]] = [[] for _ in range(n)]
    indeg = [0] * n
    for course, pre in prerequisites:
        graph[pre].append(course)
        indeg[course] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order: list[int] = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []


class DSU:
    """Union-Find：path compression（迭代版，避免遞迴深度）+ union by size。"""

    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x: int) -> int:
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:             # 第二趟：沿路全部直接指向 root
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                          # 已在同一集合 → 這條邊會形成環
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                      # 小樹接到大樹下
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True


def find_circle_num(is_connected: list[list[int]]) -> int:
    """LC 547 Number of Provinces"""
    n = len(is_connected)
    dsu = DSU(n)
    for i in range(n):
        for j in range(i + 1, n):
            if is_connected[i][j]:
                dsu.union(i, j)
    return dsu.components


def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    """LC 684：第一條連接「已連通」兩點的邊就是多餘的。"""
    dsu = DSU(len(edges) + 1)
    for a, b in edges:
        if not dsu.union(a, b):
            return [a, b]
    return []


def resolve_identities(links: list[tuple[Hashable, Hashable]]) -> list[set[Hashable]]:
    """業務版：cookie / device_id / email 兩兩出現在同一事件即視為同一人，求每個人的所有 ID。"""
    parent: dict[Hashable, Hashable] = {}

    def find(x: Hashable) -> Hashable:
        parent.setdefault(x, x)
        root = x
        while parent[root] != root:
            root = parent[root]
        while parent[x] != root:
            parent[x], x = root, parent[x]
        return root

    for a, b in links:
        parent[find(a)] = find(b)
    groups: defaultdict[Hashable, set[Hashable]] = defaultdict(set)
    for x in list(parent):
        groups[find(x)].add(x)
    return sorted(groups.values(), key=lambda g: sorted(map(str, g)))


def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    """LC 743 Dijkstra：heap 取目前距離最小的節點；第一次 pop 出來時距離即為最短（lazy deletion）。"""
    graph: defaultdict[int, list[tuple[int, int]]] = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    dist: dict[int, int] = {}
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in dist:
            continue                              # 舊的、較長的紀錄，略過
        dist[u] = d
        for v, w in graph[u]:
            if v not in dist:
                heapq.heappush(heap, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1


assert find_order(2, [[1, 0]]) == [0, 1]
assert find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) == [0, 1, 2, 3]
assert find_order(2, [[1, 0], [0, 1]]) == []
assert find_circle_num([[1, 1, 0], [1, 1, 0], [0, 0, 1]]) == 2
assert find_redundant_connection([[1, 2], [1, 3], [2, 3]]) == [2, 3]
assert find_redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]) == [1, 4]
groups = resolve_identities([("cookie:a", "email:x"), ("device:1", "email:x"), ("cookie:b", "device:2")])
assert groups == [{"cookie:a", "email:x", "device:1"}, {"cookie:b", "device:2"}]
assert network_delay_time([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2) == 2
assert network_delay_time([[1, 2, 1]], 2, 2) == -1

模式：Heap、Intervals、Greedy 進階

Heap（Top K、Merge K Sorted、Median of Stream）

訊號：top k / kth largest、反覆取最小/最大、合併多個已排序序列、資料流中的中位數。關鍵技巧：求「最大的 k 個」用大小為 k 的 min-heap（頂端是第 k 大，O(n log k)，且適合串流）。

from __future__ import annotations

import heapq
from typing import Optional


def find_kth_largest(nums: list[int], k: int) -> int:
    """LC 215：size-k min-heap，O(n log k)。另有 quickselect 平均 O(n)、最壞 O(n^2)。"""
    heap = nums[:k]
    heapq.heapify(heap)
    for x in nums[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)       # pop + push 一次完成
    return heap[0]


class ListNode:
    def __init__(self, val: int = 0, next: Optional[ListNode] = None) -> None:
        self.val, self.next = val, next


def merge_k_lists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    """LC 23：heap 放每條 list 的目前頭節點。(val, i, node) 中的 i 避免比較 ListNode。O(N log k)。"""
    heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapq.heapify(heap)
    dummy = tail = ListNode()
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next


class MedianFinder:
    """LC 295：small 是 max-heap（存負值）放較小的一半，large 是 min-heap 放較大的一半。
    維持 len(small) == len(large) 或多 1。add O(log n)、median O(1)。"""

    def __init__(self) -> None:
        self.small: list[int] = []
        self.large: list[int] = []

    def add_num(self, num: int) -> None:
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))   # 確保 small 的最大 <= large 的最小
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def find_median(self) -> float:
        if len(self.small) > len(self.large):
            return float(-self.small[0])
        return (-self.small[0] + self.large[0]) / 2


def to_list(node: Optional[ListNode]) -> list[int]:
    out = []
    while node:
        out.append(node.val)
        node = node.next
    return out


def from_list(vals: list[int]) -> Optional[ListNode]:
    dummy = tail = ListNode()
    for v in vals:
        tail.next = tail = ListNode(v)
    return dummy.next


assert find_kth_largest([3, 2, 1, 5, 6, 4], 2) == 5
assert find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4
merged = merge_k_lists([from_list([1, 4, 5]), from_list([1, 3, 4]), from_list([2, 6]), None])
assert to_list(merged) == [1, 1, 2, 3, 4, 4, 5, 6]
mf = MedianFinder()
mf.add_num(1)
mf.add_num(2)
assert mf.find_median() == 1.5
mf.add_num(3)
assert mf.find_median() == 2.0

Intervals

訊號：overlapping、merge、schedule、meeting rooms、最少移除。模板：先排序（合併類依 start，選最多不重疊類依 end），再一次掃描；需要「同時有幾個」用 sweep line 或 min-heap 存結束時間。合併與 sweep line 已在 題 9-4 示範。

def insert_interval(intervals: list[list[int]], new: list[int]) -> list[list[int]]:
    """LC 57：三段式——完全在左邊的、與 new 重疊的（合併）、完全在右邊的。O(n)。"""
    res: list[list[int]] = []
    i, n = 0, len(intervals)
    start, end = new
    while i < n and intervals[i][1] < start:
        res.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= end:
        start, end = min(start, intervals[i][0]), max(end, intervals[i][1])
        i += 1
    res.append([start, end])
    res.extend(intervals[i:])
    return res


def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    """LC 435：依結束時間排序，貪心保留「最早結束」的區間，留給後面最多空間。O(n log n)。"""
    kept_end = float("-inf")
    removed = 0
    for start, end in sorted(intervals, key=lambda iv: iv[1]):
        if start >= kept_end:
            kept_end = end
        else:
            removed += 1
    return removed


assert insert_interval([[1, 3], [6, 9]], [2, 5]) == [[1, 5], [6, 9]]
assert insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) == [[1, 2], [3, 10], [12, 16]]
assert insert_interval([], [5, 7]) == [[5, 7]]
assert erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]]) == 1
assert erase_overlap_intervals([[1, 2], [1, 2], [1, 2]]) == 2
assert erase_overlap_intervals([[1, 2], [2, 3]]) == 0

Greedy

訊號：每一步做局部最佳選擇就能得到全域最佳，常見於區間排程、跳躍、分配。風險：greedy 很容易「看起來對」但其實錯。面試時要能給出直覺證明（exchange argument：任何最佳解都可以在不變差的情況下換成 greedy 的選擇），或舉不出反例時至少說明理由；若找到反例就改用 DP（例如任意面額的找零錢，greedy 會錯）。

def can_jump(nums: list[int]) -> bool:
    """LC 55：維護目前能到達的最遠位置。O(n)。"""
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + step)
    return True


def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    """LC 134：總油量 >= 總消耗則必有解；油箱變負時，起點到此處之間都不可能是起點，從下一站重來。"""
    if sum(gas) < sum(cost):
        return -1
    start = tank = 0
    for i, (g, c) in enumerate(zip(gas, cost)):
        tank += g - c
        if tank < 0:
            start, tank = i + 1, 0
    return start


def partition_labels(s: str) -> list[int]:
    """LC 763：記錄每個字母最後出現位置；目前片段的結尾 = 片段內字母最後位置的最大值。"""
    last = {ch: i for i, ch in enumerate(s)}
    res: list[int] = []
    start = end = 0
    for i, ch in enumerate(s):
        end = max(end, last[ch])
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res


def coin_change_greedy(coins: list[int], amount: int) -> int:
    """反例示範：greedy 先拿最大面額，對 [1, 3, 4] 湊 6 會得到 4+1+1（3 枚），最佳是 3+3（2 枚）。"""
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count if amount == 0 else -1


assert can_jump([2, 3, 1, 1, 4]) and not can_jump([3, 2, 1, 0, 4])
assert can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) == 3
assert can_complete_circuit([2, 3, 4], [3, 4, 3]) == -1
assert partition_labels("ababcbacadefegdehijhklij") == [9, 7, 8]
assert coin_change_greedy([1, 3, 4], 6) == 3        # 不是最佳解 2 → 需要 DP（見下一節）

模式：Dynamic Programming 與狀態定義方法 高頻 深入

訊號：「有幾種方法」、「最小成本 / 最大收益」、「是否可能」，且暴力遞迴中有重複子問題。Appier 面試的「能否用 DP 優化」追問，本質就是要你把暴力搜尋改寫成這一節的形式。

狀態定義六步驟

1. 用一句中文定義狀態：「dp[i] = 前 i 個元素中、以 ... 為條件的最佳值/方法數」。定義講不清楚，後面一定寫錯。常見形式：前 i 個（prefix）、以 i 結尾（LIS）、區間 [i, j]、兩個序列的前 i 與前 j 個（LCS）、加上一個小維度（剩餘容量、持有狀態）。
2. 轉移方程：最後一步有哪些選擇？dp[i] 由哪些更小的狀態組成？
3. Base case：空字串、0 元、第 0 列。
4. 計算順序：確保計算 dp[i] 時依賴的狀態都已算好（或直接用 memo 遞迴讓順序自動決定）。
5. 答案位置：dp[n]？max(dp)？
6. 空間優化：若只依賴前一列/前兩個值，用滾動陣列或兩個變數。

1D DP：Climbing Stairs、House Robber、Coin Change、Word Break

def climb_stairs(n: int) -> int:
    """LC 70：dp[i] = dp[i-1] + dp[i-2]，只需兩個變數。O(n) / O(1)。"""
    a, b = 1, 1                              # dp[0], dp[1]
    for _ in range(n - 1):
        a, b = b, a + b
    return b


def rob(nums: list[int]) -> int:
    """LC 198：dp[i] = 前 i 間房最多能搶多少 = max(不搶第 i 間, 搶第 i 間 + dp[i-2])。"""
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1


def coin_change(coins: list[int], amount: int) -> int:
    """LC 322：dp[a] = 湊出 a 元的最少硬幣數 = min(dp[a - c] + 1)。O(amount * len(coins))。"""
    INF = amount + 1                          # 不可能超過 amount 枚，當作無限大
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1


def change(amount: int, coins: list[int]) -> int:
    """LC 518 組合數（完全背包）：外層跑硬幣 → 同一組合只被算一次（不考慮順序）。"""
    dp = [1] + [0] * amount
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]


def word_break(s: str, word_dict: list[str]) -> bool:
    """LC 139：dp[i] = s[:i] 可否被切分。O(n * 字典大小 * 單字長度)。"""
    words = set(word_dict)
    lengths = {len(w) for w in words}
    dp = [True] + [False] * len(s)
    for i in range(1, len(s) + 1):
        dp[i] = any(L <= i and dp[i - L] and s[i - L:i] in words for L in lengths)
    return dp[len(s)]


assert climb_stairs(1) == 1 and climb_stairs(2) == 2 and climb_stairs(5) == 8
assert rob([1, 2, 3, 1]) == 4 and rob([2, 7, 9, 3, 1]) == 12 and rob([]) == 0
assert coin_change([1, 2, 5], 11) == 3
assert coin_change([2], 3) == -1 and coin_change([1], 0) == 0
assert coin_change([1, 3, 4], 6) == 2                     # greedy 會得到 3，DP 正確
assert change(5, [1, 2, 5]) == 4 and change(3, [2]) == 0
assert word_break("leetcode", ["leet", "code"])
assert word_break("applepenapple", ["apple", "pen"])
assert not word_break("catsandog", ["cats", "dog", "sand", "and", "cat"])

2D DP：LCS 與 Edit Distance

def longest_common_subsequence(a: str, b: str) -> int:
    """LC 1143：dp[i][j] = a[:i] 與 b[:j] 的 LCS 長度。
    a[i-1] == b[j-1] → dp[i-1][j-1] + 1；否則 max(dp[i-1][j], dp[i][j-1])。O(mn)。"""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]   # 不要寫 [[0] * (n+1)] * (m+1)：每列會是同一個 list
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]


def min_distance(a: str, b: str) -> int:
    """LC 72 Edit Distance，滾動陣列版：O(mn) 時間、O(n) 空間。
    dp[i][j] = a[:i] 變成 b[:j] 的最少操作數；
    相同 → dp[i-1][j-1]；不同 → 1 + min(取代 dp[i-1][j-1], 刪除 dp[i-1][j], 插入 dp[i][j-1])。"""
    m, n = len(a), len(b)
    prev = list(range(n + 1))                     # dp[0][j] = j（插入 j 次）
    for i in range(1, m + 1):
        cur = [i] + [0] * n                       # dp[i][0] = i（刪除 i 次）
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j - 1], prev[j], cur[j - 1])
        prev = cur
    return prev[n]


assert longest_common_subsequence("abcde", "ace") == 3
assert longest_common_subsequence("abc", "def") == 0
assert min_distance("horse", "ros") == 3
assert min_distance("intention", "execution") == 5
assert min_distance("", "abc") == 3

Knapsack 與 LIS

import bisect


def can_partition(nums: list[int]) -> bool:
    """LC 416 = 0/1 背包：能否選出和為 total/2 的子集。
    1D dp 要「由大到小」迭代容量，確保每個數只被用一次。O(n * target)。"""
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [True] + [False] * target
    for x in nums:
        for cap in range(target, x - 1, -1):      # 反向！正向會變成可重複使用（完全背包）
            dp[cap] = dp[cap] or dp[cap - x]
    return dp[target]


def can_partition_bitset(nums: list[int]) -> bool:
    """同一題的 bitset 技巧：第 k 個 bit 為 1 代表和 k 可達。Python 大整數位移非常快。"""
    total = sum(nums)
    if total % 2:
        return False
    bits = 1
    for x in nums:
        bits |= bits << x
    return bool(bits >> (total // 2) & 1)


def length_of_lis_dp(nums: list[int]) -> int:
    """LC 300 O(n^2)：dp[i] = 以 nums[i] 結尾的 LIS 長度。"""
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)


def length_of_lis(nums: list[int]) -> int:
    """LC 300 O(n log n)：tails[k] = 長度 k+1 的遞增子序列中，最小可能的結尾。
    tails 必遞增 → 用 bisect_left 找替換位置（嚴格遞增用 bisect_left）。"""
    tails: list[int] = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)


for fn in (can_partition, can_partition_bitset):
    assert fn([1, 5, 11, 5]) and not fn([1, 2, 3, 5]) and not fn([1, 2, 5])
for fn in (length_of_lis_dp, length_of_lis):
    assert fn([10, 9, 2, 5, 3, 7, 101, 18]) == 4
    assert fn([0, 1, 0, 3, 2, 3]) == 4
    assert fn([7, 7, 7, 7]) == 1
    assert fn([]) == 0

模式：Trie、Bit Manipulation、Design 題 進階

Trie（前綴樹）

訊號：prefix 查詢、autocomplete、一次搜尋多個單字（LC 212）、IP 路由最長前綴匹配。插入與查詢都是 O(L)，與字典大小無關。

from __future__ import annotations


class TrieNode:
    __slots__ = ("children", "is_word", "count")

    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.is_word = False
        self.count = 0                        # 有多少單字經過此節點（可做前綴計數）


class Trie:
    """LC 208 + autocomplete。"""

    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
            node.count += 1
        node.is_word = True

    def _walk(self, prefix: str) -> TrieNode | None:
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

    def count_prefix(self, prefix: str) -> int:
        node = self._walk(prefix)
        return node.count if node else 0

    def autocomplete(self, prefix: str, limit: int = 5) -> list[str]:
        """依字典序回傳最多 limit 個以 prefix 開頭的單字（迭代 DFS）。"""
        start = self._walk(prefix)
        if start is None:
            return []
        res: list[str] = []
        stack = [(start, prefix)]
        while stack and len(res) < limit:
            node, word = stack.pop()
            if node.is_word:
                res.append(word)
            for ch in sorted(node.children, reverse=True):   # 反向 push → 字典序 pop
                stack.append((node.children[ch], word + ch))
        return res


t = Trie()
for w in ["apple", "app", "appier", "apply", "banana"]:
    t.insert(w)
assert t.search("app") and not t.search("ap") and t.starts_with("ap")
assert t.count_prefix("app") == 4 and t.count_prefix("b") == 1 and t.count_prefix("x") == 0
assert t.autocomplete("app") == ["app", "appier", "apple", "apply"]
assert t.autocomplete("app", limit=2) == ["app", "appier"]

Bit Manipulation 基礎

from functools import reduce
from operator import xor


def single_number(nums: list[int]) -> int:
    """LC 136：其他數都出現兩次 → 全部 XOR。O(n) / O(1)。"""
    return reduce(xor, nums, 0)


def hamming_weight(n: int) -> int:
    """LC 191：每次清掉最低位的 1，迴圈次數 = 1 的個數。"""
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count


def count_bits(n: int) -> list[int]:
    """LC 338：dp[i] = dp[i >> 1] + (i & 1)。O(n)。"""
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp


def is_power_of_two(n: int) -> bool:
    return n > 0 and n & (n - 1) == 0


def subsets_by_mask(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    return [[nums[i] for i in range(n) if mask >> i & 1] for mask in range(1 << n)]


assert single_number([4, 1, 2, 1, 2]) == 4
assert hamming_weight(0b1011) == 3 == (0b1011).bit_count()
assert count_bits(5) == [0, 1, 1, 2, 1, 2]
assert is_power_of_two(64) and not is_power_of_two(0) and not is_power_of_two(6)
assert len(subsets_by_mask([1, 2, 3])) == 8 and [1, 3] in subsets_by_mask([1, 2, 3])

# 業務應用：受眾分群（segment）用 bitmap 表示，第 i 位 = user_id i 是否在分群中
sports_fans = sum(1 << uid for uid in [1, 3, 5, 8])
ios_users = sum(1 << uid for uid in [3, 4, 5])
both = sports_fans & ios_users                      # 交集 = AND，極快
assert [uid for uid in range(10) if both >> uid & 1] == [3, 5]
assert (sports_fans | ios_users).bit_count() == 5   # 聯集人數

Design 題：Min Stack、LRU、LFU

LRU 已在 題 9-6 完整實作。以下補 Min Stack 與 LFU。

from collections import OrderedDict, defaultdict


class MinStack:
    """LC 155：每個元素同時存「push 當下的最小值」，所有操作 O(1)。"""

    def __init__(self) -> None:
        self._stack: list[tuple[int, int]] = []

    def push(self, val: int) -> None:
        current_min = min(val, self._stack[-1][1]) if self._stack else val
        self._stack.append((val, current_min))

    def pop(self) -> None:
        self._stack.pop()

    def top(self) -> int:
        return self._stack[-1][0]

    def get_min(self) -> int:
        return self._stack[-1][1]


class LFUCache:
    """LC 460：淘汰使用次數最少者；次數相同時淘汰最久未使用者。所有操作 O(1)。
    key_val / key_freq：key 的值與次數；freq_keys：次數 → 該次數所有 key（OrderedDict 保留 LRU 順序）；
    min_freq：目前最小次數（新 key 插入時重設為 1；touch 時若該桶清空且是 min_freq 則 +1）。"""

    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.key_val: dict[int, int] = {}
        self.key_freq: dict[int, int] = {}
        self.freq_keys: defaultdict[int, OrderedDict[int, None]] = defaultdict(OrderedDict)
        self.min_freq = 0

    def _touch(self, key: int) -> None:
        f = self.key_freq[key]
        del self.freq_keys[f][key]
        if not self.freq_keys[f]:
            del self.freq_keys[f]
            if self.min_freq == f:
                self.min_freq += 1
        self.key_freq[key] = f + 1
        self.freq_keys[f + 1][key] = None

    def get(self, key: int) -> int:
        if key not in self.key_val:
            return -1
        self._touch(key)
        return self.key_val[key]

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        if key in self.key_val:
            self.key_val[key] = value
            self._touch(key)
            return
        if len(self.key_val) >= self.capacity:
            evict, _ = self.freq_keys[self.min_freq].popitem(last=False)
            if not self.freq_keys[self.min_freq]:
                del self.freq_keys[self.min_freq]
            del self.key_val[evict], self.key_freq[evict]
        self.key_val[key] = value
        self.key_freq[key] = 1
        self.freq_keys[1][key] = None
        self.min_freq = 1


ms = MinStack()
for v in (5, 3, 7, 3):
    ms.push(v)
assert ms.get_min() == 3
ms.pop()
ms.pop()
assert ms.get_min() == 3 and ms.top() == 3
ms.pop()
assert ms.get_min() == 5

lfu = LFUCache(2)
lfu.put(1, 1)
lfu.put(2, 2)
assert lfu.get(1) == 1          # freq: 1→2, 2→1
lfu.put(3, 3)                   # 淘汰 key 2（次數最少）
assert lfu.get(2) == -1
assert lfu.get(3) == 3          # freq: 1→2, 3→2
lfu.put(4, 4)                   # 次數平手 → 淘汰較久未用的 key 1
assert lfu.get(1) == -1 and lfu.get(3) == 3 and lfu.get(4) == 4

LRU vs LFU

LRU 對「最近」敏感，實作簡單，但一次大量掃描（scan）會把熱資料沖掉；LFU 保留長期熱門項目，但舊的高頻項目可能「霸佔」快取，實務上會加入衰減（aging）。Redis 兩者都支援（allkeys-lru、allkeys-lfu，皆為近似實作），見 第 6 章。

其他常見 design 題

LC 380 Insert Delete GetRandom O(1)（list + dict，刪除時與最後一個交換）、LC 362 Design Hit Counter、LC 981 Time Based Key-Value Store（dict + bisect）、LC 355 Design Twitter（heap 合併多個時間線）。

推薦練習清單：60 題（依優先級） 高頻

選題原則：Appier 真題與其直接變形優先，其次是 Blind 75 / NeetCode 150 中與「字串、hash、stack、圖搜尋、DP 優化、設計題」相關、且難度 easy–medium 的核心題，最後是能應付追問的進階題。標 ★ 者為本章已有解答。

P0：Appier 真題與直接變形（20 題，務必全部能默寫）

P1：核心模式（25 題）

P2：進階與追問準備（15 題）

4 週刷題計畫 基礎

假設每天 1.5–2 小時：每天 2–3 題新題 + 1 題複習（重寫前幾天的題目，不看解答）。每週最後一天做一次 45 分鐘模擬面試（找朋友或自己錄影，邊寫邊講）。

面試寫碼時的常見錯誤清單 高頻

面試自測題