.jpeg)
知道越多就越有發展性
- 蒐集: 重點知識
- 理解: 讀懂問題
- 歸納: 組織解法
- 演繹: 寫虛擬碼
- 實做: 轉為程式
- 完善: 修正解題
這趟旅程從鐵人賽開始，從比賽過程熟悉python跟機器學習，也養出看書興趣，始於我在公司借的最後一本書心流，累了就去健身，現在是衝刺的時候了。
O
通過面試
KRs
前置作業：(100%)
程式語言
簡歷
100題以上中級leetcode，每題20分鐘內
Problem Solving Steps
- 所寫語言與職缺，面試官相關
- 釐清問題 Edge case，scale大小，自己的假設 0-5min
- 大聲說出基礎想法，為什麼解法可行 5-10min
- 分析TC, SC Bug優化， 10-15min
- 邊寫程式邊說出思路，一開始寫optimal，想不到再暴力 45min
- 用例子邊說邊測試優化 35-50 min
- 面試官提問 50 min-1 hr
題型回顧： (2022/9: 100%)
結構
List: 特定順序加入
ArrayList
適合
Random Access: Quick Sort TC:O(nlogn), SC:O(n)
Add, Get:O(1)
不適合
Append, Delete: Merge Sort
Add(index, element), remove, indexof, contains: O(n)
LinkedList (Circular Detection)
適合
Merge Sort TC:O(nlogn), SC:O(n)
Add: O(1), Append, Delete O(1)
不適合
Random Access: Quick Sort O(nˆ2 logn)，Quick sort nlogn基礎上再random access找刪除元素，所以要再乘以n
Add(index, element), remove, contains: O(n)
小資料
Bubble sort[不斷交換]:小scale容易達到Best O(n)
Average:O(nˆ2)
Space: O(1)
Inserting sort[取第一筆當排好，後面不斷插入適當位置]: 大部分排好容易達到Best O(n)
Average:O(nˆ2)
Space: O(1)
Traverse
Stack, Queue 類似串列 都不適合 Random Access pop(idx)，任意刪data O(n)
Stack, DFS, FILO
適合 Function call，Sequential access
push, pop, peek: O(1)
List: O(V+E)
Matrix: O(V^2)
Queue, BFS, FIFO
適合 Tree level traverse: Pop O(1)
List: O(V+E)
Matrix: O(V^2)
Priority Queue
streaming 頻繁push,pop O(logn)
適合 Get, Min, Max O(1)
不適合 Random Access，Delete
Tree
Binary tree
不能假設左子比右子小
Binary search tree
左子比右子小
Search, Insert
Tc:
Best: O(1) avg: O(logn) wst:O(n)
Sc: O(n)
Delete
Tc:
Best: O(n) avg: O(logn) wst:O(n)
Sc: O(n)
Balance tree
左右子同深度 access: O(logn)
適合 Append，Search
不適合 Delete，Copy，Change Order，In-place sorting
Trie
適合 Auto-completion O(logn)
不適合 Delete，CopyBFS, DFS，各有利弊 Tree 很深DFS可能Stack overflow，可以假定深度D，比較方便討論複雜度
Map
HashMap
可以為之後要處理的做preprocessing, reduce time complexity
適合 無順序
Put, Get,Remove, ContainsKey: O(1)，良好hash function下
TreeMap
適合 有順序
Put, Get, Remove, ContainsKey: 樹狀結構 O(logn)
Implement紅黑樹
紅黑樹是self-balancing binary search tree
Set：元素不重複
HashSet
適合 無順序
Add, Remove, Contains: O(1) ，因為底層是HashMap
TreeSet
適合 有順序
Add, Remove, Contains: O(logn) ，因為底層是TreeMap
演算法
Sorting
Quick Sort: Average: O(nlogn), Worse: O(nˆ2), SC:O(n)
Merge Sort: Average: O(nlogn), Worse: O(nlogn), SC:O(n)
Searching
二元搜尋 : 每次步驟砍半: O(logn)
動態規劃
Multithreading
Deadlock, busy wating…
List的CopyOnWriteArrayList是thread-safe
Get: O(1)
Add, remove, contains: O(n)
Mock Interview (80%)
Behavioral
任何經驗都有可取之處，所以要保持正向
依職位可能不會談到領導力，但還是要知道
- System Design
前端，後端針對自己專業回答就好，要了解Domain knowledge
Backend: 使用者很多，可用load balancer
時程：2022/09/1-2022/10
如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)