Coding Interview Preparation

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

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

最需要練習的題目清單

每一類附一句該題型的核心提醒，想看同類型的更多題目，點每段最後的 tag 連結。

Array & Two Pointers

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

模板 → Two Pointers 模板

• 1. 2 Sum
• 15. 3 Sum
• 11. Container With Most Water
• 125. Valid Palindrome
• 88. Merge Sorted Array
• 26. Remove Duplicates from Sorted Array
• 42. Trapping Rain Water
• 167. Two Sum II - Input array is sorted

更多同類型題目 → #Two Pointers

Sliding Window

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

模板 → Sliding Window 模板

• 3. Longest Substring Without Repeating Characters
• 76. Minimum Window Substring
• 209. Minimum Size Subarray Sum
• 424. Longest Repeating Character Replacement
• 567. Permutation in String
• 1004. Max Consecutive Ones III
• 239. Sliding Window Maximum
• 1423. Maximum Points You Can Obtain from Cards

更多同類型題目 → #Sliding Window

Binary Search

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

模板 → Binary Search 模板

• 704. Binary Search
• 33. Search in Rotated Sorted Array
• 153. Find Minimum in Rotated Sorted Array
• 34. Find First and Last Position of Element in Sorted Array
• 74. Search a 2D Matrix
• 875. Koko Eating Bananas
• 162. Find Peak Element
• 4. Median of Two Sorted Arrays

更多同類型題目 → #Binary Search

Hash Table

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

• 1. 2 Sum
• 49. Group Anagrams
• 128. Longest Consecutive Sequence
• 242. Valid Anagram
• 560. Subarray Sum Equals K
• 454. 4 Sum II

更多同類型題目 → #Hash Table

Stack

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

模板 → 單調棧模板

• 20. Valid Parentheses
• 155. Min Stack
• 739. Daily Temperatures
• 84. Largest Rectangle in Histogram
• 224. Basic Calculator
• 227. Basic Calculator II
• 394. Decode String
• 496. Next Greater Element I

更多同類型題目 → #Stack

Linked List

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

模板 → Linked List 模板

• 206. Reverse Linked List
• 21. Merge Two Sorted Lists
• 141. Linked List Cycle
• 876. Middle of the Linked List
• 19. Remove Nth Node From End of List
• 143. Reorder List
• 138. Copy List with Random Pointer
• 92. Reverse Linked List II

更多同類型題目 → #Linked List

Tree

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

模板 → Tree 遍歷模板

• 104. Maximum Depth of Binary Tree
• 100. Same Tree
• 226. Invert Binary Tree
• 102. Binary Tree Level Order Traversal
• 98. Validate Binary Search Tree
• 236. Lowest Common Ancestor of a Binary Tree
• 124. Binary Tree Maximum Path Sum
• 297. Serialize and Deserialize Binary Tree

更多同類型題目 → #Tree

Graph & BFS/DFS

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

模板 → BFS / DFS 模板

• 200. Number of Islands
• 133. Clone Graph
• 207. Course Schedule
• 210. Course Schedule II
• 547. Number of Provinces
• 994. Rotting Oranges
• 1091. Shortest Path in Binary Matrix
• 323. Number of Connected Components in an Undirected Graph

更多同類型題目 → #Graph

Backtracking

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

模板 → Backtracking 模板

• 46. Permutations
• 78. Subsets
• 39. Combination Sum
• 22. Generate Parentheses
• 79. Word Search
• 131. Palindrome Partitioning
• 77. Combinations
• 51. & 52. N Queens

更多同類型題目 → #Backtrack

Dynamic Programming

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

模板 → Dynamic Programming 模板

• 70. Climbing Stairs
• 198. House Robber
• 322. Coin Change
• 139. Word Break
• 1143. Longest Common Subsequence
• 300. Longest Increasing Subsequence
• 5. Longest Palindromic Substring
• 62. Unique Paths

更多同類型題目 → #Dynamic Programming

Heap

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

模板 → Heap / Top K 模板

• 215. Kth Largest Element in an Array
• 347. Top K Frequent Elements
• 295. Find Median from Data Stream
• 23. Merge k Sorted Lists
• 973. K Closest Points to Origin
• 703. Kth Largest Element in a Stream

更多同類型題目 → #Heap

Intervals

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

模板 → Intervals 模板

• 56. Merge Intervals
• 252. Meeting Rooms
• 253. Meeting Rooms II
• 57. Insert Interval
• 435. Non-overlapping Intervals
• 986. Interval List Intersections

更多同類型題目 → #Intervals

各題型模板

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

• 複雜度速查 — 各題型的時間/空間複雜度總表
• Backtracking 模板 — Backtracking
• Binary Search 模板 — Binary Search
• Sliding Window 模板 — Sliding Window
• Two Pointers 模板 — Array & Two Pointers
• Linked List 模板 — Linked List
• Tree 遍歷模板 — Tree
• BFS / DFS 模板 — Graph & BFS/DFS
• 單調棧模板 — Stack
• Dynamic Programming 模板 — Dynamic Programming
• Heap / Top K 模板 — Heap
• Intervals 模板 — Intervals

經典系列一起看

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

• 2 Sum 家族：1、167、15、454、653（搭配 2 Sum 面試應對策略）
• Best Time to Buy and Sell Stock：121、122、123、188、309、714
• House Robber：198、213、337
• Meeting Rooms 與 Intervals：252、253、56、57
• Course Schedule：207、210
• Basic Calculator：224、227、772
• Word Break 與 Word Ladder：139、140、127、126
• Max Consecutive Ones：485、487、1004
• Subsets / Combination / Permutation 家族：78、90、39、40、77、46、47
• Reverse Linked List：206、92
• Paint House：256、265
• Range Sum Query：303、304
• Shortest Word Distance：243、244
• Longest Increasing Subsequence 家族：300、673、354
• The Maze：490、505
• Strobogrammatic Number：246、247