# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 喬喬-JOJO
> Video:
>[模擬面試影片 (漢)](https://youtu.be/sIaAvdn895g)
>[模擬面試影片 (英)](https://www.youtube.com/watch?v=76oVeeQaXWE)

👨‍💻：面試官
🧑‍：面試者
## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/description/)

👨‍💻：我們希望喬喬能實作出一個 function ，將兩個 `list` 依大小合併成一個 `list` 並將其回傳。
🧑‍：請問當兩個 `list` 同時存在相同的 `value` 時，有強制規定哪一個 `list` 的節點優先嗎?用於保持 stable。
👨‍💻：這邊請你將 `list1` 的節點優先合併到 `list` 中。
🧑‍：好的，實作前我們必須先搞懂題目給的 structure ，它包含一個 integer 與一個與其型別相同的指標，這題我會想先創造一個 `dummy head` 作為 `list` 的開頭，選擇使用其中一個建構子來建造，並宣告一個 pointer 指向 `dummy head` ，其用義為指向回傳 `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) {}
};

🧑‍：我使用迴圈解決此問題，首先當兩個 `list` 皆不為空，可以從兩個 `list` 的開頭比較何者之最小者要放入回傳 `list` ，這時我們可以將回傳 `list` 的結尾與剛剛決定出的最小節點相連，並移動 `tail` 使其成為回傳 `list` 的新結尾，值到兩個 `list` 其中一個不在具有節點時，將有剩餘節點的 `list` 與回傳 `list` 相連，最後回傳 `dummy head` 的下一個節點。

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy(0) ;
    ListNode * tail = &dummy ;
    while( list1 != NULL && list2 != NULL ) {
        if ( list1->val <= list2->val ) {            
            tail->next = list1 ;
            tail = list1 ;
            list1 = list1->next ;
        } // if
        else {             
            tail->next = list2 ;
            tail = list2 ;
            list2 = list2->next ;
        } // else
    } // while
        
    if( list1 != NULL ) 
        tail->next = list1 ;
    else if ( list2 != NULL ) {
        tail->next = list2 ;
    } // else if
        
    return dummy.next ;
}

👨‍💻：那麼這個做法的時間複雜度為何？
🧑‍：由於 `while` 迴圈的執行次數是取決於兩個 `list` 中較短者，假設 `list` 長度分別為 n 與 m ，時間複雜度為 $O(n+m)$。

👨‍💻：那麼你覺得這個 function 可以應用在什麼地方?
🧑‍：我認為可以將此 function 應用在 merge sort 當中，隨著排序的進行，原先完整的 `list` 會被切割成一段一段的，這時可以利用此 function 將 `list` 片段重新組合。

## [28. Find the Index of the First Occurrence in a String](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/)
👨‍💻：那麼下一題我們會給你兩個字串，我們希望你可以在第一個字串中找尋第二個字串的身影，若其存在第一個字串則回傳他的起始位置，若不存在則回傳 `-1` 。
🧑‍：如果存在複數個字串我應該如何決定輸出的起始位置。
👨‍💻：如果存在複數字串就請你幫我輸出最先出現的字串的起始位置。
🧑‍：這題我想到最輕鬆的作法是同時走訪兩個字串，只不過字串二只有在兩個字串的當前字元相同時才會增加，若不相同則重製兩個字串的索引，字串一重置到原先起始位置的下一位，而字串二則歸零。值到找到字串二或是字串一走訪完為止。
👨‍💻：聽起來不錯那你實作一下吧。

int strStr(string haystack, string needle) {
    int len = haystack.length();
    int cur = 0;
    int walk = 0;
    while (walk < len) {
        if (haystack[walk] == needle[cur])
            cur++;
        else {
            walk = walk - cur;
            cur = 0;
        }

        if (cur == needle.length())
            return walk + 1 - cur;

        walk++;
    } // while
    return -1;
}

👨‍💻：那你有辦法提升這個方法運算速度嗎?
🧑‍：我認為可以從重製索引的部分下手，當我們在字串一找到字串二的同時去尋找下一個與字串二開頭相同的字元，這樣在重製時可以多節省幾個迴圈的運算次數。另外，當字串一的剩餘字元數不足字串二長度時，也可以直接結束迴圈。
👨‍💻：聽起來不錯，那麼這麼做的時間複雜度會改變嗎?
🧑‍：從時間複雜度的角度出發應該是不會改變的，但實際上會因為迴圈次數的減少達到提升運算時間的效果，不過所需的記憶體空間是增加的。

## [22. Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)

👨‍💻：最後一題我們會給你一個數字，數字代表左括弧的數量，每個左括弧會有一個對應的右括弧，你需要列出合法的所有組合，所謂的合法就是不能出現對應右括弧出現早於左括弧抑或是括弧組數對不上的情況。
🧑‍：好的，這題我們可以將題目想像成走訪一個二元樹，我下面舉一個以二為輸入的例子，我們可以透過遞迴走訪二元樹，當走到左右數量相同且為零時就將解放入解答中。走訪過程中我們可以優先往左子節點出發並確保只有在左括弧不超過輸入值才繼續走訪以達到結果只有合法組合。

左
左 右
左 右 左 右
左右 左(右) 左(右) 左右

👨‍💻：那你可以開始實作了。
🧑‍：沒有問題，首先我們將輸入同時賦予 `left` 與 `right`，當 `left` 不等於零代表尚可向下走訪，將 `"("` 加入字串並將 `left` 減一併向下走訪；而若當前 `right` 大於 `left` 才能下右子節點走訪，作用在剛剛所說的避免非法，當 `left` 與 `right` 皆為零時，將字串加入 `ans` 當中。

public:
    vector<string> generateParenthesis(int n) {
        operation( "", n, n ) ;
        return ans ;
    } // generateParenthesis
private:
    vector<string> ans ;
    void operation( string str, int left, int right ) {
        if ( left == 0 && right == 0 ) {
            ans.push_back(str) ;
            return ;
        } // if

        if ( left > 0 ) {
            operation( str + "(", left - 1, right ) ;
        } // if

        if ( right > left ) {
            operation( str + ")", left, right - 1 ) ;
        } // if
    } // operation()

👨‍💻：那麼這題的時間複雜度應該是多少?
🧑‍：我認為是 $O(2^{2n})$，可以看成是將有 2n 個位置，每個位置有 2 個選擇，為了尋找正解我們必須將所有組合都走過一遍。但是因為我們有設定只有 `right` 大於 `left` 才能往下訪，整體運行時間還是好過於窮舉法的。

## 第二次作業 - 他評
### interviewer
優點:
* 有討論到用途[9:57](https://youtu.be/sIaAvdn895g?t=597)。
* 說話音量跟語速都適中，聽得很清楚

缺點:
* 。
### interviewee
優點:
* 有跟interviewer互動確認題意

缺點:
* 太多 [那...](https://youtu.be/sIaAvdn895g?t=189)。
* 建議先把example寫下來，會比較清楚[3:21](https://youtu.be/sIaAvdn895g?t=201)。
* 可以再寫題前就先舉例說明會比較清楚

## 第二次作業 - 他評02
### interviewer
#### 優點:
1.表達清楚、有關於程式用途的問題

#### 可改進之處:
2.可以再多加討論空間複雜度
### interviewee
#### 優點:
1.有討論到一些特例[12:50](https://https://youtu.be/sIaAvdn895g?t=769)
2.[1:43](https://youtu.be/76oVeeQaXWE?t=101)舉例方式很容易理解
3.寫程式同時講解流暢
#### 可改進之處:
1.Merge Two Sorted Lists這題跳過Example和討論Approach直接開始Coding

## 第二次作業 - 他評03
### interviewer
- 講話清楚
- 題意表達明確
### interviewee
- 舉例很易懂
### 整體可改進之處
- 雜音有點明顯
- 講解題目時，可以保留一部份資訊，用於後續溝通

# 第二次作業-他評04
## interviewer
### 優點:
* 題目闡述清楚
* 有適時回答interviewee的問題
### 可改善的地方:
* 在闡述題目時，可能會需要包裝成另一情境來考驗interviewee的理解能力和應變能力
* 可以多和interviewee溝通

## interviewee
### 優點:
* 有用到REACTO的步驟
* 有嘗試和intervewer交換想法

### 可改善的地方:
* 在講解時避免說過多的"然後"
* 邊講解邊寫程式時可以再加快打字速度