# 2022 年資訊科技產業專案設計課程第 3 次作業

[Resume](https://docs.google.com/document/d/1-hriiH5TaQ9wvpLGD5MgBBjJ-MymPufdBiItL54CM2o/edit?usp=sharing)

### Job Description

[Full-Stack Developer, SA Engineering](https://www.amazon.jobs/en/jobs/2229449/full-stack-developer-sa-engineering)

[Software Engineer III, Front End, Google Cloud Platforms](https://careers.google.com/jobs/results/143604810348667590-software-engineer-iii-front-end-google-cloud-platforms/?distance=50&employment_type=FULL_TIME&q=Full%20Stack)

[Application Engineer, Google Cloud Sales Systems](https://careers.google.com/jobs/results/129249089393959622-application-engineer-google-cloud-sales-systems/?distance=50&employment_type=FULL_TIME&q=Back%20End)

[Software Development Engineer, AWS Galaxy](https://www.amazon.jobs/en/jobs/2241872/software-development-engineer-aws-galaxy)

### 相關能力要求

- 2年以上前端工作經驗 / 全端開發經驗
- 開發大型資料庫和 Data Pipeline 經驗
- ML 和 AI 實作能力
- 1年以上系統設計(System Design)經驗
- 物件導向語言開發經驗
- 客戶溝通能力
- Cloud platform 經驗

### 自身能力評估

- 學歷
- 國立成功大學資訊工程學系 (在學)

- 基本程式能力
- C/C++ : 解題
- Python : 爬蟲、機器學習
- Javascript : 網頁開發

- 機器學習
- 利用 Faster RCNN 實作物件偵測
- 利用 HiTANet 注意力模型實作數值分析

- 前端
- 曾利用 Vue 框架開發網頁專案
- 在 XX 科技實習利用 React 框架開發大型專案，並搭配 Storybook 提升開發效率

- 後端資料庫
- 曾利用 flask 框架搭配 MySQL 資料庫進行專案開發

- Design Pattern
- 修習軟體設計課程，重構 Github 上開源的 C# 專案 (正在進行)

> 欠缺能力

- 後端框架開發經驗
- Data Pipeline 相關知識和實作經驗
- NoSQL 資料庫開發經驗
- System Design 相關知識和實作經驗
- 前端進階技術
- Cloud platform 經驗
- 部署網站經驗

### 面試題目
- 請就你的理解說明 Reacr/ Vue/ Angular 是什麼？他們之間的差別為何？
- JavaScript 的 hoisting 是什麼？
- JavaScript 中非同步與同步操作混用時的輸出順序為何？
- JavaScript 中 promise 和 async await 要解決什麼問題？
- React Redux 要解決什麼問題？
- Cookie、localStorage、sessionStorage 的差別是什麼？
- 有哪些 HTTP Merhods？
- PUT 和 PATCH 兩者差別？
- 請說明你開發一個網站的工作流程
- 有用過什麼後端 Framework？
- HTTP/ WebSocket/ Socket 是什麼？之間的差別為何？
- 用過什麼資料庫(SQL 或 NoSQL)？
- 比較 SQL v.s. NoSQL 優缺點
- 用 ORM 的優缺點是什麼？
- TCP 該如何做流量控制
- C thread 怎麼運作？
- 用過什麼雲端？有用過其中的哪些服務？
- 試說明反向代理器

### 模擬面試

:smiling_imp: : 您好，請你先介紹一下自己。

:boy: : 您好我是 XXX，畢業於成功大學資訊工程學系，大學時期有過 React 和 Vue 框架的前端開發經驗，也有 MySQL 資料庫的開發經驗。除此之外，我的大學專題是利用時序性注意力模型做數值分析，所以也有接觸到機器學習的領域。在大三暑假的業界實習(暑期前端開發實習生)讓我接觸到大型專案的開發，也使用到了 git 版本控制和基本的 Design Pattern。

:smiling_imp: : 你剛剛有提到兩個前端框架開發的經驗，所以想請問你 React 和 Vue 的異同分別是甚麼?

:boy: : 兩者皆採用 virtual DOM 和組件化技術，避免直接對 DOM 的操作，除了提升安全性，也加速網頁的效能。差別是 react 有 jsx 的用法，把 html、css 和 javascript 混用在一起，而 Vue 則是分開來寫。除此之外兩者 diff 的方法也不盡相同。

:smiling_imp: : 請解釋 js 的非同步在甚麼樣的情況會用到?

:boy: : 可能應用的情況有: 跟資料庫拿資料、讀檔案，上述情境可能會需要等待時間，可以把獨立要做的事做完。

:smiling_imp: : 請你比較 SQL 和 NoSQL 的優缺點。

:boy: : sql 的特點是有 table 的概念，在同一個 table 裡面的資料都要有相同的 attribute。nosql 則是偏向 json 檔的概念，資料是用 key - value 的方式儲存，好處是更有彈性，不浪費空間。

:smiling_imp: : 假如今天你從資料庫撈出一筆資料，是以 linked list 的資料結構儲存，而前端用戶希望得到一個由小排到大的資料集，此外資料庫有可能沒有符合的資料也就是 linked list 可以是空的。請說明你的想法是甚麼? 會如何處理?

:boy: : 所以我可以假設題目是給我一個 linked list 然後每個節點都有一個整數的 val 和一個指向下一個節點位置的指標嗎?

:smiling_imp: : 沒錯，可以。

:boy: : 最直覺的做法可以先遍歷一遍整個 linked list 然後把值存入 vector ，再將 vector 排序，最後再把 vector 的值按順序覆寫回題目給的 linked list。如果是空 linked list 就直接 return。這樣做的時間複雜度是 O(nlogn) 因為遍歷 linked list 是 O(n)，vector 排序是 O(nlogn)，覆寫 linked list 則是 O(n)。空間複雜度是 O(n) 因為需要額外開一個和 linked list 長度相同的 vector。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head) return head;
        vector<int> numList;
        ListNode* current = head;
        while (current) {
            numList.push_back(current->val);
            current = current -> next;  
        }
        sort(numList.begin(), numList.end());
        current = head;
        for (int i=0;i<numList.size();i++) {
            current->val = numList[i];
            current = current -> next;
        }
        return head;
    }
};

:smiling_imp: : 可是我們在資料庫撈資料時資料量可能會很大，如果空間複雜度是 O(n) 會很占用記憶體，所以你能不能在時間複雜度不變的情況下把空間複雜度優化到 O(1)?

:boy: : 我麼可以利用兩個指標去找到 linlked list 的中間節點，然後用地回的寫法實作 in-place 的 merge sort。這樣做的時間複雜度是 O(nlogn) 空間複雜度則是 O(1)。

class Solution {
public:
    ListNode* mergeSort(ListNode* head){
        if(!head->next) return head;
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* prev = NULL;
        while (fast && fast->next){
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = NULL;
        return mergeList(mergeSort(head),mergeSort(slow));
    }
    
    ListNode* mergeList(ListNode* subA, ListNode* subB){
        if (!subA) return subB;
        if (!subB) return subA;
        if (subA->val < subB->val) {
            subA->next = mergeList(subA->next, subB);
            return subA;
        }
        else {
            subB->next = mergeList(subA, subB->next);
            return subB;
        }
    }    
    
    ListNode* sortList(ListNode* head) {
        if (head) return mergeSort(head);
        else return head;
    }
};

:smiling_imp: : OK，那我們面試到這邊告一個段落，感謝你今天的參與。