# Software Interview Note
[TOC]
## **作業系統**
### **Program**
Program 為軟體工程師所寫的程式碼 (code) 的集合，也就是還**尚未 load 進記憶體**的程式碼，存放在次級儲存裝置 (Secondary storage)。
### **Process**
Process 為**已經執行且 load 到記憶體**中的 Program，process中的每一行程式碼隨時都有可能被 CPU 執行。
每一個 Process 由下面兩項組成：
* 一個*Memory Space*。相當於 Object 的 variable，不同 Process 的 Memory Space 也不同，彼此看不到對方的 Memory Space。
* 一個以上的*Thread*組成。
`Process 是電腦中已執行 Program 的實體，每一個 Process 互相獨立。`
`Process 不是基本執行單位，而是 Thread (執行緒) 的容器。`
### **Thread**
Process 是 Thread 的容器，在同一個 Process 中會有很多個 Thread，每一個 Thread 負責某一項功能。
每一個 Thread 由下面兩項組成：
* Stack：紀錄從某個起始點開始 (例如main)，到目前為止所有函數的呼叫路徑，以及在這些呼叫路徑上所用到的區域變數。
* 紀錄 CPU 內部的暫存器 (如 Program Counter, Stack Pointer, Program Status Word 等) 的狀態。
在多執行緒中 (Multithreading)，兩個執行緒若同時存取或改變全域變數 (Global Variable)，可能會發生同步 (Synchronization) 問題。若執行緒之間互搶資源，則可能產生死結 (Deadlock)，如何避免 (Prevent) 或預防 (Avoid) 上述兩種情況的發生，仍是作業系統 (OS) 所關注的。
* `Thread 是系統處理工作的基本單元。`
* `一個 Process 底下的 Thread 共享資源，如記憶體、Global Variable 等，不同的 Process 則否。`
* `OS 會根據 Thread 的優先權以及使用過的 CPU 時間，切換不同的 Thread。`
* `同一個 Process 內的 Thread 使用相同的 Memory Space，但這些 Thread 各自擁有其 Stack。換句話說，Thread 能透過 reference 存取到相同的 Object，但是 local variable 各自獨立。`
### **Multi-processing v.s. Multi-threading**
#### **Multi-processing**
多個 Process 在執行，彼此有各自的資料空間，若有資料需要共用，必須採用特別的方法來傳遞。
* 相同的工作在比較短的時間內完成
* 由於每個 Process 都需要一些資源來工作，所以 Multi-process 會比 Multi-thread 更**消耗資源**
#### **Multi-threading**
一個 Process 裡有多個執行緒在執行，彼此共用相同的資料空間。
* 相同的時間內完成較多的工作
* 同一Process下的threading之間也能夠擁有彼此獨立的資源
* std::thread in C++
## **Linux**
### **Linux kernel**
一個作業系統中最早被啟動的東西，他包含了所有可以讓硬體與軟體工作的資訊。
### **Critical section**
一個存取共用資源的程式片段，而這些共用資源有無法同時被多個執行緒存取。
`mutual exclusion`：若執行緒在執行「critical section」，其它執行緒都不該進入它們的「critical section」。
### **Mutex v.s. Semaphore**
確保多個執行單元運作並存取資源時，執行結果不會因為執行單元的時間先後的影響而導致錯誤。
::: success
理論上，應該要先跟面試官互動，詢問一下其所謂的差異是指哪個部份 (實作、用途、還是結構？)，以及詢問這個問題時，想要將兩者應用在那邊，對於後續的回答會有所幫助。
:::
* 30秒：最大的差異在於 Mutex 只能由上鎖的 thread 解鎖，而 Semaphore 沒有這個限制，可以由原本的 thread 或是另外一個 thread 解開。另外，Mutex 只能讓一個 thread 進入 critical section，Semaphore 的話則可以設定要讓幾個 thread 進入。這讓實際上使用 Mutex 跟 Semaphore 場景有很大的差別。
* 60秒 (cont.)：舉例而言，Mutex 的兩個特性：一個是只能有持鎖人解鎖、一個是在釋放鎖之前不能退出的特性，讓 Mutex 常使用在 critical section 只能有一個 thread 進入，而且要避免 priority inversion 的時候；Semaphore 也能透過 binary semaphore 做到類似的事情，卻沒有辦法避免 priority inversion 出現。
* 120秒 (cont.)：而 Semaphore 更常是用在同步兩個 thread 或功能上面，因為 Semaphore 實際上使用的是 signal 的 up 與 down，讓 Semaphore 可以變成是一種 notification 的作用，例如 A thread 執行到某個地方時 B thread 才能繼續下去，就可以使用 Semaphore 來達成這樣的作用。
## **Object Oriented Programming**
### **封裝 (Encapsulation)**
將物件內部的資料隱藏起來，只能透過物件本身所提供的介面(interface)取得物件內部屬性或者方法。
### **繼承 (Inheritance)**
在某種情況下，一個類別會有「子類別」。子類別比原本的類別(稱為父類別)要更加具體化，也就是說子類別繼承了父類別。
### **多型 (Polymorphism)**
多個相同名稱的方法，傳入不同的參數，會執行不同的敘述，包含Overloading及Overriding。
* Overloading：相同類別中，定義名稱相同，但是參數個數不同，或是參數型態不同的函式。
* Overriding：覆寫掉父類別中的函式
* Virtual：不強制子類一定要實作，子類不實作的話會以父類的實作為主，子類實作的話會以子類的實作為主
## **Programming**
### **extern**
告訴 compiler 這個變數的存在，但是並不是由source file做宣告，而是由include source file的檔案宣告。
### **Static**
<font color="#0072E3">1. Static出現在variable之前，且該variable宣告在某個function之中</font>
在variable前加上static，則此variable不會在function消失後消失。
<font color="#0072E3">2. Static出現在variable之前，且該variable不是宣告在某個function之中</font>
此處static的用意是讓這樣的global只限定在該檔案內，而不是整個程式中。
<font color="#0072E3">3. Static出現在class的member variable/function之前</font>
此處static的用意是指該variable/function不屬於某個instance，他屬於這個class，所有以此class生成出來的instance都共用這個variable/function。
### **inline**
編譯時便會把函數中的程式直接展開，而不是跳至函數的記憶體位置處理。常用於函數中的程式碼或處理較短，並且常呼叫使用。
### **Macro**
巨集，前置處理器語言定義之內容，如:
```javascript=
#define min(a,b) ((a)<(b)?(a):(b))
```
```javascript=
#define add(a,b) a+b
add(10,5)*5 // = 10 + 5 * 5 = 35
```
### **Volatile**
加在變數前面。是在指示編譯器每次對該變數進行存取時都要「立即更新」，不應該對其做任何最佳化，可以跟const及pointer一起使用。
### **Template**
宣告出通用函式，如
```javascript=
#include <iostream>
template<typename T, typename V>
T fun(T a, V b) {
return a + b;
}
int main(){
int a = 10;
float b = 5.5;
cout << fun(a,b) <<endl; // 15
cout << fun(b,a) <<endl; // 15.5
return 0;
}
```
### **nullptr**
空指標，可以視為指向所有型別的指標
## **演算法**
### **Merge Sort**
```javascript=
void merge(vector<int>& v, int front, int mid, int end) {
vector<int> leftSub(v.begin() + front, v.begin() + mid + 1),
rightSub(v.begin() + mid + 1, v.begin() + end + 1);
leftSub.insert(leftSub.end(), MAX);
rightSub.insert(rightSub.end(), MAX);
int indexL = 0, indexR = 0;
for (int i = front; i <= end; i++) {
if (leftSub.at(indexL) < rightSub.at(indexR)) {
v.at(i) = leftSub.at(indexL);
indexL++;
}
else {
v.at(i) = rightSub.at(indexR);
indexR++;
}
}
}
void mergeSort(vector<int>& v, int front, int end) {
if (front < end) {
int mid = (front + end) / 2;
mergeSort(v, front, mid);
mergeSort(v, mid + 1, end);
merge(v, front, mid, end);
}
}
```
###### tags: `工作`
Sign in with Wallet
Connect another wallet