---
title: 題庫1
description: 幫忙搜集面試題庫，貼在這你
---
# 題庫1
###### tags: `Interview`

## TCP/UDP差別在哪，用途？Socket程式大概怎麼寫？
* `TCP` : 可靠傳輸，通常在每個TCP packet中都有一對序號和確認號。TCP packet傳送者稱自己的位元組流的編號為序號（sequence number），稱接收到對方的位元組流編號為確認號。
* `UDP` : `不`可靠傳輸，`不會`確認資料是否被接收，`不會`重傳遺失的資料，接收的資料可以`不按照`順序，但`UDP`比`TCP`快。對`時間有較高要求`的應用程式通常使用UDP，因為`丟棄封包`比`等待或重傳導致延遲`更可取。

TCP:
    socket -> bind -> listen -> accept -> recv <-> send -> close
UDP:
    socket -> bind -> recvfrom <-> sendto -> close

## Client和Server在做網路通訊時，recv buffer包含了什麼資訊。
* [深入浅出TCP/IP中的send和recv](http://nathanchen.github.io/14554141138605.html)

## Critical section是什麼？
* 操作`shared data`的地方就叫做`crtitcal section`
* 用來保護`shared data` (global)的地方
* 盡量會把`shared data`都放在`critical section`做操作

### Synchronization
* 不會有兩個thread再跑同一段code (有shared data)，保證不會發生`race condition`就叫做`synchronization`

## Mutex程式大概怎麼寫？撰寫時有什麼要注意的地方？

* 考慮
* atomic
* interrupt
* preemption
* SMP or not

pthread_mutex_init(&lock, NULL);
...
pthread_mutex_lock(&lock); // acquire
...
pthread_mutex_unlock(&lock); // release
...
pthread_mutex_destroy(&lock);

spin_lock(&lock);
...
spin_unlock(&lock);

* 避免DeadLock
* 對`共享資源`操作前一定要`獲得`Lock。
* `完成操作`以後一定要`釋放`Lock。
* 儘量`短`時間地佔用Lock。
* 如果有多Lock, 如`獲得順序`是ABC連環扣, `釋放順序`也應該是ABC。
* Thread錯誤返回時應該`釋放`它所獲得的Lock。

## Process 和 thread 差別？如果是不同process，如何保護Critical section？
* `Process`
* 是OS分配資源(CPU time, memory, etc)的最小單位
* 在同個`記憶體空間`有一之多個threads跑在同個`記憶體空間`
* `thread`
* 在底層行程管理和排程將thread和process一視同仁。thread是一群比較特別的process，他們彼此share資源。
* [synchronization](https://medium.com/@fdgkhdkgh/os-synchronization-c7fb8546d674)
* [Thread Synchronization](http://wiki.csie.ncku.edu.tw/embedded/2015q1w9/thread-sync.pdf)
* [Linux的thread和signal](https://medium.com/@petertc/thread-and-signal-in-linux-4f2038d18fd)

## 有沒有寫過shared memory，大概怎麼寫，寫的時候要注意什麼。

## 講講虛擬記憶體和分頁機制。

## 為什麼宣告並初始一個超大陣列會crash，而宣告成static就不會，他們的儲存方式有什麼差別。
* stack 會爆掉
* static 會直接編譯在program上(.data, .bss)，他的program size會大一點
## stack 和 heap差別是什麼。
## function在進行呼叫的時候OS會作什麼事情，組合語言大概怎麼寫。
* 疊一個stack frame

push rbp
mov  rsp, rbp
sub  ...
...
add  ...
mov  rbp, rsp
pop  rbp
ret

## pointer操作、pointer/reference的差別與實作

* [指標(Pointer)與參照(Reference)](https://bluelove1968.pixnet.net/blog/post/222284818)

## Multi-Process / Multi-Thread之間的同步與溝通問題

## Virtual Memory的觀念、Page Fault、LRU演算法

# 白板題：動態擴充的stack和queue實作
* dynamic stack

#include <stdlib.h>
#include <string.h>

struct stack {
    int capacity;
    int top;
    int *buf;
};

struct stack *init_stack(int capacity)
{
    struct stack *s = (struct stack *)malloc(sizeof(struct stack));
    memset(s, '\x00', sizeof(struct stack));
    s->capacity = capacity;
    s->top = -1;
    s->buf = (int *)malloc(sizeof(int) * capacity);

    return s;
}

int pop(struct stack *s) 
{
    if (s->top == -1) {
        return -1; 
    }   
    return s->buf[s->top--];
}

void push(struct stack *s, int data)
{
    if (s->top == s->capacity) {
        s->buf = realloc(s->buf, sizeof(int) * s->capacity * 2);      
        s->capacity = s->capacity * 2;
    }
    s->buf[++s->top] = data;
}

int main()
{
    struct stack *s = init_stack(2);
    push(s, 1); 
    push(s, 2);
    push(s, 3);
    push(s, 4); 
    printf("%d\n", pop(s));
    printf("%d\n", pop(s));
    printf("%d\n", pop(s));
    printf("%d\n", pop(s));
    printf("%d\n", pop(s));
}

* dynamic queue

# 白板題：現在有兩個整數集合要進行差集，怎麼寫？為什麼用這種資料結構？有沒有更快的方法？時間和空間複雜度各是多少？

# 白板題：算樹的高度、節點數量、BFS/DFS

# 白板題：Linked-List相關的題目（排序、插入等）

# 白板題：找出array中重複的數字
* LeetCode 217：Contains Duplicate
* LeetCode 219：Contains Duplicate II
* LeetCode 220：Contains Duplicate III
* LeetCode 287：Find the Duplicate Number

# 白板題：給定一個數列和一個數字，請寫出partition的程式，左邊小於此數字，右邊大於等於此數字，要確保所有特殊數列都能通過測試。
* 86. Partition List
# 白板題：順時鐘旋轉一張 NxN 的灰階圖片，不可以使用額外的二維陣列。

## 行有餘力題
* 解釋對稱式和非對稱式加密，為什麼他們可以運作，如何運作。
* 公鑰跟私鑰的差別跟用途？數位簽署的原理？
* Linux 系統如何儲存使用者密碼。
* 為什麼能確保加密資料不會被字典攻擊。
* 講講SQL injection 跟XSS 攻擊。