---
# System prepended metadata

title: 2023 年「資訊科技產業專案設計」作業 1

---

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> [模擬面試錄影-1](https://youtu.be/tzNY52QwA2I)
> [模擬面試錄影-2](https://youtu.be/ND10VCttwr0)
> 
> :male-office-worker: Interviewer；:male-student: Interviewee

## [1929. Concatenation of Array](https://leetcode.com/problems/concatenation-of-array/description/)
> [Google Docs](https://docs.google.com/document/d/1WPAYD8GsYkbdKQz_5Dhquhm-7BndPBphClPTCsgV5Ec/edit?usp=sharing)

### Interview

:male-office-worker:第一題給你一個長度為 n 的 array **nums**，需要你寫一個 function 回傳長度為 2n 的 array **ans**。而這個 ans 就是兩份 nums (copy & paste)
:male-student:問題是希望我們 return 一個 array ans，而這個 ans 會剛好是 nums copy 成兩份，像範例 nums=[1,2,1], ans=[1,2,1,1,2,1]。

:male-student:我會先宣告 ans，並使其長度設為 nums 的兩倍，然後再用迴圈給值。

:male-office-worker: 聽起來可行，那你就試試看吧。

```cpp
vector<int> buildArray(vector<int>& nums) {
    vector<int>ans;
    ans.resize(2*num.size());
    for(int i=0;i<num.size()*2;i++){
        ans[i] = nums[i];
    }    
    return ans;
}
```

:male-office-worker: 請你對這份程式碼做時間複雜度和空間複雜度，並想想看有甚麼可以優化的地方。
:male-student: 由於 ans 是固定為 2n，所以空間複雜度的 lower bound 在 O(2N)，而現在這段迴圈跑 2 倍的 nums 的長度，所以時間複雜度是 O(2N)。
:male-student: 可以優化的地方是由於前半和後半是一樣的，所以其實跑一次 0~n 就可以了：
```cpp
vector<int> buildArray(vector<int>& nums) {
    vector<int>ans;
    ans.resize(2*num.size());
    for(int i=0;i<num.size();i++){
        ans[i] = nums[i];
        ans[i+n] = nums[i];
    }    
    return ans;
}
```

## [2807. Insert Greatest Common Divisors in Linked List](https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list/description/)
> [Google Docs](https://docs.google.com/document/d/1duiN9X6JcX5gabproYIYnXQLCx-mixgsfgioNsf9kTg/edit?usp=sharing)

### Interview

:male-office-worker: 第二題是給你一個整數的 Linked List，希望你寫一個 function 為每兩個節點之間加上每兩個節點的值的最大公因數，最後回傳加上最大公因數的 Linked List。
:male-student: 首先，我會先設好結束的條件，也就是當**現在節點**指向 null 並且**下一個節點指向** null，那就不會繼續接下來的操作。

:male-student: 接著，找出**現在節點**和**下一個節點**的最大公因數，並以此為值創建一個新的節點，並將這幾個節點的next做調整，讓其各自指向正確的節點。

:male-office-worker: 聽起來可行，那你就試著做做看吧。

```cpp
ListNode* FindGCD(int v1, int v2){
    while(v1!=0 && v2!=0){
        if(v1>v2){
            v1%=v2;
        }
        else{
            v2%=v1;
        }
    }
    ListNode* newNode;
    if(v1>v2){
	    newNode = new ListNode(v1);
    }
    else{
	    newNode = new ListNode(v2);
    }
    return newNode;
};

ListNode* insertGreatestCommonDivisors(ListNode* head) {
    ListNode * tmp = head;
    while(tmp != null && tmp->next !=null){
        ListNode* insertNode =	FindGCD(tmp->val, tmp->next->val);
        insertNode->next = tmp->next;
        tmp->next = insertNode;

        tmp = insertNode->next;
    }
    return head;
}
```

## [1920. Build Array from Permutation](https://leetcode.com/problems/build-array-from-permutation/description/)
> [Google Docs](https://docs.google.com/document/d/15xaw8lonx8upmPM8j5Nzj0LeRzKRlu0w56Ha-Ckl3eo/edit?usp=sharing)

### Interview

:male-office-worker: Give you a integer array **nums**，build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it。
:male-student: So, First i would create an array ans, and then go through it from 0~n. For each iteration just imply ans[i] = nums[nums[i]];

```cpp
vector<int> buildArray(vector<int>& nums) {
    vector<int> ans;
    int n = nums.size();
    ans.resize(n);
    for(int i=0;i<n;i++){
        ans[i] = nums[nums[i]];
    }
    return ans;
}
```
:male-office-worker: I noticed that you used out-place implementation，can you give another approach using in-plcae implementation?

:male-student: In-place implementation: we can let nums[i] become ```(length of nums)*NewValue (nums[nums[i]]) + OriValue (nums[i])``` , then divide it by length of nums. So, nums[i] would be ```(length of nums)*NewValue/(length of nums)```=NewValue(nums[nums[i]])

```cpp
vector<int> buildArray(vector<int>& nums) {
    int n = nums.size();
    for(int i=0;i<n;i++){
        nums[i] = nums[nums[i]]*n + nums[i];
    }
    for(int i=0;i<n;i++){
        num[i]/=n;
    }
    return nums;
}
```

## 初步檢討

* 程式邏輯可以再解釋清楚一點。
* 說話可以清楚一點、大聲一點(但會吵到室友)，咬蠻多字的。
* 避免冗言贅字和過多的語助詞。
* 專有科技名詞會中英文混著使用。
* 英文會中途跑出中文，需加強練習英文說明的部分。
* 思考的過程會習慣性沉默，應該可以分享當時任何想法。

---

## 第二次作業 - 他評 01
**Interviewer**
優點
- 有先確認雙方是否都有聽到聲音 
- 沒有出現上對下的名詞，整個面試氣氛良好。

可改進處
- 建議可以針對程式碼做進一步的討論，例如：
    - [2:44](https://youtu.be/tzNY52QwA2I?si=FGdlJjS_HH1H--EC&t=164): 為什麼不直接宣告 2n 的大小，而是要使用 resize。
    - [6:31](https://youtu.be/tzNY52QwA2I?si=YNiChciMR78I9OPx&t=391): 面試者修改後實際上存取的次數依舊是 2n 次，但這樣寫帶來的好處是什麼？(參考：[Loop Unrolling](https://en.wikipedia.org/wiki/Loop_unrolling))
- (英) 建議把題目敘述一遍給面試者聽，增加雙方互動。
- (英) [7:36](https://youtu.be/ND10VCttwr0?si=vOm-uKv9p8LgiNDG&t=456): 建議使用討論的方式取代直接告訴面試者存在更佳解。例如：有沒有辦法使用更少的空間。

**Interviewee**
優點
- 有一邊寫一遍進行講解。

可改進處
- [1:06](https://youtu.be/tzNY52QwA2I?si=4k2MrCFHhWWcegGf&t=66): REACTO 中 Repeat 步驟感覺像是在告訴面試官題目，建議更改複誦方式，讓其聽起來更像是在跟面試官確認題意。
- [4:04](https://youtu.be/tzNY52QwA2I?si=olWKS5oG4k5mrJAs&t=244): 影片提到「index 的因素考慮進去」，建議可以直接講考慮的因素，例如：存取到非法記憶體。
- (英) [8:18](https://youtu.be/ND10VCttwr0?si=I__AFmOYX5H4CSh6&t=498): 建議可以更清楚的交代思考的邏輯，而非直接寫出答案。

其他建議
- [11:54](https://youtu.be/tzNY52QwA2I?si=vSbaw4sRdmIy_Q-T&t=714): 不確定翻書是否是可以的，建議可以先與面試官討論。

## 第二次作業 - 他評 02
- [ ] 優點
* 聽下來都說明得很流暢，沒有什麼比較突兀的停頓感
* 在 Appoarch 階段有明確說出自己的想法，並把想法直接列在文件中
* 第二題 [11:37](https://youtu.be/tzNY52QwA2I): 不急著把 `FindGCD()` 實作出來，而是留到後面才實作

- [ ] 可改進之處
* 第二題 [11:37](https://youtu.be/tzNY52QwA2I): `FindGCD()` 可以參考下列的寫法，就可以減去比較 `v1` 與 `v2` 大小的時間
    ```cpp
    ListNode* FindGCD(int v1, int v2){
        // 這裡會自動處理 v1 < v2 的狀況，讓後續保證 v1 > v2
        while(v2 != 0){
            int temp = v2;
            v2 = v1 % v2;
            v1 = temp;
        }
        ListNode* newNode = new ListNode(v1);
        return newNode;
    };
    ```
* 第二題 [17:47](https://youtu.be/tzNY52QwA2I): Testing 時建議可以把過程一樣打在文件中，怕單純用口述的會讓 Interviewer 不好理解
* 第三題 [6:12](https://youtu.be/ND10VCttwr0): 可以把 `i=0, nums[0] = 0, nums[0] = 0` 寫為 `i=0, nums[0] = 0, nums[nums[0]] = 0` 會更為清楚

## 第二次作業 - 他評03
### interviewer
- [ ] 優點
* 語速把控得當
* 咬字清晰
* 有雙向互動

- [ ] 可改進的地方
* 說話有點卡詞
* 有些段落氣音太重

### interviewee
- [ ] 優點
* 有完整做出REACTO
* 編寫程式碼時有做清楚的講解
* 手勢和肢體動作增加表達強度

- [ ] 可改進的地方
* 收音有點模糊