1. Top K Frequent Elements
最直接的 ranking / heavy-hitter 題，練習如何維持 top-k 候選。
開啟既有繁中詳解 →職缺對應與題目總覽
Retrieval / Ranking
Top-K、heap、binary search、prefix search 與 streaming statistics，對應廣告候選召回、排序與線上指標。
NLP / Agentic Workflows
Sliding window、word segmentation、Trie 與 graph dependency，對應文字理解、工具規劃與多步流程。
Production ML Systems
LRU、versioned lookup、task scheduling 與 interval processing，對應低延遲 serving、cache 與資源管理。
| # | Problem | Priority | Pattern | Difficulty | Role relevance | Where |
|---|---|---|---|---|---|---|
| 1 | Top K Frequent Elements | Core | Heap / Bucket | Medium | ranking、heavy hitters | 既有筆記 |
| 2 | K Closest Points to Origin | Core | Heap | Medium | top-k retrieval | 本頁詳解 |
| 3 | Search Suggestions System | Core | Sort / Binary Search | Medium | Search / Shopping suggestions | 本頁詳解 |
| 4 | Word Break | Core | DP | Medium | NLP segmentation | 本頁詳解 |
| 5 | Minimum Window Substring | Core | Sliding Window | Hard | constraint-aware text matching | 既有筆記 |
| 6 | LRU Cache | Core | Hash Map / DLL | Medium | low-latency inference cache | 本頁詳解 |
| 7 | Time Based Key-Value Store | Core | Hash Map / Binary Search | Medium | versioned features / checkpoints | 既有筆記 |
| 8 | Course Schedule II | Core | Topological Sort | Medium | workflow dependency / planning | 既有筆記 |
| 9 | Task Scheduler | Core | Greedy | Medium | throughput / serving constraints | 既有筆記 |
| 10 | Random Pick with Weight | Core | Prefix Sum / Binary Search | Medium | weighted sampling / exploration | 本頁詳解 |
| 11 | Find Median from Data Stream | Stretch | Two Heaps | Hard | online metric aggregation | 本頁詳解 |
| 12 | Minimum Interval to Include Each Query | Stretch | Sort / Heap | Hard | offline query optimization | 既有筆記 |
| 13 | Design Search Autocomplete System | Stretch | Trie / Top-K | Hard | search ranking with updates | 本頁詳解 |
| 14 | Merge Intervals | Stretch | Sort / Intervals | Medium | batch data / time ranges | 既有筆記 |
已在你的題庫：直接跳轉
5. Minimum Window Substring
練習 NLP/string matching 常見的 frequency invariant 與動態 sliding window。
開啟既有繁中詳解 →7. Time Based Key-Value Store
以 append-only versions 加 binary search，接近 feature/version lookup 的思考方式。
開啟既有繁中詳解 →8. Course Schedule II
Topological sort 對應 dependency resolution、agent planning 與 multi-step workflow。
開啟既有繁中詳解 →9. Task Scheduler
用 frequency frame 推導最短排程，練習 throughput 與 cooldown constraints。
開啟既有繁中詳解 →12. Minimum Interval to Include Each Query
offline query + heap，是大型 query processing 很典型的 sweep pattern。
開啟既有繁中詳解 →14. Merge Intervals
排序後線性 sweep，是 batch logs、time windows 與 range aggregation 的基礎題。
開啟既有繁中詳解 →2. K Closest Points to Origin
MediumHeapTop-K
題目整理
給平面上的 points 與整數 k，回傳距離原點最近的 k 個點；答案順序不拘。比較距離時不必真的開根號，只比較 x² + y² 即可。
解法說明
維護大小最多為 k 的 max-heap。Python 只有 min-heap，因此存負距離；每讀一個點就加入，若 heap 超過 k 個便移除距離最遠者。最後留下的正是目前看過的 k 個最近點。這個 invariant 很像 retrieval system 維持固定大小的 top-k candidates。
from heapq import heappop, heappush
from typing import List
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
heap = []
for x, y in points:
distance = x * x + y * y
heappush(heap, (-distance, x, y))
if len(heap) > k:
heappop(heap)
return [[x, y] for _, x, y in heap]Time Complexity: O(n log k)，每個 point 做一次大小至多 k 的 heap 操作。
Space Complexity: O(k)，heap 只保留 k 個候選。
Interview Explanation Flow
Step 1: State the ranking key
"I only need relative distances, so I compare squared distances and avoid the square root."
Step 2: Maintain a bounded candidate set
"I keep a max-heap of size k. Its root is the worst point among the current best k, so when a better candidate arrives, the worst one is removed."
points = [[1,3], [-2,2], [2,-1]], k = 2
squared distances = [10, 8, 5]
keep 10, 8
see 5 -> remove 10
result distances = 8, 5Step 3: Complexity
"Each of n points costs O(log k), so time is O(n log k) and extra space is O(k)."
Possible follow-up
- Can we do better on average? "Yes, Quickselect gives O(n) average time when output order does not matter."
中文：面試時強調 heap root 是「目前 top-k 中最差的候選」，所以能在新點進來時立刻淘汰。
3. Search Suggestions System
MediumSortBinary Search
題目整理
給 product names 與 searchWord。使用者每輸入一個字元後，要回傳最多三個具有目前 prefix 的 product；若超過三個，選字典序最小的三個。
解法說明
先把 products 依字典序排序。對每個逐漸變長的 prefix，用 bisect_left 找第一個不小於 prefix 的位置；因為所有相同 prefix 的字串在排序後必定連續，只需檢查該位置後最多三個 product。前一輪的起點可以作為下一輪 binary search 的下界，因為 prefix 變長後候選起點不可能往左移。
from bisect import bisect_left
from typing import List
class Solution:
def suggestedProducts(
self, products: List[str], searchWord: str
) -> List[List[str]]:
products.sort()
answer = []
prefix = ""
start = 0
for char in searchWord:
prefix += char
start = bisect_left(products, prefix, lo=start)
suggestions = []
for index in range(start, min(start + 3, len(products))):
if products[index].startswith(prefix):
suggestions.append(products[index])
answer.append(suggestions)
return answerTime Complexity: O(n log n + m log n + m²)，n 是 products 數、m 是 searchWord 長度；m² 反映 Python 建立逐步 prefix 與 prefix comparison 的字元成本。
Space Complexity: O(m) auxiliary（不計排序與輸出），保存目前 prefix 與每輪最多三個建議。
Interview Explanation Flow
Step 1: Use ordering
"After sorting, every product sharing a prefix forms one contiguous range, and the first three are exactly the required suggestions."
Step 2: Find the range start
"For each typed prefix, I binary-search its lower bound, then inspect at most three products from that index."
products = [mobile, moneypot, monitor, mouse, mousepad]
prefix "mo" -> start at mobile -> first 3 suggestions
prefix "mou" -> start at mouse -> [mouse, mousepad]Step 3: Complexity
"Sorting dominates preprocessing; each keystroke then uses binary search plus at most three prefix checks."
Possible follow-up
- Why not a Trie? "A Trie is attractive for many repeated queries or online updates, but sorting plus binary search is simpler and sufficient for this static input."
中文：核心是排序後相同 prefix 的 products 會連在一起，因此 binary search 找起點後只看三個。
4. Word Break
MediumDynamic ProgrammingNLP
題目整理
給字串 s 與字典 wordDict，判斷是否能把整個 s 切成一個或多個字典內單字；同一單字可重複使用。
解法說明
定義 reachable[i]：前 i 個字元是否能成功切分。若位置 i 可達，就嘗試每個 dictionary word；只要 s 從 i 開始符合該 word，就把結束位置標為可達。這把大量重複的 recursive suffix 問題濃縮成 n+1 個狀態。
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
reachable = [False] * (len(s) + 1)
reachable[0] = True
for start in range(len(s)):
if not reachable[start]:
continue
for word in wordDict:
end = start + len(word)
if end <= len(s) and s.startswith(word, start):
reachable[end] = True
return reachable[-1]Time Complexity: O(nC)，n 是 s 長度，C 是 wordDict 所有單字的總字元數；每個可達位置最多檢查整份字典。
Space Complexity: O(n)，DP 陣列有 n+1 個狀態（不計輸入字典）。
Interview Explanation Flow
Step 1: Define the state
"reachable[i] means the prefix s[:i] can be segmented completely using dictionary words."
Step 2: Propagate reachable boundaries
"From every reachable boundary, I try each dictionary word and mark the next boundary if that word matches."
s = "leetcode", words = ["leet", "code"]
reachable[0] = True
0 + "leet" -> reachable[4] = True
4 + "code" -> reachable[8] = True
reachable[len(s)] is TrueStep 3: Edge cases and complexity
"Unreachable positions are skipped, repeated words are naturally allowed, and the DP uses O(n) space."
Possible follow-up
- When would a Trie help? "When the dictionary is large, a Trie lets me scan matching prefixes without testing every word at every position."
中文：把「可以切分的位置」當成狀態，從可達邊界繼續延伸到下一個可達邊界。
6. LRU Cache
MediumHash MapDoubly Linked ListDesign
題目整理
設計固定容量的 cache，get 與 put 都需平均 O(1)。每次讀取或更新都使該 key 成為 most recently used；容量超過時移除 least recently used key。
解法說明
Hash map 提供 key 到 node 的 O(1) lookup；doubly linked list 維護使用順序並支援 O(1) 移除。使用 dummy left/right nodes 簡化邊界：靠近 left 是 LRU，靠近 right 是 MRU。任何成功的 get/put 都把 node 移到 right 前面。
class Node:
def __init__(self, key: int, value: int):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.nodes = {}
self.left = Node(0, 0) # Least recently used side
self.right = Node(0, 0) # Most recently used side
self.left.next = self.right
self.right.prev = self.left
def _remove(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def _insert_mru(self, node: Node) -> None:
previous = self.right.prev
previous.next = node
node.prev = previous
node.next = self.right
self.right.prev = node
def get(self, key: int) -> int:
if key not in self.nodes:
return -1
node = self.nodes[key]
self._remove(node)
self._insert_mru(node)
return node.value
def put(self, key: int, value: int) -> None:
if key in self.nodes:
self._remove(self.nodes[key])
node = Node(key, value)
self.nodes[key] = node
self._insert_mru(node)
if len(self.nodes) > self.capacity:
lru = self.left.next
self._remove(lru)
del self.nodes[lru.key]Time Complexity: O(1) average for
get and put，hash lookup 與 list pointer updates 都是常數操作。Space Complexity: O(capacity)，map 與 linked list 最多保存 capacity 個 entries。
Interview Explanation Flow
Step 1: Identify two independent needs
"I need O(1) lookup by key and O(1) removal by recency. A hash map solves lookup, while a doubly linked list solves ordering and deletion."
Step 2: State the invariant
"The node next to the left sentinel is always the LRU item, and the node before the right sentinel is always the MRU item."
capacity = 2
put(1,1): LRU [1] MRU
put(2,2): LRU [1,2] MRU
get(1): LRU [2,1] MRU
put(3,3): evict 2 -> LRU [1,3] MRUStep 3: Complexity
"Every operation performs a constant number of dictionary and pointer operations, so both APIs are O(1) average time."
Possible follow-up
- Why doubly linked? "Given a node from the map, I need to unlink it without searching for its predecessor."
中文：面試時先拆成 O(1) lookup 與 O(1) recency update，再說明 hash map + doubly linked list 各自負責哪一半。
10. Random Pick with Weight
MediumPrefix SumBinary SearchRandomized
題目整理
給正整數 weights，設計 pickIndex()，讓 index i 被選到的機率等於 w[i] / sum(w)。呼叫多次時，較大 weight 應按比例更常被選到。
解法說明
把 weights 轉成 prefix sums，相當於在一條數線上為每個 index 分配長度等於 weight 的區段。均勻抽一個介於 1 與總權重的整數，再用 binary search 找第一個 prefix sum 大於或等於它的位置；區段越長，被抽中的整數越多，機率自然與 weight 成比例。
from bisect import bisect_left
from random import randint
from typing import List
class Solution:
def __init__(self, w: List[int]):
self.prefix = []
total = 0
for weight in w:
total += weight
self.prefix.append(total)
def pickIndex(self) -> int:
target = randint(1, self.prefix[-1])
return bisect_left(self.prefix, target)Time Complexity: 初始化 O(n)；每次
pickIndex O(log n)。Space Complexity: O(n)，保存 prefix sums。
Interview Explanation Flow
Step 1: Convert probability into geometry
"I represent each weight as a segment on a number line. Uniformly picking a point then gives each index probability proportional to its segment length."
w = [1, 3]
prefix = [1, 4]
target 1 -> index 0
targets 2,3,4 -> index 1
probabilities = 1/4 and 3/4Step 2: Locate the sampled segment
"The prefix sums are sorted, so I binary-search the first cumulative sum that reaches the random target."
Step 3: Complexity
"Preprocessing is O(n), and each sample is O(log n) with O(n) stored prefix sums."
Possible follow-up
- What if weights change frequently? "A Fenwick tree can support both weight updates and prefix selection in O(log n)."
中文：把每個 weight 變成數線上的區段長度，均勻抽點後用 binary search 找落在哪一段。
11. Find Median from Data Stream
HardTwo HeapsStreaming
題目整理
設計 MedianFinder，支援持續加入數字與隨時查詢目前所有數字的 median；查詢前保證至少已有一個數字。
解法說明
用兩個 heap 把資料分成兩半：small 是較小一半的 max-heap（以負值實作），large 是較大一半的 min-heap。維持兩個 invariants：small 所有值都 ≤ large 所有值；small 的大小等於 large 或多一個。奇數筆時 median 是 small top，偶數筆時是兩個 top 平均。
from heapq import heappop, heappush
class MedianFinder:
def __init__(self):
self.small = [] # Max-heap via negative values
self.large = [] # Min-heap
def addNum(self, num: int) -> None:
heappush(self.small, -num)
heappush(self.large, -heappop(self.small))
if len(self.large) > len(self.small):
heappush(self.small, -heappop(self.large))
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return float(-self.small[0])
return (-self.small[0] + self.large[0]) / 2Time Complexity:
addNum O(log n)；findMedian O(1)。Space Complexity: O(n)，兩個 heaps 合計保存所有輸入。
Interview Explanation Flow
Step 1: Split around the median
"I do not need the full sorted order. I only need the maximum of the lower half and the minimum of the upper half."
Step 2: Maintain two invariants
"All values in small are no greater than values in large, and small has either the same number of elements or one extra."
add 1: small=[1], large=[] median=1
add 2: small=[1], large=[2] median=1.5
add 3: small=[2,1], large=[3] median=2Step 3: Complexity
"Insertion rebalances a constant number of heap elements in O(log n), while reading the median is O(1)."
Possible follow-up
- If values are only 0–100? "I can use a fixed counting array and scan 101 buckets to find the median."
中文：不用維護完整排序，只需維護 median 左右兩半的邊界值與平衡大小。
13. Design Search Autocomplete System
HardTrieTop-KDesign
題目整理
初始化時給 sentences 與出現次數。每輸入一個普通字元，要回傳以目前輸入為 prefix 的 top 3 sentences，排序先看頻率由高到低，再以字典序打破平手；輸入 # 表示一句話完成，要把新句子頻率加一並重設狀態。
解法說明
Trie 負責 prefix traversal；每個 Trie node 保存通過該 prefix 的完整 sentences 與 frequencies。輸入普通字元時走到下一個 node，從該 node 的 candidates 選出 top 3；輸入 # 時，把完整輸入沿 Trie 更新。這個版本偏向清楚與正確；若 scale 很大，可在每個 node 維護預先計算的 top-k cache，讓查詢更快。
from collections import defaultdict
from heapq import nsmallest
from typing import List
class TrieNode:
def __init__(self):
self.children = {}
self.counts = defaultdict(int)
class AutocompleteSystem:
def __init__(self, sentences: List[str], times: List[int]):
self.root = TrieNode()
self.current_node = self.root
self.current_text = ""
for sentence, count in zip(sentences, times):
self._add(sentence, count)
def _add(self, sentence: str, count: int) -> None:
node = self.root
for char in sentence:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.counts[sentence] += count
def input(self, char: str) -> List[str]:
if char == "#":
self._add(self.current_text, 1)
self.current_text = ""
self.current_node = self.root
return []
self.current_text += char
if char not in self.current_node.children:
self.current_node.children[char] = TrieNode()
self.current_node = self.current_node.children[char]
return nsmallest(
3,
self.current_node.counts,
key=lambda sentence: (
-self.current_node.counts[sentence], sentence
),
)Time Complexity: 初始化 O(T)，T 是所有 sentence 長度總和；一般輸入字元 O(M)，M 是目前 prefix 的候選 sentence 數（top 3 heap 視為常數 k）；輸入 # 為 O(L)。
Space Complexity: O(T) prefix-sentence associations；每個 sentence 會登記在它經過的 Trie nodes。
Interview Explanation Flow
Step 1: Separate prefix lookup from ranking
"A Trie gets me to the node for the typed prefix, and that node stores the sentences eligible for ranking."
Step 2: Define the ranking rule
"I rank by negative frequency first and lexicographic order second, then return only the best three."
sentences = ["i love you":5, "island":3, "i love leetcode":2]
input "i" -> ["i love you", "island", "i love leetcode"]
input " " -> ["i love you", "i love leetcode"]
input "#" -> store the completed sentence and resetStep 3: Discuss the production trade-off
"This design favors simple updates. For read-heavy production traffic, I would cache only top-k results per node and update those caches when sentence counts change."
Possible follow-up
- How would you shard it? "Partition by an early prefix, replicate hot prefixes, and keep ranking updates observable and eventually consistent."
中文：先用 Trie 找到 prefix candidates，再依 frequency 與 lexicographic tie-break 做 top-3 ranking。
建議練習順序
第一輪：必做
Top K Frequent、K Closest、Search Suggestions、Word Break、LRU Cache。這五題涵蓋最可能在一小時面試展開的核心 patterns。
第二輪：系統感
TimeMap、Course Schedule II、Task Scheduler、Random Pick with Weight、Minimum Window。練習把資料結構選擇連到 production / ML context。
最後：Stretch
Median Stream、Minimum Interval、Autocomplete、Merge Intervals。重點是能說 invariant、trade-off 與 complexity，不只背 code。
每題的 45 分鐘答題節奏
3–5 分鐘釐清 input/output 與 constraints；5 分鐘提出 brute force 與關鍵 observation；20–25 分鐘 coding 並口述 invariant；5–8 分鐘測 example、edge cases 與 complexity；最後主動回答可擴展性或 follow-up。