FAANG 面試準備經驗與建議（一）
前言：
拿到 Google & Amazon Offer 的面試之旅（一）
拿到 Google & Amazon Offer 的面試之旅（二）
這篇文章算是前兩篇面試介紹的後續，前面只講了面試經驗，這篇回頭來聚焦在最多人問過我的 Leetcode 練習上面，如果這方面你已經足夠，也可以選擇置底看下一篇聊模擬面試的續集。
那就開始吧！
到底需要怎樣的實力，才有機會通過一線公司的面試？如果不是從小打演算法競賽的人，有機會上嗎？要練習多久？要怎樣練習？面試的注意事項有哪些？還有最常見的問題就是
Leetcode 到底該刷到多少才夠啊？
相信這是很多人的疑問，並且去網路上會看到各種各樣不同的答案，有人好像說的很簡單，有人說的很難，這邊文章就用我自己查到的各家資訊，還有自身面試經驗來統整一下，讓大家有一個更明確的認知。
很多人會被那些頂尖天才選手的成長故事嚇到，什麼國小就會寫 c++，國中自己架網站賺了多少，高中拿了幾個奧賽獎牌… 等等。那跟這些人累積幾十年的天份加努力，自己永遠不可能追得上，那不如放棄吧。
但你可以想想，這樣的人一年才幾個？台灣給你算 10 個很多了，世界百大資工系加起來，給你算 1000 好了，但大公司們，光 Google 就有數十萬的員工，其他一線大公司也都算進來的話，數百萬的頂尖大公司員工裡，這種神人的佔比也沒多少，剩下的絕大多數人，也就是跟你我一樣的凡人而已。
所以，FAANG 面試的題目難度與題型廣度，其實遠遠沒有到頂尖競賽的那種誇張等級，而且差距非常非常遠。也就是說，你其實僅需在一個非常有限的範圍內，將題目做到熟練就可以。要比喻的話，假如頂尖競賽要會的是整個數學系學士班的知識，那 FAANG 面試的難度，頂多就是大學入學測驗的數學考試，而且依據運氣可能每次錄取標準會在 70~90 分浮動。因此你的準備範圍就是高中三年那些東西，例如什麼三角函數、指對數、機率、幾何… 等等，非常固定。不管你從幾歲開始學習，只要能唸完那幾本書，熟練那些題目即可。並非一定要很年輕加上絕頂聰明才有機會。
另外還有一個特點，由於你會經過大約 4~5 輪的面試，每個面試官會從公司的超大題庫中，選他自己覺得有意義的考題。而大多數考官其實也不會去挑那些特別刁鑽困難的題目，再者，若只有一輪表現不佳，如果其他幾輪表現不錯，且有一兩輪很突出（Strong Hire），仍然有機會。
因此你的目標，其實不是什麼 Hard 題都要秒解，而是穩定的 Medium 都能順利在 20 min 左右完成，最後加上運氣不太差，就有機會通過了。
所以 Leetcode 該練到哪？
我個人認為 CP 值最高的刷題數是 200~500 之間，分配上要涵蓋所有常見主題，且大多有很認真好好看懂各種思路與解法，不是拿到 AC 就算過了，常見主題可以參考我另一篇系列文。
當然正常人即使好好看懂一次，也一定過段時間會忘記特定題目的解法，但這沒關係，重要的是過程中基本核心概念有被一次次加強，直到內化成思維中很直覺的一部分，這樣的題數應該已經足夠了。也因此解法太特殊的題目其實意義不大，硬要背這些當然可以增加成功率，但時間利用價值低很多。
當然還是有例外，有一些經典套路，例如用雙指針在 Linked List 找環，空間複雜度可以做到 O(1)，我覺得這沒看過真的太難憑空想到了，但不少人面試時遇到過類似的變化題
至於題目難度，一般取決於三個方向
- 基礎知識的要求
- 觀察力與巧思
- 實作的複雜程度
第一點來說，透過有系統的分章節學習，就可以掌握，報名任何一門不太差的線上演算法課，或者透過較有系統整理的免費教材，都能學會。
第二點是最困難的，需要透過大量的練習，才能慢慢掌握，靠上面提到的 Leetcode 刷題數量與搭配適當的 Weekly Contest 挑戰來達到
第三點則是熟練度的問題，一樣要透過練習，較難的題目實作很複雜，一般建議常見題型練一套熟練的寫法當模板，才不會讓你在細節上浪費太多時間。例如 Dijkstra、Binary Search、Sliding Window、在 2D Array 上做 Graph Traversal、… 等等做法都很多，找一個你最舒服的寫法練熟很重要。
一般來說 Easy 題目通常三者都不要求，或只要求 1 的能力，也就是你只要有掌握各個基本資料結構與演算法，通常都能很快看出他在考哪一個知識點，並簡單的實作出來，這也是我覺得無論有沒有打算面試大公司，都該具備的基礎能力。
Medium 則通常有兩種要求，但也不會到太難，可能是稍難一點的概念的基本題，或看似複雜，但透過一些轉換後，會發現等同於某個簡單演算法或常見技巧，再或者是雖容易想到，但實作偏複雜。這邊是頂尖大公司面試的主要題庫。
Hard 則可能三種要求都有，首先第一眼會不容易看出方向，需要多觀察幾個例子，嘗試不同思路，經過幾次轉換後才會成為你看過的套路，找到後也可能仍然不好實作，要在時限內解決需要非常非常熟練才行。
以 FAANG 公司的面試來說，普遍與平均的難度，其實只落在 Medium，但必須要求一題在 15～20min 內解決，而且要在沒有 IDE 與 compiler 可用的情形下，一邊流暢的敘述想法與每個步驟，並能給出正確無誤、最高效且 bug free 的 code。
因此在基本功都到一定程度後，與其鑽研過難的 Hard 題，不如把時間投入到直接真人模擬練習的價值會更高。
附註：其實 Leetcode 的難度標籤做的並不好，有時不能正確反應題目的難度，想找更有系統化的分類難度的方法，可以參考這篇的介紹，但先當作一個簡單的標準還是能用啦。
Leetcode Weekly Contest 打到第幾名才夠？
很多人會用 Contest 名次來證明自己，或當成一個實力的指標，其實還算有道理，但小心不要過度。
我自己覺得 Weekly Contest Rank 的目標是能進到 2000 名以內就可以了，能到 500～1000 名內更穩些，但不一定需要。大約是穩定解完前三題 （一般是 Easy、偏簡單的 Medium、偏難的 Medium），而第四題 Hard 賽中做不出來不要緊，賽後看一些提示並慢慢花時間還是能做的出來即可。
由於週賽的難度起伏很大，如果有累積打比賽一段時間的話，你的帳號會得到一個更準確的分數，叫做 Contest Rating，這是經由滿成熟的統計算法，用你每一場比賽的成果，去算出你目前實力的絕對數值，一般面試大公司，會建議達到 2000 分以上，2300 大概算極限，再更多反而不一定好了，可以看下面介紹。
首先，檢驗一下你現在是否適合打 Contest
如果你發現你打 contest 都只能做出前兩題，我會建議先回去分章結的熟練各種題型，不用急着每週參賽。前兩題一般都不太困難，從第三題開始才有顯著的難度斷層。
接下來分成三個階段
第一階段：核心能力達標
用意在測驗自己是否能在不知題目類型，且有時限壓力的情況下順利做出正解。這個階段目標就是練到大多時候可以順利在 1.5 hr 內寫完前三題，中間有些錯誤 Submit 也沒關係，第四題也先不管他。另外第三題難度飄動比較大，有時候甚至逼近或超過 Hard，如果遇到就算了，先不用一定非做出來不可。
第二階段：追求速度與穩定度
這邊開始，練習的目標是速度與穩定度
- 快速把想法轉換成 code 實作出來（越快名次越好）
- 一次送出 submit 就正確（不然錯一次會被扣 5 分鐘，對名次很傷）
這些訓練對面試還是很有價值的，實作速度夠快，可以幫你多爭取一點思考時間，以 Google 來說，45 分鐘平均會問大約 2 題 Medium。等於你一題只有 20 分鐘左右，扣掉聽題目、溝通解釋、尋找解題方向等等，真正打 code 的時間可能僅剩 10～15 分鐘，如果中間想法卡住可能就剩 5～10 分鐘，能不能寫出來就是考驗實作速度了。
而一次 Submit 就要正確則是訓練思維的縝密程度，邏輯是否完全正確無誤，還有能否把 Corner Case 都考慮乾淨，這也是 FAANG 面試會看的一環，看面試者能否自行發現各種可能的細小 Bug，而不是等面試官提示才發現。
最終目標是練到 1 hr 寫完前三題，總錯誤儘量在一次以內（亦即整場最多被罰 5 分鐘），至於第四題可能還是來不及做完，但賽後花個一小時有辦法搞定。如果能到這邊，面試準備其實已經非常充足了。
第三階段：邁向極限（但面試不需要）
到這邊，是 rank 500 內，rating 在 2300 以上的世界，幾乎在拼速度的極限了，儘可能要在 10～20 分鐘內掃完前 3 題，剩下時間儘可能快速完成第 4 題，但到了這階段，為了提升速度，測試資料小的題目一定都是用暴力解快速過，而不是思考最佳做法，難題也有時會靠已經事先寫好的模板或特殊資料結構去偷時間，變數名稱通常也是隨便亂取，c++ 使用者更是習慣 define 一堆只有自己看的懂的縮寫來加速（除非你是世界頂尖玩家，順順寫最佳解也能秒殺），但這些行為在面試時反而是大扣分的！
所以以面試準備來說，建議是最多練習到第二階段就好了，不用繼續執著下去要衝高名次，否則有時會適得其反。
面試中更重要的事
面試時，更注重流暢的解釋思考過程，並找到最佳解，尤其空間複雜度的最優化很容易被忽略，很多 Easy 題，若要追到空間最佳都有很多的知識隱藏在裡面，這些若能注意到，面試時都很加分。然後使用有意義的命名，適度的拆分 Function 與 Class ，避免全域變數，減少副作用等等基本工程師的素養，也同樣都會幫你加分。這些都是打 contest 時不會去注意的。
舉個例子：733. Flood Fill (Easy)
應該是很經典的 Graph 基本題，常見的兩種做法 DFS 與 BFS 時間複雜度是一樣的，但 BFS 的空間複雜度卻非常有趣，到底是 O(N*M)、O(min(N,M)) 還是 O(max(N,M)) ？你會發現衆說紛紜，大多寫這個題目教學的網路文章甚至課程也都避而不談這件事，或是用直覺的想當然爾但其實解釋方式是錯誤的，有興趣深究的人，可以看這篇的精彩討論。
當然以這題來說，面試可能不會真的有時間追到這麼深，但用這個例子只是告訴大家，很多以為簡單的題目，背後都藏了無數的 follow up 可以追問下去，如果你可以想到並解釋的很清楚，一定是大加分。然後上面這題的類似題 200 Number of Islands 甚至還有 Union Find 的做法，如果你也能提到，也會是加分點。但這些面向拼 Contest 排名時一般不會去想，看到就是不囉唆 Graph DFS 模板直接無腦貼上去改一改就送出，所以要提醒自己：
排名不是一切，回歸基本功的扎實練習更重要
另外有關大量背題的準備方式，以前看一些論壇說會去背題目再當場演戲假裝沒看過，但我覺得這實在太難了，要麼是某種程度的背題天才，再不然就是運氣夠好剛好抽到最近練過得題目，總之是個非常不實際的做法。
刷題數量的提升遠不如質的提升有意義
把 1 題 Easy 或 Medium 題裡裡外外各種做法比較都好好研究透徹，比寫 10 題但都用相同思路速刷有意義。
如果你到此為止已經準備的很不錯了，就可以進入最終階段了，下一篇來聊聊實戰練習與一些好用的其他資源！
