# 資訊科技產業專案設計課程作業 4
###### tags: `資訊科技產業專案設計`
>貢獻者: 鵰民 Eagle
## 作業要求
1. 自 [IC 產業結構和軟體工程師的機會](https://hackmd.io/@sysprog/BkE4X5vvF) 列出的 IC 設計公司的官方網站中，找出較符合自身興趣/規劃的職務描述 (即 JD，至少找出二份)
2. 分析上述職缺所需要的能力，探討自己在專業上匹配的程度
3. 嘗試列出上述職缺 (或類似的職缺) 的面試題目，可以是網路搜尋整理，也可以自行改寫
4. 在不揭露自身資訊的狀況下，比照第一次和第二次作業的問答形式，對面試題目進行問答，文字紀錄即可。避免只用教科書內容回答，儘量搭配自己過去 (或近期學習到) 的程式開發經驗，進行自問自答
# 職缺
## MediaTek
[Embedded Linux System Software Engineer(CPU)](https://careers.mediatek.com/eREC/JobSearch/JobDetail/MTK120200724001?langKey=en-US)
### 職務描述
* Job Description
1. Write or port device drivers
2. Write hardware module testing program
3. Perform hardware module pre- and post-silicon validation
4. Analyze system issues
5. Analyze power consumption and improve performance or power
* Requirement
1. Familiar with embedded Linux software development
2. Familiar with CPU(ARM like) architecture and RTOS
3. Strong programming skills in C
4. Knowledge and experience with Linux device driver and kernel
### 分析職務描述
JD的部份要開發跟移植裝置驅動程式，所以需要了解 CPU 架構跟 RTOS，之所以要很懂 C 語言而不是熟悉 C 語言，主要應該是為了克服在移植時可能會發生的 Undefined Behavior 跟 Unspecified behavior 詳見 [C11 附錄 J - Portability issues](http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf)，這部份包含在分析系統問題(system issues)所以要會用工具像是 [Santizer](https://github.com/google/sanitizers)(UBSan/ASan)、Valgrind, etc. 至於分析 power consumption 這我還不知道要怎麼做。
## Google
[Linux System Software Developer
](https://careers.google.com/jobs/results/75519189055349446-linux-system-software-developer/)
### 職務描述
由於 Google 的 JD 篇幅較長，這邊只摘錄重點
* Minimum qualifications:
1. Experience working on the Linux kernel.
2. Experience with C or C++.
* Preferred qualifications:
1. Experience in configuring the Linux kernel and curating the core userspace libraries for optimal operation in memory constrained environments.
2. Expertise in one of the following areas: microcontroller/SoC firmware development, system-level RTOS development (IPC, synchronization primitives, etc.), low-level peripheral drivers & hardware bringup, embedded system security, performance optimization and power management for ARM processors, system-level development, middle layer frameworks/APIs.
3. Understanding or willingness to learn about Linux initial boot, uboot (or other bootloaders), building boot images, kernel architecture, low-level driver.
### 分析職務描述
從 Minimum qualifications 可以看出需要 C 語言跟 C++，但是我不知道 google 的有經驗是什麼程度？而如果從 Preferred qualifications 來看，只有第3點的 willingness 我有，雖然第2點列出了很多，但應該只要有其中幾項就可以了。
這個職位似乎是為各種硬體開發 driver，多數的時候是硬體供應商提供，但必要的時候必須從無到有開發出自己的 driver，再觀察 Responsibilities 後，主要應該是為 AR 開發 driver 之外，還要能想出一系列的解決方案，除此之外還要能夠跟其它部門合作所以溝通能力也很重要。
# 自我檢視
* 雖然懂得用指標的指標這樣的技巧，但缺乏開發經驗跟不熟悉C語言，因此要多做 side Projects 跟研讀[你所不知道的 C 語言](https://hackmd.io/@sysprog/c-prog/%2F%40sysprog%2Fc-programming)還有規格書來補強
* 由於是半路出家來學 Linux 的新手，不懂的東西還很多，也沒寫過 device driver，對於作業系統、編譯器、CPU 等底層只有科普般的了解
* 對改善效能跟撰寫優雅的程式碼有強烈的興趣
* 會使用基本的 Linux 指令跟部份開發工具 Git、ASan、Valgrind
* 會使用基本的 x86 SIMD intrinsics
---
# 模擬面試
🧔：interviewer 👶：interviewee
🧔： 請問下面這段程式碼中 printf 會印出什麼？
```c=
int a = 10;
int b = 20;
int max_ptr = &(a > b? a: b);
printf("*max_ptr = %d", *max_ptr);
```
👶： 什麼都不會印出來，因為第三行是錯的，依據 [C99 6.5.15](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) 三元運算子並不會回傳 lvalue 所以無法使用 address of operator 取得位置。
🧔： 沒錯，那麼要怎麼修改才會對？
👶： 要把第三行改成 `int max_ptr = a > b? &a: &b;`
🧔： 沒錯，那麼請解釋一下什麼是 lvalue？
👶： 簡單來說 lvalue 為包含了記憶體位置的 value，因此能夠用指標來指向它的位置，進而修改 value，由此可知 `l` 並不是 `left` 而是 `locator`。
🧔： Undefined behavior 跟 Unspecified behavior
👶： undefined behavior 是程式的行為在 C 語言規格書中沒有其規範，Unspecified behavior 指程式行為依據編譯器跟平台而定
🧔： 請舉一個 Unspecified behavior 的例子
👶： 下面這段程式碼如果 main 是 `return sum(foo(), bar())` 的話會顯示 `bar foo`，但如果是 `return foo() + bar()` 則會顯示 `foo bar`
```c=
#include <stdio.h>
int foo(){
printf("%s ", __FUNCTION__);
return 1;
}
int bar(){
printf("%s ", __FUNCTION__);
return 2;
}
int sum(int i, int j) {
return i + j;
}
int main() {
return sum(foo(), bar());
// return foo() + bar();
}
```
👶： 一般來說預期 `sum(foo(), bar())`，會輸出 `foo bar`，不過C語言的規範中並沒有指定參數的解析順序，所以參數的解析順序是依照編譯器而定，這裡使用的編譯器是 GCC。
C99 §6.5.2.2 10
>The order of evaluation of the function designator, the actual arguments, and
subexpressions within the actual arguments is unspecified, but there is a sequence point
before the actual call.
[leetcode 21 mergeTwoLists](https://leetcode.com/problems/merge-two-sorted-lists/)
🧔： 如果今天給你兩條排序好的串列，並回傳合併的結果，比如說 `[1,2,4]` 跟 `[1,3,4]`合併成 `[1,1,2,3,4,4]`，而 ListNode 的結構如下
```C
struct ListNode {
struct ListNode *next;
int val;
}
```
👶： 會傳入串列的長度範圍為何？節點的 val 範圍大小？
🧔: 串列的長度為 0 到 50 個，節點的範圍為 -100 到 100
👶: 那麼傳入的兩條串列長度會一樣嗎？
🧔: 不一定，有長有短甚至可兩個都是空串列
👶: 因為是升序合併也就是由小排到大，那麼可以先比較 l1 跟 l2 節點的值，然後將值小的節點放前面，並接上剩下合併好的串列，pseudocode 如下，可以用遞迴的方式將 l1 跟 l2 合併再一起，如果傳入的是空串列，就回傳不是空的那一條串列，比如說如果 l1 是空的，就回傳 l2。
```javascript=
func mergeTwoLists(l1, l2) {
if(!l1 || !l2)
return l1? l1: l2;
if(l1.val < l2.val)
return l1.next(mergeTwoLists(l1.next, l2));
else
return l2.next(mergeTwoLists(l1, l2.next));
}
```
🧔: 那麼用 C 語言把虛擬碼實作出來吧
👶:
```c=
struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {
if(!l1 || !l2)
return l1? l1: l2;
if(l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
```
🧔: 你可以分析一下遞迴的時間跟空間複雜度嗎。
👶: 好的，這題由於是用遞迴，函式在記憶體不斷的堆疊直到執行到執行終止條件才會一步一步釋放，所以空間複雜度為 $O(N)$，而因為要走訪兩條串列，所以一般的情況下時間複雜度為 O(N)，最差的情況是走訪完兩條串列，其時間複雜度為 $O(M + N)$, M 跟 N 分別為 l1 跟 l2 的長度。
🧔: 舉一個最差情況下的 case
👶: 比如說 `l1 = [1,3,5]` 跟 `l2 = [2,4,6]`，l1 跟 l2 會輪流去接上下個節點，無法提早結束只能夠完整走訪完兩條串列。
🧔: 那麼你有辦法將遞迴轉成迭代嗎？
👶: 關於迭代，我有一些想法想討論一下
🧔: 請說
👶: 迭代有兩種作法，一種是先建立一個節點 result，然後用指標 ptr 去指向它，接著合併的時候用 `ptr->next` 去接上下個節點，合併完再回傳 result 的 next，這麼做會浪費一個節點。
👶: 另一種是用指標的指標 indir 去更新 result 每個節點的位置，要更新節點的時候對 indir 做 dereference 回傳 result 再去指向要合併的節點，這種方法合併完 l1 跟 l2 後只要回傳 result 就好，**跟上個作法不同的地方在於從接上節點改成更新節點位置**
🧔: 指標的指標不會浪費節點，那你就用指標的指標來實作吧
👶: 那麼先建立一個指標 result，再用指標的指標 indir 去指向 result，因為 result 是指標，要透過 `&` 變成指標的指標才會跟 indir 的型態相符，接著去合併 l1 跟 l2，將 val 小的節點更新到 result，假設 l1 比較小，這時候 dereference indir 去指向 l1，那麼 dereference indir 會回傳 result，此時 result 就從 NULL 變成 l1，因為還要合併剩下的節點，所以要更新 l1 到下個節點。
👶: 更新好 result 目前的位置後再將 indir 去指向 result 的下個位置，進入下一輪迴圈的時候才會把要合併的節點更新到 result 的下一個位置
👶: 因為 while 是用 l1 and l2，表示說只要其中一條串列走訪完畢就會結束迴圈，因此要把沒走訪完的串列接上(`*indir = l1? l1: l2`) 接完後表示合併完畢，這時候就可以回傳 result 了
```c=
struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {
struct ListNode *result = NULL;
struct ListNode **indir = &result;
while(l1 && l2) {
if(l1->val < l2->val) {
*indir = l1; // result = l1
l1 = l1->next;
} else {
*indir = l2;
l2 = l2->next;
}
indir = &(*indir)->next;
}
*indir = l1? l1: l2;
return result;
}
```
🧔: 如果 indir 是指標而不是指標的指標，發生什麼事？
👶: 如果是指標 *indir，則 indir = l1，只是將 indir 從 result 指向 l1。最後只會回傳 NULL
#### 圖解：
參考你所不知道的C語言 :arrow_right: [指標篇](/@sysprog/c-prog/%2Fs%2FHyBPr9WGl)、[linked list 和非連續記憶體操作](/@sysprog/c-prog/%2Fs%2FSkE33UTHf)
```c=
struct ListNode *result = NULL;
struct ListNode **indir = &res;
*indir = l1;
```
如果是指標的指標 ``**indir`` ，則 `*indir = l1` 時, `*indir` 會回傳 `result` 這個節點，相當於 `result = l1`
```graphviz
digraph list {
node[shape=record];
rankdir=LR;
edge[tailclip=false, arrowtail=dot, arrowhead=vee,dir=both]
indir [label="{*indir\n(deref)|<next>}", width=1.2]
result [label="{result|<next>}", width=1.2]
node1 [label="{node1|<next>}", width=1.2]
node2 [label="{node2|<next>}", width=1.2]
node3 [label="{node3|<next>}", width=1.2]
node4 [label="{node4|<next>}", width=1.2]
subgraph cluster {
color="#eeeeee";
style=filled;
label="l1"
node1:next:c->node2;
node2:next:c->node3;
node3:next:c->node4;
}
indir:next:c->result
result:next:c->node1
}
```
```c=
struct ListNode *result = NULL;
struct ListNode *indir = result;
indir = l1;
```
如果是指標 ``*indir``，則 ``indir = l1``，只是將 `indir` 從 `result` 指向 `l1`。
```graphviz
digraph list {
node[shape=record];
rankdir=LR;
edge[tailclip=false, arrowtail=dot, arrowhead=vee,dir=both]
indir [label="{indir|<next>}", width=1.2]
result [label="{result|<next>}", width=1.2]
node1 [label="{node1|<next>}", width=1.2]
node2 [label="{node2|<next>}", width=1.2]
node3 [label="{node3|<next>}", width=1.2]
node4 [label="{node4|<next>}", width=1.2]
subgraph cluster {
color="#eeeeee";
style=filled;
label="l1"
node1:next:c->node2;
node2:next:c->node3;
node3:next:c->node4;
}
indir:next:c->node1
}
```
🧔: 你認為指標的指標迭代版，還有沒有改進的空間？
👶: 仔細觀察了一下還可以再用一個指標的指標來重構程式碼？
🧔: 怎麼說呢？
👶: 因為要判斷 l1 還是 l2 小，再把小的節點更新到 `result`，完畢後再把 l1 或是 l2 更新到下一個，如下所示
```c
if(l1->val < l2->val) {
*indir = l1;
l1 = l1->next;
}
```
👶: 可以再用一個指標的指標 `node` 來指向小的節點，這樣子無論是更新到 `result` 或是更新到 next 都不用管是 l1 還是 l2 了
```c=
struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {
struct ListNode *result = NULL;
struct ListNode **indir = &result;
struct ListNode **node = NULL;
while(l1 && l2){
node = l1->val < l2->val? &l1: &l2;
*indir = *node;
*node = (*node)->next;
indir = &(*indir)->next;
}
*indir = l1? l1: l2;
return result;
}
```
👶: 用 for 迴圈取代 while 迴圈來提升可讀性。
```c=
struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {
struct ListNode *result = NULL;
struct ListNode **indir = &result;
struct ListNode **node;
for(node = NULL; l1 && l2; *node = (*node)->next) {
node = l1->val < l2->val? &l1: &l2;
*indir = *node;
indir = &(*indir)->next;
}
*indir = l1? l1: l2;
return result;
}
```
補充說明：
英文版 :arrow_right: [link](https://leetcode.com/problems/merge-two-sorted-lists/discuss/1593917/CC%2B%2B-9-lines-after-refactor-pointer-to-pointer-solution-with-explanation)
| expression | dereference | 說明 |
| ------------------------ | ------------------------ | --------------------------------------------------------------- |
| indir = &result; | result | `indir` 指向 result |
| node = &l1; | l1 | 假設比較完 `l1` 跟 `l2` 後， `node` 指向 `l1` |
| *indir = *node; | result = l1; | 將要合併節點更新到 `result` |
| *node = (*node)->next; | l1 = l1->next; | 因為要合併剩下的節點，所以將節點更新到 `next` |
| indir = &(*indir)->next; | indir = &(result)->next; | 將 `indir` 指向 `result->next`. 讓下一輪迴圈更新 `result->next` |
Sign in with Wallet
Connect another wallet