2021 年「[資訊科技產業專案設計]

貢獻者: 勞孰-Mouse
video

英語影片題目

977. Squares of a Sorted Array

直觀想法: 走訪 input array 並 squares 每個 element，然後再針對新元素進行排序。
- Time complexity: 因為需要排序，所以是 O(nlogn)












class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        
        for (int i{0}; i<nums.size(); ++i) {
            nums[i] = nums[i]*nums[i];
        }
        sort(nums.begin(), nums.end());
        return nums;
    }
};

改進方法: 考慮以下兩點，可使用 2 pointers 技巧實做 O(n) 的演算法。

input elements 已經是 sorted 的狀態
given two integer a and b, 有
$| a | > | b | - > a^{2} > b^{2}$

因此我們可以使用 two pointers

剛開始分別指向 the most negetive element 和 the most positive element
比較此二 element 誰的絕對值較大，將較大者的平方從頭插入 output array，並將其 pointer 向內移動一格
如果兩個指標已經交叉，中止並回傳結果。否則回到 2.




















class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int l = 0;
        int r = nums.size() - 1;
        vector<int> res;
        
        while (l <= r) {
            if (abs(nums[l]) > abs(nums[r])) {
                res.push_back(nums[l]*nums[l]);
                l++;
            } else {
                res.push_back(nums[r]*nums[r]);
                r--;
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }      
};

278. First Bad Version

直覺想法: 從第一個 version 開始，線性搜尋至發現第一個 bad version
- Time complexity: O(n)
- 此法在 leetcode 提交得到 TLE














// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int i = 1;
        for (; i <= n; ++i) {
            if (isBadVersion(i))
                break;
        }
        return i;
    }
};

改進方法: 考慮到小於 first bad version 之所有版本皆為 not bad; 而大於等於 first bad version 之所有版本皆為 bad version。我們可以用 binary search 找出產品由 good version 轉為 bad version 的分界點
- Time complexity: O(logn)




















class Solution {
public:
    int firstBadVersion(int n) {
        long long l = 1;
        long long r = (long long)n;
        long long m = 0;
        
        while (l <= r) {
            m = (l + r) >> 1;
            
            if (isBadVersion(m) == true) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        
        return (int)l;
    }
};

34. Find First and Last Position of Element in Sorted Array (HW2)

想法 1: linear search 找到 target element 的開頭以及結束位址
想法 2: 考慮到 element 已經 sorted，可以使用 binary search 找到其中一個 target value (若有多個以上，找到任一個即可)。隨後從這個 element 往兩邊的 index probe 開頭/結束位址。
想法 3: 原問題可以理解成要找出兩個目標位置，即由左至右
- 第一次出現 target element 的位置
- 第一次出現 > target element 的位置 - 1
  -> 所以此問題可以使用兩次的 binary search 解決:













































class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        return {findFirst(nums, target), findLast(nums, target)};
    }
private:
    int findFirst(vector<int>& nums, int target)
    {
        int l = 0;
        int r = nums.size()-1;
        
        while (l <= r) {
            int m = (l+r)/2;
            
            if (nums[m] >= target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        if (l == nums.size() || nums[l] != target)
            return -1;
        return l;
    }
    int findLast(vector<int>& nums, int target)
    {
        int l = 0;
        int r = nums.size()-1;
        
        while (l <= r) {
            int m = (l+r)/2;
            
            if (nums[m] > target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        l--;
        if (l < 0 || nums[l] != target)
            return -1;
        return l;
    }
};

695. Max Area of Island

想法: iterate over input matrix 的每一個 cell，一旦碰到一個 1 (land)，就執行一次 DFS (從一個 cell 出發可能走的方向有四個方向) 已計算出包含此 cell 的 island 大小。計算出所有 island 大小後回傳最大者。
- Time complexity: O((mn)^2)
- 此法會重複計算同一島嶼多次，在 leetcode 提交得到 stack overflow






























class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        
        m = grid.size();
        n = grid[0].size();
        int curMax = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j])
                    curMax = max(curMax, findMax(grid, i ,j));
            }
        }
        
        return curMax;
    }
private:
    int m, n;
    int findMax(vector<vector<int>>& grid, int i, int j)
    {
        
        if (i < 0 || i >= m || j < 0 || j >= n)
            return 0;
        if (grid[i][j] == 0)
            return 0;
        
        return 1 + findMax(grid, i+1, j) + findMax(grid, i, j+1) + findMax(grid, i-1, j) + findMax(grid, i, j-1);
    }
};

改進空間: 對原本的遞迴進行剪枝，將已經走訪過的 cell 設為 0。這樣可以讓同一個 island 不會被重複計算多次。
- Time complexity: O(mn)































class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        
        m = grid.size();
        n = grid[0].size();
        int curMax = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j])
                    curMax = max(curMax, findMax(grid, i ,j));
            }
        }
        
        return curMax;
    }
private:
    int m, n;
    int findMax(vector<vector<int>>& grid, int i, int j)
    {
        
        if (i < 0 || i >= m || j < 0 || j >= n)
            return 0;
        if (grid[i][j] == 0)
            return 0;
+        grid[i][j] = 0;
        
        return 1 + findMax(grid, i+1, j) + findMax(grid, i, j+1) + findMax(grid, i-1, j) + findMax(grid, i, j-1);
    }
};

漢語影片題目

242. Valid Anagram

想法1: 對兩個字串分別 sorting，然後比對 sorted 字串是否完全相同
- Time complexxity: O(nlogn)













class Solution {
public:
    bool isAnagram(string s, string t) {
        
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        
        if(s.compare(t) == 0){
            return true;
        }
        return false;
    }
};

想法2: 利用一個 array 記下某一字串的各字元出現次數 (字串只會有 lower case letter-> O(1) space 成本)，再拿此 array 與另一個字串之各字元次數比對。
- Time complexxity: O(n)





















class Solution {
public:
    bool isAnagram(string s, string t) {
        
        vector<int> hashMap(26, 0);
        
        for (auto c : s) {
            hashMap[c-'a']++;
        }
        for (auto c : t) {
            hashMap[c-'a']--;
        }
        
        for (int i = 0 ; i < 26; ++i) {
            if (hashMap[i] != 0)
                return false;
        }
        
        return true;
    }
};

198. House Robber

想法: 遞迴。
首先給定遞迴函式 f(n) 之邊界條件:
(1) 如果只有一間房子，則最大可搶的錢為這間房子內的錢。f(1) = nums[0]
(2) 如果有兩間房子，因為同時不能搶相鄰的房子，選錢多的房子。f(2) = max(nums[0], nums[1])

接著，考慮第 n 間房子，如果
(1) 我們搶了第 n 間房子，則不能搶第 n-1 間房子。可搶到的錢為 nums[n] + f(n-2)
(2) 我們不搶第 n 間房子。可搶到的錢為 f(n-1)

另外，為了不重複計算遞迴，我們利用 recursion with memorization (top down dp) 記下算過的值。



























class Solution {
public:
    vector<int> dp;
    int rob(vector<int>& nums) {
        int len = nums.size();
        
        if (len == 1)
            return nums[0];
        
        for (int i = 0; i < len; ++i)
            dp.push_back(-1);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        return rec(len-1, nums);
    }
    
private:
    int rec(int n, vector<int>& nums)
    {
        if (dp[n] != -1)
            return dp[n];
        
        dp[n] = max(rec(n-2, nums) + nums[n], rec(n-1, nums));
        return dp[n];
    }
};

11. Container With Most Water

想法1: 對任二個牆壁計算他們所形成的容器大小，並記下最大者
- Time complexity: O(n^2)
想法2: 基於以下觀察
對於兩個容器 a 和 b，如果 a 的寬度比 b 小，則有

$若 a 的容量比 b 大，則 a 較低的牆較 b 較低的牆高$

由上敘述，則可知其實不用每種組合都算一次，我們只需算"可能可以得到更多水量的組合"。我們可利用 two pointers 技巧，分別指向最左，最右的牆壁，即從最寬的容器開始算。每次算完一種組合後，將指向較低的牆壁向內 (往另一個指標方向) 移動一格。(因為若移動較高的牆壁，新容器的高度仍為原較低的牆)


















class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0;
        int r = height.size()-1;
        int maxWater = INT_MIN;
        
        while (l < r) {
            maxWater = max(maxWater, (r-l)*min(height[l], height[r]));
            
            if (height[l] > height[r])
                r--;
            else
                l++;
        }
        return maxWater;
    }
};

第三次作業 - 他評

Interviewee

優點

在第一個題目的coding之前，有和interviewer進行良好的溝通，並更明確的確定題目的限制及邊界。
在approach階段有清楚說明方法，並且可以同時coding讓interviewer更進入coding的現狀。

可改進

在4:40，interviewer表示希望時間複雜度在linear的時候，應該簡單介紹原本的時間複雜度之後盡快進入下一種方法，以免再interviewer不期望的approach上耗費時間。
11:40，在進階問題的時候，有重新描述一次題目，但少了和intertviewer討論問題的環節。
在coding完之後，應該做一些簡單的驗證來證明自己的code。

Interviewer

在進階問題的階段，應該做多一點討論，而不是interviewer自己coding然後就草草結束。

第三次作業 - 他評 2

Interviewer

優點

題目講解的很清楚
有與面試者進行討論

缺點

第一個題目空間複雜度為 linear time 的優化解法完成後，沒有其他的評論就進到下一題了
第二題都是 interviewee 一直講， interviewer 缺乏互動

Interviewee

優點

有完整 REACO 且有詢問題目的一些可能的限制條件
完整分析程式碼的時間複雜度，也有考慮到空間複雜度且優化
有完整解釋 hash_table 的使用

缺點

10:59 這邊寫完後可以加入 Test，舉個 Example 來驗證自己的程式碼
13:08 可以說因為有
$C_{n}^{2}$ 種可能，所以會是 string 個數的平方
19:39 第二題解完後沒有任何的 Test 去驗證程式碼的正確性，也解釋時間複雜度的部分

第三次作業 - 他評 3

Interviewer

優點

有清楚的描述題目需求，且 Interviewee 對第一個問題提出問題時有明確定義邊界與內容

缺點

4:33 Interviewer 可以先問 Interviewee 會採用的 Sorting 演算法時間複雜等級為多少，再提出須要更快的方法
11:11不用明確表達要進到第二個問題，可直接給一個簡單的例子和 Interviewee 討論

Interviewee

優點

第一題時有和 Interviewer 討論是否會有其他狀況發生
兩題都有做到 REAC，並且花在 Example 的時間不算太長

缺點

Interviewee 完成題目時沒有做 Test 和 Optimization

第三次作業 - 他評 4

8:19 宣告已知大小的陣列時建議使用 std::array<T, N> 或 T[N]
16:17 變數命名應避免與 std 衝突
第二題沒有兩方互動

第三次作業 - 他評 5

Interviewer

優點

題目講解清楚
第一題有與 interviewee 做互動且給予回饋

缺點

4:35 「對演算法做優化或是加速」這句話可以改成「時間上的優化」比較好

Interviewee

優點

有做到 REACO，也有先詢問邊界和 constraint
有舉出例子和解說

缺點

13:06 這裡分析時間複雜度時花費的時間有點久，前面已經有說明了需要兩兩配對做比較，那只需要告訴 interviewer 其時間複雜度為
$O (n^{2})$ ，字串長度為常數，不需要計算進去
沒有做 test

第三次作業 - 他評 6

Interviewer

優點：

不是以背題目的方式來說明題目。
題目設計第一題和第二題有連貫。

可改進：

第二題的互動可以再多一點。

Interviewee

優點：

有完整做到 REACO。
口語表達流暢清晰。

可改進：

可以做簡單的 Test 驗證自己的 Code。

第三次作業-他評7

題目敘述完整，且清楚表達要求

互動過程中有舉例及解釋，也有討論的行為

選題有相關

interviewer

00:15 解釋題目的時候很像在背題目，解釋題目時避開一些特定名詞可以避免interviewee背答案

interviewee

1:00 馬賽克不見了@@
1:52 字有點小，看不太清楚

2021 年「[資訊科技產業專案設計]

英語影片題目

977. Squares of a Sorted Array

278. First Bad Version

34. Find First and Last Position of Element in Sorted Array (HW2)

695. Max Area of Island

漢語影片題目

242. Valid Anagram

198. House Robber

11. Container With Most Water

第三次作業 - 他評

Interviewee

優點

可改進

Interviewer

第三次作業 - 他評 2

Interviewer

優點

缺點

Interviewee

優點

缺點

第三次作業 - 他評 3

Interviewer

優點

缺點

Interviewee

優點

缺點

第三次作業 - 他評 4

第三次作業 - 他評 5

Interviewer

優點

缺點

Interviewee

優點

缺點

第三次作業 - 他評 6

Interviewer

優點：

可改進：

Interviewee

優點：

可改進：

第三次作業-他評7

interviewer

interviewee

Read more

你所不知道的 C 語言：數值系統

建構 User-Mode Linux 的實驗環境

Linux 核心設計: Scheduler(8): Energy Aware Scheduling

你所不知道的 C 語言: linked list 和非連續記憶體