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

貢獻者: 黑瑟甘-Hei
interviewer: 👨‍💼
interviewee: 👩‍🎓

1. Two Sum

Easy
模擬面試影片

👨‍💼：黑瑟甘同學你好，題目給你一個整數陣列nums和一個整數target，請你回傳可以加總為target的兩個數字的索引值。你可以假設每個輸入只會有一個解答，而且同個索引的數字不能重複使用，答案能以任何順序回傳。

👩‍🎓：請問我有需要幫回傳的陣列配置和釋放記憶體空間嗎？

👨‍💼：只需要配置記憶體空間，我們假設使用函式的人會呼叫free()。

👩‍🎓：好的，那麼我先舉一個例子，如果nums = [2,7,11,15]，而target = 26，因為nums[2]+nums[3]=11+15=26，所以答案為[2,3]。請問我的理解正確嗎？

👨‍💼：對的。

👩‍🎓：那麼直覺的作法是使用兩層for迴圈，檢查陣列的任兩項相加是否等於target，如果是的話，將這兩項的索引值放入回傳的陣列中。

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    if(!numsSize)
        return NULL;
    
    int i, j;
    int* ans = (int* )malloc(2*sizeof(int));
    
    for(i = 0; i < numsSize; i++)
    {
        for(j = i+1; j < numsSize; j++)
        {
            if(nums[i]+nums[j] == target)
            {
                ans[0] = i;
                ans[1] = j;
                
                break;
            }
        }
    }    
    
    *returnSize = 2;
    return ans;
}

時間複雜度會是

$O(n^2)$。

👨‍💼：那麼你可以想到時間複雜度更好的演算法嗎？

👩‍🎓：先宣告一個結構來儲存陣列的索引，將陣列由小到大排列，宣告兩個變數left和right，分別為最小和最大的數字，將這兩個變數相加，如果總和太小，則left往下一項移動，反之總和太大的話，right往前一項移動。

typedef struct {
    int index; 
    int num;
} labeledNum;

int cmp(const void* a, const void* b)
{
	return (*(labeledNum*)a).num - (*(labeledNum*)b).num;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    if(!numsSize)
        return NULL;
    
    int i;
    int left = 0, right = numsSize - 1;
    int* ans = (int* )malloc(2*sizeof(int));
    labeledNum* sortNums = malloc(sizeof(*sortNums) * numsSize);
    
    for (i = 0; i < numsSize; i++) {
        sortNums[i].index = i;
        sortNums[i].num = nums[i];
    };
    qsort(sortNums, numsSize, sizeof(*sortNums), cmp);
    
    while (left < right)
    {
        if (sortNums[left].num + sortNums[right].num < target) left++;
        else if (sortNums[left].num + sortNums[right].num > target) right--;
        else {
            ans[0] = sortNums[left].index;
            ans[1] = sortNums[right].index;
            break;
        };
    };
    
    *returnSize = 2;
    return ans;
}

時間複雜度因為quick sort的關係為

$O(n\log n)$。

198. House Robber

Medium
模擬面試影片

👨‍💼：Hello, Ms.Hei. In this question, You are a robber planning to rob houses along a street. Each house has a certain amount of money hidden, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. The integer array nums representing the amount of money of each house, please return the maximum amount of money you can rob tonight without alerting the police.

👩‍🎓：Is there any constraints of the array's length and value?

👨‍💼：The length of the array is greater than or equal to 1 and less than or equal to 100, the value of every element is greater than or equal to 0 and less than or equal to 400.

👩‍🎓：To my knowledge, there will be an integer array called nums, and it represent how much money that each house has. I have to find out the maximum amount of money I can rob without alerting the police.

Then, the length of the array is greater than or equal to 1 and less than or equal to 100, the value of every element is greater than or equal to 0 and less than or equal to 400.

For example, there is an array [2, 1, 1, 2]. I choose to rob house 1 and rob house 4, then the result will be the maximum total amount of 2 + 2 = 4.

I think the way to implement is dynamic programming. First, I declare two variables for the current index of the loop and an array saving the maximum amount robbing a night respectively. More specifically, rob[i] means the maximum amount robbing from house 1 to house i.

If I choose to rob house i, then I can`t rob house i-1. It means that rob[i] = rob[i-2] + nums[i]. If I choose not to rob house i, then rob[i] = rob[i-1].

Consider the initial conditions, rob[0] must be nums[0] since it is the first house. rob[1] will be the maximum of nums[0] and nums[1] since I have to rob one from this two house.

After that, use a loop and the aforementioned equations to calculate the total amount of money and return the answer.

int rob(int* nums, int numsSize){
    int i;
    int rob[numsSize];
    
    for(i = 0; i < numsSize; i++)
    {
        if(i == 0)
            rob[i] = nums[i];
        else if(i == 1)
            rob[i] = fmax(nums[i], rob[i-1]);
        else
            rob[i] = fmax(rob[i-2]+nums[i], rob[i-1]);
    }
    
    if(numsSize >= 2)
        return rob[numsSize-1] > rob[numsSize-2] ? rob[numsSize-1] : rob[numsSize-2];
    else
        return rob[numsSize-1];
}

Both the time complexity and the space complexity are

$O(n)$.

👨‍💼：Can the space complexity further be reduced?

👩‍🎓：Yes. We can observe that the value of rob[i] is only related to rob[i-1] and rob[i-2], hence the array rob[numsSize] can be replaced into three integers robPrev, robCurr, total represent rob[i-2], rob[i-1], rob[i] respectively. Change the above code into:

int rob(int* nums, int numsSize){
    int i;
    int robPrev, robCurr, total;
    
    for(i = 0; i < numsSize; i++)
    {
        if(i == 0)
        {
            robPrev = nums[i];
            total = robPrev;
        }
        else if(i == 1)
        {
            robCurr = fmax(nums[i], robPrev);
            total = robCurr;
        }
        else
        {
            total = fmax(robPrev+nums[i], robCurr);
            robPrev = robCurr;
            robCurr = total;
        }
    }
    
    return total;
}

The space complexity will be

$O(1)$.

392. Is Subsequence

Easy
模擬面試

👨‍💼：接下來這題題目給你兩個字串s和t，若s是t的子序列的話，回傳true，否則回傳false。
子序列的定義是從最初序列通過去除某些元素但不破壞餘下元素的相對位置而形成的新序列。
這樣有問題嗎？

👩‍🎓：沒有，這題會有兩個字串s和t，若s是t的子序列的話，回傳true，不然回傳false。
s的長度<=100, t的長度<=104，而且都只會由小寫英文組成。

那子序列舉例來說，
若t = abcde, s = ace的話，因為相對位置一樣所以是子序列要回傳true,
s = aec的話，因為e出現在c前面所以要回傳false，

我目前想到的方法是寫兩個函數，
其中一個函數會另外多傳s和t目前分別比對到的索引值的參數，
如果兩個索引的值相同，回傳這個函數，並且兩個索引值都+1，
不然就回傳這個函數，只有t的索引值+1，
然後遞迴每次要先檢查，
如果s的長度都比完了就代表是子序列，
如果t的長度都比完了，代表s還沒比完，所以不是子序列。
接著主函數會回傳這個函數，參數值是(s,t,0,0)。

bool subsequenceHelper(char * s, char * t, int sIndex, int tIndex) {
        if (strlen(s) == sIndex) {
             return true;
         }
         if (strlen(t) == tIndex) {
               return false;
         }
        return *(s+sIndex) == *(t+tIndex) 
        ? subsequenceHelper(s, t, sIndex + 1, tIndex + 1) 
               : subsequenceHelper(s, t, sIndex, tIndex + 1);
}
bool isSubsequence(char * s, char * t) {
      return subsequenceHelper(s, t, 0, 0);
}

這個方法的時間複雜度，假設t的長度是n的話就是big

$O(n)$。

👨‍💼：如果以遞迴方式做的話，空間複雜度會是big

$O(n)$，有沒有更好的方法呢？

👩‍🎓：嗯…直接取兩個變數，存取s和t分別要比對的索引值，
在while迴圈裡，每回合會比對s目前索引的值和t目前索引的值是否相同，
而且不論結果如何，下一回合s目前索引的值會比t的下一個索引的值。
若這兩個值相同的話，則下一回合比s的下一個索引的值，
直到其中一個字串的值都比完跳出迴圈，
如果s的長度全都比完了，代表是子序列，不然就不是。
那這題就這樣結束了。

bool isSubsequence(char * s, char * t){
    int s_index = 0;
    int t_index = 0;
    
    while(s_index < strlen(s) && t_index < strlen(t))
    {
        if(s[s_index] == t[t_index])
            s_index++;
        
        t_index++;
    }
    
    if(s_index == strlen(s))
        return true;
    else
        return false;
}

---

作業二-他評01:

針對interviewer

• 優點

• 解釋題目清楚。

• 可改進之處

• 感覺有點像在念稿
• 0:03: 開頭沒有鋪陳直接進入題目有點太過快速。
• 8:02: 題目要做點包裝會比較好，且直接問是否有更好的演算法難以避免面試人背答案。
• 8:09: 先說明想法會比較好。
• 11:40: 發音要注意"space complexity"。

針對interviewee

• 優點

• 邊講解邊寫程式。
• 對話大致清晰。
• 有與interviewer互動確認題意再開始答題。

• 可改進之處

• 缺少TEST的步驟。
• 0:26: 在repeat時不要直接說"我重複敘述一次"，可以改成直接repeat。
• 語速過慢。
• 整個面試都沒什麼精神的感覺，感覺很有氣無力。
• 11:20-11:57: 程式碼太糊看不清楚，下次要開全螢幕會比較好。

作業二-他評02:

針對interviewer

• 優點

• 語氣柔和
• 題意講解清楚

• 可改進之處

• 開頭直接帶入題目，少了一些鋪陳
• 語速偏慢，尤其是英文部分
• 可以將題目帶入情境之中，避免受試者背解法

針對interviewee

• 優點

• 遵循REACTO，與面試官有互動性
• 程式撰寫時有加入解釋

• 可改進之處

• 程式碼撰寫時註解與解釋演算法空白時間偏長
• 程式碼有些模糊
• Two sum可以使用Hash map之類的方式達到O(N)的time complexity

作業二-他評03:

針對interviewer

• 優點

• 題目講解清楚

• 可改進之處

• 並沒有和受試者討論使用 coding 的語言，回答受試者「是否需要配置記憶體空間」時，不應回答「假設使用函式會呼叫 free」，而該用「使用者會自行釋放記憶體空間」等詞。

針對interviewee

• 優點

• Example 的部分講解清楚

• 可改進之處

• 應先講解 Approach 部分，再進入 Coding。