HackMDLeetcode刷題學習筆記–心得統整
Useful references
面試準備
刷code心得
- LeetCode高效刷題心得分享
- COVID期間拿到Google FB 微軟 Offer Part3
- 面試分享 Google/MS/Amazon/Roku
- Google TW SWE 面試心得（上）
- Google TW SWE 面試心得（下）
- 0到100的軟體工程師面試之路
薪資比較
推薦題庫
- Blind Curated 75, (我的整理)
- Leetcode 题解
- 花花酱 LeetCode Problem List 题目列表
- Leetcode 101
- NeetCode 150
- Grind 75 questions
- Lee215 good medium problems for interview and for practice
解題網站
- Grandyang
- 花花酱
- wisdompeak
- Leetcode Solutions in Java Python C++ Php Go Typescript
- lzl124631x/LeetCode
教學網站
面試時的反問
資訊科技產業專案設計(2021年秋季)
- Repeat: 重複提問，確認自己理解原本的要求
- Examples: 針對題目條件，舉出符合的案例，不限於特例
- Approach: 說明自己打算採用的方案
- Code: 撰寫程式
- Test: 若不能實際測試，那說明驗證程式的方案
Google Tech Dev Guide
超牢記憶法Make It Stick
- 努力回想才是記憶的關鍵（retrieve檢索）
- 奮力回想(從題目到解答自己做一次)
- 不要重複翻閱(不要只看code不動手做，試著回想解答的流程)
- 穿插式練習(同時練習好幾種類型的題目)
- 將練習當成比賽，才能把比賽當成是練習。
- 每天回想學習過的東西，不能拿出筆記來參考
- 費曼學習法(把學過的東西給12歲小孩聽得懂，看見事物的原始結構)
- 找一個好的教練（簡答題考試）
- 當一個在某個領域越不擅長時，就越容易高估自己的能力。
- 花幾分鐘為幾天後自己出一張考卷(周末把一個禮拜的每日精選做一次)
- 考試的時機點，在大腦開始遺忘，但還沒完全遺忘之前。(隔天)(每天選一題隔天再做一次)
- 演算法
- Recursive
把問題切成相同的小題目。 - Tree Traversal
分為pre-order, in-order，post-order和level-order，可以使用DFS或BFS. - Depth-First-Search/Breadth-First-Search
依深度或是廣度瀏覽所有的資料 - Dynamic Programming
通常是求maximal或是minimal或是幾種方法的時候會用到。 - Divide and Conquer
將題目分成一樣的小題目，最後將結果合併起來。 - Binary Search
在排序過的資料中，尋找目標值。用二分法找效率為O(logN)。 - Two-pointers Binary Search
在排序過的1D或是2D vector中尋找想要的值。 - Two Pointers
通常為array中，使用前後兩個pointer來比較資料。 - Fast Slow Pointers
在linked-list中使用快慢pointer來解決問題。 - Combination
在所有的組合中，找出最佳的答案。 - Sliding Window
需要找出連續資料的關聯性。ex. substring, subarray. - Backtracking
- Sort algorithm
- Selection/Bubble/Insertion/Heap sort
- Bucket Sort
把數字分成一個一個的區段，ex: [0] : 0~9, [1] : 10~19, [2] : 20~29 - Counting/Radix Sort
- Greedy + heap
如果問題是詢問max或是min，最直覺的解法就是依序把最大或是最小的數值相加，但是有時候必須刪減就是用heap提供的數值。 - Greedy
每次都把目前的狀態update到最有利的狀態。
- Recursive
- 資料結構
- Set
只能儲存value，必把value當成key。 - Map
把資料做成key-value的對應，可以快速找到key對應的value。
或是使用客製的key來對資料做統計。 - stack [後進先出]
利用後進先出的特性，可以解決pair的問題或是反轉的效果。兩個stack也可以組成不同的特性。 - Queue
先進先出，可以用在BFS。使用BFS通常可以解決最小數量的問題。 - Double-end Queue(deque)
一般的queue，只能pop_front和push_back，但是double-end queue可以pop_front/back和push_front/back。兩頭都可以做pop/push。 - monotonic stack
一樣是stack，但是stack的內容有照一定的順序排列。遞增或遞減。找出前後比自己大或小的element。或是往左看往右看的最大值。 - Binary Search Tree(BST)
他是一個binary tree，但是準守著左邊的node小於root, 右邊的node大於root。 - Graph
有向圖和無向圖。- Disjoint set/Union Find
使用root array來紀錄每個vertex的root或是parent node - Minimal spinning tree
最小weight和，可以把全部的node連起來的tree，通常使用greedy演算法，每次都從最小的weight開始選，如果沒在graph裡面就加進來。 - Single Source Shortest Path Algorithm
- Dijkstra
類似BFS，但是使用priority_queue來取最小weight路徑。 - Shortest Path Faster Algorithm(SPFA)
使用vector和queue來記錄從source到每個node的最短路徑。可用在negative weight。 - Floyd Warshall Algorithm
- Dijkstra
- Topological sorting
走訪有相依性的圖。
- Disjoint set/Union Find
- Trie
統計字串或是數字的bit - Priority_queue
統計最大最小值的出現。 - Binary Index Tree(BIT)
計算range sum可以達到 update是O(logN)，getSum也是O(logN)
使用prefix sum只能達到 update是O(N), getSum是O(1)
使用array sum 只能達到 update是O(1), getSum是O(N) - Segment Tree
和Binary Index Tree一樣，可以用來計算range sum。除此之外還可以計算range maximum/minimum，或是有效率的update一個區間的elements。
- Set
- 其他
- Brute Force暴力破解
走訪所有的可能性，來找出最佳解。通常是面試時提出的第一個解法。從這邊也許可以延伸出sub-optimal或是optimal的解法。 - Math數學解法
有些時候分析完題目，發現用數學解反而更精簡。 - Randomized
選取element並且每個的機率都一樣。 - Bit Manipulation
對bit做處理。 - 加法器設計
- prefix sum
prefix_sum[i] = sum(nums[0:i - 1]); 前i個的和，適合用來解區段sum的題目。 - subset sum
把一個數列分成若2個subset，求出兩個subset的特殊 關係。例如sum(s1) = sum(s2) 或是 sum(s1) - sum(s2) = target等等。 - Interval
使用[start, end)來表示一個區間。 - Line Sweep
依序掃描x或是y，來得到答案。 - Binary Lifting
尋找第k個parent的技巧。 - two pass
題目的解答和前後都有關係。
- Brute Force暴力破解
- 解題技巧
- 小技巧/code snippet
- 關鍵字/keyword
- C++API/STL整理
- C++ Operator Precedence
- Learn C++
- 名詞解釋
- Time/Space Complexity
