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

貢獻者: 靈魂程式手-Soul Coder
模擬面試錄影: 漢語
模擬面試錄影: 英語

interviewer🤖:

interviewee🐯:

2. Add Two Numbers

面試過程

🤖: 好，我是今天的面試官麻煩你打開我剛剛發給你的文本
🐯: 好，我已經打開了。
🤖: 這邊呢，會有一些問題需要你去回答。然後，我們的問題呢是這邊有兩個linked list會當做輸入 l1、l2, 那會回傳一個新的linked list。那這個新的linked list呢，它左邊的位元是比較低，右邊的位元是比較高，所以相加的時候要注意像中間這個它加起來等於10的時候，它進位是進位到下一個ListNode裡面去所以它這邊會變8，3+7+1 = 8 。那這裡有一些constructor你可以使用，接下來就麻煩你完成這個method

/**
 * 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 *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
    }
};

🐯: 那我們要做的呢是把兩個linked list給相加後回傳結果，那假設我的l1 = 9 9 9 那l2 = 1 那我的回傳是0 0 0 1。想請問我這樣理解有錯嗎。
🤖: 嘿，你這樣理解是對的。
🐯: 那接下來我們就開始邊實作邊講我們的想法，那我們這樣會遇到長度不同的問題，那我們可以分成三個部分。就是l1跟l2有長度的時候，像l1 跟 l2有相同的長度是1嘛，那我們就可以用一個回圈去處理，那後面這個l1 剩餘的我們就可以用另一個回圈去處理，相反l2比較長的話我們也需要多一個，所以我們總共需要三個while回圈。這三個回圈分辨代表l1，就是檢查l1 & l2是不是nullptr除了這個意外我們還需要檢查l1再來還會有一個l2，那我們就具備這三個回圈去處理上面的這三個問題。再來呢我們需要建置一個輸出的linked list一開始先給他設成一個無效的0那這設成null的話也可以。但是設成null的話一開始就要去判斷他是不是null如果是null才給他建置一個null如果不是則繼續往next接，那我們不那麼做，因為那樣做會在回圈裡面消耗一定的性能。好，那我們這邊就直接改成now，now就指向那個head。那這邊now的作用就是在回圈裡面指向最後一個node節點。那，我們就開始實作這個l1跟l2有相同長度的時候，那..我們這個sum他就會等於l1的value加上l2的value，那這邊呢需要考慮另一個問題。像他會導致一個進位所以我們需要有另一個變數去存這個進位，這邊叫它"addDelay"，那這個"addDelay"我們可以把它宣告在回圈的外部，這邊先設成0，那…相加完這個"addDelay"此時就會變成1(口誤手打是0)嘛已經加總了，此時我們還需要再檢查它還有沒有進位到下一個位，就是下一個相加的位置上。如果他大於等於10的話那他就會再進位到下一個位置上，所以我們這邊需要判斷這個那"addDelay"的話他就會變回1。sum的話我們就把他減一個10，因為進位了嘛我們這邊是十進制所以是-10，那這邊不用除的原因是因為它最大只會是兩個9 + 1最大只會到18（口誤實際19）。用出發會導致性能開銷更大，但是沒有這個必要。好…那我們就可以把結果加到我們的輸出的最末端上。好那加上去了之後我們就要把我們最末端的…我們就要把我們當前的這個now的node移到就是他的指針要移到最後一個節點上。所以它就會等於它自己的下一個，那當然l1 跟 l2 因為已經做完加法所以他們也要移到下一個位元上。好…那這一部分就把長度相同的給做完。那長度不相同的跟長度相同的差不多它們會有一些區別。區別就區別在這個l1(嘴巴打結)只有l1然後這個rrr,然後這個l2是沒有的因為他已經到了nullptr(重複了兩次第二次更正讀音)。那已經到nullptr之後就沒有這個東西了。所以再接下來這個l2也一樣就留下這個l2，這個l1也不需要因為它也已經到nullptr。好，那…我們這邊就已經把加法做完了。那我們就已經到最後一個位元這邊，那還有一個沒有處理的就是這一個，最後一位是進位的話我們還沒有處理，所以我們去給他做一個判斷。如果這邊"addDelay"不是0的話，就代表說他最後在這邊還是需要進一位的。那我們這邊加一個判斷就可以處理掉它了。那處理掉它之後我們就要開始准備回傳，回傳的話我們回傳head，但是這邊head我們之前說過它前面有一個無用的ListNode所以我們這邊需要把這個ListNode給拔掉，那首先我們需要把free掉那個空間防止內存洩露，所以now先指向head，那head它就指向它的下一個真正有用的節點上。就是真正的開始位置再來把這個now給刪掉，那這題的解法就這樣完成了，謝謝。
🤖: 好，謝謝你的回答。

程式碼

/**
 * 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 *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *head = new ListNode();
        ListNode *now = head;
        int addDelay = 0;
        while (l1 && l2)
        {
            int sum = l1->val + l2->val + addDelay;
            addDelay = 0;
            if (sum >= 10)
            {
                addDelay = 1;
                sum -= 10;
            }
            now->next = new ListNode(sum);
            now = now->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while (l1)
        {
            int sum = l1->val + addDelay;
            addDelay = 0;
            if (sum >= 10)
            {
                addDelay = 1;
                sum -= 10;
            }
            now->next = new ListNode(sum);
            now = now->next;
            l1 = l1->next;
        }
        while (l2)
        {
            int sum = l2->val + addDelay;
            addDelay = 0;
            if (sum >= 10)
            {
                addDelay = 1;
                sum -= 10;
            }
            now->next = new ListNode(sum);
            now = now->next;
            l2 = l2->next;
        }
        if (addDelay)
            now->next = new ListNode(1);
        now = head;
        head = head->next;
        delete now;

        return head;
    }
};

改進方案，和初步檢討自己的表現

interviewer檢討

• 不該說出面試官這個詞
• 也不應該說有一些問題，應該說有興趣跟你探討某些問題之類的話
• 應該主動打斷interviewee問一下額外的問題不應該讓其變成獨角戲。
• 除非功力很深厚確定是對的，否則在interviewee沒有主動測試的情況下應該主動提出測試。
• 程式碼有redundancy的情況出現沒有想interviewee提出more "clean code"的要求
• 雖然BigOh很明顯但是還是可以試探性問一下

interviewee檢討

• 代名詞有問題不應該一直用我們、我們的
• 說話會口誤說的跟寫的不一樣還沒有發現自己說錯了問題
• 念nullptr的時候念錯了應該錯到底，不應該突然換唸法。
• 說話有時候會鬼打墻，說了一些沒用的話。
• 沒有測試
• 說話的語速可以適當放慢，給自己有時間想接下來應該說的話。這樣可以減少鬼打墻、胡說八道的情況。
• 可以適當的丟一些問題給interviewer回答讓自己有喘息的時間。
• 程式碼redundancy寫完後也沒有嘗試enhance當前的程式架構
• 雖然BigOh很明顯但是還是可以分析一下

1646. Get Maximum in Generated Array

面試過程

🤖: 那，這邊還有一題需要你來完成。那就是會給你一個n整數n。然後你需要准備一個0到n+1的array去完成一下動作。那這個動作呢其實是幫你計算這個數組裡面的值，那你要回傳的不是數組，而是數組裡面最大的一個值。那這邊就要麻煩你完成這個method。

You are given an integer n. 
A 0-indexed integer array nums of length n + 1 is generated in the following way:

nums[0] = 0
nums[1] = 1
nums[2 * i] = nums[i] when 2 <= 2 * i <= n
nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n

class Solution {
public:
    int getMaximumGenerated(int n) {
    }
};

Return the maximum integer in the array nums​​​.
🐯: 好，那…我們要回傳這個最大值，那假設我算完之後我的array裡面是{1,4,5,3,1}(口誤手打是{2,4,5,3,1}),那我的回傳值是不是應該是5。想請問這樣對嗎？
🤖: 嘿，對就是那樣。
🐯: 好，那… 我把他註解掉。好，那…抱歉。（修復排版中…）
🐯: 那接下來我們就直接先建一個array。然後是n+1，那我們就還需要考慮到他等於0或者1的時候會導致的問題所以我們這邊如果它小於2，那我們就直接回傳它的值就可以了，那如果他大於2的話我們的dp[0]就要設成0。然後dp[1]就要設成1。那我們除了這個以外我們還需要一個變數叫做"maxValue"，那這個"maxValue"我們一開始可以把它設為最小值（INT_MAX）。那接下來我們就可以開始我們的回圈然後去把每一個結果都算出來。i < n, i<=n,然後i++（胡言亂語中）。那這邊他有兩個轉移方程，那第一個的話就是他的條件當i等於偶數的時候，那另一個的話就是i等於非偶數的時候，那i等於偶數的時候我們可以得知它是等於~就是dp[i]會等於dp整數的i除2。好，那…當他是奇數的時候我們可以看到他的dp[i]會等於兩個數字相加一個是dp i除2另一個是dp i除2加1。那它就會形成這個樣子，那我們可以知道可以計算出來之後那也要就是把這個"maxValue"也更新。因為我們要的不是整個數組回傳，我們要的只是它的最大值而已。那maxValue = max(maxValue, dp[i][j])那就可以確保說我們拿到的一定是最大的數值，那假設說它小於2沒進入回圈，那它其實在上面就會回傳回去了。所以我們也不需要考慮這個問題。那這個問題就這樣算是解出來了。最後只需要把它回傳，回傳"maxValue"，那這題就這樣解出來了。那…謝謝。
🤖:那謝謝你，我們今天的面試就到這邊。

程式碼

class Solution
{
public:
    int getMaximumGenerated(int n)
    {
        if (n < 2)
            return n;
        int dp[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        int maxValue = INT_MIN;
        for (int i = 2; i <= n; i++)
        {
            if (i % 2 == 0)
            {
                dp[i] = dp[int(i / 2)];
            }
            else
            {
                dp[i] = dp[int(i / 2)] + dp[int(i / 2) + 1];
            }
            maxValue = max(maxValue, dp[i]);
        }
        return maxValue;
    }
};

改進方案，和初步檢討自己的表現

interviewr檢討

• 也不應該說還有一個問題，應該說有興趣跟你探討另一個問題之類的話
• 使用了數組（大陸）用語，台灣用語應該是陣列(?，真的不會應該用英文array來串場
• 應該主動打斷interviewee問一下額外的問題不應該讓其變成獨角戲。
• 不應該把轉移方程直接展示給interviewee看。
• 雖然BigOh很明顯但是還是可以試探性問一下

interviewee檢討

• 看見轉移方程就手癢開始急於寫程式，沒有嘗試先講解架構
• 可以在一開始的時候講解recursive v.s. dp， why dp and how good are dp and etc…
• 代名詞有問題不應該一直用我們、我們的
• 說話會口誤說的跟寫的不一樣還沒有發現自己說錯了問題
• 說話有時候會鬼打墻，說了一些沒用的話。
• 說話的語速可以適當放慢，給自己有時間想接下來應該說的話。這樣可以減少鬼打墻、胡說八道的情況。
• 可以適當的丟一些問題給interviewer回答讓自己有喘息的時間。
• 雖然BigOh很明顯但是還是可以分析一下

20. Valid Parentheses

面試過程

🤖: Hi, I'm the interviewer today. Here is the problem you need to solve it. This problem is the verify parentheses string is legal or not. So, you need to considere this three kind of parentheses, you no need to considere another parentheses. So, you need to completely this function. Just go through please.

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
    
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

class Solution
{
public:
    bool isValid(string s)
    {
        
    }
};

🐯: Ok, now we need to verify a parentheses string is legal or not. For example, like the… s is equal to branket parentheses and we will return false. For like this, we also need return false. Althought is close and open parentheses is same but the order is not legal and another one is only the open parentheses. But it doesn't close, so it also return false. The legal one is only for the order correct and the parentheses open and close is same. So, it will be return true. Is this correct for my understanding?
🤖: Yes, it's correct.
🐯: Ok, I will go through to complete the method. Ok~~~ , this… method can complete by two approach one is soft coding another one is hard coding. But I will go through with soft coding. If using the hard coding, we will use the if else or switch(在亂念). So, I will just go through with map using soft coding. Here we I use unorder_map because using map the BigO is logn and unorder_map the BigO is 1. So for the performance I will go through with unordered_map. And then the key and value is(are) characters. Besides that, we also need a… stack, we need a stack store the store the parentheses we check or we convert and then we should initialize the map…(typing…). Ok, we set up the map. Here we can use auto, ops sorry character is better, i iterator s. And then we can check the i is in mp or not. So I try find if it's not equal~ mp.end() it's mean that we got it in mp. So when it's in mp, we try to convert and push it to the stack, (repeating script one more time…), else here is mean that it's not the open parentheses it's the close parentheses here. (開始胡說八道了~)So, we will try to check the stack, the top of the stack is equal the i or not. If it's not equal then i will just return false. Like this one the stack of the top is the close parentheses of this and then we touch another parentheses but it's not same with the top of stack so it will just return false. So here, it here until here it's mean that is matched so we just pop it. Okay, oh here need another one condition because probably the stack is empty and then it~~ the i will be the, the i be the cross parentheses so we need to check the stack is empty or not it's stack, if the stack is empty then it just return false it means that the stack is empty but it touches a close parentheses. Okay here we gonna return true before we return true we need to check the stacks empty or not if it's not empty then it's return false because when the parentheses is open at the last and then it doesn't close the parentheses and then when we return true then the program will be false. So for the correctly output so here need to check again. Ok that's my solution. Thank you very much.

程式碼

class Solution
{
public:
    bool isValid(string s)
    {
        unordered_map<char, char> mp = {{'[', ']'}, {'(', ')'}, {'{', '}'}};
        stack<char> st;

        for (char &i : s)
        {
            if (mp.find(i) != mp.end())
            {
                st.push(mp.find(i)->second);
            }
            else
            {
                if (!st.size() || st.top() != i)
                    return false;
                st.pop();
            }
        }
        if (st.size())
            return false;
        return true;
    }
};

改進方案，和初步檢討自己的表現

interviewr檢討

• 不該說出interviewer這個詞， 也不應該說這裡有一個問題需要你來解
• 應該主動打斷interviewee問一下額外的問題不應該讓其變成獨角戲。
• 雖然BigOh很明顯但是還是可以試探性問一下
• 語法有問題，parentheses念出了神學(the被吃了)
• 英文講出來還以為是印度人

interviewee檢討

• 代名詞有問題不應該一直用我們、我們的
• 說話有時候會鬼打墻，說了一些沒用的話（胡說八道）。
• 發音容易打結就不應該多說一些實作沒有要用的方法。（e.g., switch 念到亂七八糟）
• 說話的語速可以適當放慢，給自己有時間想接下來應該說的話。這樣可以減少鬼打墻、胡說八道的情況。
• 可以適當的丟一些問題給interviewer回答讓自己有喘息的時間。
• 雖然BigOh很明顯但是還是可以分析一下
• 語法有問題，parentheses念出了神學(the被吃了)
• approach感覺在碎碎念聽不清楚
• 靈壓不夠強, 要去給第零番隊訓練一下

---

第二次作業-他評 01

文本建議

• 錯別字偏多 (「回圈」=>迴圈,「准備」=>準備)另外bigO()通常是n(N) 這邊打h(H)應該沒差但要注意
• 文案只是給觀看者看個大意，不用連失誤也一起打出來，心裡話也不用打，演算法部分可以把code省略掉，這樣比較精簡
• 建議先在這邊擬一個大綱再去拍影片

interviewer

• 優點

• 未面試者準備文本也有圖例很用心可以省略時間

• 可改進的地方

• 建議從實例來包裝問題，給文本應該可以敘述的比臨時構思的還要好
• 建議適當的明知故問一下來溝通彼此的想法

interviewee

• 優點

• code寫完有簡單帶過之前舉的例子做驗證
• 做錯了懂得及時修正並向面試官道歉

• 可改進的地方

• REACTO中的O(optimizition)階段需要加強建議一開始先向面試官展示暴力解或次優解，在optimizition階段再展示最優解，會給人一種「我可以在短時間內進步」的正向觀感
• coding部分相信很多地方都可以做優化，像Add Two Numbers的部分可以直接用其中一種的link list做加法即可，省下名為sum 的link list 的空間，Get Maximum in Generated Array部分如果是用C語言撰寫程式的話他的除法(/)就已經是整數型態了不用再外面包一層int type
• 在R(repeat))可以先詢問邊界條件向面試官展示我有考慮到邊界案例

第二次作業-他評02

interviewer

• 優點

• 題目的說明簡潔清楚，有圖檔輔助，且會將重要的部分框起來，讓interviewee更快了解題意。

• 可改進的地方

• 07:26 在interviewee回答完之後，可以再進行題目的變型，像是將加法改成乘法的實作。

interviewee

• 優點

• 在舉例時，直接在Google Docs上寫出來，看起來很清楚。

• 可改進的地方

• 01:34: 音量可以再大一點，影片音量已調到最大，有些片段滑鼠點擊和敲擊鍵盤的聲音大於interviewee說話的聲音。
• 07:26: 程式碼寫完後，可以將題目或是舉幾個會用到進位的數值，作為驗證。

第二次作業-他評03

interviewer

• 優點

• 題目敘述很清楚明瞭，也有針對題目給出範例，解釋後讓人能馬上跟上題意。

• 可改進的地方

• 可以詢問為什麼要利用DP的概念，以及如果給定某些情境下，DP作法的優缺點。

interviewee

• 優點

• 面試者在解題的想法有考慮到題目設計，讓人感到是透過分析題目形式而為了接下來跟解法鋪成，而不是透過背答案的方式想說後面的思路。

• 可改進的地方

• Get Maximum in Generated Array ，雖然光看題意就直覺想到DP，可講解DP的概念，跟題目進行連結，可以讓聽者更容易進入狀況。

第二次作業-他評04

interviewer

• 優點

• 設計題目的時候很簡潔有力，只有非常少的文字量但卻能夠讓面試者完全理解題意。

• 可改進的地方

• 與面試者的互動較少，如果可以的話應該在面試者寫code時多多與她互動。

interviewee

• 優點

• 能夠很好的理解題意，以及直覺地就想到做法，並且能夠邊寫邊說明自己的實作細節。

• 可改進的地方

• 如果可以的話能夠說明一下自己為何要使用這些方法，並且實際的舉例，這樣有較高的互動性。