---
tags: INFO2022
---

# 2022-12-06 課堂問答簡記

## [System Design Course](https://github.com/karanpratapsingh/system-design)
> System design helps us define a solution that meets the business requirements. It is one of the earliest decisions we can make when building a system. Often it is essential to think from a high level as these decisions are very difficult to correct later. It also makes it easier to reason about and manage architectural changes as the system evolves.

### Example: Twitter
* '#' function implementation
* Explaination: Tag功能，可以自行在貼文中標註此貼文與某個議題相關
* Criteria:
* 避免search all data/tweets
* latency
* computational cost
* 不需要"精準搜尋"
* How:
* 可以先透過額外紀錄常使用此'#'的userID、region等等資訊，之後當用這個tag進行搜尋時，則直接在這個另外儲存的空間中尋找即可。
* The [index](https://en.wikipedia.org/wiki/Database_index) in the database
* 索引(Index)是一種資料結構，目的為在進行資料庫搜尋、檢索時可以更有效率，例如：無須搜尋整個表(table)。
* 若表中有n條紀錄(record)，逐條進行比對則需要O(n)的時間。
* 通常透過使用額外的儲存空間(表)來儲存。
* 索引會複製原表中部分的欄位，且通常可以連結回原本的完整紀錄，以方便取得其他欄位的資料。
* 索引也可以事先過濾掉不需要的紀錄，以縮小所需的空間，並提高這種資料結構的效率。
* e.g., 我們可以在索引中儲存包含"#Linux"這個tag的column以及對應的UserID，將來在搜尋"#Linux"這個tag時，我們便可以快速地取得對應的UserID，而不需要逐條紀錄進行比對。

### Search Tree

#### 2-3-4樹

除了葉節點外，每個節點都有2~4個子節點，故名2-3-4樹。實作較為困難，因為其特殊情況很多，所以現今較少使用在 Database 中，取而代之的是「紅黑樹」，因紅黑樹與2-3-4樹為等價的資料結構，所以對於每個2-3-4樹，都存在至少一個資料元素是同樣次序的紅黑樹。

#### 紅黑樹

有以下基本五個的特性
1. 每個節點會是紅色或是黑色
2. 根節點一定是黑色
3. 葉節點一定是黑色(葉節點會是 NIL 節點)
4. 紅色節點的子節點一定都是黑色的
5. 從任意節點到其所有葉節點，經過的黑色數量是一樣的

利用這些性質保證了從根節點到任意葉節點的路徑，最多相差一半，應其較好時做所以比2-3-4樹常實用

#### B+Tree
上週的課程筆記已經提及過，可以看這邊 - [Link](https://hackmd.io/@sysprog/r1GEJNMDj#B-Trees-Implement-in-SQL)。B+Tree改善了 B Tree 可能會因為資料量太大(這了指的是 Key-Value 的 Value 大小，不是只資料總數)而一個節點能儲存的空間變少的問題，且因為葉節點的串聯達到很方便的範圍搜尋。

#### Search in Database
(以下皆以 InnoDB 為例)
- Search by Primary Key
只需要用搜尋樹的走法找到目標就可以了。

- Search by Secondary Key (Not Primary Key )
會有一顆利用 Secondary Key 建出來的樹，LeafNode 除了目標值外，也儲存了 其對應的 Primary Key所以可以再用 Primary Key 建的樹找到目標資料。

#### Join Table
通常 Join 使用上就是"Select From Where"，若沒有 Where 則就只是將所有狀況列出來而已。所以通常會是由一個 Table 從頭往後走(因為葉節點都串聯，所以可以直接從第一個走到最後一個)，將每個 Data 根據 Where 條件去另外一個 Table 的 Tree 中 Search。

## 校友經驗分享問答: [Tony](https://www.linkedin.com/in/chonyy/)
* [面試過的公司清單](https://hackmd.io/@chonyy/ry4I3oKBi)
* [新鮮人 offer 選擇](https://www.ptt.cc/bbs/Soft_Job/M.1652500150.A.F8D.html)
* [2020 Software Intern 面試心得](https://www.ptt.cc/bbs/Soft_Job/M.1598009742.A.4F6.html)

1. Intern 的選擇
* 在履歷上有加分作用的的的
* 牌子大的優先
2. 海外求職眉角
* 求職方的準備流程不多
* 缺開出來就投
3. 畢業後的 Offer
* 先投 Startup 練面試
* Startup 的 Hire 流程比較快
* 快則 2-3 週
* 也把 Offer 當 Backup
4. 選 AWS 的原因
* 目標：想要參與高流量的 back-end 開發
* AWS CloudWatch Million QPS
* What's [CloudWatch](https://aws.amazon.com/tw/cloudwatch/features/)
* 在開發時會想更多效率上的優化
* Case： 改一個流程幫公司省了 7 Million USD
5. AWS 面試流程
1. Online Assessment (OA)
2. Visual interview
* Amazon 注重 Leadership
* Behavior question
6. Performance Improvement Plan
* [參考](https://zhuanlan.zhihu.com/p/74938330)
* Tony 澄清：不容易發生
7. Bloomberg terminal
* 金融資訊整合系統
* 股價、新聞消息
* [參考](https://www.bloomberg.com/tc/solution/bloomberg-terminal/)
> 學長的 Keynote: 看到缺就投！
## QA
1. 怎麼針對這麼多的公司作 Resume 的修改和面試的準備呢？
* 【Tony 個人看法】
* 不太用特別客制
* 但要在 Resume 上要有亮點
* 投的量和速度要夠多和快
* Interview
* LeetCode
* 大多會是常見題目
* 作用是讓面試官看到解題的方法和過程的溝通
* 個人經歷
* 要對自己做的東西很理解
* (經典的 5W1H)
* 不要被自己做過的事情問倒
* Behavior question
* [Leadership Principles](https://www.amazon.jobs/content/en/our-workplace/leadership-principles)
* System design
* e.g., Tiny url, Twitter, High Concurrency Service
2. Medium 技術寫作經驗加分的程度、一定要 promote 到讓社群或是讓流量很好看嗎？
* 難被量化、但面試時需要包裝
* e.g., Github open source contributing, medium 的 view stat
* 學生時期
* Final project / 專題的東西可以包裝一下、寫個 README
* 在 Interview 上有被提到嗎？
* 基本沒有、但作為自己 profilio 的補充
3. 昨天收到 Amazon [Cloud Support Intern](https://www.amazon.jobs/en/jobs/2173880/cloud-support-intern) 的 OA，想詢問學長此職位未來面試方面，有沒有準備上的建議？
* Aws 在台灣只有 support,沒有開發， OA 記得是問答題，不太問技術方面，進去只做一點開發，如果要做 software engineer 不是很推薦
* 看到職位就投，有沒有資格給 HR 決定
4.