# 一些我夢到的常見面試問題
這邊紀錄一些我夢到或是想到的面試常見問題
如果對題目或是解答有問題, 或是想改東西加東西, 歡迎email給我
email: benson40111@gmail.com
先放參考連結
>[你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer)
>[C/C++ - 常見 C 語言觀念題目總整理（適合考試和面試）](https://mropengate.blogspot.com/2017/08/cc-c.html)
>[考古題相關](https://hackmd.io/@jQSlhiN3QaGkugpbD4NDAA/rkvNkyQfi)
>[面試整理](/KlnPOwLlS6uQ_uYK-uCtMQ)
>[發哥(聯發科)上機考題目整理](@Rance/SkSJL_5gX)
>[C語言 : 超好懂的指標，初學者請進～](https://kopu.chat/c%e8%aa%9e%e8%a8%80-%e8%b6%85%e5%a5%bd%e6%87%82%e7%9a%84%e6%8c%87%e6%a8%99%ef%bc%8c%e5%88%9d%e5%ad%b8%e8%80%85%e8%ab%8b%e9%80%b2%ef%bd%9e/)
>[ISO/IEC 9899](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
## Content
- Basic concepts
- Data structure
- Basic concepts of C language
- Linux
- Pointer
- Basic usage
- Function pointer
- Advanced usage
- struct, union and enum
- bitwise operator
- Programming
- Basic
- Sort
- Linked list
- MCU
- GPIO
- ADC
- I2C
- SPI
- undefined behavior (TODO)
- Network (TODO)
## Basic concepts
### Data structure
#### Q: Compare stack, queue, heap
>[Stack vs. Heap](https://medium.com/joe-tsai/stack-vs-heap-b4bd500667cd)
>[Stack vs Heap Memory – Difference Between Them](https://www.guru99.com/stack-vs-heap.html)
| Features | Explain |
|:-------- |:--------------------------------------------------------------------------------------- |
| stack | **LIFO** (Last In First Out) 大部分情況用來存local variable的地方, 可以用來實作四則運算 |
| queue | **FIFO** (First In First Out) stack的相反, 有些CPU的排班會利用queue |
| heap | 二元樹的一種, 特性是root一定是最大或最小, 父節點必定大於子節點 |
---
#### Q: Compare sort alogorithm
直接畫表格比較快
這邊只討論平均
| Algorithms | Time complexity | Space complexity | Stability |
|:-------------- |:--------------- |:-------------------- |:--------- |
| Selection sort | $O(n^2)$ | $O(1)$ | unstable |
| Insertion sort | $O(n^2)$ | $O(1)$ | stable |
| Bubble sort | $O(n^2)$ | $O(1)$ | stable |
| Quick sort | $O(n\log n)$ | $O(\log n)$ ~ $O(n)$ | unstable |
---
#### Q: Binary Search Tree (BST) Traversal
一般都是給BST然後要你traverse三或四種方法
網路上很多, 懶得寫出來了
>[基礎演算法系列 — Tree 樹狀資料結構](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-tree-%E6%A8%B9%E7%8B%80%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-d10fe8ac1ce2)
---
### Basic concepts of C language
#### Q: Memory allocation
給一段C的程式片段, 問變數配置在哪些地方
>寫得很好, 建議看完
>[C 語言程式的記憶體配置概念教學](https://blog.gtwang.org/programming/memory-layout-of-c-program/)
```C=
int global_var = 0; //global初始化區(data)
int *global_ptr; //global未初始化區(bss)
int main()
{
int local_var; //stack
char str[] = "1234"; //stack
char *p1; //stack
static int static_var = 0; //global初始化區(data)
p1 = (char *)malloc(sizeof(char *)); //heap
return 0;
}
```
---
#### Q: Compare Compile error, linker error, run time error
比較三種差異, 比較常在寫直譯語言的話可能會比較不熟悉
建議用個簡單的程式然後用gcc分段跑一次會比較熟
>[Compiler error vs linker error?](https://stackoverflow.com/questions/14947050/compiler-error-vs-linker-error)
| Features | Explain |
|:-------------- |:--------------------------------------------------------- |
| Compile error | 通常都是語法錯誤,warning不算錯誤, 不過也是要注意 |
| linker error | 找不到某些include進來的東西或是function |
| run time error | 最常見就是指標亂指導致OS把程式殺掉 ex: Segmentation fault |
---
#### Q: Explain define, const, volatile, inline, extern
解釋這四種關鍵字在幹嘛
比較需要注意的是volatile,inline,extern
| Features | Explain |
|:-------- |:------------------------------------------------------------------------------------------- |
| define | 巨集的一種, 預編譯時會展開且**不會做型別檢查**, 因為是展開, 所以要注意一些陷阱題 |
| const | read-only變數, 一般用來宣告常數, 編譯階段使用 |
| volatile | 告知編譯器不要對它做最佳化, 每次都從記憶體撈值, 而不是從暫存器. 常用於ISR或是一些硬體暫存器 |
| inline | 可以拿來修飾function, 主要用來加速執行速度, 參數類型會檢查, inline後編譯器不一定會實作 |
| extern | 可以引用外部的全域變數 |
---
#### Q: data types
基本觀念, 建議背一些常用的就好
以下是常見情況, 占用多少memory還是要看機器而定
| Data Type | Bytes |
|:----------------- |:----- |
| short | 2 |
| long | 8 |
| float | 4 |
| double | 8 |
| **int** | 4 |
| **char** | 1 |
| unsigned | 4 |
| **unsigned int** | 4 |
| **unsigned char** | 1 |
| **pointer** | 8 |
---
#### Q: What is the output
通常都是給一段程式問你輸出
define
```C=
#define A 2+3
#define B (2+3)
printf("%d\n", A*A); //2+3*2+3=11
printf("%d\n", B*B); //(2+3)*(2+3)=25
```
static v.s local
```C=
/* Call this function 10 times, a=?, b=? */
void fun()
{
static int a = 0;
int b = 0;
a++;
b++;
printf("%d\n", a); //10
printf("%d\n", b); //1
}
```
const
```C=
const int c = -5;
c++; //Compile error
printf("%d\n", c);
```
switch
```C=
switch(2) {
case 0:
printf("0\n"); //won't print
break;
case 1:
printf("1\n"); //won't print
case 2:
printf("2\n"); //will print
case 3:
printf("3\n"); //will print
}
```
### Linux
>[Words Commonly Mispronounced by Chinese Programmers](https://github.com/shimohq/chinese-programmer-wrong-pronunciation)
Linux真正的唸法參考連結內有, 裡面還有很多其他常見單字的唸法
Linux相關的題目大部份都會出現在考卷上, 一般都是問command可以幹嘛
基本command不列在這邊, 這邊列出我工作遇過或夢到的相關題目
#### Q: 以下哪個Linux command可以列出當前目錄中的檔案?
(A) free
(B) top
\(C\) cd
(D) ls
```
free: 查看記憶體
top: 效能分析工具, 類似工作管理員
cd: 切換目錄
ls: 列出當前目錄的檔案
```
---
#### Q: 請說明tar的功能
Linux常用的壓縮或解壓縮command
參數有很多種組合, 都是用來壓縮或解壓縮不同的壓縮格式
>[ GNU / Linux 各種壓縮與解壓縮指令](http://note.drx.tw/2008/04/command.html)
---
#### Q: Compare user space(mode) and kernel space(mode)
作業系統(OS)的基本觀念
基本上Linux系統很多設計上的東西跟恐龍書差不多
>[圖片來源](https://www.redhat.com/rhdc/managed-files/2015/07/user-space-vs-kernel-space-simple-user-space.png)
***注意 sudo還是run在user mode***
---
#### Q: 用chmod更改file.txt的權限為 -rwxrwx\-\-\-
要先懂文件權限在幹嘛
>[Linux chmod命令](https://www.runoob.com/linux/linux-comm-chmod.html)
然後我們就可以開始作答了
```bash
$ chmod 770 file.txt
or
$ chmod ug+rwx file.txt
```
---
#### Q: 如何將程式放置到後台執行
任何的command加上 ```&```就好了, 雖然我不確定是不是所有常用command都可以這樣
```bash
$ ./test.sh &
```
#### Q: 承上題, 進入後台執行後的程式如何回到前台執行
```bash
$ fg
```
如果有超過一個以上的後台執行, 可以先用```jobs```確認編號, 然後加上編號就可以指定要把哪個後台程式放回前台
---
#### Q: 在linux中, kernel space如何傳遞資料給user space
>[Linux 驅動程式的 I/O, #3: kernel-space 與 user-space 的「I/O」](https://www.jollen.org/blog/2006/12/linux_device_driver_io_3.html)
>[開發 driver 需要的基礎知識](https://www.cntofu.com/book/46/linux_device_driver_programming/05.md)
有寫過kernel module的話應該會大概知道怎麼做
主要就是copy_to_user和copy_from_user這兩個function
---
#### Q: spin lock, mutex, semaphore在linux的差異
>[Mutex v/s Semaphore v/s Spinlock](https://medium.com/freethreads/mutex-v-s-semaphore-v-s-spinlock-98c6884356b9)
>[淺談同步機制](https://rickhw.github.io/2020/09/12/ComputerScience/Synchronization/)
```
mutex同一時間只能讓一個process進入critical section, 有鑰匙的人可以進去
semaphore允許多個process進入critical section, 滿了就要等process出來才能進去, 沒有鑰匙
spin lock為busy waiting的機制, 比較適合在需要保護某一小段data時, 因為等待時間較長
```
---
## Pointer
應該算是很多人都不熟的東西了(包括我), 所以需要花點時間念
>[c語言有沒有call by reference(or call by address)?](http://eportfolio.lib.ksu.edu.tw/~T093000170/blog?node=000000119)
- ```*``` : pointer, dereference (解指標)
- ```&``` : address-of
- ```**```: pointer to pointer(指標的指標)
- ```call-by-value```: caller and callee各自有自己的記憶體, C的function call都屬於這種
- ```call-by-reference```: caller and callee使用相同的記憶體, C++才有
---
### Basic usage
一些基本的用法
```C=
int a = 5;
int *p; //assign a pointer to int
p = &a; //assign the address of variable "a" to pointer p
printf("%d\n", *p); //dereference p: 5
printf("%p\n", &a); //0xXXXXX
printf("%p\n", p); //same as address of variable a
```
```C=
int a[] = {1,2,3,4,5};
int *p1 = a; //pointer p will point to the address of head of a
char c[] = "54321";
int *p2 = c;
/* array of pointer to int */
printf("%d\n", *p1); //a[0] = 1
printf("%d\n", *p1 + 1); //a[0]+1=2
printf("%d\n", *p1++); //1, and the pointer moves to next element
printf("%d\n", *++p1); //3, the pointer moves first then dereference
printf("%d\n", ++*p1); //4, dereference then plus one
/* array of pointer to char */
printf("%c\n", *p2); //c[0] = 5
printf("%c\n", *(p2+1)); //c[0+1]=4
printf("%lu\n", sizeof(c)); //6 bytes, 5 + 1(end char)
```
```C=
*p++ = *(p++)
*++p = *(++p)
++*p = ++(*p)
```
---
### Function pointer
很少遇到, qsort函數的callback參數就有需要
```C=
/* function define */
void fun(char *str, int len);
/* function pointer define */
void (*fun_ptr)(char *, int) = &fun;
```
---
### Advanced usage
我認為比較進階的題目
#### Q: 給一句話, 把那句話表達出來
```C=
/* define */
//1. A pointer to a pointer to an integer
//2. An array of 10 integers
//3. An array of 10 pointers to integers
//4. A pointer to an array of 10 integers
//5. A pointer to a function that takes an integer as an argument and returns an integer
//6. An array of ten pointers to functions that take an integer argument and return an integer
int **p;
int a[10];
int *p[10];
int (*p)[10];
int (*p)(int);
int (*p[10])(int);
```
---
#### Q: What is the output (64-bits machine)
```C=
int main(void)
{
char *a[] = {"abc", "def", "ghijk", "lmnop"};
char *b = a[2];
printf("%d\n", sizeof(a)); //8*4=32
printf("%d\n", sizeof(b)); //8
printf("%d\n", sizeof(a[2])); //8
printf("%d\n", sizeof(b[2])); //1
return 0;
}
```
---
#### Q: Write two functions that are able to access a fixed memory location
>[Interview Guide for Embedded C Programmers](https://binaryupdates.com/interview-guide-for-embedded-c-programmers/2/)
寫兩個function, 一個可以read memory一個可以write memory
答案很多種, 主要是要看pointer操作懂不懂
```C=
/* 64-bits machine */
uint64_t *read_mem(uint64_t addr)
{
uint64_t *p = addr;
return *p;
}
void write_mem(uint64_t addr, uint64_t data)
{
uint64_t *p = addr;
*p = data;
}
```
---
## struct, union and enum
算是C/C++的必考題之一, 實務上也很常用到
```
struct: 自定義的一種型別, 可以包含多個不同型別的變數, 每個成員都會配置一塊空間
union: 跟struct有點像, 主要差別是裡面的成員共用一塊記憶體, 所需記憶體由型別最大的成員決定
enum: 可以用來定義常數, 主要是可以提升程式可讀性, 裡面的值從值指定的值開始遞增, 預設為0
```
```C=
/* struct */
struct GPIO {
char name[12];
unsigned char direction;
unsigned int value;
struct GPIO *gpio_ptr;
//struct不能含有自己, 但可以有自己的pointer
};
int main(void)
{
/* normal */
/*
struct GPIO g = {
"GPIO_IO1",
0,
1,
NULL
};
*/
/* designated initializers(recommend) */
struct GPIO g = {
.name = "GPIO_IO1",
.direction = 0,
.value = 1,
.gpio_ptr = NULL
};
printf("%s\n", g.name); //GPIO_IO1
printf("%d\n", g.direction); //0
printf("%d\n", g.value); //1
printf("%p\n", g.gpio_ptr); //nil
return 0;
}
```
```C=
/* union */
union data {
unsigned char c; //1 byte
int val; //4 bytes
long int li; //8 bytes
};
int main(void)
{
union data d;
d.c = 255;
printf("%d\n", d.c); //255
return 0;
}
```
```C=
/* enum */
enum GPIO_NUM {
GPIO_IO0 = 0,
GPIO_IO1,
GPIO_IO2,
GPIO_IO3,
GPIO_IO4
};
int main(void)
{
enum GPIO_NUM G = GPIO_IO3;
printf("%d\n", G); //3
return 0;
}
```
structure pointer
Linked-list很常用到
```C=
typedef struct _GPIO {
char *name; //8 bytes
unsigned char direction; //1 byte
unsigned int value; //4 byte
} GPIO;
int main(void)
{
GPIO *ptr = (struct GPIO *)malloc(sizeof(struct GPIO));
ptr->name = "GPIO_IO20";
ptr->direction = 0;
ptr->value = 1;
printf("%s\n", ptr->name); //GPIO_IO20
printf("%d\n", ptr->direction); //0
printf("%d\n", ptr->value); //1
return 0;
}
```
struct size計算
寫得滿仔細的
>[C 語言:關於 sizeof 及結構及同位的記憶體對齊](https://magicjackting.pixnet.net/blog/post/221968938)
```C=
typedef struct _GPIO1 {
char *name; //8 bytes
unsigned char direction; //1 byte
unsigned int value; //4 byte
} GPIO1;
typedef struct _GPIO2 {
unsigned char direction; //1 byte
char *name; //8 bytes
unsigned int value; //4 byte
} GPIO2;
int main(void)
{
printf("%lu\n", sizeof(GPIO1)); //16
//因為struct會被編譯器拿去做對齊最佳化,
//所以"direction"和"value"這兩個變數會被合在一起然後補滿(padding)8 bytes
printf("%lu\n", sizeof(GPIO2)); //24
//"direction"會補滿8 bytes, "value"也會補滿8 bytes, 所以加起來是24 bytes
return 0;
}
```
union and CPU endian
一般CPU都是Little-Endian, 也就是lowest bytes會放在最低的記憶體位子上
Big-Endian則相反
>[Big-Endian 與 Little-Endian 的差異與判斷程式碼](https://blog.gtwang.org/programming/difference-between-big-endian-and-little-endian-implementation-in-c/)
>[2018q3 Homework3 (rewiew)](https://hackmd.io/@cheese/r1OKM-yo7?type=view)
```C=
union data {
unsigned char c; //1 byte
unsigned int val; //4 bytes
};
int main(void)
{
union data d;
d.val = 0x12345678;
printf("0x%x\n", d.c); //Little-Endial: 0x78
d.c = 256;
printf("%d\n", d.c); //0
return 0;
}
```
---
#### Q: sizeof(struct data)? (64-bits machine)
>[【C++ Primer】 神秘的 sizeof(union) 、sizeof(struct) 和内存对齐技术](https://blog.csdn.net/tianshuai1111/article/details/7576279)
```C=
struct __attribute__((__packed__)) data {
char c; //1
short s1; //2
short s2; //2
int h; //4
};
printf("%lu\n", sizeof(struct data)); //9
```
---
## bitwise operator
基本上都是考一個數字, 經過一些運算後輸出是什麼
set bit, clear bit建議背起來, firmware必考題
>[[C 語言] Bitwise operation note](https://m033010041.github.io/2020/02/28/bitwise-operation-in-C/)
>[awesome-bits](https://github.com/keon/awesome-bits)
#### Q: What is the output
```C=
unsigned int x = 0xf;
x <<= 4;
x |= 0x03;
printf("0x%x\n", x); //0xf3
```
---
#### Q: Complete the program
```C=
/*
* en is '0': clear bit, en is '1': set bit, en is '2': inverse bit
* loc is bit location
*/
void write_register(unsigned int *x, unsigned int loc, unsigned char en)
{
//Complete the code below
if (loc < 0) return;
if (en == '0') {
*x &= ~(1 << loc); //clear bit
} else if (en == '1') {
*x |= (1 << loc); //set bit
} else if (en == '2') {
*x ^= (1 << loc); //inverse bit
} else {
printf("input error\n");
}
}
```
---
#### Q: Write a program to check is power of 2
如果不給用if來判斷的話, 可以用bitwise來判斷
如果是2的次方的話, 在2進位中只會有1個1
```C=
/* 0: is not power of 2, 1: is power of 2 */
int is_pow_2(unsigned int x)
{
return (x & -x) == x;
}
```
---
#### Q: Write a program to calculate number of 1
數一個值轉二進位後有幾個1
```C=
int number_of_one(unsigned int x)
{
int c = 0;
while (x != 0) {
x = x & (x - 1);
c++;
}
return c;
}
```
---
#### Q: Find the MSB and LSB location
找最高位元和最低位元的位置
要注意輸入的型別是什麼
找最高位元的位置
```C=
void highest_bit(unsigned int x)
{
unsigned int test = 0x80000000;
int count = 31;
if (x <= 0) {
return;
}
while ((x & test) >> count != 1) {
count--;
test >>= 1;
}
printf("highest bit is at %d\n", count);
}
```
另一種寫法, 如果型別比較大的話就不太適合這樣寫
```C=
int highest_bit(unsigned char x)
{
int n = 7;
if (x == 0) return -1;
if ((x >> 4) == 0) {
x = x << 4;
n -= 4;
}
if ((x >> 6) == 0) {
x = x << 2;
n -= 2;
}
if ((x >> 7) == 0) {
n -= 1;
}
return n;
}
```
找最低位元的位置
```C=
void lowest_bit(unsigned int x)
{
unsigned int test = 0x1;
int count = 0;
while ((x & test) << count == 0) {
test <<= 1;
count++;
}
printf("lowest bit is at %d\n", count);
}
```
---
#### Q: Write a program to check the hex is equal
看16進位數字有沒有都一樣
ex: 0xAAAA 有, 0xAABB 沒有
```C=
int is_hex_equal(unsigned short input)
{
unsigned short hex[4] = {0};
hex[0] = (input & 0xF000) >> 12;
hex[1] = (input & 0x0F00) >> 8;
hex[2] = (input & 0x00F0) >> 4;
hex[3] = input & 0x000F;
if (hex[0]==hex[1] && hex[0]==hex[2] && hex[0]==hex[3])
return 1;
else
return 0;
}
```
---
## Programming
這邊就放程式題目了, 難度頂多到leetcode的medium
如果前面懶得看, 也可以只看這邊就好
先從基礎開始吧
### Basic
#### Q: Write a program to print fibonacci number
基本題目, 一般用遞迴解, 因為比較直覺
不過這邊建議用DP(Dynamic Programming)
```C=
/* recursive */
int fib_recursive(int n)
{
if (n <= 1) return n;
return fib_recursive(n-2) + fib_recursive(n-1);
}
/* DP */
int fib_dp(int n)
{
int dp[1001] = {0};
dp[0] = 0;
dp[1] = 1;
if (n <= 1) return dp[0];
if (n == 2) return dp[1];
for (int i = 2; i < n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1] + dp[n-2];
}
```
---
#### Q: Write a swap function
交換兩個數值
有兩種寫法, 看題目有沒有限制
```C=
/* normal */
void swap(int *a, int *b)
{
int tmp = 0;
tmp = *a;
*a = *b;
*b = tmp;
}
/* without tmp */
void swap(int *a, int *b)
{
*a = (*a) ^ (*b);
*b = (*a) ^ (*b);
*a = (*a) ^ (*b);
}
```
---
#### Q: Print stars
\*
\**
\***
\****
標準印星星題目
```C=
void print_step()
{
for (int i = 1; i <= 4; i++) {
for (int j = 0; j < i; j++) {
printf("*");
}
printf("\n");
}
}
```
---
#### Q: Calculate the GCD
計算最大公因數, 可以用遞迴或是迴圈來解
概念就是輾轉相除法
順便也把最小公倍數放這邊
```C=
/*
* recursive
* Notice: b must > a
*/
int gcd_recursive(int a, int b)
{
if (b == 0) return a;
return gcd(b, a%b);
}
/* loop */
int gcd(int a, int b)
{
while(a != b) {
if (a > b) a -= b;
if (b > a) b -= a;
}
return a;
}
/* Least Common Multiple */
int lcm(int a, int b)
{
return a * b / gcd(a, b);
}
```
---
#### Q: Find 1 ~ 100 prime
```C=
void find_prime(int n)
{
int flag = 1;
int prime = 0;
for (int i = 2; i <= n; i++) {
prime = i;
flag = 1;
for (int j = 2; j < i; j++) {
if (i % j == 0) {
flag = 0;
break;
}
}
if (flag) printf("%d\n", prime);
}
}
```
---
#### Q: Write a program can round off
寫一個簡單的四捨五入程式, input只會到小數點第一位, 所以要進位到個位數
ex: 5.5=>6, 5.4=>5
一般都會限制不給用if-else, 所以要善用C的型別轉換
```C=
int round(float x)
{
return (int)(x + 0.5);
}
```
---
#### Q: Write a program to reverse string(char array)
手刻反轉字串
```C=
void swap(char *c1, char *c2)
{
char tmp = ' ';
tmp = *c1;
*c1 = *c2;
*c2 = tmp;
}
char *reverse_str(char *str)
{
const int len = strlen(str);
for (int i = 0; i < len/2; i++)
swap(&str[i], &str[len-1-i]);
return str;
}
```
---
#### Q: Complete strcpy, strcat, strlen, strcmp
手刻這幾個程式, 算挺常見的題目
```C=
/* strcpy */
void strcpy(char *dest, const char *src)
{
if (dest == NULL || src == NULL) return;
while (*src != '\0') {
*dest = *src;
dest++;
src++;
}
}
/* strcat */
void strcat(char *dest, const char *src)
{
char *p = dest;
int loc = 0;
if (dest == NULL || src == NULL) return;
while(*(p++) != '\0') loc++;
while(*src != '\0') {
dest[loc] = *src;
src++;
loc++;
}
}
/* strlen */
int strlen(const char *str)
{
int len = 0;
while (*str++ != '\0') len++;
return len;
}
/* strcmp */
int strcmp(const char *s1, const char *s2)
{
char *ptr = s1 + strlen(s1);
while (*s2 != '\0') {
*ptr++ = *s2++;
}
*ptr = '\0';
return s1;
}
```
---
#### Q: Complete binary search
寫一個二元搜尋法, 也是算比較簡單的問題
```C=
void binary_search(int *arr, int len, int target)
{
int right = len - 1, left = 0, mid = 0;
while (right >= left) {
mid = (right + left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else if (arr[mid] > target) {
right = mid - 1;
} else if (arr[mid] == target) {
printf("Found it\n");
return;
}
}
printf("Not found\n");
}
```
---
#### Q: Macro
寫一個define可以回傳兩個數字中的最大值
寫一個define可以回傳陣列長度
set bit, clear bit and toggle bit use macro
兩題都是考條件運算式(conditional expressions)和巨集而已
需要注意的是要記得把變數刮起來
計算陣列這題一般而言這樣寫就可以交卷了
不過因為巨集不做型別檢查, 所以在Linux kernel裡面會多一個檢查的機制
Linux kernel定義路徑: include/linux/kernel.h
>[Linux Kernel: ARRAY_SIZE()](http://frankchang0125.blogspot.com/2012/10/linux-kernel-arraysize.html)
```C=
/* MAX */
#define MAX(a, b) ((a)>(b))?(a):(b)
/* numbers of array element */
#define ARRAY_SIZE(arr) (sizeof(arr)/sizeof(arr[0]))
/* set bit */
#define set_bit(b, n) ((b) |= ((n)<<1))
/* clear bit */
#define clear_bit(b, n) ((b) &= ~((n)<<1))
/* toggle bit */
#define toggle_bit(b, n) ((b) ^= ((n)<<1))
```
---
#### Q: 大小寫轉換
大寫轉小寫, 小寫轉大寫
大寫'A'在ascii是65
小寫'a'在ascii是97
兩個差32, 所以也就是說大寫加32就會變小寫, 反之
```C=
char convert(char c)
{
if (c >= 'A' && c <= 'Z')
return c + 32;
else if (c >= 'a' && c <= 'z')
return c - 32;
else
return 0;
}
```
---
#### Q: 輸入3個數, 找出最大和最小值
```C=
struct ret_val {
int max;
int min;
};
struct ret_val find(int a, int b, int c)
{
struct ret_val ret;
ret.max = 0;
ret.min = 0;
if (a > b) {
if (a > c) {
ret.max = a;
} else {
ret.max = c;
}
} else {
if (b > c) {
ret.max = b;
} else {
ret.max = c;
}
}
if (a < b) {
if (a < c) {
ret.min = a;
} else {
ret.min = c;
}
} else {
if (b < c) {
ret.min = b;
} else {
ret.min = c;
}
}
return ret;
}
```
---
### Sort
算是常見題目了, 有些是填空題, 有些是直接手寫
>[【Day23】[演算法]-插入排序法Insertion Sort](https://ithelp.ithome.com.tw/articles/10277360)
>[【Day22】[演算法]-選擇排序法Selection Sort](https://ithelp.ithome.com.tw/articles/10276719)
>[[演算法] 快速排序法 (Quick Sort)](https://ithelp.ithome.com.tw/articles/10202330)
#### Bubble sort
初學者會接觸到的第一個排序法
概念就是兩兩互換, 最大或最小的值讓它跑到最右邊
```C=
void bubble_sort(int *arr, int len)
{
int tmp = 0;
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
if (arr[j] < arr[i]) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}//for
}//
```
---
#### Insertion sort
```C=
void insertion_sort(int *arr, int len)
{
int key = 0, j = 0;
for (int i = 1; i < len; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && key < arr[j]) {
arr[j+1] = arr[j];
j -= 1;
}
arr[j+1] = key;
}
}
```
#### Selection sort
```C=
void selection_sort(int *arr, int len)
{
int min = 0, tmp = 0;
for (int i = 0; i < len; i++) {
min = i;
for (int j = i + 1; j < len; j++) {
if (arr[min] > arr[j])
min = j;
}
/* 如果本身就是最小, 多這個if可以避免自己跟自己交換 */
if (i != min) {
tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}//for
}//
```
---
#### Quick sort
可以選擇直接背起來比較快
把第1個當成pivot
```C=
void quick_sort(int *arr, int left, int right)
{
int i = left, j = right, p = arr[left], tmp = 0;
if (left >= right) return;
while (i != j) {
while (p < arr[j] && i < j) j--;
while (p >= arr[i] && i < j) i++;
if (i < j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
arr[left] = arr[i];
arr[i] = p;
quick_sort(arr, left, i-1);
quick_sort(arr, i+1, right);
}
```
把最後一個當成pivot, 要多一個partition
```C=
int partition(int *arr, int left, int right)
{
int p = arr[right], i = left - 1, tmp = 0;
for (int j = left; j < right; j++) {
if (arr[j] <= p) {
i++;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
tmp = arr[i+1];
arr[i+1] = arr[right];
arr[right] = tmp;
return i + 1;
}
void quick_sort(int *arr, int left, int right)
{
int mid = 0;
if (right > left) {
mid = partition(arr, left, right);
quick_sort(arr, left, mid-1);
quick_sort(arr, mid+1, right);
}
}
```
---
### Linked-list
必考題, 不管怎樣一定要加減念一下
考卷都是考題組或是考程式填空, 當然也有要重頭寫的
不管是面試軟體還是韌體都算是一定要準備的題目
#### Data structure
基本結構
Linux kernel是採用雙向連結
>[Linux内核链表——看这一篇文章就够了](https://zhuanlan.zhihu.com/p/546794612)
>[linux/tools/include/linux/types.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/types.h#L84)
```C
struct list_head {
struct list_head *next, *prev;
};
```
會發現list_head裡面沒有data相關的member
這種結構稱為Intrusive Linked List
這樣做的好處是可以處理泛型
但是一般面試都是考單向鏈結, 所以寫底下這個就夠了
```C=
struct listNode {
int data;
struct listNode *next;
};
```
---
#### Append node
把node加在list最後面
簡單的做法就是走完一整個list, 然後加上去
如果list是空的, 就直接加上去
>[Insertion in Linked List](https://www.geeksforgeeks.org/insertion-in-linked-list/)
底下的寫法是不回傳的方法, 所以傳入head的時候需要用pointer to pointer來確保資料有在function裡面更動
>[Linux Kernel 中的数据结构——泛型 LinkedList](https://studymakesmehappy.club/posts/linux-kernel-%E4%B8%AD%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E6%B3%9B%E5%9E%8B-linkedlist/)
```C=+
void append(struct listNode **head, int data)
{
struct listNode *new_node = NULL, *curr = *head;
new_node = (struct listNode *)malloc(sizeof(struct listNode));
if (new_node == NULL) return;
new_node->next = NULL;
new_node->data = data;
if (curr == NULL) {
*head = new_node;
return;
}
while (curr->next) curr = curr->next;
curr->next = new_node;
}
```
---
#### Push node
node加在最前面
```C=+
void push(struct listNode **head, int data)
{
struct listNode *new_node = NULL;
new_node = (struct listNode *)malloc(sizeof(struct listNode));
if (new_node == NULL) return;
new_node->next = *head;
new_node->data = data;
*head = new_node;
}
```
---
#### Print list
也算是最基本的題目了, 就是把所有node走過一次, 不過如果node有cycle的話就需要額外處理
底下這段是假設沒有cycle
```C=+
void print_list(struct listNode *head) {
struct listNode *ptr = head;
while (ptr->next) {
printf("%d->", ptr->data);
ptr = ptr->next;
}
printf("%d\n", ptr->data);
}
```
---
#### Delete node
刪除給定的節點, 我這邊是實作給一個數值, 然後刪除該數值
這樣寫會導致只能刪除遇到的第一個, 如果後面有重複的會刪不到
所以又寫了一個刪除指定位置的
>[Linked List: 新增資料、刪除資料、反轉](http://alrightchiu.github.io/SecondRound/linked-list-xin-zeng-zi-liao-shan-chu-zi-liao-fan-zhuan.html)
```C=+
/* delete node by value */
void delete_node_value(struct listNode **head, int data) {
struct listNode *prev = NULL;
struct listNode *curr = *head;
while (curr && curr->data != data) {
prev = curr;
curr = curr->next;
}
if (curr == NULL) {
printf("Node doesn't exits\n");
} else if (*head == curr) {
prev = curr;
free(curr);
curr = NULL;
} else {
prev->next = curr->next;
free(curr);
curr = NULL;
}
}
/* delete node by position */
void delete_node_position(listNode **head, int pos)
{
struct ListNode *prev = NULL;
struct ListNode *curr = *head;
int i = 0;
if (pos < 0) return; //Not allowed -1,-2...
while (curr && i != pos) {
prev = curr;
curr = curr->next;
i++;
}
if (curr == NULL) {
printf("Node doesn't exits\n");
} else if (*head == curr) {
*head = curr->next;
free(curr);
curr = NULL;
} else {
prev->next = curr->next;
free(curr);
curr = NULL;
}
}
```
>[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
>indirect pointer操作, 有點複雜, 但是很值得一看
---
#### Insert node after a given position
插入node在給定的position之後
沒特別檢查輸入進來的pos, 所以如果輸入進來的pos大於list長度, 那就會直接接在最後一個後面
```C=+
void insert_node_after(struct listNode **head, int pos, int data)
{
struct listNode *new_node = NULL;
struct listNode *curr = *head;
int i = 0;
new_node = (struct listNode *)malloc(sizeof(struct listNode));
if (new_node == NULL) return;
new_node->next = NULL;
new_node->data = data;
if (*head == NULL || pos < 0) return;
while (curr->next && pos != i) {
curr = curr->next;
i++;
}
new_node->next = curr->next;
curr->next = new_node;
}
```
---
#### Q: Remove Duplicates from Sorted List (leetcode 083)
>[題目網址](https://leetcode.com/problems/remove-duplicates-from-sorted-list/)
>給一個list, 移除重複的
>input: 1->1->2->3, output: 1->2->3
概念大概就是反正他是排序過的list, 所以重複的一定連在一起
所以就是把指標挪到下下一個, 跳過去就好
然後大多數linked-list的題目第一步通常都是把head空的情況先回傳回去
```C=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplicates(struct ListNode* head){
struct ListNode *curr = head;
if (head == NULL) return head;
while (curr) {
if (curr->next != NULL && curr->next->val == curr->val) {
curr->next = curr->next->next;
} else {
curr = curr->next;
}
}
return head;
}
```
---
#### Q: Linked List Cycle (leetcode 141)
>[題目網址](https://leetcode.com/problems/linked-list-cycle/)
>給一個list, 回傳是否有cycle
>有的話回傳true, 沒有回傳false
>pos是cycle開始的位置
>input: 3->2->0->-4, pos = 1, output: 1
用[快慢法](https://zh.wikipedia.org/zh-tw/Floyd%E5%88%A4%E5%9C%88%E7%AE%97%E6%B3%95)來解,
用兩個pointer, 一個跑比較快, 一個跑比較慢, 當相遇時就代表有cycle
```C=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode *slow = head, *fast = head;
int cycle_loc = 0;
if (head == NULL) return false;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
cycle_loc++;
}
return false;
}
```
---
#### Q: Reverse Linked List (leetcode 206)
>[題目網址](https://leetcode.com/problems/reverse-linked-list/)
>給一個list, 把list反轉
>input: 3->2->0->-4, output: -4->0->2->3
改變指標的指向就好, 用3個指標去存前中後
```C=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode *next = NULL;
struct ListNode *curr = head;
struct ListNode *prev = NULL;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev;
return prev;
}
```
---
#### Q: Merge Two Sorted Lists (leetcode 21)
>[題目網址](https://leetcode.com/problems/merge-two-sorted-lists/)
>給兩個已經排序好的list, 合併成一個list並且也是要排序好的
>input: list1: 1->2->4, list2: 1->3->4, output: 1->1->2->3->4->4
一般做法就是開一個空的list, 然後比較小的先放進去
最後假如其中一個list還有東西的話, 必定都是比較大的值, 直接接上去就好
最後要回傳的是新的list的next, 因為第一個node是NULL
```C
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode *ans = malloc(sizeof(struct ListNode));
struct ListNode *ptr = ans;
if (list1 == NULL) return list1;
if (list2 == NULL) return list2;
while (list1 && list2) {
if (list1->val < list2->val) {
ptr->next = list1;
list1 = list1->next;
} else {
ptr->next = list2;
list2 = list2->next;
}
ptr = ptr->next;
}
if (list1) {
ptr->next = list1;
} else {
ptr->next = list2;
}
return ans->next;
}
```
>這樣寫最直觀最好理解, 不過會需要開一個新的空間
>[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E5%BE%9E-Linux-%E6%A0%B8%E5%BF%83%E7%9A%84%E8%97%9D%E8%A1%93%E8%AB%87%E8%B5%B7)
>這篇的 "案例探討: LeetCode 21. Merge Two Sorted Lists"裡面有很詳細的介紹其他解法
>(神跟人看到的東西就是不一樣)
---
#### Q: Implement a Queue and Stack by linked-list
>[你所不知道的 C 語言：物件導向程式設計篇](https://hackmd.io/@sysprog/c-oop)
用linked-list實作queue和stack
方法很多, 就看資料結構要怎麼設計
Queue
```C=
struct linked_list {
struct linked_list *next;
uint8_t data;
};
struct Queue {
struct linked_list *head, *tail;
void (*qpush)(uint8_t);
void (*qpop)();
};
struct Queue queue = NULL;
void qpush(uint8_t val)
{
struct linked_list *tmp = malloc(sizeof(struct linked_list));
tmp->next = NULL;
tmp->val = val;
if (queue->head == NULL)
queue->head = tmp;
else
queue->tail->next = tmp;
queue->tail = tmp;
}
void qpop()
{
struct ListNode *tmp = malloc(sizeof(struct ListNode));
queue->tail->next = NULL;
queue->head = queue->head->next;
if (queue->head == NULL)
queue->tail = NULL;
free(tmp);
tmp = NULL;
}
void init_queue(struct Queue **q)
{
*q = (struct Queue *)malloc(sizeof(struct Queue));
if (*q == NULL) return;
(*q)->head = NULL;
(*q)->tail = NULL;
(*q)->qpush = qpush;
(*q)->qpop = qpop;
}
int main(void)
{
init_queue(&queue);
list.push(1);
list.push(2);
list.push(3);
list.pop();
list.push(4);
list.pop();
}
```
Stack (TODO)
```C=
struct linked_list {
struct linked_list *next;
uint8_t data;
};
struct Stack {
struct linked_list *top;
void (*spush)(uint8_t);
void (*spop)();
};
struct Stack stack = NULL;
void spush(uint8_t val)
{
struct linked_list *tmp = malloc(sizeof(struct linked_list));
tmp->next = NULL;
tmp->val = val;
if (stack->head == NULL)
stack->head = tmp;
else
stack->top->next = tmp;
queue->tail = tmp;
}
void spop()
{
struct ListNode *tmp = malloc(sizeof(struct ListNode));
queue->tail->next = NULL;
queue->head = queue->head->next;
if (queue->head == NULL)
queue->tail = NULL;
free(tmp);
tmp = NULL;
}
void init_stack(struct Stack **s)
{
*q = (struct Queue *)malloc(sizeof(struct Queue));
if (*q == NULL) return;
(*q)->head = NULL;
(*q)->tail = NULL;
(*q)->qpush = qpush;
(*q)->qpop = qpop;
}
int main(void)
{
init_stack(&stack);
list.push(1);
list.push(2);
list.push(3);
list.pop();
list.push(4);
list.pop();
}
```
---
#### Q: 移除值為偶數的node
```C=
void delete_node_even(struct ListNode **head)
{
struct ListNode *prev = NULL, *next = NULL, *tmp = NULL;
struct ListNode *curr = *head;
if (curr == NULL) return;
while (curr) {
if (!(curr->val & 1)) {
tmp = curr;
if (prev == NULL) {
curr = curr->next;
*head = curr;
} else {
next = curr->next;
prev->next = next;
curr = next;
}
free(tmp);
tmp = NULL;
} else {
prev = curr;
curr = curr->next;
}
}
}
```
---
#### Q: Copy list
copy一模一樣的list
```C=
struct ListNode *copy_list(struct ListNode *head)
{
struct ListNode *tail = NULL;
struct ListNode *new_list = NULL;
struct ListNode *curr = head;
if (head == NULL) return NULL;
new_list = (struct ListNode *)malloc(sizeof(struct ListNode));
new_list->val = curr->val;
new_list->next = NULL;
tail = new_list;
curr = curr->next;
while (curr) {
tail->next = (struct ListNode *)malloc(sizeof(struct ListNode));
tail = tail->next;
tail->val = curr->val;
tail->next = NULL;
curr = curr->next;
}
return new_list;
}
```
---
## MCU
系統場比較愛問的東西(個人經驗), 新鮮人的話大部分都是問在學校實驗過那些protocol
做過哪些照實回答即可, 如果可以的話建議回答的越詳細越好
有使用過示波器或邏輯分析儀(Logic Analyzer LA)量測過訊號的話, 加分很大, 可以特別提出來
其實幾乎所有底層操作都是去操作register, STM32裡面的HAL lib也不例外
所以如果有直接對底層操作過的經驗而不是都用別人寫好的lib加分很大
---
### Interrupts
中斷這個機制在MCU的開發中很常使用, 為了要做到一些低功耗的開發, 中斷是一定會用到的, 所以也算是必考之一
#### Q: 請說明底下程式哪裡需要改
>題目來源
>[中斷 (Interrupts)](https://blog.xuite.net/tzeng015/twblog/113273155#)
```C=
__interrupt double compute_area(double radius)
{
double area = PI * radius * radius;
printf("nArea = %f"， area);
return area;
}
```
---
### GPIO
>[STM32-3 GPIO初探 ](https://ithelp.ithome.com.tw/articles/10284264?sc=rss.qu)
>stm32的gpio簡介, 要看的話記得去看留言區
GPIO(General-Purpose Input/output)
算是所有protocol的基本類型了, 通常學校實習課一定會用到
```
GPIO大致分成input和output, 這個稱為direction
output可以設定要輸出High or Low, input則是可以讀取外部的電壓資訊是High or Low
input讀回來的電壓值通常都是讀到超過3V就會判定High, 反之就是Low
所以在做電路設計時, 要避免讓電壓處於臨界值, 這樣很容易誤判
詳細的判定值要看datasheet來決定
```
最後補充一點, 如果gpio是input的話最好預設要pull-high or pull-low
不要floating, 不然很容易誤判
>[[問題] 為什麼會有floating 這種狀態？](https://www.ptt.cc/bbs/Electronics/M.1515253667.A.26D.html)
>[為什麼 GPIO input 要用 pull-up/pull-down，output 要用 push-pull 或 open-drain?](https://tfing.blogspot.com/2019/10/gpio-input-pull-uppull-downoutput-push.html)
---
### ADC
>[ADC](http://wiki.csie.ncku.edu.tw/embedded/STM32F429-ADC)
>[[Day 19] STM32 ADC 類比數位轉換器](https://ithelp.ithome.com.tw/articles/10300851)
>[单端（Single-Ended）模式与差分（Differential）模式的区别](https://blog.csdn.net/qq_34447192/article/details/101208745)
ADC(Analog-to-digital Coverter)
也算是很常遇到的應用
主要功能就是把類比連續的訊號轉成數位離散的訊號
既然扯到轉換, 那當然就要考慮到解析度以及取樣率
進來電壓的計算方式需要去看datasheet
使用ADC前一定要記得校正, 不然值很容易出錯
---
#### Q: 請簡單介紹ADC的檢測方式
有被某間做面板的問過, 所以還是把它放上來
| Single-ended | Differential |
| ------------------------ |:-------------------------- |
| **量測點與ground的比較** | **會有兩個量測點互相比較** |
---
### I2C
>[【Day21】I2C的介紹](https://ithelp.ithome.com.tw/articles/10278308)
>google搜尋I2C的第一個搜尋結果, 沒接觸過的話一定要看完
I2C (Inter-Interated Circuit)
很常見的protocol, 幾乎所有場合都用的到
尤其是做IoT相關的, 一堆device都是用I2C在傳輸的
```
傳輸方式大概就是靠device上的address
master先用start condition加上address告訴device要溝通了
device再回傳1個ACK告訴master說我有收到, 然後接下來每8個bit會回傳1個ACK給master
所以一般的device如果是7-bit address的話, master存取一次device通常要送18個bits
去掉start condition, 7-bit address + R/W bit + ACK + data(8bit) + ACK
```
大致上都是這樣, 主要還是要看datasheet怎麼寫
我就遇過藉著I2C的名義, 但是跟平常用的完全不一樣
---
### SPI
>[SPI](http://wiki.csie.ncku.edu.tw/embedded/SPI)
SPI(Serial Peripheral Interface)
也算常見, 不過我遇到的device還是I2C居多
通常都是一組SPI接一個device
也有一組SPI接多個device, 不過這樣的話通常要看driver有沒有支援
如果沒有driver處理, 可能就要自己去控制CS(chip select) pin
不然常見的做法是會接一顆MUX去做切換, 同樣的方法也會用在I2C
```
主要由4根pin組成:
MISO(Master Input Salve Output)
MOSI(Master Output Salve Input)
SCLK(Serial Clock)
CS(Chip Select)
其中傳輸模式有分同步以及非同步
同步傳輸就是master和slave clock共用clock, 非同步則是各自有自己的clock
```
#### Q: 簡介clock phase(CPHA) and clock polarity(CPOL)
以新鮮人來說算偏難的問題, 因為通常來說MCU會幫你處理好很多問題
通常只要去call MCU提供的lib就可以傳輸了
```
CPHA:
表示要在哪個edge取值, 可以是第一個或是第二個
CPOL:
clock閒置時的電位, 通常都是High
```
---
Sign in with Wallet
Connect another wallet