# 《提升程式設計師的面試力》
> 一. Big O
> 二. 技術問題
> 三. 聘用問題
> 四. 面試題目

---
## 一. Big O
### A. 時間複雜度
### B. 空間複雜度

---
## 四. 面試題目
### A. 資料結構 [[筆記]](https://hackmd.io/bm6wBuebQ6GoKIi-cPXqgQ)
1. 陣列、字串、雜湊表
a. 雜湊表
b. ArrayList & 可調整大小Array
c. StringBuilder

2. 連結串列
a. 建立鏈結串列
b. 單向鏈結刪除節點
c. 第二指標技巧

3. 推疊和佇列
a. 實作堆疊
b. 實作佇列

4. 樹和圖 [[筆記]](https://hackmd.io/9JZ8uC5YRymCqc_vaLxrvw)
a. 樹的類別
- 樹 vs 二元樹
- 二元樹 vs 二元搜尋樹
- 平衡 vs 不平衡
- 完整二元樹
- 完滿二元樹
- 完美二元樹

b. 二元樹尋訪
- 中序尋訪
- 前序尋訪
- 後續尋訪
- 層序尋訪

c. 二元堆積
d. 線索樹
e. 圖
- 鄰接表
- 鄰接矩陣

f. 圖搜尋

### B. 概念與演算法
1. 位元操作
a. 二進位運算
- 四則運算:
- 加法 : 當遇到 ` 1 + 1 `時，向左進位


- 減法 : 當遇到` 0 - 1 `時，向左借1當2


- 乘法 : 各數相乘，再作加法運算


- 除法 : 各數相除，再作減法運算


- 技巧
- `^ : XOR` `~ : NOT`

| XOR | AND | OR |
| ------------- | ------------ | ---------------- |
| x ^ 0000 = x | x & 0000 = 0 | x \| 0000 = x |
| x ^ 1111 = ~x | x & 1111 = x | x \| 1111 = 1111 |
| x ^ x = 0 | x & x = x | x \| x = x |

- 乘$2^n$ = 左移 n 位
$\left (0110)\right| _2$ * 2 = $\left (1100)\right| _2$
$\left (0110)\right| _2$ * 2 = $\left (1010)\right| _2$
- a^(~a) = 1111...

b. 二補數和負值
- 一補數: 針對正數進行NOT運算

| 絕對值 | 正數 | 負數 |
| ------ | ---- | ---- |
| 0 | 0000 | 1000 |
| 1 | 0001 | 1110 |
| 2 | 0010 | 1101 |
| 3 | 0011 | 1100 |
| 4 | 0100 | 1011 |
| 5 | 0101 | 1010 |
| 6 | 0110 | 1001 |
| 7 | 0111 | 1000 |

問題 : 0有$\pm$之分，這會造成某些問題

- 二補數: 針對正數進行NOT運算(不包含符號位元)，在加1
> 範例: $3 = 0011| _2 \to 1101| _2 = -3$
> 下圖中，左邊和右邊二進位的值相等，原因??

| | 正數 | | 負數 |
| --- | ---- | --- | ---- |
| 0 | 0000 | | |
| 1 | 0001 | -7 | 1001 |
| 2 | 0010 | -6 | 1010 |
| 3 | 0011 | -5 | 1011 |
| 4 | 0100 | -4 | 1100 |
| 5 | 0101 | -3 | 1101 |
| 6 | 0110 | -2 | 1110 |
| 7 | 0111 | -1 | 1111 |

c. 算數位移和邏輯位移

| 運算子 | 符號 |
| ------- | ---- |
| 邏輯右移 | >> |
| 邏輯左移 | << |
| 算術左移 | >>> |
| 算術右移 | <<< |
> 算數位移和邏輯位移主要差別如下
> 邏輯移位 : 不管左移還是右移，都會移 "0" 進來
> 算術移位 : 右移時會依照數字的正負號決定，正的話移入 "0"，負則移入 "1"。
- 算術右移等同於將2進位數字除以2

d. 常用位元任務:取得和設定
- 取得位元值
> 針對常數n，建立一個類似00010000的遮罩，並利用AND取第i個位元的值

public boolean getBit(int num, int i) {
    return ((num & (1 << i)) != 0);
}

- 設定位元值
> 針對常數n，建立一個類似00010000的遮罩，並利用OR修改第i個位元值

public int setBit(int num, int i) {
    return num | (1 << i);
}

- 清除位元值
> 與setBit相反，針對常數n，建立一個類似11101111的遮罩，並利用AND清除第i個位元值

public int clearBit(int num, int i) {
    int mask = ~(1 << i);
    return num & mask;
}

> 若要清除從i到最高為間的所有位元，要先建立一個類似00011111的遮罩，並利用AND清除i位元後的所有位元值

public int clearBitsThroughI(int num, int i) {
    int mask = (1 << i) - 1;
    return num & mask;
}

> 若要清除從i到0的所有位元，要先建立一個類似11100000的遮罩，並利用AND清除i位元前的所有位元值

public int clearBitsThrough0(int num, int i) {
    int mask = (-1 << (i+1));
    return num & mask;
}

- 更新位元值
> 針對常數n將第i位更新成v，
> 先建立一個類似11101111的遮罩來清除第i位，
> 再將v左移i位元，利用OR將n的指定位元做更新

public int updateBit(int num, int i, boolean bitIs1) {
    int mask = ~(1<<i);    //11101111
    num = num & mask;
    int v = (bitIs1?1:0) << i;
    return num | v;
}

2. 數學和邏輯
a. 質數
b. 機率

3. 物件導向設計
a. 分析
b. 設計模式

4. 遞迴與動態程式設計

5. **系統設計與可擴縮性**
a. 處理問題
b. 分解動作
c. 可擴展的演算法
d. 核心概念
e. 考量點

6. **排序和搜尋**
a. 常見排序演算法

| 時間複雜度 | Bubble Sort | Selection Sort | Insertion Sort | Merge Sort |
| ------------ | ----------- | -------------- | -------------- | ---------- |
| best case | $O(N)$ | $O(N^2)$ | $O(N)$ | $O(NLogN)$ |
| average Case | $O(N^2)$ | $O(N^2)$ | $O(N^2)$ | $O(NLogN)$ |
| worst case | $O(N^2)$ | $O(N^2)$ | $O(N^2)$ | $O(NLogN)$ |

| 時間複雜度 | Linear Search | Binary Search | Interpolation Search |
| ------------ | ------------- | ------------- | -------------------- |
| best case | $O(1)$ | $O(1)$ | $O(1)$ |
| average Case | $O(N)$ | $O(LogN)$ | $O(N)$ |
| worst case | $O(N)$ | $O(LogN)$ | $O(N)$ |

- 氣泡排序: [[筆記]](https://hackmd.io/yOMwsoiIR1C6ob4N_l4ibw)
> 原理是從第一筆資料開始，逐一比較相鄰的資料，
> 若大小有誤則交換，反之則不動，接著再進行下一筆資料，
> 每一輪比較完之後，可以確保**最後一筆**資料是正確的位置。

- 選擇排序: [[筆記]](https://hackmd.io/AG-05x1KTZSq4aal40q4cQ)
> 逐筆比較所有資料，找出最小的數值，
> 並將之與最左邊的資料做交換，交換後進行下一輪比較
> 每一輪比較完之後，可以確保**第一筆**資料是正確的位置。

- 插入排序: [[筆記]](https://ithelp.ithome.com.tw/articles/10277360?sc=iThomeR)
> 從左邊開始，逐一將未排序的資料加入已排序的資料中，
> 並逐一與已排序的資料作比較，找到正確的位置插入。

- 合併排序:
> 合併排序，採用經典的 divide & conquer，基本的步驟可以分為「拆分」與「合併」
- 快速排序:
> $時間，平均:O(NlogN)，最壞:O(N^2)$
> $空間，O(NlogN)$

- 基數排序:
> $時間，O(kN)$

b. 搜尋演算法
- 線性搜尋 [[筆記]](https://hackmd.io/47stpm5sSo60-rVNzyRdaQ)
> 適合用於資料少量時的搜尋，並且不須針對資料做排序。
- 二分搜尋 [[筆記]](https://hackmd.io/pE9qQFwCStmzf2okxwYgMg)
>
- 插補搜尋 [[筆記]](https://hackmd.io/c2FGKRmoT3yuhfbDWv29LA)
> 在已排序好的序列中根據資料的預測線或近似線來進行高效率的搜尋
> 若資料趨近於等差級數，搜尋效率甚至接近$O(1)$

7. 測試
a. 面試官想看到什麼
b. 測試真實物體
c. 測試軟體個部分
d. 測試一個函式
e. 除錯

### C. 知識基礎
1. **Java**
a. override、overload
b. collection

2. DB
a. 正規化 [[筆記]](https://hackmd.io/FM2Dd7zmQn2NI7qilRuB8A)
b. 小型DB設計
c. 大型DB設計

3. **Thread & Lock** [[筆記]](https://hackmd.io/4pBtuAzIQXKfrfFy2LeOJQ)
a. Java中的執行緒
b. 同步與鎖
c. deadlock

### D. 補充
1. Medium
2. Hard