# 求職筆記
## LeetCode 刷題指南
#### 1. [**每周清單**](https://www.techinterviewhandbook.org/coding-interview-study-plan/)
#### 2. [**Blind 75**](https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions)
## 資料結構
#### 1. 基礎需知
- Linked List vs Array
- Linked List 新增、刪除節點須熟練
| | 優點 | 缺點 |
| -------- | -------- | -------- |
| Linked List | 動態配置、彈性，刪除新增節點快 | 需額外空間儲存指向下一個節點的指標 |
| Array | 隨機存取容易，sorting後用sorting方便 | 新增刪除不易 |
- Queue vs Stack
- Queue :
- FIFO
- BFS用
- Stack :
- FILO
- DFS用
- Heap
- Max Heap vs Min Heap
- Heap Sort
- Tree
- 需會操作:
- traversal : preorder, inorder, postorder
- BST : insert, delete, search
- 需知道的terms:
- BST
- Balanced Binary Tree
- Complete Binary Tree
- Red-Black Tree
| Binary Tree | Complete Binary Tree | Balanced Binary Tree |
| -------- | -------- | -------- |
|  | | |
| 最多有兩個節點 | 除了最後一層都有nodes，且僅右子樹可以有缺 | 節點左右子樹高度差不超過1 |
- [Graph](https://www.techinterviewhandbook.org/algorithms/graph/)
- 需會操作：
- BFS, DFS, topological sort
#### 2. C++ STL
- map
| 區別 | ordered_map | unordered_map |
|:-------------:|:-----------:|:-----------------------------:|
| 有順序性(key) | 有 | 無 |
| 實作方法 | 紅黑樹 | 雜湊表 |
| Search | $log(n)$ | $O(1)$-Average, $O(n)$-Worst |
| Insert | $log(n)$ | $O(1)$-Average, $O(n)$-Worst |
| Delete | $log(n)$ | $O(1)$-Average, $O(n)$-Worst |
- set
- same as map
- priority_queue
- 不同於queue，以**max heap**實作，預設**從大排到小**，top為最大元素。
- 有n個資料欲插入排序情況下，複雜度與**heap sort**皆為$O(nlogn)$。
- 需 `#include <queue>`
| Operation | Find max/min | Insert |Remove |Heapify (create a heap out of given array of elements)|
| -------- | -------- | -------- |-------- |-------- |
| Big-O | $O(1)$ | $O(log(n))$ |$O(log(n))$ |$O(n)$ |
## 演算法
- Sorting
| 演算法 | Best | Worst |Worst/Best Case情況| Avg | 空間複雜度 | 穩定性 | 類型 |
| --------------------------- |:------------:| ----------------------- | ---------------- | ----------------- | ------ | ---- |---- |
| 選擇排序法(Selection Sort) | Ο($n^2$) | Ο($n^2$) |一直都須全部跑過一次比較 | Ο($n^2$) | Ο(1) | 不穩定 | 比較選擇後交換 |
| 插入排序法(Insertion Sort) | Ο($n$) | Ο($n^2$) | (best)輸入是排序過的數列 | Ο($n^2$) | Ο(1) | 穩定 | 比較後插入 |
| 氣泡排序法(Bubble Sort) | Ο($n$) | Ο($n^2$) |(best)輸入是排序過的數列 | Ο($n^2$) | Ο(1) | 穩定 | 左右比較後交換 |
|~~謝爾排序法(Shell Sort)~~ | Ο($n$) | Ο($n^2$)~ Ο($n^1$$^.5$) |-| Ο($n^5$$^/$$^4$) | Ο($n$) + Ο(1) | 不穩定 | 插入 |
| ~~搖晃排序法(Shaker Sort)~~ | Ο($n$) | Ο($n^2$) | -|Ο($n^2$) | Ο(1) | 穩定 | 交換 |
| **快速排序法(Quick Sort)** | Ο($n log n$) | Ο($n^2$) |(best)pivot剛好是中位數/ \(worst)輸入排序過的數列| Ο($n log n$) | Ο($log n$)~Ο($n$) | 不穩定 | 交換 |
| **合併排序法(Merge Sort)** | Ο($n log n$) | Ο($n log n$) |一直都須全部跑過一次比較| Ο($n log n$) | Ο($n$) | 穩定 | 合併 |
| **堆積排序法(Heap Sort)** | Ο($n log n$) | Ο($n log n$) |? | Ο($n log n$) | $MaxHeapTree$ Ο($n$) + $Inplace$ Ο(1) | 不穩定 | 選擇 |
| **計數排序(Counting Sort)** | Ο($n+k$) | Ο($n+k$) |k較大 / k較小| Ο($n+k$) | Ο($n+k$) | 穩定 | 計數(非比較型) |
| **基數排序(Radix Sort)** | Ο($d×(n+k)$) | Ο($d×(n+r)$) |?| Ο($d×(n+k)$) -LSD | Ο($n+k$) | 穩定 | 每個digit是用counting sort比 |
- Searching
- Binary Search
- String
- [KMP](https://medium.com/nlp-tsupei/kmp%E7%AE%97%E6%B3%95%E8%A9%B3%E8%A7%A3-1b1050a45850) (Knuth–Morris–Pratt )
| 方法 | 比對字串(搜尋) |說明|
| -------- | -------- | -------- |
| 爆破法 | $O(mn)$ |遍歷尋找|
| Knuth–Morris–Pratt | $O(m+n)$ |建立failure_function: $O(m)$, 比對過程: $O(n)$|
- Min Path in Graph
- [Dijkstra Algorithm](https://medium.com/%E6%8A%80%E8%A1%93%E7%AD%86%E8%A8%98/%E5%9F%BA%E7%A4%8E%E6%BC%94%E7%AE%97%E6%B3%95%E7%B3%BB%E5%88%97-graph-%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%88%87dijkstras-algorithm-6134f62c1fc2)
## C++課程
#### 1. [線上課程](http://ocw.nctu.edu.tw/course_detail-v.php?bgid=9&gid=0&nid=412&v5=0J2eLvkuF8k)
#### 2. 經典問題
- 1. virtual function是什麼？
- 2. override, overwrite, overload?
- 3. 繼承的建構、解構順序
- 4. OOP三大概念
- 封裝
- 繼承
- 多型
## 面試經驗分享
### 1. 群聯
- 面試職位:
- 軟韌體1601
- 韌體03
#### 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的情況
- #### 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++基本上取對界大小跟最長成員長度兩者中**較小**的那個。
- #### 面試流程
- 1601
- 主管
- HR
- 03
- 工程師
- 小主管
- 大主管
- HR
> 面試經驗不佳，細節可以問我XD
### 2. 台積
- #### 面試職位:
- IT
- #### 需準備的：
- 自我介紹
- 專案須熟悉
- 如有docker, k8s, CICD概念佳
- 如有資料庫專案經驗可能會問
- #### 面試流程:
- codility
- 主管面試
- HR面試
- 適性測驗/英文測驗(五年內多益700up免測)
### 3. 新思
- #### 面試職位:
- Software RD Engineer
- #### 需準備的：
- 英文自我介紹
- C++
- 基本面試問題
- #### 面試流程
* DAY-1 : 104丟履歷
* DAY-5 : HR電話簡單訪談
* DAY-13: 部門主管電話簡單說明工作內容、給codility
* DAY-17: 寫完codility
* DAY-24: 主管面談、寫C++考卷
* DAY-31: 兩位工程師技術面談
* DAY-34: 口頭offer
* DAY-38: 書面offer
Sign in with Wallet
Connect another wallet