Python Tips for Interview

──────────────────────────────────────────────────────────────────────

這一頁整理我在題解裡反覆用到的 Python 手法 — 都是實際寫過的，每個都連到用它的那一題。面試時能少寫幾行、少出幾個 bug，就是這些小 API 的價值。

collections：把資料結構一步到位

defaultdict — 免去「key 不存在」的判斷

分組、建鄰接表時最好用，不用先檢查 key 再初始化：

from collections import defaultdict
table = defaultdict(list)
for s in strs:
    table[tuple(sorted(s))].append(s)   # key 不存在時自動給 []

用過的題：49. Group Anagrams、Graph / BFS·DFS 建鄰接表。計數用 defaultdict(int)，或直接下一個 —

Counter — 計數與「取最多的前幾個」

from collections import Counter
count = Counter(nums)          # {值: 次數}
count.most_common(k)           # 直接拿出現次數前 k 名

用過的題：347. Top K Frequent Elements、75. Sort Colors、1189. Maximum Number of Balloons。

deque — 兩端都 $O(1)$ 的佇列

BFS 的標準容器。千萬不要用 list.pop(0)，那是 $O(n)$：

from collections import deque
q = deque([start])
q.popleft()        # O(1)；list.pop(0) 是 O(n)
q.append(x)

用過的題：127. Word Ladder、994. Rotting Oranges、239. Sliding Window Maximum。細節見 BFS / DFS 模板。

heapq — 只有最小堆，要最大堆就取負

heapq 沒有最大堆。要最大堆就把值變號放進去，取出時再變回來；排序依據不是值本身時，push tuple：

import heapq
heapq.heapify(heap)                       # O(n) 原地建堆
heapq.heappush(heap, (-dist, point))      # 取負 → 模擬最大堆
heapq.heappushpop(heap, (-dist, point))   # 推入再彈出，一步完成

用過的題：973. K Closest Points to Origin、215. Kth Largest Element in an Array、295. Find Median from Data Stream。完整套路見 Heap / Top K 模板。

排序：key 才是重點

key=lambda — 自訂排序依據

points.sort(key=lambda x: x[1])   # 依每個區間的結尾排序

用過的題：452. Minimum Number of Arrows to Burst Balloons、56. Merge Intervals。Intervals 題幾乎第一步都是排序，見 Intervals 模板。

tuple key — 多關鍵字排序，正負號控制升降

回傳 tuple 就是「先比第一個、再比第二個」；某一維要降冪就把值取負：

# 第一維升冪，第二維降冪
envelopes.sort(key=lambda x: (x[0], -x[1]))

用過的題：354. Russian Doll Envelopes — 這個「一維升、一維降」的技巧正是把二維問題壓成一維 LIS 的關鍵。

反向遍歷：不用手算索引

你提到的 reversed(range(...)) 就在這類。兩種寫法等價，我偏好 reversed(range(...)) 因為讀起來就是「從後往前」：

for p in reversed(range(m + n)):   # m+n-1, m+n-2, ..., 0
    ...
# 等價於：
for p in range(m + n - 1, -1, -1):

用過的題：88. Merge Sorted Array（從後往前填，避免覆蓋還沒讀的元素）、739. Daily Temperatures、516. Longest Palindromic Subsequence。

哨兵與初始化

float('inf') — 求最小值的起點

求最小值時初始化成無窮大，第一個真實值就會取代它；求最大值用 float('-inf')：

res = float('inf')
for cost in costs:
    res = min(res, cost)

用過的題：265. Paint House II、256. Paint House。

二維陣列初始化 — 別用 [[0]*n]*m

[[0]*n]*m 會讓每一列共用同一個 list，改一個全部跟著變。要用 comprehension：

grid = [[0] * n for _ in range(m)]   # 每列各自獨立

用過的題：63. Unique Paths II、289. Game of Life。

字串處理

''.join() — 組字串別用 +=

字串是不可變的，迴圈裡 s += c 是 $O(n^2)$。收集進 list 最後 join：

result = ''.join(chars)   # O(n)

用過的題：93. Restore IP Addresses、71. Simplify Path、301. Remove Invalid Parentheses。

ord() / chr() — 字元與數字互換

把字母映射成 0–25 的陣列索引，比 dict 快也省空間：

idx = ord(c) - ord('a')   # 'a'→0, 'b'→1, ...

用過的題：127. Word Ladder、316. Remove Duplicate Letters。

[::-1] — 一行反轉

s[::-1]        # 反轉字串/list

用過的題：557. Reverse Words in a String III、103. Binary Tree Zigzag Level Order Traversal（奇數層反轉）。注意這會建新物件；要原地反轉 list 用 list.reverse()。

bisect — 在排序陣列上二分，不用自己寫

已經排序好的陣列要找「插入位置」或「第一個 ≥ target 的索引」，不用手刻二分，bisect 一行搞定：

from bisect import bisect_left, bisect_right, insort

bisect_left(arr, x)    # 第一個 >= x 的索引（左邊界）
bisect_right(arr, x)   # 第一個 > x 的索引（右邊界）
insort(arr, x)         # 插入並保持有序（插入本身是 O(n)）

bisect_left / bisect_right 對應到我在 Binary Search 模板 裡手寫的 lower/upper bound — 面試時如果不要求自己實作二分，直接用它最省事。

用過的題：1751. Maximum Number of Events That Can Be Attended II（bisect_left(start_days, end + 1) 找下一個能參加的活動）。

另外一個經典用法是 LIS：把「維護一個遞增的 tails 陣列、二分找替換位置」交給 bisect_left，就能把 300. Longest Increasing Subsequence 從 $O(n^2)$ 降到 $O(n\log n)$。

遞迴與快取

@cache — 一行加上記憶化

DP 最快的起手式：先寫暴力遞迴，再加 @cache，就自動有 memoization，不用手動管表格和遍歷順序：

from functools import cache

@cache
def dp(i, prev):
    if i == n:
        return 0
    ...

用過的題：265. Paint House II、70. Climbing Stairs。這個「暴力遞迴 → 加 cache」的順序見 Dynamic Programming 模板。

巢狀函式 + nonlocal — 遞迴時共享外層變數

把遞迴函式定義在主函式內，就能直接用外層的 nums、n、grid，不用一路傳參；要修改外層變數則加 nonlocal：

def kthSmallest(self, root, k):
    ans = None
    def inorder(node):
        nonlocal ans, k    # 要改外層變數才需要 nonlocal
        ...
    inorder(root)
    return ans

用過的題：230. Kth Smallest Element in a BST、394. Decode String、99. Recover Binary Search Tree。

幾個小手法

XOR 消消樂 — 找落單的數

a ^ a == 0、a ^ 0 == a，所以把所有數 XOR 起來，成對的抵銷，剩下的就是答案。$O(1)$ 空間：

ans = 0
for num in nums:
    ans ^= num

用過的題：136. Single Number。

多重賦值與交換 — 不用暫存變數

a, b = b, a + b      # 右邊先整個算好，再一次賦值
prev = curr = None   # 一次初始化多個

用過的題：509. Fibonacci Number、206. Reverse Linked List。

負索引 — 直接取尾端

nums[-1]      # 最後一個
stack[-1]     # 看棧頂（不彈出）

單調棧裡 stack[-1] 看棧頂是最常見的用法，見 單調棧模板。

---

回到總索引 → Coding Interview Preparation