---
# System prepended metadata

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

---

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 哈默迪-Horus

[1920. build array from permutation](https://leetcode.com/problems/build-array-from-permutation)
---
> https://www.youtube.com/watch?v=uMd5cEGXNL4

🥸首先，給定一個長度為n的陣列in，裡面的資料由不重複的0到n-1的整數組成，而我想讓輸出的陣列out[i]=in[in[i]]，你會怎麼解決這個問題

🙂也就是out陣列裡索引值i的資料，會是in陣列索引值i的資料作為新的索引值，再取一次值，而且in陣列的資料會是順序不定的0到n-1。

🥸沒有錯

🙂那我舉個例子以便我更清楚的了解題目，如果輸入陣列是[1,0,2]，那麼輸出陣列就會是
[0,1,2]。

🥸是的

🙂我會宣告一個長度為n的陣列，將這個陣列遍歷一遍，然後根據要求逐個賦值。

```cpp=
class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        vector<int> ans;
        for(int i=0;i<nums.size();i++){
            ans.push_back(nums[nums[i]]);
        }        
        return ans;
    }
};

```

🥸當然，這是一個很直接和簡明易懂的方式，不過既然輸入和輸出的陣列長度是一樣的，你能不能操作原陣列得到結果。

🙂很顯然的，我並不能簡單的以交換操作，這樣會打亂後面索引到的值。不過，從題目的描述，陣列裡的值恰好是一個整數對n取餘數的結果，我們可能可以利用這個特性。

🙂在對輸入陣列取值的時候，改為取值對n的餘數，而在賦值的時候改為加上取到的值乘上n。最後基於c++對整數除法的特性，只需要在最後對陣列除以n就會是所求結果。

```cpp=
class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            nums[i]+=(nums[nums[i]]%nums.size())*nums.size();
        }
        for(int i=0;i<nums.size();i++){
            nums[i]/=nums.size();
        }         
        return nums;
    }
};
```

[2807. insert greatest common divisors in linked list](https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list)
---
> https://www.youtube.com/watch?v=uMd5cEGXNL4&t=230s

🥸接著下一個問題，給定一個鏈結串列，我想在原本鏈結串列相鄰兩節點之間，插入一個值為兩節點最大公因數的節點，那你會怎麼處理這個問題。

🙂我重複一下問題，回傳的鏈結串列會是，輸入的鏈結串列相鄰兩節點之間插入值為兩節點最大公因數的節點後的結果

🥸沒有錯

🙂簡單來說，如果輸入的鏈結串列是18 6 10 9，那麼輸出就會是18 6 6 2 10 1 9。

🥸對的

🙂那我可能會使用兩個指標，分別儲存兩個節點的位址，如果第二個節點為空就結束。接著新宣告一個數值為兩節點數值最大公因數的新節點，並將第一個指標的next指向新節點，而新節點的next指向第二個指標。接著將第二個指標的內容指派給第一個指標，第二個指標的next指派給第二個指標，重複這個操作。

```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode *temp1=head,*temp2=head->next;
        while(temp2!=nullptr){
            temp1->next=new ListNode(__gcd(temp1->val,temp2->val),temp2);
            temp1=temp2;
            temp2=temp2->next;
        }
        return head;
    }
};
```

🥸好，那有沒有可能只使用一個指標。

🙂像你說的，可以把第二個指標所參與的操作，以第一個指標的next取代，而不破壞他的正確性。

```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* p = head;
        while(p->next){
            p->next = new ListNode(__gcd(p->val, p->next->val),  p->next);
            p = p->next->next;
        }
        return head;
    }
};
```

[1929. Concatenation of Array
](https://leetcode.com/problems/concatenation-of-array/)
---
> https://www.youtube.com/watch?v=L4NX7O_tjmM
 
🥸Good evening, appreciate your time, I'm  in charge of this interview.

🙂Good evening.

🥸Alright, from now, I want to know the thinking pattern  when you're programming. Therefore, I have some questions for you.

🙂No problem.

🥸Let's get started. Given an interger array, after processing, the result will be input array repeated twice. How would you solve this problem.

🙂I want to make sure that I didn't misunderstand. You mean output array is an input array appended an input array. 

🥸Precisely.

🙂So if input is 1,2,3 output would be 1,2,3,1,2,3

🥸That's what I mean

🙂OK, I think I will use a new vector, and a for loop doing traversal through input array twice. Simultaneously, append the values in input array to the new vector.

```cpp=
class Solution {
public:
    vector<int> getConcatenation(vector<int>& nums) {
        vector<int> ans;
        for(int i=0;i<nums.size();i++){
            ans.push_back(nums[i]);
        }        
        for(int i=0;i<nums.size();i++){
            ans.push_back(nums[i]);
        }
        return ans;
    }
};
```

🥸Excellent, but what if you could modify input array.

🙂If so, new vector is unnecessary. I will use an interger n to store the length. Then, use a for loop doing traversal through first n elements in the vector and append to it.

```cpp=
class Solution {
public:
    vector<int> getConcatenation(vector<int>& nums) {
        int n=nums.size();    
        for(int i=0;i<n;i++){
            nums.push_back(nums[i]);
        }
        return nums;
    }
};
```

初步檢討
---
* 英文口語發音待加強，詞彙量少

---
## 第二次作業-他評01
### 關於interviewee
### 優點
- 在服飾上的禮儀有注意到
### 可改進的地方
- [00:25](https://youtu.be/uMd5cEGXNL4?si=qqinFhSeNivFz7Do&t=24)可以考慮把題目用一份文字檔傳給面試者，讓他可以比較好理解問題
- 可能要先跟面試者提說要使用什麼語言去作答會比較恰當
- [03:49](https://youtu.be/uMd5cEGXNL4?si=4Cdp6naUsBzyi18z&t=229)這邊感覺有點敷衍面試者的感覺，可以給多一點的回饋，或是提問time complexity之類的問題
### 關於interviewer
### 優點
- 作答流暢，口齒清晰
- 有根據interviewee沒有補充的題目規則以例子來重複做確認
### 可改進的地方
- [02:34](https://youtu.be/uMd5cEGXNL4?si=suuObhiAzkN4gHb1&t=154)可以再多補充改過code後的空間複雜度，加以證實其優點

## 第二次作業-他評02
### Interviewer
- [ ] 優點
* 口齒清晰，講話簡短扼要
* 服裝穿著得體，適合正式場合又不會過於拘謹，給人第一印象很好
- [ ] 可改進的地方
* 三題如果可以舉出實際的應用場景來包裝題目會更好
* 第二題可以再多問一題 follow up，問面試者若不使用 C++ 標準函式庫 `<algorithm>` 中的 `__gcd`，該如何求出最大公因數
* 第三題可以加考如果 input array 改用 linked list，該如何實作，並讓面試者比較 array 和 linked list 的不同，藉此判斷面試者的基礎夠不夠扎實
* 和面試者的互動偏少，感覺比較像是一個出題機器，而較少溝通的成分，做為面試官，可以思考要問哪些問題可以幫助你來判斷一個面試者是否符合公司職位要求

### Interviewee
- [ ] 優點
* 能夠一邊撰寫程式碼一邊解釋，且過程流暢不打結
* 沒有令人煩躁的小動作，整體表現自然大方
- [ ] 可改進的地方
* 第一題的第一種作法很直觀，但第二種作法可以用確認題意時舉的例子來驗證一下程式碼的正確性，即 REACTO 中的 Test
* 第一題根據面試官給的題目描述，並不能直接假設陣列長度 n 一定是正整數，Repeat 時還需要確認陣列是否可能為空
* Repeat 不應該只是單純複誦面試官講的題目，還應該要同時確認題目的 contraint，像是第二題應該詢問面試官輸入的 linked list 是否為 singly linked list，且是否可能為空等
* [6:40](https://youtu.be/uMd5cEGXNL4?si=tXU2-JOnrwmgcoPq&t=400) algorithm 的正體中文翻譯為「演算法」而非「算法」，這次作業有要求應採取[台灣的科技用語](https://hackmd.io/@sysprog/it-vocabulary)
* 第二題也漏掉 Test 的部分，可以稍微舉例來證明實作的正確性