# 8/6讀書會(開發工具、資料結構)
###### tags: `面試考古題` 開發工具 資料結構 演算法

### 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』的空檔案

- 在專案中放入一個`gitignore`檔案，設定想要忽略的規則，但只會過濾掉設定完過濾條件後新增的檔案
- 過濾掉新增過濾條件之前的檔案做法
- `git rm --r --cached`清除本機git的快取，相當於移除所有檔案git的追蹤
- `git add .`重新加入git追蹤，這時會套用gitignore設定
- `git commit -m`

[忽略特定檔案.gitignore](https://sinyilin.github.io/git/20191109/1510464038/)
[Github - A collection of useful .gitignore templates](https://github.com/github/gitignore)

示意圖

#### 忽視gitignore的方法
- 只要在`git add`時加入`-f`參數，就可以無視規則

git add -f 檔案名稱

#### 清除忽略的檔案
- 使用`git clean`搭配`-X`參數及`-f`強制刪除

git clean -fx

# 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

## 參考資料

易懂：多圖

[](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)