Notes

Links

Not All LeetCode Questions are Created Equal
- These types of questions won’t get asked:
  - problem statement are too long for interviewer to remember
  - too many corner cases to finish in interview
- Look for:
  - questions that implement popular fundamental algorithms like trees, string manipulation, dfs/bfs, matrix
  - questions that have good real life application like regular expression
算法模板 repo
BFS 模板
- 同一作者寫的完整（？）模板
OA difficulty
- Akuna 比 Google 難，最簡單的一題是 upper medium，也有 hard leetcode 數學題
- Citadel: 3 leetcode mediums in 60 minutes (hard but you don’t need to get all 3 perfectly).
- Two Sigma
  - 1 leetcode easy, 2 medium in 60 minutes
  - Easier side of medium, on-site interviews are harder
  - 要練到 20 分鐘可以做完 most mediums，10 分鐘可以做完大部份 easies
  - 又有說 2 questions in 3 hours, be ready for DP/Graphs/DFS, all that stuff
  - 考過 friend circle leetcode question
  - Relatively easy/on par with tech companies
  - 2 sample questions
Lists
- Teamblind’s Curated List (75 題)
- NeetCode 150
  - Superset of Blind 75
- LeetCode 75: Ace Coding Interview with 75 Qs
  - Minimal redundancy covering all core patterns
- Top Interview 150: Must-do List for Interview Prep
  - More variations of the same patterns，有點 complement to LC75

High Frequency

LeetCode Questions CompanyWise
在下面這些題單裡出面過三次以上的題
- ZXI（花花酱題目分類）
- BL75（Blind 75 題單）
- LC75（LeetCode 75 題單）
- LC150（Top Interview 150 題單）
- 有 16 題出現了四次，26 題出現三次

題目名稱	難度	Freq	ZXI	BL75	LC75	LC150
1. Two Sum	Easy	4	o	o	o	o
121. Best Time to Buy and Sell Stock	Easy	4	o	o	o	o
20. Valid Parentheses	Easy	4	o	o	o	o
21. Merge Two Sorted Lists	Easy	4	o	o	o	o
242. Valid Anagram	Easy	4	o	o	o	o
226. Invert Binary Tree	Easy	4	o	o	o	o
141. Linked List Cycle	Easy	4	o	o	o	o
206. Reverse Linked List	Easy	4	o	o	o	o
53. Maximum Subarray	Medium	4	o	o	o	o
238. Product of Array Except Self	Medium	4	o	o	o	o
102. Binary Tree Level Order Traversal	Medium	4	o	o	o	o
56. Merge Intervals	Medium	4	o	o	o	o
33. Search in Rotated Sorted Array	Medium	4	o	o	o	o
3. Longest Substring Without Repeating Characters	Medium	4	o	o	o	o
139. Word Break	Medium	4	o	o	o	o
207. Course Schedule	Medium	4	o	o	o	o
125. Valid Palindrome	Easy	3	o	o	_	o
217. Contains Duplicate	Easy	3	o	o	_	o
70. Climbing Stairs	Easy	3	o	o	o	_
252. Meeting Rooms	Easy	3	o	o	o	_
253. Meeting Rooms II	Medium	3	o	o	o	_
49. Group Anagrams	Medium	3	o	o	_	o
5. Longest Palindromic Substring	Medium	3	o	o	_	o
647. Palindromic Substrings	Medium	3	o	o	_	o
271. Encode and Decode Strings	Medium	3	_	o	o	o
230. Kth Smallest Element in a BST	Medium	3	o	o	_	o
235. Lowest Common Ancestor of BST	Medium	3	o	o	_	o
208. Implement Trie	Medium	3	o	o	_	o
211. Add and Search Word	Medium	3	o	o	_	o
347. Top K Frequent Elements	Medium	3	o	o	_	o
322. Coin Change	Medium	3	o	o	o	_
198. House Robber	Medium	3	o	o	o	_
62. Unique Paths	Medium	3	o	o	o	_
55. Jump Game	Medium	3	o	o	o	_
133. Clone Graph	Medium	3	o	o	o	_
200. Number of Islands	Medium	3	o	o	o	_
261. Graph Valid Tree	Medium	3	o	o	o	_
57. Insert Interval	Medium	3	o	o	o	_
435. Non-overlapping Intervals	Medium	3	o	o	o	_
212. Word Search II	Hard	3	o	o	_	o
295. Find Median from Data Stream	Hard	3	o	o	_	o
269. Alien Dictionary	Hard	3	o	o	o	_

C

常見題目（近一年）from AI’s web search

題目	難度	Done	題型分類	備註
146. LRU Cache	Medium		設計題、Linked List + HashMap	高頻設計題，需要自訂資料結構
647. Palindromic Substrings	Medium		雙指標	可用中心擴展解法，C 出現過
221. Maximal Square	Medium	o	動態規劃	經典 2D DP 題，C 題庫中
200. Number of Islands	Medium	o	DFS / BFS	C 高頻，圖遍歷入門
239. Sliding Window Maximum	Hard		單調佇列	難度稍高但公司常問，可酌量準備
295. Find Median from Data Stream	Hard		Heap	雙 heap 設計，C 常見進階設計題
1048. Longest String Chain	Medium		動態規劃	字串 + DP，C 題庫中頻率高
740. Delete and Earn	Medium		動態規劃	關聯到 House Robber 思維
37. Sudoku Solver	Hard		回溯	複雜回溯問題，不常出但代表性高
150. Evaluate Reverse Polish Notation	Medium		Stack	經典堆疊運算題，C 出現紀錄

Sliding Window

題目名稱	難度	Done	題型	備註
3. Longest Substring Without Repeating Characters	Medium		Sliding Window	高頻且直覺
121. Best Time to Buy and Sell Stock	Easy	o	Sliding Window / DP	雙分類題型
239. Sliding Window Maximum	Hard		Monotonic Queue	C 曾出現但可跳過
438. Find All Anagrams in a String	Medium		Sliding Window + Hash	字串處理經典
567. Permutation in String	Medium		Sliding Window	與 438 類似但更簡潔

Tree / Graph Traversal

題目名稱	難度	Done	題型	備註
102. Binary Tree Level Order Traversal	Medium	o	BFS	你已經被問過
200. Number of Islands	Medium	o	DFS / BFS	C 高頻
199. Binary Tree Right Side View	Medium		BFS	C 題庫中
104. Maximum Depth of Binary Tree	Easy	o	DFS	快速上手
112. Path Sum	Easy	o	DFS	經典遞迴題型

String / Array Manipulation

題目名稱	難度	Done	題型	備註
151. Reverse Words in a String	Medium	o	字串處理	C 題庫中
28. Implement strStr()	Easy	o	字串搜尋	KMP 可選但不必要
1. Two Sum	Easy	o	HashMap	所有公司都愛問
724. Find Pivot Index	Easy		Prefix Sum	C 題庫中
647. Palindromic Substrings	Medium		DP / Expand Center	C 高頻

Dynamic Programming（DP）

題目	難度	Done	題型說明與考點
70. Climbing Stairs	Easy	o	經典 DP 入門題，類似斐波那契數列，狀態轉移非常簡單
53. Maximum Subarray	Easy	o	Kadane’s Algorithm，找最大連續子陣列和
198. House Robber	Easy	o	線性 DP，相鄰不能同時選擇，是 DP 與貪婪策略的結合基礎
121. Best Time to Buy and Sell Stock	Easy	o	雖非典型 DP，但常見於量化面試，考察最大利潤與滑動窗口
5. Longest Palindromic Substring	Medium		回文與 DP，考區間 DP 或中心擴展技巧
139. Word Break	Medium	o	字典查詢與 DP 結合，考察子字串切割與記憶化技巧
221. Maximal Square	Medium	o	二維 DP，找最大面積的正方形，你已經做得很好啦！
647. Palindromic Substrings	Medium		計算所有回文子字串的數量，考察區間處理與效率
322. Coin Change	Medium	o	類似背包問題，常用在金融類的動態選擇策略中
62. Unique Paths	Medium	o	二維 DP，經典路徑計算題，可用 combinatorics 或 DP
55. Jump Game	Medium		一維 DP 或 greedy 解法，DP 是官方標準分類之一
150. Evaluate Reverse Polish Notation	Medium		字串與堆疊邏輯題，常見於 C 的邏輯考題中
91. Decode Ways	Medium		字串與 DP 結合，考邊界條件與有效數字解析
740. Delete and Earn	Medium		類似 House Robber 的變形題，考數字間的互斥處理
718. Maximum Length of Repeated Subarray	Medium		二維 DP，類似 LCS（Longest Common Substring）題型
71. Simplify Path	Medium		字串與堆疊處理，考目錄結構與邏輯解析，常見於 C 題庫中
1143. Longest Common Subsequence	Medium		經典 DP 題型，常見於字串比對與資料結構設計

DP

221. Maximal Square

Medium

用一個二維的表 dp[i][j] 記下以 matrix[i][j] 為左下角的最大方型邊長
如果 matrix[i][j] 為 0 則 dp[i][j] 為 0，
否則

dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

因為方型的大小受限於它的上面，左邊，和左上

198. House Robber

Easy

對於每間房子，robber 有兩個選擇：
- 不搶這間：保留 \(dp[j-1]\)
- 搶這間：加上 \(dp[j-2] + n_j\)

53. Maximum Subarray

Easy

Kadane’s algorithm: Maximum subarray ending \(n_i\) is either \([n_i]\), or the maximum subarray ending \(n_{i-1}\), with \(n_i\).

44. Wildcard Matching

Hard

Use pattern as columns and string as index, both starting with an empty character (and \(T_{0, 0}\) is True). \begin{align*} T_{i, j} = \begin{cases} T_{i-1, j-1} &\mbox{ if } (s_i==p_j) ~||~ (p_j==\text{'?'})\\ T_{i-1, j} ~||~ T_{i, j-1} &\mbox{ if } p_j==\text{'*'}\\ \text{False} \end{cases}. \end{align*} First row is TTT… until the first non-asterisk character shows up, under which a sequence FFF… starts. First column is TFFFFF…

309. Best Time to Buy and Sell Stock with Cooldown

Medium

賣完之後不能隔天馬上買而是要等一天。

兩個狀態的 DP ：h 和 u 分別為持有股票和空倉時，現金帳戶價值的最大值。把 prices 跑完時 u 的結尾即是答案。Transition function 的 max 裡第一項是第 n 天有改變狀態的情況，第二項是沒有改變狀態。

Base case hold 狀態因為買入股票，現金帳戶變成負值。第二天的 hold 是前兩天股票選便宜的那天買：

p	8	6	4	3	3	2	3	5	8	3	8	2	6
h	-8	-6
u	0

Transition:

\[\begin{split}\begin{pmatrix} h_n\\ u_n \end{pmatrix} = \begin{pmatrix} \max(u_{n-2}-p_n, h_{n-1})\\ \max(h_{n-1}+p_n, u_{n-1}) \end{pmatrix}\end{split}\]

714. Best Time to Buy and Sell Stock with Transaction Fee

Medium

用兩個狀態的 DP，同 309，但只需要一天的 Base case。Transition function 改成

\[\begin{split}\begin{pmatrix} h_n\\ u_n \end{pmatrix} = \begin{pmatrix} \max(u_{n-1}-p_n, h_{n-1})\\ \max(h_{n-1}+p_n- f, u_{n-1}) \end{pmatrix}\end{split}\]

交易成本一定要加在賣掉那邊（從 hold 轉成 unhold）因為這兩個變數記的是現金帳戶價值。

188. Best Time to Buy and Sell Stock IV

Hard

最多可以交易 \(k\) 次，這裡看來的解答。

下面的答案是對的但在 LeetCode submit 不會過。如果遇到很長的 list 或 \(k\gg n\) 時間或空間會爆。

	5	7	1	4	3	1	3
0	0	0	0	0	0	0	0
1	3	5	5	5	5	5	5
2	3	5	5	8	8	8	8
3	3	5	5	8	8	8	10

\[\begin{split}T_{i, j} = \max \begin{cases} T_{i, j-1} \\ (p_j - p_m) + T_{i-1, m}\quad m=0, 1, \ldots, j-1 \end{cases},\end{split}\]

可再優化成

\begin{eqnarray*} T_{i, j} &=& \max \begin{cases} T_{i, j-1} \\ p_j + \text{maxDiff}_j \end{cases}\\\\ \text{maxDiff}_{j} &=& \max(\text{maxDiff}_{j-1},~T_{i-1, j} - p_j), \end{eqnarray*}

每一列初始 \(\text{maxDiff}_0 = 0 - p_0\)。

Misc

Implement eval()

‘2 + 2’ –> 4
‘100-5+1’ –> 96
Input 裡只會有加減號和整數，可能會有 space
只能用 ? 查 doc
檢查 input，raise error
這個程式還有其它問題嗎？ –> 連續兩個運算符就會爆

[1]:

import re

def compute_expression(expression):
    if re.search(r'[+-]{2,}', expression):
        raise ValueError('illegal expression')

    return sum([int(n) for n in expression.replace(' ', '').replace('+', ',+').replace('-', ',-').split(',')])

# compute_expression('1+-2') # ValueError

all((compute_expression(expression) == eval(expression)) for expression in ['2 +2', '100-5+1'])

[1]:

True

829. Consecutive Numbers Sum

Consider \begin{align*} N &= m + (m+1) + (m+2) + \cdots + n\\ &= (n-m+1)(n+m)/2, \end{align*} 其中 \(n-m+1\) 和 \(n+m\) 一個是奇數，一個是偶數，而且已知 \(n-m+1 > n+m\)。所以所有 \(N\) 的奇因數都確定了一組分解 \(2N = (n-m+1)(n+m)\)，從而確定了一組 \(m\) 和 \(n\) 的解。

floor(sqrt(N)) 遇到很大的 \(N\) 會 overflow。python 能處理任意大的整數，但 sqrt 會先轉成 float 然後就有可能出錯。一個安全判斷一個正整數是否為平方數的方法是牛頓法。

239. Sliding Window Maximum

Deque solution（video 裡存的是 index，這裡直接存數字）：用一個 deque 存下 sliding window 裡的數字，並且要以 descending order。如果新進來的數不是最小的，就不斷 pop out 比它小的數直到它是最小的再 append。只要這個新進來的數存在，這些被 pop out 的數都不會是 sliding window maximum 所以可以直接 pop out。每次 slide 就檢查最左邊的數是不是應該被 pop out

123. Best Time to Buy and Sell Stock III

最多可以交易兩次。

Best Time to Buy and Sell Stock (121) 的解答有一個性質就是把 input 整個取負號再倒過來會得到一樣的結果，例如 maxProfit([5, 3, 6, 4]) 會等於 maxProfit([-4, -6, -3, -5])。

可以交易兩次相當於把長度 n 的 array 拆成兩半分別求 121 的 maxProfit 再加起來。有 n 種拆法，例如 [7, 1, 5, 3, 6, 4] = [7, 1] + [5, 3, 6, 4] 是其中一種。隨著分拆點推進，第一個數列變長，第二個數列變短。第一個數列直接丟 121 的解答（但要記下 running max profit，不能用 O(1) space 的作法），第二個數列先倒過來取負號再丟，這樣新增的才是後面的數而不是前面的。

下面 pass1 是在求 [7, 1, 5, 3, 6, 4] 的 121 解答，pass2 是求 [-4, -6, -3, -5, -1, -7] 的 121 解答。最後把其中一個 running max profit 倒過來和另一個相加，得到的數列就是用不同分拆點時得到的兩次交易 max profit。取 max 就是這題的答案。

986. Interval List Intersections

用 two pointers 分別追蹤 A 和 B 的區間。兩閉區間有重疊 iff \(s \leq e\)。如果題目改開區間則是 \(s < e\)。

969. Pancake Sorting

最簡單的算法是 selection sort 變形：每次找出還沒排序的數之中最大的，先把它翻到最前面，再翻到還沒排序的部份的最後面。所以答案的偶數 subarray 會是 n, n-1, …。看了 LeetCode 最快解法和一些 youtube，大家都只寫這種。

200. Number of Islands

每次踩到 1 就 DFS 把同一個島都著色成 0，並且 count 累加一次。

560. Subarray Sum Equals K

用一個 hash table 存下到目前為止，這個 cumsum 一共出現過幾次。

53. Maximum Subarray

用一個變數 curMax 去 track 當前數字結尾的所有 subarray 中產生最大的 sum

47. Permutations II

如果 input list 裡沒有重覆的數字，答案就是把每一個數字抓出來當開頭，剩下的拿去做 permutation（遞迴）。現在 input list 雖有重覆的數字，但重覆的數字只抓出來當開頭一次就會得到正確答案。例如 [1, 1, 1, 2, 2, 3, 3, 3, 3] 之中 1, 2, 3 各當開頭一次。第一個迴圈只是為了抓每個數字第一次出現時的 index。

15. 3Sum

可以用 two sum (see the 2nd cell below) 但既然都要 \(O(n^2)\) 不如先排序然後用三個指標從左右往中間靠近。

121. Best Time to Buy and Sell Stock

直接找出最大和最小再相減行不通，因為可能出現先賣再買。但一邊求 running max profit 一邊 update current min 就不會有這個問題了。