# 面試筆記整理

## 一、程式題
### **1. 求 f(n) = 1-2+3-4+5......+99-100 ?**

// python解法 //
n = 1
sum = 0

while sum < 101:
    temp = n % 2 //用來判斷n是基數還是偶數
    if temp == 0:
        sum = sum - n
    else:
        sum = sum + n
    n = n + 1

print(sum)

### 2. 計算bit1個數

// 方法一 //

int bit_count(unsigned int n){
    int count = 0;
    while(n){
        count++;
        n &= (n-1);        
    }
    return count;
}

// 方法二 //

unsigned char bit_count(int sample){
    unsigned char count = 0;// bit1 number
    unsigned int bit1FL = 0x01;// bit1 flag 
    
    // calculate bit1 number
    while (bit1FL){
        if (sample & bigt1FL)
            count++;
        
        bit1FL = bit1FL << 1;
    }
    return count;
}

// 方法三 //

int bit_count(int n){
    int cnt = 0;
    while(n){
        if (n % 2 == 1){
            cnt++;
        }
        n /= 2;        
    }
}

### 3. 給予10個任意整數，輸出其最小值、最大值、平均值

// c++解法 //
int Max = a[0], Min = a[0], Avg = 0; 

for(int i = 0 ; i < 10 ; i++){
        if(Min > a[i])
            Min = a[i];
        if(Max < a[i])
            Max = a[i];
        Avg += a[i];
}
cout << Min << Max << static_cast<float>(Avg)/10 << endl;

### 4. 寫出一個字串拷貝程式： void StrCpy(char* dst , char* src) ;

// array version //
void strcpy(char *dst, char *src){  
    int i = 0;
    while((dst[i] = src[i]) != '\0'){
        i++;
    }
}

// pointer version //
void strcpy(char *s, char *t){  
   while((*s = *t) != '\0') {
       s++;
       t++;
   }
}

### 5. 判斷linked list中有無cycle

bool hascycle(struct ListNode *head){
    struct ListNode *fast = head;
    struct ListNode *slow = head;
    
    while(fast != NULL && fast->next){
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return true;
    }
    retuen false;
}

### 補充：求中位數

mid = left + (right - left) / 2

prove：

You have left < right by definition.

As a consequence, right - left > 0, 
and furthermore left + (right - left) = right
(follows from basic algebra).

And consequently left + (right - left) / 2 <= right. 
So no overflow can happen since every step of the operation 
is bounded by the value of right.

## 二、作業系統相關

### 1. stack & heap

**(1) stack**：用於靜態記憶體配置，操作特色是 LIFO。
由編譯器自動分配釋放 ，存放函數參數和local variables等。

優點：

1. 存取快速
2. 無須明確取消(釋放)分配變數
3. 空間由CPU管理，memory不會變成碎片

缺點：

1. local variable only
2. 大小被限制（取決OS）
3. 變數無法調整大小（須用resize）

**(2) heap**：用於動態記憶體配置，有別於stack，heap的大小在程式的運行中不固定，因此我們可以自由地請求或釋放heap的記憶體。
一般由程序員分配釋放， 若程序員不釋放，程序結束時可能由OS回收。

優點：

1. 變數可以被全域訪問
2. 記憶體大小沒有限制
3. 可以使用realloc()調整變數

缺點：

1. 存取速度(相對)較慢
2. 會有記憶體碎片產生（無法保證空間被有效利用）
3. 必須管理記憶體（分配和釋放變數），否則會發生記憶體洩漏/流失

### 2. process & thread 差異

process是一個單一應用程式或程式，而thread是該應用程式的子程序。每個process在記憶體中都有自己的地址空間，threads則可以共享地址空間(address space)。

(1) process：位在記憶體中正在被執行的程式碼，process組成如下：

code segment->將指令讀到記憶體中，等待被cpu擷取並執行
data section->全域變數
stack->區域變數以及函數的參數
heap->動態配置記憶體的變數或是類(classes)

(2) threads：又稱Lightweight process，是使用cpu的最小單位。
同個process裡的threads可以共享記憶體空間

### 3. Threads哪些是共享的

同process中，threads共用以下內容：

* code section
* data section
* OS resource(eg. open file and signals)

但以下各自獨立：

* stack
* register set
* thread ID
* program counter

### 4. 什麼是multithread

一個process內有多個thread在執行，彼此共用相同的資料空間。同一個process下的所有thread會分享該process的所有資源，此外各個threads彼此間也可以擁有自己的私有資源。

#### multithreading的好處：
multithreading能夠在閒置或等待時，透過不斷互相切換，來節省執行時間。
(1)responsiveness：即使program的一部分被block住，仍可運行，來節省執行時間。
(2)resource sharing：不同threads可利用相同的記憶體位置來共享資源

### 5. Process的溝通方式

process間的溝通須透過IPC(interprocess communication)，而IPC有兩種模式設計：

(1) share memory(共享記憶體)：
process間共享部分記憶體(shared variables)，透過存取記憶體達到彼此溝通、交換資訊的目的。share memory是用read跟write資料來完成資訊交換。

(2) message passing(訊息傳遞)：
process間會建立連接通道(communication link)來溝通，非借助共享變數，過程是：

* 建立Communication link
* 互傳訊息(Message)
* 傳輸完畢，中斷連接通道(release link)

建立連接通道時，會分成傳送方與接收方(send & receive)，而通訊的方式也分成兩種：直接傳訊息(Direct)和間接傳遞(Indirect)

### 6. Message passing的實作方式

### 7. kernel space 和 user space 寫程式的差異

### 8. 解釋什麼是Page Fault

### synchronization

同時訪問資料可能導致資料不一致的情形。保持資料的一致性需要一些機制，來確保合作的processes有序的執行。

### 9. Mutex, Semaphore 和 spinlock 的差異

* 最大的差異在於 Mutex 只能由上鎖的 thread 解鎖，而 Semaphore 沒有這個限制，可以由原本的 thread 或是另外一個 thread 解開。
* 另外，Mutex 只能讓一個 thread 進入 critical section，Semaphore 的話則可以設定要讓幾個 thread 進入。
------------
(1)mutex：
* 一個只能容納一個人的房間，有一把鑰匙
* 只有一個人和一把鑰匙，拿了鑰匙可以進房間
* A mutex is really a semaphore with value 1

(2)semaphore：
* 一個可以容納N個人的房間，沒有鑰匙
* 如果房間沒滿，人就可以進去
* 如果房間滿了，就要等待有人出來
* N=1時，為binary semaphore，用來限制對某一個資源的同時訪問

(3)spin lock(自旋鎖)：
* 用來保護critical section，如果執行緒沒有獲取鎖，則會進入迴圈直到獲得上鎖的資格
* Spinlock 是 busy waiting，Semaphore 是 sleep

#### 補充
**blocking(阻塞) vs non-blocking(非阻塞)**

1.blocking：在作業系統中，當系統等待操作完成，接著才允許程式碼繼續執行，用戶在等待期間無法執行其他任務。

2.non-blocking：則是允許執行緒繼續執行，無需等待該操作完成，不會影響其他進程(process)。

### 10. 說明virtual memory

虛擬記憶體(virtual memory)會讓應用程式認為其擁有連續可用的記憶體空間(連續完整的位址空間)。而實際上，其被分隔成多個實體記憶體碎片，還有部分暫時儲存在外部磁碟記憶體上，需要時才進行資料交換。

優點：

1. 允許程式大小大於實體記憶體大小的情況，程式然可以執行
2. 是OS的負擔，programmer無負擔
3. 讓記憶體各個"小空間"皆有機會被利用到，記憶體使用度上升
4. 提高multiprogramming degree，提升cpu使用度
5. 較少I/O load或是要把process搬上搬下

實作方式：demand paging & demand segmentation

### 11. 解釋什麼是socket

### 12. Big/Little endian

## 三、資料結構相關

### 1. array 和 linked list 差異

#### (1) Array：

優點：

1. 對 Array 的資料做存取只需要 O(1) 的時間
2. 比 Linked list 為節省記憶體空間，因為 linked list 需要多一個指標 pointer 來記錄下一個節點的記憶體位置。

缺點：

1. 新增/刪除資料降麻煩，需花費O(n)的時間複雜度
2. 若時常在新增資料，要時常調整陣列的大小，會花費 O(n) 的時間在搬動資料

> 適用時機：
>
> 1. 快速存取資料時
> 2. 已知資料的數量，如此便不用經常改變陣列大小
> 3. 要求記憶體空間的使用越少越好。

#### (2) Linked list:

優點：

1. 插入/刪除資料較Array簡單，只需要對新增/刪除的相關節點調整指標即可
2. linked list 的資料數量能動態的向記憶體要空間/釋放空間，不像 Array 會有"重新定義陣列大小"的問題

缺點：

1. 因為 linked list 不能直接透過索引值找到某節點(ex: 像陣列可以透過 array[index] 找到要的元素)，若要找到特定節點，需要從頭開始找起，搜尋的時間複雜度為 O(N)。
2. 需要額外的記憶體空間來儲存指標。

> 適用時機：
> 1. 無法預期資料數量或頻繁變動資料數量時。
> 2. 需要頻繁地新增/刪除資料時。
> 3. 不需要快速查詢資料。

#### (3) Tree

### Hash Table(雜湊表)

又稱為哈希表，是一種透過鍵值(key)找到資料在記憶體位置的儲存方式。將數據透過雜湊函式（hash function）映射（map）到其在表中的對應位置後，可同步降低操作時的「空間複雜度」與「時間複雜度」。

### 2. queue vs stack

### 3. Sorting algorithm

// Insertion sort

void insertion_sort(int *arr, int size){
    if(!arr)
        return;
    
    for(int i = 0; i < size; i++){
        int target = arr[i];
        int j = i-1;//前一個數字
        while(arr[j] < target && j >= 0){
            arr[j+1] = arr[j];
            j--; 
        }
        //find the proper place and place it
        arr[j+1] = target;   
    }
}

//Selection sort

void selection_sort(int *arr, int size){
    if(!arr)
        return;
    
    for(int i = 0; i < size-1; i++){
        int min_pos = i;
        for(int j = i+1; j < size; j++){
            if(arr[j] < arr[min_pos]){
                min_pos = j;
            }
        }
        // swap
        int temp = arr[i];
        arr[i] = arr[min_pos];
        arr[min_pos] = temp;
    }
}

### 4. LRU cache(LRU演算法)

## 四、物件導向（OOP）和 C/C++觀念

### 1. 解釋封裝、繼承、多型的概念

### 2. 解釋virtual function

### 3. override & overload

### 4. lvalue & rvalue

### 5. global & local

### 6. struct vs union 差異
1. 在儲存多個成員訊息時，編譯器會自動給struct的成員分配儲存空間，struct可以儲存多個成員訊息。而union每個成員會共用同一個儲存空間，只能儲存最後一個成員訊息。
2. 都是由多個不同數據類型的成員組成，但在任何同一時刻，union只存放一個被先選中的成員，而struct的所有成員都存在。
3. 對於union的不同成員賦值，將會對其他成員重寫，原來成員的值就不存在了；而對於struct的不同成員賦值，是互不影響的。

### 7.extern和static的差異

1. extern：不同文件中想要互相使用的變量。當我們在某一個文件中定義了一個global variable，使用extern修飾變數即可在多個檔案中使用該變數。
1. static：包含同一個include檔的文件間想要互相使用的變量，但又不希望其他文件的操作改變本文件的變量。static 的意義就是 “被修飾的東西，會從程式一開始執行就存在，且不會因為離開 scope 就消失，會一直存在到程式結束”。

* static 出現在哪裏及用什麼定義如下:
static 出現在 variable 之前，且該 variable 宣告在某個 function 之中 (C/C++)
static 出現在 variable 之前，且該 variable 並不是宣告在某個 function 中(C/C++)
static 出現在 class 的 member variable 之前 (C++ only)
static 出現在 class 的 member function 之前 (C++ only)

#### static的在C/C++中的三種用法
1. 在一個block內的函式，用static修飾的變數會在函式呼叫期間仍維持其數值。表示該變數離開作用域(scope)後記憶體還保留著，直到程式結束為止。
2. 在一個block內但在函數外的變數，即static放在全域變數之前。該變數可以被同個block內的函數存取，在其他block中的函數不能存取。(表示該c/cpp檔無法被其他c/cpp檔用extern來使用。)
> 因為在別的檔案extern該變數之後，就可以在別的檔案修改此變數。所以static放在全域變數之前是預防其他人修改你的變數，也有保護變數的作用。
3. 在一個block內宣告為static的函數，只可以被同一block內的其他函數呼叫，有點像class裡的private function的含意。