[LeetCode] 寫了400題 LeetCode 後的經驗
相信大部分人寫 LeetCode 是為了面試，我也不例外，我的 LeetCode 過程大概可以分成三段:
- 一開始覺得很難，就斷斷續續的寫，也不知道方向在哪
- 面試將近，每天瘋狂地刷題目
- 面試後，每天寫 daily challenge 磨練自己的技巧
我就列出一些我覺得我寫 LeetCode 犯的一些錯誤，還有後來要怎麼避免的方法。
LeetCode 常犯的錯誤
錯誤 1: 按照題號寫
一開始只是覺得說哪天會要面試，所以我先來寫寫看，所以就從題號 1, 2, 3, ... 往後慢慢寫。後來發現這樣寫其實不是很好的做法，因為:
- 遇到 hard 的題目就會讓人卡住花很多時間，而這些 hard 題目要達到 optimized solution 的一些步驟會需要練過一些 easy 或 medium 的題目的解法才會知道怎麼寫
- 遇到困難一點的題目就會讓人害怕不想繼續解
- 相反地，遇到連續好幾題太簡單的題目也會讓人失去興趣
後來我就開始搜尋網路上有沒有人推薦 LeetCode 要寫哪些題目，於是就找到了幾個不錯的資源:
- LeetCode 本身自己的 Study Plan，像是 LeetCode 75, Data Structure, Algorithm, Dynamic Programming, Programming Skills, Graph Theory 免費版的其實我都解過一輪了，但有的題目沒有官方解答，就只能去挖討論版的解答
- NeetCode 150/Blind 75，reddit r/LeetCode 滿推的清單，也有按照 pattern 分類，可以重複練習不熟的 pattern
- LeetCode Patterns，除了列出 patterns 以外還有問過題目的公司清單，題目都滿經典的，就算是 easy problem 也其實都值得讓人思考各式各樣不同的寫法
以上清單的題目其實都高度重複，我在面試前會專注去練這家公司愛考的 pattern (像是 Google HR 就說 DP & Graph 題目可以多練)。
錯誤 2: 太在意語法和 Clean Code
LeetCode 的 solution 以及討論區的解答其實可以分成兩大類: competitive programming 與 clean code。但其實我覺得自己需要走哪個風格要看你寫 LeetCode 的目的:
- 在意競賽時間: 希望自己能快速寫出解答，會偏好 competitive programming 的解答，這種解答通常不會超過 10 行，複雜一點的 20 行以內應該都可以解決
- 在意軟體維護: 希望自己的 code 越乾淨越好，可讀性應該要 maximize，所以各種變數可能都會命名的比較長，甚至是會切成很多行數短的 functions 來達到 modular 的 code (在 Cracking the Coding Interview 書中也有提到)
- 在意面試: 希望自己不但能夠快速寫出解答，也能達到一定的好的 coding style
一開始我太在意 clean code，就作了以下不好的示範:
- 寫過長的變數命名，但如果題目描述裡面都有寫 n, m, i, j, k 的話，不妨直接借用 (除了 2D graph 我還是會寫 numRows/numCols/row/col 避免 x/y 方向的混淆)
- 逼迫自己超過 80 行左右就一定要換行，導致寫出來的 code 在網頁中不好編輯
- 常見的 STL containers 前面一直加 std:: 或是在 class 裡面特別加 public: private: 或是 member variables 前面加底線等，但我發現實際面試中其實面試官從來沒有太注意這種小細節
所以我後來最喜歡的風格其實是介於中間的 style，可以在 30 分鐘內寫出解答，又不會失去可讀性，要達到這樣的目標其實就和下一個錯誤有關。
錯誤 3: 直接開始寫 Code
直接寫有錯了嗎? 就和我們解某一題卡住的時候去討論版打開一個文章來看，結果只看到一堆程式碼沒有任何解釋或註解一樣。有時候因為同時進行好幾個清單在 LeetCode 解到同一個題目，發現說這可能一個禮拜前已經解過了，但看著自己寫的程式碼卻早就忘記自己當初是怎麼解的了，然後就會停止思考，直接重新 submit，卻錯過了練習其他解法或 optimized solution 的好機會。
後來我寫題目都會在最前面加上一些註解:
- Observations: 觀察到題目/範例測資的一些 pattern 或是可能的方向，有助於寫下接下來的 approach
- Approach: 解題的方法是什麼，用了什麼資料結構，步驟是什麼
- Time complexity: 分析一下上面寫的 approach 中的各個步驟的 time complexity，最後再總結全部的 time complexity
- Space complexity: 和 time complexity 一樣，也是要分析然後總結
寫這些註解的過程其實就在強迫自己練習如何與面試官說明你怎麼解的。光是用想的其實很容易陷入幾個狀態:
- 想不出來解法，但其實只要列一些 example 就可以幫助自己觀察出 pattern 寫出解法
- 想到模糊的解法，寫 code 後才發現在某個步驟卡關
- 想到解法可是想的不夠仔細，寫 code 後才發現這個解法時間複雜度太高，甚至 TLE
- 想到解法但是太專注在優化某個步驟，但該步驟卻不是 time complexity 的 bottleneck，其實用更簡單(但效率可能不見得比較好)的寫法就好了，沒有分析每個步驟的 time complexity 就常常會這樣
- 想到解法也寫得出來，可是要解釋卻不知道從何開始
所以後來我都把每一題解的過程當作自己在面試一樣，思考一下怎麼把解題的過程解釋給面試官。
例如說 1383. Maximum Performance of a Team 這一題我 submit 出去的 code 就長這個樣子:
// Observations:
// - If we sort the two arrays by efficiency, we would get
// - speed = 8 3 10 2 5 1
// - efficiency = 2 3 4 5 7 9
// - If we pick the 3rd enginner (10*4==40), we would select the 5th (j==4) enginner since we want to maximize 4*speed[j]
// - If we just pick k engineers of the highest efficiency and scan other enginners by decreasing efficiency, we can check whether replacing the old engineer with new enginner would get better result
// - If we replace with the new enginner, we always get lower efficiency
// - We should greedily replace the old enginner of the lowest speed with new enginner with higher speed
// - Looks like what a heap is doing
//
// Approach:
// 1. Sort the (speed, efficiency) arrays together by decreasing efficiency
// 2. Scan each enginner from highest efficiency to lowest efficiency
// - We keep track of the current lowest efficiency in the team as minEff
// - We use a min priority queue to store the speeds of the current team
// - For a new engineer i, if speed[i] > heap.top():
// a. Replace heap.top() with speed[i], then calculate the new performance
// b. Update minEff
// c. Check if the new performance == minEff * sum(speed) is larger
// - Instead of calculating the sum every time, we can just calculate the speed diff and update the sum
// 3. Output the highest performance
//
// Time complexity:
// 1. O(n log n)
// 2. O(n log k) <= O(n log n)
// 3. O(1)
// Total: O(n log n + n log k) <= O(n log n)
//
// Space complexity:
// 1. O(1)
// 2. O(k) <= O(n) since the heap needs to store k engineers
// 3. O(1)
// Total: O(k) <= O(n)
class Solution {
public:
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
// Step 1: Sort
vector<int> sortedIndexes(n);
std::iota(sortedIndexes.begin(), sortedIndexes.end(), 0);
std::sort(sortedIndexes.begin(), sortedIndexes.end(), [&](const auto &lhs, const auto &rhs) -> bool {
return efficiency[lhs] > efficiency[rhs];
});
// Step 2 and 3
priority_queue<int, vector<int>, std::greater<>> maxSpeeds;
long totalSpeeds = 0;
long maxPerformance = INT_MIN;
for (int i = 0; i < n; i++) {
const int sIndex = sortedIndexes[i];
const int newSpeed = speed[sIndex];
int diff = 0;
if (maxSpeeds.size() < k) {
maxSpeeds.push(newSpeed);
diff = newSpeed;
} else {
// Check whether the new engineer is better
const int minSpeed = maxSpeeds.top();
if (newSpeed > minSpeed) {
maxSpeeds.pop();
maxSpeeds.push(newSpeed);
diff = newSpeed - minSpeed;
}
}
totalSpeeds += diff;
const long minEff = efficiency[sIndex];
maxPerformance = std::max(maxPerformance, totalSpeeds * minEff);
}
return maxPerformance % MOD_VALUE;
}
const int MOD_VALUE = 1000000000 + 7;
};
在面試中其實也可以把簡單的 idea 和 approach 寫在 shared document (當然不用像上面這樣這麼長)。這樣子他們在評分的時候也比較有依據。
錯誤 4: 沒有去看官方解答/參與討論版
一開始只要看到 Accepted 就很開心地直接關掉網頁，但我們不可能隨時都寫出 optimized solution。就算我們寫出 optimized solution，是不是還有其他更簡單的寫法? 或是有 C++ STL API 其實可以直接套用? 看了官方解答或是討論版 most upvoted 的一些解答後有時會突然恍然大悟: "啊，原來可以這樣子解!"。
如果覺得自己的解答與眾不同或是值得讓大家參考，其實我就會貼我的解答 + 我的解法。偶爾也在別人的解答底下留言，不管是發問或是糾正都可以，不只練習英文也可以多看看不同的寫法，也是滿寶貴的經驗。
錯誤 5: 沒有測試更多的測資
光是用官方的 example testcases 其實常常會測不到 corner cases 或是一些沒考慮到的狀況，導致 Run 的時候是 Accepted，實際 Submit 後才發現 Wrong Answer 或是 Runtime Error。
在面試時有時候面試官會問說，你要怎麼證明自己的解答是正確的? 這時候其實就在考驗我們有沒有能力自己生出測資測試一些奇怪的 case，也順便證明自己了解自己的解答。
在 Submit 前我都會盡量自己造以下的 cases:
- Corner cases: 例如說 input data 是空的甚至只有一兩個的狀態
- Debugging cases: 很正常的測資，數字單純，input data 資料長度也偏少，如果出問題的話可以快速幫自己 debug
- Problematic cases: 自己的作法有什麼可能的缺陷? 這種測資就是把自己想成另外一個人，想盡辦法把自己程式碼搞壞
- Extreme cases: 數字特別大或是 input data 特別長，有時候會比較難造一點，不過還是盡量測試看看，主要是為了怕 TLE/MLE
- Random cases: 有時候以上的測資都還是可以過，但是隨便亂打一些數字反而就會找到缺陷
Extreme cases 和 random cases 對面試的幫助就比較小，如果是遇到用 shared document 寫 code 就無法幫助到，畢竟 shared document 沒辦法像 LeetCode 有個 Run button 可以快速 evaluate extreme/random cases 的結果。但如果面試第一關有用一些平台 (例如 HackerRank) 來當作 phone interview，那就可以幫助到。
LeetCode 最右邊有個 Notes 的功能，其實我都會在裡面偷偷塞測資:
因為 Notes 的資料會存在 server 上，如果要重複練習題目就不怕測資消失不見，展開來就會看到自己以前建的測試資料:
錯誤 6: 在一個題目卡太久
一開始寫題目時比較常遇到，有些 medium/hard 的題目想了超過一個小時，就是不知道怎麼解，完全沒有任何 idea。一開始會覺得千萬不要去看解答，一定要自己想出來才行，過了一天後發現還是沒有任何頭緒，只好去看解答，發現解答的方法是自己從來沒學過的，整個過程就浪費了許多寶貴時間。
這在 reddit 版上也常被拿來討論，正反方意見都有，但我自己設定的時間是從我開始沒任何進一步的想法超過一個小時候，我就會去看看解答或討論版看他們怎麼解的。當然直接 copy/paste code 是不好的習慣，我們可以依序看看到什麼步驟其實我們就有辦法解得出來:
- 先看解答/討論版的 title，有時候 hint 就很多，例如 title 就寫 DP 或 binary search，那我們可以先思考看看用這樣的技巧有沒有辦法解出來? 有時候 time complexity 也是一個很大的 hint，如果你覺得 O(n^2) 都很難解，標題卻寫 O(n)，那是不是其實有 greedy 的解法?
- 再看解答/討論版上面的思路，先不看 code，如果能靠這樣寫出自己的 code 那其實也有練習到
- 真的都不行才來看 code，有時候是因為解釋的不夠詳細，有時候是因為受不了 TLE/MLE/Runtime Error 了，看看別人 code 用什麼 data structure/trick 才可以 accepted
另外我也滿推薦裝一下 LeetCode Timer 這個 Chrome 插件 (當然用一般的馬錶也可以)，他會記錄從開始解題到 Accepted 前過了多少時間，可以同時達到兩個目的:
- 防止自己卡在一個題目太久，看超過特定時間就可以開始去看解答了
- 測試自己能不能在一般面試 30/45 分鐘以內寫出解答
結語
在面試前與面試完後寫 LeetCode 的心態和寫法就有了滿大的轉變，我也有加入 Reddit 的 r/leetcode 版與大家一起繼續 grind LeetCode，也學到了很多滿有用的小知識。
一開始寫 LeetCode 每寫幾題就會卡住一次，現在的話幾乎是一小時內幾乎都可以解出任何 easy/medium 的題目，hard 題目雖然想解答比較久，但也幾乎都可以解得出來。解出來的瞬間反而沒有以往的成就感，因為在分析 approach 與 time complexity 幾乎就知道能不能解的出來了。現在反而在意的是解題時間與解題的方法夠不夠好，可以在面試時重寫一次沒有問題。
祝福大家都能刷題順利，繼續 LeetCode!
留言
發佈留言