Coding Interview:
參考Cracking the coding interview這本書 https://www.crackingthecodinginterview.com/
如果是video interview，記得多用打字，不管是在一開始講解暴力法， 或是講解準備要implement的方法，以及最後再驗證每一步時，都把目前的變數寫出來，並且驗證到哪了。
- Listening carefully
- 仔細聽到題目給的線索 ex: sorted array
- 可以把可能的線索先寫在白板上，確保記得，晚點要優化的時候再來看是否都用到這些線索
- Draw some example:
- 不用太大的example，
- 但盡可能把所有的情況都想到，透過跟面試官討論，
- 以及多問一些題目的限制，比如說元素有沒有重複，等等
- 多列舉example可以輕鬆看出題目要解什麼問題
- 列舉example的過程邊跟面試官確認input and output
- 把所有example都討論出來後，再開始想演算法。
- State a brute force
- 先說出暴力法，分析其time and space complexity
- 不用寫code
- 並重此方法開始優化
- Optimization
- 回頭看有沒有什麼線索沒用到
- 或用一些小的Example去找規律，
- 類似小問題可以組成大問題等等 ex:permutation, generate parenthemes
- do it yourself，可以實際操作看看現有的example，可能找出本能上最優化的步驟
- 看可不可以預先處理，
- 比如先排序
- 先算一些值, 例如先算linked_list的長度
- 原本的data要前後各放一個測資，讓等等程式可以簡化
- 找到ＢＵＤ(Bottleneck, Unnecessary work,Duplicate work )
- Bottleneck是在哪，等等可以思考換了什麼資料結構可以解決此bottleneck
- Unnecessary work是什麼，看可以不可以簡化
- Duplicate work是什麼，看可以不可以簡化
- 空間換時間，看可不可以用什麼資料結構，
- 通常hash table是很好的出發點
- 活用其他資料結構
- heap的insert是logn，如果不用知道整體的排序，只需要最大或最小，或是中間（用min-heap and max-heap
- Binary Search tree，insert 花O(logn)時間複雜度，但這會是有一個整體排好序的結構，看題目需不需要，因為找尋也會需要花O(logn)
- deque，最前面可以存最大的，不需要此最大的時候可以從前面pop，新的可以從後面Insert，比新的小可以直接從後面pop
- hash配double linked list，ex: LRU
- queue，ex: BFS
- stack，ex: mono stack 或是 找longest increasing squence問題
- ＢＣＲ(Best Conceivable Runtime):
- 從暴力法開始： O(n^2)
- 架設BCR是O(n)，表示可能有方法變成O(nlogn) 到 O(n)
- 這時候就用前面那些方法，看有哪些方法可以看出如何優化
- 任何小於目前bigＯ的pre handle都可以嘗試，因為不會影響到最後的結果
- walk through:
- 找到優化後，先別急著寫code
- 先試著走一次，用草稿，pseudocode都可以，感覺一下架構會長怎樣，變數會有哪些
- 切記，如果還沒很透徹就開始寫，只會越來越糟
- Implement:
- modularized code:
- 可以先寫一個funtion，到時候再實作他，可以讓自己思緒不中斷，可以讓程式有架構
- 一些error handling
- don’t make assumptions about the input
- 比較複雜的checking可以留TODO，等等有空再來寫
- 有些小的資料結構，可以先假設有了，等等有空再實作他，或是資料結構裡的method可以等等在實作，先使用，確保思緒維持住
- Great naming
- 如果寫到一半卡住了，代代看剛剛的測資，確保沒有偏離原先想法。
- modularized code:
- Self Testing before submitting
- 先看一下每一段在幹嘛，是不是自己要的
- 驗證的時候，讓測試資料給面試官知道，
- 讓面試官知道現在在驗哪裡，現在測資是什麼，ex: idx = 多少，value = 多少
- 也讓面試官知道我的驗證步驟是不是哪裡有錯誤
- 看一些特殊邊界條件, ex:
- start從1開始，為什麼不是0開始
- end為什麼是len(array)-2，不是len(array)-1
- 或是partitiony = (x+y)//2 – partitionx，這種特殊的計算
- 或是一些length減了多少變成某index，或是某index加了多少等於另一個index等等一些shift的操作
- Hot spot區
- node會不會是None，又對他存取
- recursive的終止條件，會不會無限循環
- array or string會不會超出界
- 開始帶入真的測資：
- 先帶入正常小一點的測資即可
- 再帶入一些特殊測資看會不會有例外狀況
- 找到bug，別急著修，看一下為何會有此bug，找到root cause並確認準備要修的修法是最好的修法
System Design:
相關知識點可以參考
How to prepare for System Design Interview 系統設計面試準備
大概的面試流程:
- 先問使用情境，把user如何使用這個系統先理清楚
- 多少客戶，多少流量，會產生多大的資料，是持續增長的資料還是一直維持在那的資料，算出QPS
- 選定要用什麼機器後，可以用QPS推出大概要多少機器。
- 選定Design Goal: CAP theorem, C or A, write heavy or read heavy。
- Abstract Design，畫出大架構
- 大致的API有哪些
- 以gift card 系統為例大概會有三種API
- 一開始讓user 寫入序號，
- 要使用這個禮物卡時，要讀這個序號，對應到多少錢。
- 最後用完這個禮物卡，要把這個序號標記用過了。
- Deep Dive, 例如有些跟地圖相關的設計，牽扯到比較複雜的 quadtree algorithm或是其他的演算法，這一部分通常可以提到這個知識即可，畢竟在30~40分鐘裡面通常無法講得很深，所以這一部分在短時間的面試通常可以跳過。
- How to scale up, fault tolerance
Live In the Future 