# 面試筆記
## 職位共通基本資料
### OS
- #### Stack, Heap, Data section 分別存什麼？
- #### Process 和 thread差別？
- Process是載入記憶體的program，每個program有其獨立的CPU、I/O、file system等資源；process為thread的容器，一個process乘載著多個thread。
- Thread是執行緒(可視為CPU最小執行單元)，一個process中的thread共享著上述CPU、I/O、file system等資源。
- #### deadlock/starvation?
- #### 什麼是deadlock？
- 容易在multi-process的情況下發生。
- 兩個以上的運算單元(進程/process/thread)都在等待對方停止執行，來取得自己需要的系統資源，但沒有一方提前停止。
- 死結需同時滿足四個條件：
- 禁止搶占（no preemption）：系統資源不能被強制從一個行程中登出。
- 避免方法: 只要握有一些資源，但得不到其他的，就先釋出，並重新申請。
- 持有和等待（hold and wait）：一個行程可以在等待時持有系統資源。
- 避免方法: 保證在要求一項資源時，如果無法一次得到所有資源時，不可以持有其他資源。
- 互斥（mutual exclusion）：資源只能同時分配給一個行程，無法多個行程共享。
- 避免方法: 同一份資源只能被單一執行緒所訪問。
- 循環等待（circular waiting）：一系列行程互相持有其他行程所需要的資源。
- 避免方法: 強制安排線性，盡量避免circular條件達成。
- #### 什麼是starvation?
- ?????????
- Race Condition/ Critical Section?
- Race Condition : 兩個以上的threads/processes對同一個變數做讀寫，可能因為還沒寫回就讀取導致與原先期待的結果不同的問題。通常透過以下限制避免:
- 互斥性(mutex) : 一次僅一個thread/process進入critial section。
- 可進行性(progress):不執行的thread/process不得阻礙其他的進入critical section.
- 有限等待(bound waiting): 總共有n個thread/process想進入critical section時，最多只要等n-1次就可以進入。
- Critical Section : 即一段程式，其中包含了對共享資源的訪問。
- Avoidance的演算法分為兩種：
- Resource-Allocation Graph(RAG)：如果resource type只有一個instance
- Banker’s algorithm：如果resource type有多個instance
- #### 什麼是mutex?
- #### 什麼是sephamore?
- #### 什麼是page fault?
- #### System call（系統呼叫）
- 是指由操作系統核心所提供的服務。這些服務包括檔案操作、網路操作、設備操作等，可以讓應用程式可以存取作業系統的資源。不同的作業系統提供的系統呼叫可能有所不同，以下是一些常見的系統呼叫：
* 檔案操作：open, read, write, close, lseek, mmap, stat, fstat, lstat 等。**(打開、讀寫文件)**
* 進程操作：fork, exec, wait, waitpid, exit, getpid, getppid 等。 **C裡面malloc在linux會用到 brk和mmap在配置進程內存。**
* 訊號操作：kill, signal, sigaction, sigprocmask 等。**(發送訊號close一個process)**
* 網路操作：socket, bind, listen, accept, connect, send, recv 等。**(不同電腦建立連接、傳輸資料、關閉傳輸)**
* 設備操作：ioctl, open, read, write, close, select 等。**(設定設備參數、讀取設備資訊等)**
### 網路
- #### UDP/TCP差別？
### 資料結構
- #### stack/queue/heap差別？
- stack: 先進後出(FILO)，從top取值。像recursion就是用stack儲存
- queue: 先進先出(FIFO)，從front取值。
- heap: 父節點永遠小於等於子節點，如果是maxheap就相反。求最大最小值容易。用在動態分配的儲存(new in C++/malloc in C)。
```
char *str;
/* 最初的内存分配 */
str = (char *) malloc(15);
/* 重新分配内存 */
str = (char *) realloc(str, 25);
```
- #### linked list/ array優缺點？
- linked list:
- 優：
- 動態配置記憶體，不需要一開始就決定大小。
- 插入刪除方便$O(1)$。(但需要先走到新增刪除要發生的位置，最差$O(n)$)
- 缺：
- 無法random access。(搜尋上很不方便$O(n)$)
- 除了本身儲存的資料外，需要額外的記憶體儲存指下下一個node的指標。
- array:
- 優：
- 可以random access。($O(1)$)
- 搜尋方便(binary search)。
- 缺：
- 需要一開始就配置好他的大小。
- 新增刪除都需要很長時間。
### 演算法
- #### sorting的時間複雜度與best/worse case？
- #### 寫一種sorting:
### C
[快速看一遍](https://mycollegenotebook.medium.com/c-%E8%AA%9E%E8%A8%80%E7%B5%B1%E6%95%B4%E7%AD%86%E8%A8%98-f97326e2323c)
- 基礎I/O:
- Input:
```
int num;
scanf("%d",&num);`
```
- Output:
```
int num = 10;
printf("this apple costs %d dollars.",num);`
```
- 資料型別大小：
- float
- [小數怎算](https://hackmd.io/@A7mW1DtZSiuuCn3Bh0KIjQ/B1S5MvGsw)
- [如何表示float](https://dotblogs.com.tw/daniel/2018/11/10/161148)
- 
- sign: 1位
- exponent: 8位
- mantissa: 23位
- 精準度: $2^{23}$~ $10^{3^{2.3}}$ ~$10^{6.9}$: 保證6位(6~7位)
- 表示值：$正數最大:10^{38}$,正數最小$10^{-38}$
- double
- sign: 1位
- exponent: 11位
- mantissa: 52位
- 精準度: $2^{52}$ ~ $10^{3^{5.2}}$ ~ $10^{15.6}$: 保證15位(15~16位)
- 表示值: $正數最大:10^{308}$,正數最小$10^{-308}$
- #### Little Endian/ Big Endian
```
#include <stdio.h>
typedef union {
unsigned long l;
unsigned char c[4];
} EndianTest;
int main() {
EndianTest et;
et.l = 0x12345678;
printf("本系統位元組順序為：");
if (et.c[0] == 0x78 && et.c[1] == 0x56 && et.c[2] == 0x34 && et.c[3] == 0x12) {
printf("Little Endiann");
} else if (et.c[0] == 0x12 && et.c[1] == 0x34 && et.c[2] == 0x56 && et.c[3] == 0x78) {
printf("Big Endian");
} else {
printf("Unknown Endian");
}
printf("0x%lX 在記憶體中的儲存順序：n", et.l);
for (int i = 0; i < 4; i++) {
printf("%p : 0x%02Xn", &et.c[i], et.c[i]);
}
return 0;
}
```
- #### bitwise operation
- [SET,CLEAR,CHECK,FLIP BITS](http://j890111tw.blogspot.com/2019/10/bitwise-operation.html)
- #### 確認是否為2的次方
- 2的倍數共通點：**n & (n-1) = 0**
- ex. 2 & 1 = 10 & 01 = 00
- #### 一個array裡面除了某一個數字以外，其他數字都出現2次，請找尋出現一次的數字？
- **xor : 兩個bit不同才回傳1，相同回傳0**
- 1100 xor 1100 = 0000
- 1100 xor 1100 xor 1001 = 0000 xor 1001 = 1001
- **以0000去xor所有數字，最後ans = 只出現一次的數字**
- #### 找尋第n個bit的數字:
- **& mask with only bit n = 1**
- ex. 0001 1001 , get bit 5:
- ((0001 1001) & (0001 0000)) >> 4 = (0001 0000) >> 4 = 1
- ((op_bits) & $2^{n-1}$) >> (n-1) = (opbits >> (n-1)) & 1
- #### 確認是偶數或奇數:
- 奇數共通點: 第一個bit($2^0$)為1
- **return n & 1 ==1 ? odd result : even result;**
- ex. 0011 & 0001 = 0001
- #### Basic Operation
- #### 重要須知：set、clear、flip bits時，默認最右邊最低位bit的索引編號為0；但是在講取得第5個bit的值時，是假設右邊最低位bit為第1個bit；須明辨！
- setbit(int x, int bitN): 用or
```
int setbit(int x, int bitN)
{
x = (x | 1<<bitN);
return x;
}
```
- clearbit(int x, int bitN): 用 not 跟 and
```
int clearbit(int x, int bitN)
{
x &= ~(1<<bitN);
return x;
}
```
- **flipbit(int x, int n)/reversebit: 把bit翻成相反值: 用xor**
```
int flipbit(int x, int n)
{
x ^= (1<<bitN);
return x;
}
```
- **getbit(int x, int n) : 用 and: 注意index從0**
```
int flipbit(int x, int n)
{
x = (x >>(bitN)) & 1;
return x;
}
```
- #### string operation
- 宣告：就算不設陣列大小也是可以宣告字串
```
char str1[ 6 ] = "hello";
char str2[] = "starbucks"; // size 10
//一般的陣列宣告也適用，只是要注意會多一項‘\0’
char str3[ 6 ] = {'h', 'e', 'l', 'l', '0', '\0'};
char str4[] = {'s', 't', 'a', 'r', 'b', 'u', 'c', 'k', 's','\0'};
```
- 輸入: 字串儲存方式本身即為一個char陣列，輸入不須用&指位址，本身就是位址。
`scanf("%s %d", name, &age);`
- scanf: 遇到空格就結束
- gets: 遇到換行才結束(但用法不安全，即不確定多少個字元才會結束)
- fgets: 指定最多幾個char結束，輸入的字串會自動加入換行符號
`fgets(字串開頭位址s,輸入字元數20,輸入方式stdin)`
- sscanf: 讀取字串，並把字串中的值依照要求個別放入不同變數
```
char weather[100] = "cloudy 20";
int tp;
char s[100];
sscanf(weather,"%s %d",s,&d);
printf("the day is %s, temperature is %d.\n",s,d);
```
- 輸出：
- printf
- fputs
`fputs(字串開頭位置s,輸出方式stdout)`
- sprintf: 整合輸出到一個字串(含輸出+整合)
```
char weather[100];
int tp = 20;
char* s = "cloudy";
sprintf(weather,"the temperature is %d, the day is %s.",tp,s);
printf("the weather is %s.\n",weather);
```
- <string.h>
- strlen(char* s) : 得到字串長度，不計終止符號'\0'
```
#include <stdio.h>
int strlen_implement(char * s)
{
int count = 0;
while(*(s+count)!='\0')
{
count++;
}
return count;
}
```
- strcmp(char* s1, char* s2):從字串的開始逐一比對兩字串的字元是否相同
```
#include <stdio.h>
#include <string.h>
int strcmp_implement(char* s1, char* s2)
{
while(*s1==*s2)
{
if (*s1 == '\0' || *s2 == '\0')
break;
s1++;
s2++;
}
return (*s1-*s2);
}
```
- strncmp(char* s1, char* s2, int n):從字串的開始逐一比對，兩字串**前n個字元**是否相同
```
#include <stdio.h>
#include <string.h>
int strncmp_implement(char* s1, char* s2, int n)
{
int count = 0;
while(*s1==*s2 && count < n)
{
if (*s1 == '\0' || *s2 == '\0')
break;
s1++;
s2++;
count++;
}
return (*s1-*s2);
}
```
- strcat(char* dest, char* src):把source字串加在目標字串上
```
#include <stdio.h>
#include <string.h>
void strcat_implement(char* s1, char* s2)
{
//s1,s2 are copy of address
//change position didn't influence the pointer in the main fucntion
char* tmp = s1;
while (*tmp!='\0')
{
tmp++;
}
while (*s2 != '\0')
{
*tmp = *s2;
tmp++;
s2++;
}
*tmp = '\0';
}
```
- strncat(char* s1, char* s2, int n): 把s2前n個character加到s1上。
```
#include <stdio.h>
#include <string.h>
void strcat_implement(char* s1, char* s2, int n)
{
int count = 0;
char* tmp = s1;
while (*tmp!='\0')
{
tmp++;
}
while (*s2 != '\0' && n > count)
{
*tmp = *s2;
tmp++;
s2++;
count++;
}
*tmp = '\0';
}
```
- strcpy(char* s1, char* s2):把s2複製到s1上
```
#include <stdio.h>
#include <string.h>
void strcpy(char* s1, char* s2)
{
while(*s2!='\0')
{
*s1 = *s2;
s1++;
s2++;
}
*s1 = '\0';
return;
}
```
- strncpy(char* s1, char* s2, int n):把s2前n個字元複製到s1上
```
#include <stdio.h>
#include <string.h>
void strncpy(char* s1, char* s2, int n)
{
int count = 0;
while(*s2!='\0' && count < n)
{
*s1 = *s2;
s1++;
s2++;
count++;
}
*s1 = '\0';
return;
}
```
- 字串數字轉換： `include <stdlib.h>`
- atoi(char* s) : 字串轉成int
- atof(char* s) : 字串轉成float
- atol(char* s) : 字串轉成long
- #### structures
- 自訂義資料型態，可儲存多種資料型態
```
struct student
{
char name[30];
int age;
};
//ver 1 : initialize
struct student s1 ;
struct student s2 ;
//ver 2 : initialize
s1 = (struct student) {"Aliee",25};
//ver 3 : initialize
struct student s2 = {"Kevin",30};
```
- **typedef** : 減輕需要很長的宣告與使用
```
typedef struct
{
char name[30];
int age;
}student;
//ver 1 : initialize
student s1 ;
student s2 ;
//ver 2 : initialize
s1 = (student) {"Aliee",25};
//ver 3 : initialize
student s2 = {"Kevin",30};
```
- struct pointer:
```
typedef struct
{
char name[20];
int age;
}student;
void show(student* s)
{
prinft("The student %s is %d years old.\n",s->name,s->age);
}
student s1 = {"Willy",28};
student s2 = {"Lisa",27};
show(&s1);
show(&s2)
```
- #### extern 和 static?
- extern: 引用外部的全域變數；ex.在a.cpp定義的全域變數，可在b.cpp當中透過extern方法來引用。(但引用的變數不可為static。)
- static: 變數存在的時間與主程式一樣長，但作用域不變，ex.寫在function內的變數仍只能在該function中使用。如果用在類別當中的變數或函式上，該static的變數和函式不屬於任何一個物件，為該類別共用的。
- #### const(還有分前後順序，請參考新思的考古)
- #### ????????????????
- #### pointer operation
- [簡單說明](https://mycollegenotebook.medium.com/c%E8%AA%9E%E8%A8%80%E7%AD%86%E8%A8%98-%E6%8C%87%E6%A8%99-pointers-d28edcdd6283)
- btw, nullptr僅C++有
- 記憶體位址(16進制)：0xFFFFFFFF : $2^{32} bytes=4GB$
- **較大重點:**
- 對於陣列 a = {1,2,3,4,5};
- **&a : 指的是整個陣列的位址**， &a+1 會走到下一個相鄰未定義的記憶體區塊
- **a : 指的是陣列的開頭位址**， a+1 會走到陣列裡下一個位址，在這裡即下一個整數。
```
int a = {1,2,3,4,5};
int* ptr = (int*)(&a + 1);
printf("ptr-1 = %d",*(ptr-1)); //output: 4
int b = {1,2,3,4,5};
int p = (int*) (b+1);
printf("p-1 = %d",*(p-1)); //output: 1
```
- #### function/ array of function pointer
- function pointer : 指向函式的pointer，**指標處一定要括號**
```
//宣告函式pointer
void checkAccess(int num){return num >= 1;};
void (*funcptr) (int); //output_t (*pointer_name) (input_t)
funcptr = checkAccess; // assign函式指標
int n = 0;
printf("enter the access number=>\n");
scanf("%d",&n);
funcptr(n); //實際使用function
```
- array function pointer : 幫助減少if-else等流程控制
```
#include <stdio.h>
int add(int num1, int num2); //宣告加法函式
int subtract(int num1, int num2); //宣告減法函式
int multiply(int num1, int num2); //宣告乘法函式
int divide(int num1, int num2); //宣告除法函式
//宣告函式指標陣列
int (*op[4]) (int,int);
op[0] = add; // assign函式指標
op[1] = subtract; // assign函式指標
op[2] = multiply; // assign函式指標
op[3] = divide; // assign函式指標
int choice = 3;
op[choice](0,1); //實際使用function
```
- #### array reverse || string reverse
- 頭尾交換，直到中間。
```
void swap(int* a1, int* a2)
{
int tmp = *a1;
*a1 = *a2;
*a2 = tmp;
return;
}
void reverse_arr(int* a, int m)
{
if (m<=1)
return;
for(int i = 0; i < m/2 ; i++)
{
swap(a[i],a[m-i-1]);
}
return;
}
```
- #### linked list
- linked list insert
```
struct ListNode
{
int val;
ListNode* next;
ListNode(int x): val(x), next(NULL){};
};
class LinkedList
{
public:
void insert(ListNode* prev, ListNode* add)
{
ListNode* nxt = prev->next;
prev->next = add;
add->next = nxt;
}
void insert(ListNode* prev, int v)
{
ListNode* nxt = prev->next;
prev->next = new ListNode(v);
prev->next->next = nxt;
}
private:
ListNode* head = NULL;
};
```
- linked list 實作 queue
```
struct ListNode
{
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL){};
};
class Queue
{
public:
bool isEmpty()
{
if (head==NULL)
return true;
else
return false;
}
int front()
{
if (!isEmpty())
return head->val;
else
return NULL;
}
void push(int x)
{
if (isEmpty())
{
head = end = new ListNode(x);
}
else
{
end->next = new ListNode(x);
end = end->next;
}
return;
}
int back()
{
if (!isEmpty())
{
return end->val;
}
else
{
return NULL;
}
}
void pop()
{
if (!isEmpty())
{
ListNode* nxt = head->next;
delete head;
head = nxt;
}
return;
}
private:
ListNode* head = NULL;
ListNode* end = NULL;
};
```
- #### shuffle the array
```
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void shuffle(int *array, size_t n){
//亂數前置
srand(time(NULL));
if (n > 1){
size_t i;
for (int i = n-1; i >= 0; i--){
size_t j = rand() % (i+1);
int t = array[j];
array[j] = array[i];
array[i] = t;
}
}
}
```
- #### compile / linker / runtime error?
- **compiler error**: 編譯時發生的錯誤，可能是像是語法錯誤造成的
- **linker error**: 要把不同的object file連結在一起時發生的問題，可以確認是否有正確include其他object file。(或是不同object file裡面使用到同名的全局變量也可能造成這個問題，static可解決:static僅在當前文件可見->也是為什麼不能用在extern的原因。)
- **runtime error**: 在執行時才發生的錯誤，例如除法分母為0的情況
### C++:
- #### OOP概念
- 封裝
- 把物件的屬性跟方法包在一起，在內部的屬性跟方法定義完後，外部只能透過物件提供的介面去進行操作。可以避免外部的不當操作，在使用上也可以變得比較簡單，不需要去在意內部的實作。
- 繼承
- 讓程式的重用性高，可以把一些共通性很高的類別定義在同個父類別，子類別可以繼承父類別共通的屬性，再根據子類別的一些特異性去定義自己的屬性與方法。
- 多型
- 包含overload(靜態)跟override(動態)，同名的function根據接收者不同可以對同一事件做出不同回應。
- overload是指同樣function名稱透過輸入數量或類型不同，function會做不同的事情。
- override指的是子類別，在有宣告virtual的情況下，父類別同名的function可以直接改寫父類別的function，但是父類別跟子類別function的參數必須相同。
- overwrite指的是將父類別的function隱藏起來，(覆寫掉父類別的function)，父類別跟子類別同名function的參數可以相同也可以不同。
- virtual function也是多型的一個實踐，可以做dynamic binding，實際執行上根據接收者是誰再來決定實作內容。實際上的例子 ex.父類別跟子類別都有同一個function，在父類別的function加上virtual，在外部做運用的時候，只要透過父類別的pointer來指父類別跟子類別的物件，就能根據他們實際上的類別來實踐這個同名的function。
-
- #### 什麼是virtual function？
- 程式一般是static binding，也就說在compile time就需要去定義程式的定義跟他的實作；而virtual function讓程式可以做dynamic binding，也就是說在實際執行時，再看接收者決定要執行什麼內容，相較起來更有彈性。
- 是C++多型中override的實踐。
- abstract class 抽象類別 : 該類別至少有一個pure virtual function。(即為了子類別存在)。
- pure virtual function:
`virtual void show() = 0;`
- #### overload/overwrite/override的不同？
- overload: 同名function，參數數量不同、類別不同、順序不同，function會根據參數來做出不同回應。
- overwrite: 父類別與子類別有同名的function，會把父類別的function隱藏起來，同名的function參數相同與不同都可以。
- override: 父類別與子類別有同名function且參數相同，在父類別宣告virtual的情況下，子類別可以改寫父類別的function(宣告function是virtual的情況下，程式會根據實際上接收者決定要執行什麼)。
- #### union/struct/class sizeof()計算與對齊方法？
- struct vs class:
- class預設成員為private，struct預設成員為pulic。
- class有繼承、多型等應用，但struct沒有。
- union vs struct:
- union 和 struct 都可以儲存不同型態。
- union 同時只有一個類別的值可以儲存。union大小為最長的那個型態且可以整除該union最長基本儲存型態；可以節省記憶體空間;而struct則是可以同時儲存多項，故比較佔記憶體。
- union 宣告上基本上長的和struct相同，只差把關鍵字換成union:
```
union student
{
int x;
char hi;
float height;
};
```
- sizeof()/對齊問題：
- union: 該union內**最長的數據長度**，但要**對齊最長基本類型長度**
```
union u
{
double a; //最長數據=8,同時為最長基本類型->不用對齊
int b;
};
union u2
{
char a[13]; //最長的數據=13
int b; //最長的基本類型長度4
};
union u3
{
char a[13]; //最長的數據=13
char b; //最長的基本類型長度1->不用對齊
};
printf("sizeof(u) = %d.\n",sizeof(u)); // 8
printf("sizeof(u) = %d.\n",sizeof(u2)); // 16
printf("sizeof(u) = %d.\n",sizeof(u3)); // 13
```
- struct: 以struct內**下一個類別的長度來對齊**，最後**總長度要對整個struct內最長的基礎類型補齊**。
```
structA
{
inta; // 4
shortb; // (4) + 2 = 6 下一元素爲 int，需對齊爲 4 的倍數， 6 + (2) = 8
intc; // (8) + 4 = (12)
char d; // (12) + 1 = 13， 需補齊爲 4 的倍數，13 + (3) = 16
};
structB
{
inta; // 4
shortb; // (4) + 2 = 6，下一成員爲 char 類型，不考慮對齊
char c; // (6) + 1 = 7，下一成員爲 int 類型，需對其爲 4 的倍數，7 + (1) = 8
intd; // (8) + 4 = 12，已是 4 的倍數
}
union C //24字節:20對齊8
{
int a[5]; //20
short b; // 2
double c; //8
char p2; //1
};
struct D {
int n; // 4字節 +(4):union C 最長基礎類型8
C c; // 4 + (4) +24字節
char c[10]; // 4 + (4) + 24 +10 + (6) = 48字節
};
```
- 可以用**pragma back(size)** 設定編譯時對齊的長度，C++基本上取對界大小跟最長成員長度兩者中**較小**的那個。
- #### memory leak?
- 發生在還沒釋放一段記憶體時，就失去對那段記憶體的控制，造成長期的記憶體浪費。
- 例如: 用new的方式建立一個物件，但指向他的pointer後來拿去指別人，在指向別人前沒有做delete的動作，所以儲存這個物件的記憶體沒有被釋放，但又無法觸及他。
- #### call by value / call by reference(僅C++有reference哦，C僅call by address)?
- call by value: 直接複製一份值傳進去
- call by reference: 傳入參數的別名(參考)，不用複製一份value進去，更改這個參考的值會直接影響到外部原本的值。
- #### MACRO vs inline?
- MACRO: 純粹的文字替換，不限型態。
```
#define MAX(a,b) (a+b) > (b+a)
#define SQUARE(a,b) a*3+b
int c = 1, d = 2;
cout << MAX(c++,--d); //執行時: cout << (c++ + --d) + (--d + c++);
SQUARE(c+d,c);//c+d*3+c :無括號
```
- inline: function簡單的時候，用inline讓編譯時，呼叫function直接把function內容展開，不用跳轉到function內容定義的地方；加速編譯。必須定義function型態。
```
inline int MAX(a,b){(a+b)>(b+a);}
```
### Git Flow
[Git Flow 介紹](https://gitbook.tw/chapters/gitflow/why-need-git-flow)
- 過往通常使用到的功能:
- 新增一個repo
```
cd target_folder
git init
```
- 加入索引，讓git追蹤檔案
```
git add file_name
```
- 根據目前的index.html提交一個新的版本
```
git commit -m 版本資訊
```
- 查看目前是否有檔案還沒有追蹤，或當前版本是否還沒提交
```
git status
```
- 推送版本更新到遠端
```
git push origin branch_name
```
- 以遠端更新本地版本
```
git pull
```
- 下載遠端版本至本地
```
git clone <url>
```
### Linux 指令
- #### 關機/重新開機 **(權限root)**
- shutdown: 搭配不同參數，可以是關機也可以是重開
`shutdown -h time(20:30,now,+10)` : 關機(10單位mins)
`shutdown -r time(20:30,now,+10)`: 重新開機
- reboot: 重新開機
`reboot`
- #### 檔案與目錄管理
- ls : 列出檔案/目錄，根據參數可以改變排序方式或顯示資訊
`ls path -a`: 顯示隱藏檔案(開頭為.)
`ls path -l`: 顯示檔案所有資訊，ex.修改時間、大小等
`ls path -h - l`: 以人容易閱讀的方式顯示資訊，比如說2300000KB,顯示成2.3GB
`ls path -s`: 以檔案大小排序
- cd : 進入一個資料夾
`cd path` : absolute/relative path
- pwd :顯示路徑
`pwd`
- cat : 把檔案內容輸出
`cat testSource.sh` : 把檔案內容輸出在command line
`cat testSource.sh >> testSource2.sh`: 把檔案內容輸出到新的檔案內
- mkdir/rmdir: 新增資料夾/刪除空資料夾
`mkdir test_dir`
`rmdir test_dir`
- mv: 移動檔案/資料夾/改檔名
`mv apple.sh ./` : 把apple.sh移到當前目錄
`mv apple ./` : 把apple資料夾移到當前目錄
`mv ./apple.sh ./cat.sh` : 在同一層底下，改檔名
- cp: 複製檔案/資料夾
`cp apple.sh ./`: 把apple.sh複製一個到當前目錄
`cp -a apple/*.txt ./`: 把apple資料夾內所有檔案複製到當前目錄
`cp apple ./` : 把apple資料夾複製到當前目錄
- chmod: 設定檔案/資料夾權限
`chmod 777 file.txt`
| 數字| 檔案擁有者 | 使用者群組 | 其他使用者群組 |
| --------| -------- | -------- | -------- |
| 777 | 可執行讀寫 | 可執行讀寫 | 可執行讀寫 |
| 764 | 可執行讀寫 | 可讀寫 | 可讀 |
| 721 | 可執行讀寫 | 可寫 | 可執行 |
- #### 磁碟與硬體管理
- mount: 將硬碟或者是光碟、軟碟接掛上系統的指令
`mount -t ext2 /dev/hdc1 /mnt/harddisk`:-t ext2是指為硬碟型態
- df: 查看硬碟空間的指令
- #### network
- ifconfig
- 查詢目前我們這個系統的網路卡的狀況。
- #### 查詢
- find + grep
`find "/var/www/" -name "*.php" -exec grep -H "Exception" {} \;` : 在/var/www/中尋找，檔名包含".php"的檔案，並得到內容含有"Exception"的檔案。
- find + ls
`find / -type f -size 0 -exec ls -l {} \;`: 尋找一般類型文件且大小為0的檔案，並列出檔案資訊。
### 常見leetcode問題：
- #### reorder linked list {1,2,3,4,5} in {1,5,2,4,3} order？
- split to two linked list : {1,2,3}, {4,5}
- reverse {4,5} -> {5,4}
- merge two linked list -> {1,5,2,4,3}
- #### Valid Parenthesis
```
//C version
#include <stdio.h>
#inlcude <stdlib.h>
#define MAX_STACK 100
bool valid_parenthesis(char* s)
{
int stack[MAX_STACK];
int top = -1;
if (*s==NULL)
return 0;
while(*s!='\0')
{
if (*s=='(' || *s=='[' || *s=='{')
{
top++;
stack[top] = *s;
}
else if (*s==')')
{
if (top < 0 || stack[top]!='(')
return false;
else
top--;
}
else if (*s==']')
{
if (top < 0 || stack[top]!='[')
return false;
else
top--;
}
else if (*s=='}')
{
if (top < 0 || stack[top]!='{')
return false;
else
top--;
}
s++;
}
return top==0 ? true : false;
}
```
- #### 質數計算
```
#include<stdio.h>
int isPrime(int n);
int main()
{
int n;
scanf("%d", &n);
if(isPrime(n))
{
printf("It's a prime\n");
}else{
printf("It's not a prime\n");
}
return 0;
}
int isPrime(int n)
{
if(n==1)
return 0;
int i=2;
for(; i*i<=n; i++)
{
if(n%i==0)
{
return 0;
}
}
return 1;
}
```
### 常見腦筋急轉彎
- #### 五個人共持一支手電筒過橋，橋一次只能容納兩個人，五人分別過橋時間是1,3,5,11,13分鐘，請問最短過橋時間是幾分鐘？如何過橋？
- 不斷來回的人盡量是花時間最少的人，如1、3分鐘。
- 1,3 去->3
- 1 回->1
- 11,13去->13
- 3 回->3
- 1,5 去->5
- 1 回->1
- 1,3 去->3
- 共29分
- #### 一條不均勻的繩子燒完需要一個小時，如何用這條繩子量測出半小時？
- 從兩端開始燒，繩子燒完就是剛好半小時。
## 群聯電子
- 公司基本資訊：
是做快閃記憶體(NAND flash)的，商品包含SSD、UFS、SD等。快閃記憶體的好處是非揮發性，不同於揮發性的DRAM、SRAM等，快閃記憶體在斷電後資料可以繼續保存，而且存取速度快、省電，所以適合用來當作記憶體。像是SSD一般用在電腦設備，UFS通常用在嵌入式裝置或高階手機，SD通常用在攝影機、相機、手機等設備。
- 公司文化:
重視品質、效率，同時重視創新、技術研究。
### 韌體工程師03
#### - 職務內容相關了解：
- 設計 NAND FLASH 演算法 (eMMc & UFS)
- 5G、IoT、車用、嵌入式裝置
- 有新controller時，與硬體team討論spec，進行FPGA驗證
- RMA maintain
#### - 工作福利/會議
- 通常早9晚6，緊急狀況或客戶開會才會加班，假日通常不需
- 台南/竹南都有廠
- 需與客戶開會、工程師至少每周會有一次內部會議、會有讀書會
- 責任制獨立作業但很彈性，不會可以求助，自己訂時程、資源等等
- **下班時間比較早、同事氛圍也比較好、像開發小組**
#### - 困難與培訓
- 一開始掌握架構比較難，且很難一次就接觸到整個大架構，需要不斷地學習新的區塊，部會單一，但需要一直學習
- 初期會有大約3~4個月的培訓制度，了解基礎硬體背景、spec、protocal等等
#### - 需要去熟悉的技能:
- C語言
- 資料結構: linked list, queue
- 演算法: sorting, binary search
- FTL : protocal, 但比較不open source, 資料比較零散，進去還是會教
- 作業系統
- mutex vs. sephamore
- 计数：Semaphore 是一个计数信号量，它维护一个整数值，用于控制同时访问某个资源的线程数量。Mutex 是一种互斥锁，它只有两个状态：锁定和非锁定，用于保护共享资源的互斥访问。
- 操作：Semaphore 提供两个主要的操作，即 P（等待）和 V（发信号）。P 操作会将信号量的计数值减一，如果计数值小于零，则线程会被阻塞。V 操作会将信号量的计数值加一，如果有线程正在等待该信号量，则唤醒一个等待线程。Mutex 提供的操作主要是 lock（加锁）和 unlock（解锁），线程在获取锁之前会被阻塞，直到锁被释放。
- 所有权：Mutex 是一种独占锁，只有成功获取锁的线程才能访问被保护的资源，其他线程需要等待锁释放。Semaphore 是一种共享资源访问控制机制，多个线程可以同时访问受信号量保护的资源，只要信号量的计数值大于零。
- 使用场景：Semaphore 适用于控制同时访问资源的线程数量，例如控制连接池中可用连接的数量。Mutex 适用于保护共享资源，确保在任何时刻只有一个线程可以访问该资源，例如对文件的读写操作。
- 总的来说，Semaphore 和 Mutex 都是用于实现线程同步的机制，但它们的应用场景和具体实现有所不同。Semaphore 用于控制资源的并发访问数量，而 Mutex 用于保护共享资源的互斥访问。
- **韌體相關資料(NAND FLASH)**
- 由NAND閘組成，(透過幾個mosfet + 電晶體)。
- 以bitline的方式儲存位元組，每個NAND閘可以儲存一個位元(0或是1)。
- 通過特定的電壓來讀取資料，並透過電壓的改變，來寫入資料。
- 可以做批量擦除，且容量相對較大(NOR)
- UFS vs eMMc
- UFS 可以雙向讀寫，較快
- eMMc 則讀寫分開，較慢
#### - IDE: Visual Studio Trace Code
- ##### 1. 設 breakpoint : 點一下程式碼一行前面，會有一個紅色的點
- ##### 2. 在 Debug 狀態下執行
- ##### 3. 下面視窗切到監看式
- ##### 4. 監看式視窗輸入想要追蹤的變數名稱
- 註：目前還沒跑到u賦值那行，故為未初始化的值
- ##### 5. 點選逐步進行
- 註 : 依照情況可以看要不要點選不要進入函式等等
- #### 6. 注意執行到每一步的時候，左下角監測值的改變
#### - [C複習](https://hackmd.io/DOqKtobSSpGJI87cdFfWAg?both#C)
#### - LeetCode複習：
### 軟韌體工程師1601
#### - 職務內容相關了解：
- 對**UFS & USB Product** 功能驗證程式開發，也就是用**自動化的程式去驗證**一些功能，例如**傳輸速度、資料讀寫、電源管理**。
#### - [C複習](https://hackmd.io/DOqKtobSSpGJI87cdFfWAg?both#C)
#### - LeetCode複習：
- (X) 沒有考
#### - 工作內容：
- 包含firmware, hardware, system的驗證
- 可能需要去測試產品 (客戶要求+基本規格)和(經驗學到的特殊測試)兩個部分
- 主要產品是 隨身SSD / USB
- 定條件，把驗證的需求量化，寫腳本去測試。比如說讀寫速度、續航力時間、在低溫高溫下測試、用10hrs以後會不會當機。
- 需要大量溝通需求
#### - 工作福利
- 工時10~12hrs，壓力大，可報加班
- 有員工宿舍，但可能只能住1~2個月
#### - 工作挑戰
- 分成三個階段： 剛進去、稍微上手、熟練。
- 剛進去
- 兩個月培訓期，有mentor。
- 上基本知識UFS/protocal/NAND flash，會有定期需要去報規格、理論等狀況，也有考試會去測試新人期的程度。
- 稍微上手
- 實際上去看為什麼測試跑不過。
- 分析原因。
- 熟練
- 設計合格的驗證項目
- 要設計什麼、為什麼
## 台積電
- 公司基本資訊：
### IT DevOps Engineer
- 須熟悉k8s,docker,microserice, cloud-native
- 工作有時候會on-call
### HR問題
HR面談
1. 自我介紹 (我說了學歷和工作經歷)
2. 預定幾月畢業
3. 為什麼想轉職
4. 你讀研究所期間有沒有覺得自己和大學就讀資工的同學有差距?
5. 那你們有一起合作的時候嗎? 工作上如何分配? (回答後會再問更細節的地方)
6.以前有遇到過覺得很挫折的時候嗎?
7. 有沒有論文或研究遇到狀況或瓶頸時會怎麼辦? (回答後會再問更細節的地方)
8. 讀研究所或工作時有沒有沒有遇到覺得覺得事後可以強化流程的地方? (回答後會再問更細節的地方)
9. AI 也有分很多領域, 你為什麼覺得AI和醫療可以合作?
10. 有沒有發生或發現自己考慮不夠全面的時候? 怎麼處理? (回答後會再問更細節的地方)
11. 你覺得目前對你應徵的工作上有哪些缺點?
12 . 有沒有面試其他公司
13. 有家人或三等親內在台積電上班嗎?
14. 有家人或三等親內在台積電相關供應鏈或競爭公司上班嗎?
15. 目前身上有簽什麼保密協定是還在期的嗎?
16. 主管有和你說需要oncall 或值班嗎?
17. 希望在什麼地區上班?
18. 之後台積電如果調派其他地點可以接受嗎?
19. 寄信給賀保羅做資歷查核可以嗎?
20. 碩士論文做的東西有沒有和指導教授的要求不同過? 如果有怎麼處理?
QA
我：今天表現有可以加強或改進的地方嗎？
我：我今天回答很多都是關於以前工作相關的，會不會讓你們沒辦法了解到我現在在資訊領域相關的狀況？
HR: 不會, 主要我們是要看人格特質。
### DB問題
#### 基礎定義
- ER model
- 中介
- 以OOP方式去處理資料
- Entity
- 一個物件
- 具有其屬性,以及唯一的primary key(每一筆記錄需獨特不重複)
- Weak Entity
- 一個實體是依附另一個實體存在，ex.學校系統中監護人依附學生存在
- Attribute
- 描述實體的特性
- Derived Attribute
- 用來描述屬性的小屬性，ex.姓名分為姓、名
- Entity group
- 一個class，含多個entities
- 需定義每個entity的ID屬性(primary key)，除了弱實體
- Relationship
- entities之間的關係
- 可以是1-1、1-many、many-many
- many-many需要通過中間轉換(+另一個表，可能包含多主鍵)
- 1-1:
- 1-many:
- many-many:
- 關係本身有屬性: ex.新建一個選課表，含學生主鍵(學號)+開課主鍵(課程代碼)+關係屬性(分數)
- 關係本身無屬性且為複雜關係：ex.如果拿教師、課程、班級等主鍵需要三個主鍵，故用直接在關係新增屬性(開課代碼)作為主鍵
- relational model
- 最終目標，透過ER model 比較好轉換；同樣是logic的模型(非physical直接implement的樣子)
- 利用table和table之間的連結，表示1-1、1-many、many-many的關係
- 簡化了資料管理跟query處理(透過table處理)
- terms
- fields/attributes
- columns: 單一屬性
- records/tuples
- rows: 一筆完整的資料
- primary key
- 每個table裡面唯一定義一筆資料的attribute
- ex. student ID
- foreign key
- 不同tables之間的關係
- 1-1、1-many只需要透過foreign key就可表示關係
- many-many需要intermediate relation(其中有多個foreign keys)
- schema
- 就是每個tables、relations的集合
- Data Definition Language (DDL)
- 用於定義schema
- 與法:
- CREATE TABLE ({項目1:type 項目2:type...})
- ALTER TABLE ...
- DROP TABLE ...
- Data Manipulation Language (DML)
- 用於對records進行操作
- 用法:
- INSERT INTO (table)(columns,...) VALUES (插入數值,...)
- SELECT (某column) FROM (tables=縮寫) WHERE (條件)
- UPDATE ...SET...WHERE...
- DELETE FROM...WHERE...
- Query Algebra
- Operators
- 預定義的functions
- 如product(b,u):合併兩個tables
- Operands
- 輸入的tables
- 如product(b,u)當中的b與u這兩個tables
- Query Plan
- 以Tree方式表示，每個DBMS都會自動搜尋最佳plan來執行
- Normalization 正規化
- 把大table盡可能拆分成更小更模組化的table，來達到重複利用(降低資料重複性)、避免資料更新的異常(考慮資料連結)；但也要考慮越分越細會造成資料查詢更複雜(使用上不方便)。
- ex.下圖table，如想將programming topic拆更細成windows/linux programming，需要選擇所有programming的records一起改；但其實其中topic與topic_id兩項是可以直接拆分為另一個table的
- 方法：
- 關鍵
- 功能性相依:
- 直接相依: 如果A欄位因B欄位產生，則A->B直接相依
- 傳遞相依: 如果A因B產生，B因C產生，則A->C傳遞相依
- 1. 3rd normal form
- 1NF:
- Atomic: 每個欄位不可再分割
- 2NF:
- 1NF + 所有主鍵以外的欄位都需與主鍵功能相依
- 3NF:
- 2NF + 所有主鍵以外的欄位都"只"和主鍵功能相依，不和其他欄位相依(即將對主鍵有傳遞依賴的部分移出去)
- 2. BCNF normal form
- 3NF + 多主鍵需主鍵獨立相依於其他欄位(即不能有一個非主鍵欄位相依於所有主鍵欄位)
- Engine
- Query Engine
- Accept and Process queries
- Storage Engine
- Data Access
- Transaction management
- SQL Statement Processing
- Two Stages:
- Parsing(syntax-based):query.parse
- 看目前的statement語法上是否是一個正確的query
- ex. SELECT FROM ... : 無table名字在FROM前
- Verification(semantic-based):query.planner
- 是否是真的是有意義可以執行的query
- ex. SELECT a FROM ... : a是不是真的是存在的table
- Find a good plan
- 設計流程: bidirectional(可能會往回改)
- 系統規格/需求定義
- 需求與資料蒐集
- 概念設計
- 定義ER model
- 邏輯設計
- relational model並確認是否正規化
- 實體建置
- 定義資料的型態
- 資料庫
- ### Indexing
- 用在**大型資料庫**裡面，通常是用**B-tree**去實作。
- 透過在**常被查詢的欄位加入索引**，來**減少查詢時間**；通常加入索引的資料可以用**binary search**等方法完成，複雜度可以降低$O(logn)$左右。
- 優點: 提升查詢效率
- 缺點: 會占用磁碟空間
- ## Container
- Docker 是容器執行階段技術，可讓您比傳統方法更快速地建置、測試和部署應用程式。 其將軟體封裝到名為容器的標準化單位，其中包含程式庫、系統工具和程式碼等執行軟體所需的所有項目。 Kubernetes 是一種容器協同運作工具，藉助該工具可擴展容器系統，從而大規模地管理、協調和排程容器。
- Docker:
- 是一種容器，用於封裝和運行應用程式及其相關的環境依賴。
- 透過一致性的運行環境，幫助快速建立、部署和管理應用程式的目的。
- k8s:
- 容器管理、自動化部署的工具。
- microservice(微服務)
- 是一種軟體架構風格，其中應用程式被拆解為一組小型、獨立且相互協作的服務。彼此之間透過(輕量級通訊機制)（通常是通過網路API）來與其他服務進行溝通。
- cloud-native
- 包含上述三個特性
- 容器化、微服務架構、自動化部署。
#### 線上課紀錄
[清大課程](https://www.youtube.com/watch?v=E4DLGaZGWMk&list=PLS0SUwlYe8cyln89Srqmmlw42CiCBT6Zn&index=15)
CH3-Architecture and Interfaces
CH4-Server and Threads
CH5-Query Processing: C以後跳
CH6-Data Access & File Management
CH7-Memory Management
CH8~12 皆跳過
[翻轉教學](https://www.youtube.com/watch?v=1V_GDdSQtHA&list=PLWCTS9kq2MwQCBQ7ZLRrF9_iokAVj78Tu&index=49)
看到影片e.89
## 新思科技
- ### 公司基本資訊：
- #### EDA
- ### 面試基本流程：
- #### 1. HR 10~15分鐘電訪
- 簡單了解經歷背景
- email補件成績單與履歷
- #### 2. 需要2 weeks: 等待主管審閱履歷
- 開放履歷多部門審閱
- #### 3. 收到codility test
- C/C++
- 底層實作類，包含資料結構、演算法、OS
- #### 4. 主管電話面試訪談+約面試
- 視情況可能會有英文問題
- 視情況有可能有technical問題
- #### 5. 主管視訊/實體面試
- presentation(自介+經歷+專案)
- 視情況可能穿插英文問題
- 視情況可能有technical問題
- #### 6. (視情況)外國主管全英文面試
- 如部門需對外會有
- 多personality
### Software RD
#### - 部門做什麼:
- EDA在幹嘛？
- 很小的晶片上可能有數百億顆晶體管，很難人為的完成所有的設計跟驗證，所以需要EDA tool去幫助設計(及分析效能)跟驗證。
- 先進封裝部門:
- 先進封裝是什麼?
- 在EDA（Electronic Design Automation）領域，先進封裝通常指的是為了更好地支援先進半導體製程和先進封裝技術，EDA工具需要不斷更新和升級，以滿足設計和製造的需求。這些工具包括晶片設計軟體、電路模擬器、物理設計軟體、佈局工具、驗證工具等。先進封裝和EDA領域密切相關，因為隨著製程和封裝技術的不斷進步，設計和製造的要求也不斷提高，因此需要不斷升級和優化EDA工具，以應對日益複雜的設計需求和製造挑戰。
- 設計軟體演算法符合需求
- 通常都會是 NP-hard 的問題!
#### - 職務內容相關了解：
- Soc(system on chip) vs 3D chips
- IC Design
- Analog 類比電路
- Digital 數位電路
- Hybrid 混和電路
- VLSI
- 硬體描述語言
- IC Design Flow
- 廠商
- 
- 各階段需考慮的部份
- 先進封裝:
- 3D Chips的立體堆疊。
- 為了提高功能密集度，半導體的製程希望把晶體管的尺寸做得越小越好(比如台積的3nm、2nm)，可以在單位面積的芯片塞更多功能單位進去。
- 另一種方法，把chips做立體的堆疊，也可以達到提高功能密集度，甚至可以減短芯片連接的距離，可以減少訊號延遲的情況。
- 但是3D chips由於是立體多層堆疊，比較複雜，所以在進行驗證的部份可能會有更高難度。ex. 可靠性(在各種狀況下，能否正常運作)、熱管理(TI，有效控制溫度)、功率(PI，電源穩定、功率分布)、訊號(SI，驗證芯片之間的訊號傳輸時序正確、不失真等)。
- 困難:
- 小晶片創建的聚合系統需要系統級的驗證，儘管每個單獨的小晶片都通過了簽核檢查，例如靜態時序分析(STA)、電源、電子遷(EM)和電壓(IR)分析，但在系統中連接在一起的所有這些都需要額外的驗證。因此，「設計收斂」(design closure)涉及「系統級收斂」，以及額外的驗證檢查，例如翹曲(warpage)等長期影響就需要熱應力和機械應力檢查，對於在RDL或矽中介層上彼此相鄰放置的小晶片，就需要進行電磁干擾(EMI)，以及訊號和電源完整性(SI/PI)分析。
#### - C++複習：
- #### OOP概念
- SOLID
- 設計模式
- #### 資料結構
- 基本需複習：
- Tree
- Graph
- Queue
- Stack
- Heap
- Linked List
- Array
- 須知道時間複雜度、實作方式(C++ STL)：
- map, unordered_map
- set, unordered_set
- priority_queue
- #### 演算法
- Graph
- BFS, DFS
- Topological Sort
- Dijkstra Algorithm
-
- Tree
- traversal : preorder, inorder, postorder
-
Sign in with Wallet
Connect another wallet