# 8/6讀書會(電腦科學、開發工具)
###### tags: `面試考古題`

==翊廷==
https://www.notion.so/8-6-5ce21f43917c416a9349ad96724e3340
# Tree(資料結構)

## 什麼是Tree?

用來描述具有階層結構問題的首選，階層代表順序。

只有一個root，且不存在cycle→

1. 節點只存在一條路徑
2. 每個節點只有一個parent

常見的元素/定義

1. **degree(分歧度)**：一個node擁有的subtree(子樹)的個數。
- 圖四，A的degree為3，F的degree為2，N的degree為0。
2. **root(樹根)**：樹中最上層的node，也是唯一一個其parent為**NULL**的node。
- 圖四，A即為root。
3. **leaf**：沒有child/subtree的node稱為leaf node。
- 圖四，G、H、J、K、L、M、N皆為leaf node。
4. **external node**：沒有child的node。因此，leaf node與external node同義。
5. **internal node**：至少有一個child的node，稱為internal node。
- 圖四，A、B、C、D、E、F、I皆為internal node。

## 可以用來做什麼?

方便快速找資料

## 常見概念

時間複雜度、空間複雜度

EX：DOM Tree 搜尋的時間複雜度是什麼?

## 樹的變化：

1. 二元樹→二元搜尋樹

## 二元搜尋樹：

1. 比此node小的會在節點左邊，反之右邊
2. 每個node只有兩個child
3. BFS 廣度優先搜尋 v.s. DFS 深度優先查詢

## 舉例

目錄、族譜、企業職位關係、心智圖、DOM tree

## 參考資料

[Tree(樹): Intro(簡介)](http://alrightchiu.github.io/SecondRound/treeshu-introjian-jie.html)

[[資料結構] 樹 Tree](https://medium.com/starbugs/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%E6%A8%B9-tree-1cfddf5685ce)

# Git Flow

## 什麼是Git Flow

是有人提出的一套流程讓大家共同遵守，有五種branch定義及功能，分別是master、develop、hotfix、release 以及 feature。

1. develop及master會一直存活在Git flow中。
2. 其餘支援性(Supporting)branch會因為任務結束建議刪除。

## Branch功能介紹：

- Master
放置穩定、可隨時上線的版本，不會直接commit到這個branch，而是合併其他branch而來，常會使用版本號標籤。
- Develop
由master一開始分支而來，是所有開發分支的base，所有feature都從這邊分支出去，也會在開發完成後合併進來。
- Hotfix
master的穩定產品出現重大緊急問題時，會開hotfix做修復，修復完成後會合併回master，也會合併進develop，避免後續develop合併回master時出現一樣問題。
- Release：不應該有新功能
若是Develop成熟後會開release分支，此分支不應該有新功能，僅測試bug，是上線前的最後測試，OK後會合併回master，如果過程有針對bug做額外修正時需要merge 回develop做更新的概念。
- Feature：只會被merge回develop分支
若有新功能需要開發就是從Develop開分支出來，也可以依據需求從其他feature分支分出來。
開分支時建議前綴 `feature + / + 功能名` 例如： `feature/filter`

## 狀況題

### 遠端的 feature 分支有新的 commit

可以使用`git pull --rebase origin feature/myFeature`

邏輯概念參考[大大](https://blog.hellojcc.tw/understanding-git-flow/)：把目標分支可以fast forword的commit都merge到目前分支(此案例應該是在`feature/myFeature`)，再把目前分支有的commit一個一個加/插入(?)回去。

因為是同個功能開發，理所當然遇到conflict機率高，但rebase好處是可以看到每個commit遇到conflict的地方，merge的話會是一次處理所有commit的conflict。

## 補充：對於git flow修正的建議與討論

### develop的存在必要性?

- *hotfix*: 已經出版的舊有功能需要修正
- *feature*: 要新增新的功能
- *release*: 由feature分支而來，集結下一個版本要的功能，在這裡修正 bug 後準備出版，進到 *master*

### 問題：

- 不必要的相依性：F1、F2


- 重複的流程


暫時解答：[看開發的CI環境的設定](https://blog.wu-boy.com/2017/12/github-flow-vs-git-flow/)，

## 參考資料：

[Git Flow 是什麼？為什麼需要這種東西？ - 為你自己學 Git | 高見龍](https://gitbook.tw/chapters/gitflow/why-need-git-flow.html)

[git flow 實戰經驗談 part1 - 別再讓 gitflow 拖累團隊的開發速度](https://blog.hellojcc.tw/the-flaw-of-git-flow/)

[A successful Git branching model](https://nvie.com/posts/a-successful-git-branching-model/)

[了解 Git Flow](https://blog.hellojcc.tw/understanding-git-flow/)

# 敏感資料的儲存

## 問題：

在 Rails 專案中，config/database.yml 這個檔案裡有資料庫的設定、帳號密碼等資訊，在使用 Git 時，你通常會怎麼處理這類型內容比較敏感的檔案？

## 另外給定.env檔案切換不同環境所需變數(使用dot.env等套件)

### 方式：

在development時去讀取.env檔，並且同時在.gitignore上設定忽略，避免將這些資料被公開。

### 優點：

方便又簡單!!!!!!

### 缺點：

1. 若有設定必須修改就要重新上新版本
2. 難保沒有人為失誤不小心將機密資料上git

## kubernetes管理

### 方式：

使用他提供的config map及secrets解決

## AWS Paremeter Store @ AWS System Manager

### 方式：

# merge vs rebase @ 大量conflict

## 問題

兩個 branch 各有五十個 commit 要接起來時，極有可能會出現大量的 conflict ，這時你會選擇用 merge 還是 rebase 處理它？哪個可能比較方便（或比較少的衝突）？為什麼？

## 簡單解答

merge會一次性解決所有conflict，比較容易；而rebase會多次解決，並針對不同次commit造成的衝突進行更改。

merge是把要merge的最後一個commit做合併；rebase則是一個個commit合併進去，所以可能會有多次的衝突須要解決

## rebase細節

可以一次處理多個commit，概念就如同高見龍說的，re-base，重新變換基礎。


### 流程

1. `git rebase <commit_id> [-i | --interactive]`會在VI介面產生一個rebase todo list，並逐項執行rebase todo
2. `git rebase --continue`每次改動好就使用此指令繼續下一項rebase todo

### 額外指令

1. `git rebase --skip`跳過當前rebase todo
2. `git rebase --abort`跳出整個rebase

## 參考資料

易懂：多圖

[多圖rebase講解](https://www.maxlist.xyz/2020/05/02/git-merge-rebase/)

中：機制的比較

[Git: 更新分支+解衝突 | Summer。桑莫。夏天](https://cythilya.github.io/2018/05/27/git-merge-and-solve-conflict/)

[機制比較](https://kknews.cc/zh-tw/news/k8alv2v.html)

複雜：Git較底層知識、原理，但有圖片、實作

[Rebase 與 merge conflict 機制](https://medium.com/@RiemannAC/rebase-%E8%88%87-merge-conflict-%E6%A9%9F%E5%88%B6-b01f0d49d747)

==TINA==
## Linked List
### 1. 重點

- 與陣列一樣都是**線性資料結構**，但不同於陣列，它為鏈式儲存結構，也就是記憶體位置儲存為不連續性。
- 等於是自己創造一個資料結構
- 使用Linked List可以克服陣列串列需要預先知道資料大小的缺點，Linked List可以充分利用電腦記憶體空間，實現靈活的記憶體動態管理。但是失去了陣列隨機讀取的優點，同時Linked List 由於增加了結點的指標域，空間開銷比較大。

### 2. 定義

Linked List 是由一連串 **節點（node）** 組成，節點之間是透過 pointer 來連接。所以儲存上並不需要連續的空間。

每個節點包含：

- 資料元素
- pointer 若沒有上／下一個節點，則為 Null。如果pointer斷裂，資料就遺失在記憶體大海中。

舉生活上的例子來說，鏈結串列如同火車的車廂一樣，一節拉著一節。

因為Linked List沒有index，若要存取特定node，需要從頭開始找起，因此相較於陣列，存取資料較費時。

### 2. 類型

鏈結串列有很多種不同的類型：

- 單向鏈結串列（Singly Linked List）
- 雙向鏈結串列（Doubly Linked List）
- 迴圈鏈結串列（Circularly Linked List）

### 單向Linked List

是最基本的鏈結串列，其特點是鏈結串列的鏈結方向是單向的，對鏈結串列的存取要通過從頭部開始，依序往下讀取。


[讀書會時的簡報檔案](https://drive.google.com/file/d/1I6WMkZyS2F-j2AtfSqNdESyjBIwbiSDA/view?usp=sharing)

[中文教學](https://chupai.github.io/posts/200427_ds_linkedlist/)

[英文教學](https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/)

### LEETCODE 可研究題目
[https://leetcode.com/problems/palindrome-linked-list/](https://leetcode.com/problems/palindrome-linked-list/)

[https://leetcode.com/problems/remove-linked-list-elements/](https://leetcode.com/problems/remove-linked-list-elements/)

## 版本管理系統是什麼？為什麼要用
### 1. 定義
「版本控制系統」，就是指會幫你記錄這些所有程式碼的狀態變化，並且可以隨時切換到過去某個「版本」時候的狀態。

### 2. 解決了什麼問題？
主要使用版本控制系統原因就在備份及協作，不論是個人或是多人協作，都有需要切換到過去某個版本或是還原某個版本的需求，或是共同編輯專案的需求，但只要協作的人一多，備份檔案就會更多，也有可能程式碼被別人或自己不小心覆蓋或遺失的問題。

因此更需要版本控制系統來解決這個問題，可以更清楚的記錄每個檔案是誰在什麼時候加進來、什麼時候被誰修改或刪除

### 補充：
Git 與其他版控系統最大的差異就於，他是「分散式儲存」， DVCs（Distributed Version Control System） 將資料分散於不同設備上(就是儲存資料的本地端)，如此一來，就算其中一處設備損壞，也不影響其他用戶使用。

集中式版本控制：
這類系統（如：CVS、Subversion 和 Perforce），都有一個伺服器來管理所有版本的檔案，而許多用戶端會連到這台伺服器取出檔案來使用。
* 優點
每個人都可以一定程度的知道專案中的其他人正在做些什麼。
管理員也可以輕鬆掌控每個開發者的權限。
* 缺點
最嚴重的當然是中央伺服器如果發生故障的時候。 如果當機一小時，那麼這個小時之中，沒有人可以提交更新，也就無法協同合作。
如果中心版本庫的硬碟發生損壞，又沒有做適當的備份，那麼你就絕對會遺失所有資料——包括專案的全部變更歷史，只會剩下用戶端各自機器上保留的單獨快照。

參考資料：https://git-scm.com/book/zh-tw/v2/%E9%96%8B%E5%A7%8B-%E9%97%9C%E6%96%BC%E7%89%88%E6%9C%AC%E6%8E%A7%E5%88%B6

## 請寫下從 Github 上複製一個專案下來，做一次遞交，然後推上去會用到的所有 git 指令。

1. 從他人 gitHub 專案 fork 到自己的 repository
2. clone 自己的 repository，在本地的 Terminal 輸入`git clone 請求網址`
（Clone 指令會把整個專案的內容複製一份到你的電腦裡，這裡指的「內容」不是只有檔案，而是指所有整個專案的歷史紀錄、分支、標籤等內容都會複製一份下來。）
3. 再修改程式碼後透過 `git add .` 登記檔案變動
4. 透過 `git commit -m "WRITE SOMETHING"` 建立版本細節
5. `git push origin <分支名稱>`
6. 到原先專案的擁有者 gitHub 頁面 pull request 合併回原專案

[參考連結](https://ithelp.ithome.com.tw/articles/10140305)

## 當多人協作時你要開發個功能，但不影響主程式，該怎麼作呢？要下什麼指令？開發好功能後需要下什麼指令合併回主程式？如果衝突了要如何處理？

假設團隊已開立 Develop 分支 + 使用 git flow + 已經處理過上一題的流程

1. **`git checkout develop`**
2. 從 Develop 再開一個 Feature branch：**`git checkout -b Feature-branch`** 後就可以開始在這個分支上修改程式碼
3. 完成編輯後，再回到 Develop 分支：**`git checkout develop`**
4. 先取得最新的 Develop 分支狀態： **`git pull 原專案Develop`**
5. 若有衝突，可以回到程式碼區塊查看衝突發生的點，並且與團隊討論
6. 修改完衝突後 **`git add 衝突發生檔案`** 把這個檔案登記檔案變動
7. 說明衝突情況 **`git commit -m "WRITE SOMETHING"`**
8. 合併 Feature branch 到 本地Develop 分支：**`git merge Feature-branch`**
9. **`git pull`** 自己的遠端 develop分支
10. 到原專案擁有者的頁面 pull request

==YJ==

## Graphs（資料結構）
### 圖是什麼？
- 柯尼斯堡七橋問題（The Königsberg Bridge Problem）
- 東普魯士柯尼斯堡（今俄羅斯加里寧格勒）市區跨普列戈利亞河兩岸，河中心有兩個小島。小島與河的兩岸有七條橋連接。有人就開始想，在所有橋都只能走一遍的前提下，如何才能把這個地方所有的橋都走遍？
- 尤拉把問題的實質歸於一筆畫問題，即判斷一個圖是否能夠遍歷完所有的邊而沒有重複。對於一個給定的連通圖，如果存在超過兩個（不包括兩個）奇頂點，那麼滿足要求的路線便不存在了，且有 n 個奇頂點的圖至少需要 n/2 筆畫出。如果只有兩個奇頂點，則可從其中任何一地出發完成一筆畫。若所有點均為偶頂點，則從任何一點出發，所求的路線都能實現。
- 定義：圖 (Graph)，在資料結構上指的是點和點之間的關聯的東西，並不是數學定義上的兩點成一線，三點成一面的那種圖。一張圖由數條邊 (Edge) 和數個點 (Vertex) 所構成，點和點之間可用邊相連，表示這兩個點之間有所關聯。兩點之間可以有多個邊，一個點可與多個點相連。

- 有向圖 vs 無向圖
- 有向圖：G = (V, E), 其中V為頂點集合，E為邊集合。邊集合中的毎一個邊都有方向性，以指向下一個頂點。
- 無向圖：G = (V, E), 其中V為頂點集合，E為邊集合。 邊集合中的毎一個邊都沒有方向性。

- 若要表示一個圖形，需要儲存兩個集合：頂點 & 邊

### 圖常用的儲存方式：

- Adjacency matrix 相鄰矩陣：把一張圖上的點依序標示編號，然後建立一個矩陣，來記錄連接資訊。方陣中的每一個元素都代表著某兩點的連接資訊。
- Adjacency list 相鄰串列：在每一個點後方，串連所有相鄰有連接的點

### 圖的遍歷 Traverse Graph（檢查 Graph 是否連通？）
- Depth First Search (DFS；深度優先搜尋)
- Breadth First Search (BFS；廣度優先搜尋)

## Rebase
- Rebase -> Re + base -> 重新定義分支的參考基準
- 用途：將所有歷史 commits 放在同一條線上，若用 merge 會留下 merge commit，如果 merge 很多次線圖會有很多 merge commit，很醜而且回看的時候會很亂不乾淨。但若用 rebase 是直接把 commits 拉到別的基準，不會生成新的 commit 紀錄，線圖就會很美（但同時也代表分支紀錄會消失，會找不到這個功能的上源是什麼）。
- Interactive Rebasing
- 用途：ex: develop merge 回 master 前清理線圖用

    git checkout feature
    git rebase -i master

- 在 terminal 打上面的指令後會出現如下圖的畫面

- 可以依據 git 的指令提示更改自己的 commit 紀錄

- 例如像上圖把 `pick` 改成 `fixup` 後就會把第一個 commit 跟第二個 commit 合成同一個 commit

### Rebase 準則：
==不能用在別人在用的分支上（ex: master 或任何推上 remote 的）==

## 為什麼 Git 稱作「分散式」版本管理系統？
- 版本管理系統：
- Local version control 本地式：都在自己本機
- Centralized version control 集中式：都在系統上
- Distributed version control 分散式：有存在本機的但也可以推上去讓其他人取得
- 定義：軟體開發者可以共同參與一個軟體開發專案，但是不必在相同的網路系統下工作。每個開發者電腦中複製一份完整的 code 以及完整歷史，因此在無法連接網路時，仍可以進行軟體的分支及合併，可以加速大部份的作業，而且可以在多家電腦上備份，不需靠單一位置的備份。不同位置的資料再透過其他機制來達到同步（push, pull）。
- 分散式管理系統優點：
- 使用者在沒有網路的情形下，也可以存取其電腦中的軟體儲存庫。
- 常見工作（例如上傳、看修改履歷、回退變更）不需要和中央伺服器通訊即可達成，只有要和其他人分享變更內容時才需要通訊。
- 允許個人作業，使用者可以將不希望公開的早期修改（甚至是草稿）上傳
- 工作複本的作用類似遠端備份，因此不會依賴單一的實體機器，分散風險

## 什麼是 staging area？（暫存準備遞交區）

- Staging area 在提交 commit 出去後並不是空的，而是儲存著最後那次的 commit，這樣對檔案有變動的時候，因為新的變動跟本來儲著的最後 commit 有差異，就可以知道有更改
- 優點：
- Working tree 可能很亂，包含了想要 commit 的內容和不相關的實驗修改等，Staging area 的設計可以讓你只 commit 想要的檔案，甚至是想要的部份修改而已

==Marco==

## HashTable 雜湊表 (哈希表)
- 定義：由key-value組成的pair
- 類似於arrray存資料的方式，差別在於，array是用位置儲存，但hash table是根據key而直接查詢在記憶體儲存位置
- 可以用`Map`、`Object`做為hash table使用 (也可以用array製作，用index當key)

- 優點：
- 資料量大時，相較於array的靠位置找資料，直接用key來找資料的速度較快

將key透過hash function對應到特定的記憶體位置就是hash table，若使用object, Map的話JavaScript會自行幫我們做hash function


[Leetcode 136. Single Number](https://leetcode.com/problems/single-number/)
[Repl](https://replit.com/@MarcoLin1/test-2)

### HashTable collision怎麼辦？
1. 一個一個往下移
2. linked list

### Map
- 類似object的key-value pair

let map = new Map([
    ['one', '123']
])

map.set('two', '456') //修改
map.get('two')       // 取得資料
map.delete('two')    // 刪除

### Map與Object有何不同
Object: 沒有順序，key的格式都是String
Map: 有時間順序 (依照加入的時間排序，first in first out)，key的格式可以是任何格式

## GitHub Flow
- 定義：工作流程的一種，以主分支`master`為基底，不論是解issue或者開發新功能，都是從主分支再開其他分支，讓主分支時常保可以部署的狀態
- 流程：
1. 建立團隊的repo
2. 團隊成員fork團隊的repo到自己帳號
3. 開新的feature
4. 增加commit (修改後)，將feature推到GitHub上
5. 針對團隊的repo發PR
6. 討論並檢核code
7. merge回主分支，部署到production環境 (也有可能先部署到測試環境)

[GitHub Flow](https://guides.github.com/introduction/flow/)
[三種版控流程](https://medium.com/@lf2lf2111/%E4%B8%89%E7%A8%AE%E7%89%88%E6%8E%A7%E6%B5%81%E7%A8%8B-29c82f5d4469)


## GitLab Flow
- 定義：
- 只有一個主要分支，所有的分支都是從主分支建立
- 原則：
- upstream first (上游優先)，只存在一個主分支master，是所有其他分支的上游，只有上游採納的程式碼變化後，才能應用到其他分支，除非是緊急情況，才允許跳過上游直接在下游操作合併
- 工作流程： (持續發布的專案)
- 有三個分支，分別為master (開發環境)、pre-production (預發環境)、production (生產環境)
- 如果production發生問題，先建立一個分支修改完後合併到master
- 經過測試沒問題後再合併到pre-production
- 在pre-production測試沒問題後，再合併到production


## 空的資料夾無法被加入 Git 進行版本控制，但這個資料夾如果又是很重要的資料夾，你會怎麼處理？

- 原因：
- Git在計算、產生物件的時候，根據『檔案的內容』做計算的，所以空的資料夾沒有檔案內容，Git無法處理

- 解決方法：
- 在空目錄裡隨便放一個檔案就行了 <font color="red">(大家的想法和高見龍大大一樣，英雄所見略同！！！)</font>
- 慣例上會放一個名為『.keep』、『.gitkeep』的空檔案