Leetcode刷題學習筆記–心得統整

Useful references

面試準備

1. 軟體工程師求職 (1)履歷撰寫
2. 軟體工程師求職 (2)公告於市
3. 軟體工程師求職 (3)面試準備
4. 軟體工程師求職 (4)面試工具篇
5. 分享技術部落格: 酷殼
6. 中年找工作心得
7. 軟體職缺準備心得

刷code心得

1. LeetCode高效刷題心得分享
2. COVID期間拿到Google FB 微軟 Offer Part3
3. 面試分享 Google/MS/Amazon/Roku
4. Google TW SWE 面試心得（上）
5. Google TW SWE 面試心得（下）
6. 0到100的軟體工程師面試之路

薪資比較

1. 薪資透明化
2. levels.fyi

推薦題庫

1. Blind Curated 75, (我的整理)
2. Leetcode 题解
3. 花花酱 LeetCode Problem List 题目列表
4. Leetcode 101
5. NeetCode 150
6. Grind 75 questions
7. Lee215 good medium problems for interview and for practice

解題網站

1. Grandyang
2. 花花酱
3. wisdompeak
4. Leetcode Solutions in Java Python C++ Php Go Typescript
5. lzl124631x/LeetCode

教學網站

1. LABULADONG 的算法网站
2. LEARN C++

面試時的反問

1. 面試時的反問

資訊科技產業專案設計(2021年秋季)

1. 課程進度表和公告
2. 作業1
3. REACTO

• Repeat: 重複提問，確認自己理解原本的要求
• Examples: 針對題目條件，舉出符合的案例，不限於特例
• Approach: 說明自己打算採用的方案
• Code: 撰寫程式
• Test: 若不能實際測試，那說明驗證程式的方案

Google Tech Dev Guide

超牢記憶法Make It Stick

1. 努力回想才是記憶的關鍵（retrieve檢索）
   • 奮力回想(從題目到解答自己做一次)
   • 不要重複翻閱(不要只看code不動手做，試著回想解答的流程)
2. 穿插式練習(同時練習好幾種類型的題目)
   • 將練習當成比賽，才能把比賽當成是練習。
3. 每天回想學習過的東西，不能拿出筆記來參考
4. 費曼學習法(把學過的東西給12歲小孩聽得懂，看見事物的原始結構)
5. 找一個好的教練（簡答題考試）
   • 當一個在某個領域越不擅長時，就越容易高估自己的能力。
   • 花幾分鐘為幾天後自己出一張考卷(周末把一個禮拜的每日精選做一次)
   • 考試的時機點，在大腦開始遺忘，但還沒完全遺忘之前。(隔天)(每天選一題隔天再做一次)

---

• 演算法
  • 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到最有利的狀態。
• 資料結構
  • 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
    • Topological sorting
      走訪有相依性的圖。
  • 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。
• 其他
  • 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
    題目的解答和前後都有關係。
• 解題技巧
• 小技巧/code snippet
• 關鍵字/keyword
• C++API/STL整理
• C++ Operator Precedence
• Learn C++
• 名詞解釋
• Time/Space Complexity

tags: leetcode 刷題