@laigary.com~/coding-interview-pre….md$
$ cat ./coding-interview-preparation.md

Coding Interview Preparation

這一頁是 coding 面試準備的總索引：先照題型把最值得反覆練習的題目刷熟，需要時查各題型的模板，最後把同一個系列的題目放在一起看，感受題目是怎麼被「加料」變形的。

下面依題型列出最需要練習的題目，每一類附一句該題型的核心提醒；想看同類型的更多題目，點每段最後的 tag 連結。

Array & Two Pointers

先問「陣列有沒有排序」— 排序後大多能用雙指針把 O(n2) 降到 O(n)。想不出解法時先寫暴力解，再觀察哪些計算是重複的。

模板 → Two Pointers 模板

更多同類型題目 → #Two Pointers

Sliding Window

右指針負責擴張、左指針負責收縮。動手前先講清楚窗口要維護的條件是什麼（不重複？至多 k 個？），條件被破壞了才移動左指針。

模板 → Sliding Window 模板

更多同類型題目 → #Sliding Window

除了「在排序陣列裡找元素」，更常考的是對答案二分（如 Koko 吃香蕉：答案有單調性就能二分）。邊界寫法固定一種（例如左閉右閉）練到閉著眼睛都不會錯。

模板 → Binary Search 模板

更多同類型題目 → #Binary Search

Hash Table

空間換時間的第一選擇：「找配對、查出現過沒有、分組」都先想 hash。2 Sum 的「補數」思路是一大票題目的原型。

更多同類型題目 → #Hash Table

Stack

「最近的、還沒處理完的東西」就是 stack。成對符號、計算器用普通棧；「下一個更大/更小元素」系列想單調棧。

模板 → 單調棧模板

更多同類型題目 → #Stack

Linked List

dummy head + 快慢指針可以解掉八成的題。先畫圖再寫 code — 指針改動的順序錯了是最常見的 bug。

模板 → Linked List 模板

更多同類型題目 → #Linked List

Tree

先決定遍歷方式（前序 / 中序 / 後序 / 層序），再決定遞迴要回傳什麼給父節點 — 大多數題目就是「在遍歷的某個時機做事」。看到 BST 先想「中序遍歷 = 遞增」。

模板 → Tree 遍歷模板

Tree 是我寫過最多題的一類，變形也最雜，所以這裡再往下拆成小主題，一組四題、一次練一組：

遍歷基本功

遞迴版寫熟之後要能改成 iterative（自己用 stack 模擬），這是 LeetCode 在這三題的共同 follow-up，也是它們真正的考點。難度是 144 最單純、94 最經典、145 最麻煩（做「根右左」再反轉）。

層序遍歷的變形

同一個 BFS 骨架，差別只在「每一層要取什麼」：整層、最右邊一個、最大值、最深的一層。

深度與結構比較

兩棵樹一起遞迴就是同步走。最小深度要小心「單邊子樹為空」不算葉節點，而且用 BFS 找到第一個葉節點就能提早結束。

路徑總和家族

從「根到葉」一路加碼到「任意起點終點」。先問清楚路徑的定義，再決定要不要回溯、要不要前綴和。

後序回傳值（樹形 DP）

這類題的精髓：回傳給父節點的值，和答案要的值常常不一樣。124 回傳單邊最大、答案卻取左右相加，講得出這個差別就贏一半。

最近共同祖先（LCA）

236 的「左右子樹各找到一個，那我就是答案」是原型，其餘四題都是換一個條件。BST 可以直接用值域往下走；不保證節點存在就不能提早回傳；給了 parent 指標就退化成兩條鏈結串列求相交；1676 把兩個節點換成一組，root in nodes 就解決了。

BST 與中序遍歷

看到 BST 先寫中序 — 它就是一個遞增序列。驗證、找第 k 小、找出被交換的兩個節點，全都是同一招。

BST 的增刪查

查跟插入都很短，刪除要處理「有兩個子節點」的情況（拿中序後繼頂替）— 這題值得完整背下來。

序列化與重建

兩個必答的點：哪兩種遍歷可以唯一還原一棵樹，以及為什麼補上 null 標記之後光靠前序就夠了。

改寫指標 / 換結構

這類題不是在算答案，是在原地改指標。先在紙上畫出「改完長什麼樣」再動手，不然一定接錯。

N-ary Tree

把 left / right 換成 children 迴圈，二元樹的寫法幾乎可以整套搬過來。

更多同類型題目 → #Tree

Graph & BFS/DFS

先把題目翻譯成「節點是什麼、邊是什麼」。最短路徑 / 逐層擴散 → BFS；連通性 → DFS 或 UnionFind；依賴順序 → 拓撲排序。

模板 → BFS / DFS 模板

更多同類型題目 → #Graph

Backtracking

模板是固定的：做選擇 → 遞迴 → 撤銷選擇。真正的難點在剪枝和去重（先排序，同層跳過重複元素）。

模板 → Backtracking 模板

更多同類型題目 → #Backtrack

Dynamic Programming

順序是：先講得出暴力遞迴 → 加上 @cache → 需要時再轉成表格。面試時把「dp[i] 代表什麼」的狀態定義說清楚，比急著寫 code 重要。

模板 → Dynamic Programming 模板

DP 的題量僅次於 Tree，而且子題型之間差得很遠，所以也往下拆成小主題，一組三題：

一維遞推入門

先寫出「第 i 項只依賴前面幾項」的遞推式，再想能不能只用兩個變數滾動。91 是同一套遞推加上條件判斷。

選或不選（House Robber 系列）

狀態是「到第 i 個為止，選了 / 沒選」。740 換了個皮，排序後就是一樣的題。

背包三形態

完全背包求最少個數、完全背包求方案數、0/1 背包求可不可行 — 三題把「迴圈順序決定了什麼」講完。

兩個字串一起走

dp[i][j] 代表兩個字串各取前 i、前 j 個的答案。差別只在「字元相同 / 不同時」怎麼轉移。

網格 DP

從左上走到右下最直觀，但要先確認能不能原地改陣列、以及第一行第一列的初始化。

子序列與字串切分

這三題的狀態定義最容易講錯，面試時務必先說清楚 dp[i] 是「以 i 結尾」還是「前 i 個」。

更多同類型題目 → #Dynamic Programming

Heap

「前 k 個 / 第 k 大 / 資料流中動態取最大最小」就是 heap 的訊號。Python 只有 min-heap，要最大堆就把值取負放進去。

模板 → Heap / Top K 模板

更多同類型題目 → #Heap

Intervals

幾乎都是先按起點排序，然後只需要比較「前一段的結尾」和「下一段的開頭」。Meeting Rooms II 的「拆成開始/結束兩條時間線」值得單獨記住。

模板 → Intervals 模板

更多同類型題目 → #Intervals

Greedy

「每一步直接拿最好的，而且不回頭」—— 但這件事需要交換論證才成立。先花 30 秒找反例，找不到再想證明；判斷能不能貪比寫 code 難得多。

模板 → Greedy 模板

更多同類型題目 → #Greedy

各題型模板

把一個題型的固定寫法整理成一篇，面試前快速復習用 — 每篇都是「模板 + 變形 + 面試時怎麼講」：

經典系列一起看

同一個系列從 I 做到 III，最能感受出題者是怎麼一步步加條件的 — 面試遇到沒看過的變形題，多半就是這些套路：