---
title: 2021 年資訊科技產業專案設計課程面試範例
tags: INFO2021
---
# 2021 年「[資訊科技產業專案設計]
> 貢獻者: 勞孰-Mouse
> ==[video](https://youtu.be/AXq38zDe_vw)==
## 英語影片題目
### [977. Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/)
* 直觀想法: 走訪 input array 並 squares 每個 element，然後再針對新元素進行排序。
* Time complexity: 因為需要排序，所以是 O(nlogn)
```cpp=
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) 的演算法。
1. input elements 已經是 sorted 的狀態
2. given two integer a and b, 有 $|a| > |b| -> a^2 > b^2$
因此我們可以使用 two pointers
1. 剛開始分別指向 the most negetive element 和 the most positive element
2. 比較此二 element 誰的絕對值較大，將較大者的平方從頭插入 output array，並將其 pointer 向內移動一格
3. 如果兩個指標已經交叉，中止並回傳結果。否則回到 2.
```cpp=
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](https://leetcode.com/problems/first-bad-version/)
* 直覺想法: 從第一個 version 開始，線性搜尋至發現第一個 bad version
* Time complexity: O(n)
* 此法在 leetcode 提交得到 TLE
```cpp=
// 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)
```cpp=
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)](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)
* 想法 1: linear search 找到 target element 的開頭以及結束位址
* 想法 2: 考慮到 element 已經 sorted，可以使用 binary search 找到其中一個 target value (若有多個以上，找到任一個即可)。隨後從這個 element 往兩邊的 index probe 開頭/結束位址。
* 想法 3: 原問題可以理解成要找出兩個目標位置，即由左至右
* 第一次出現 target element 的位置
* 第一次出現 > target element 的位置 - 1
-> 所以此問題可以使用兩次的 binary search 解決:
```cpp=
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](https://leetcode.com/problems/max-area-of-island/)
* 想法: iterate over input matrix 的每一個 cell，一旦碰到一個 1 (land)，就執行一次 DFS (從一個 cell 出發可能走的方向有四個方向) 已計算出包含此 cell 的 island 大小。計算出所有 island 大小後回傳最大者。
* Time complexity: O((mn)^2)
* 此法會重複計算同一島嶼多次，在 leetcode 提交得到 stack overflow
```cpp=
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)
```diff=
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](https://leetcode.com/problems/valid-anagram/)
* 想法1: 對兩個字串分別 sorting，然後比對 sorted 字串是否完全相同
* Time complexxity: O(nlogn)
```cpp=
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)
```cpp=
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](https://leetcode.com/problems/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) 記下算過的值。
```cpp=
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](https://leetcode.com/problems/container-with-most-water/)
* 想法1: 對任二個牆壁計算他們所形成的容器大小，並記下最大者
* Time complexity: O(n^2)
* 想法2: 基於以下觀察
對於兩個容器 a 和 b，如果 a 的寬度比 b 小，則有
$若a 的容量比 b 大，則 a 較低的牆較 b 較低的牆高$
由上敘述，則可知其實不用每種組合都算一次，我們只需算"可能可以得到更多水量的組合"。我們可利用 two pointers 技巧，分別指向最左，最右的牆壁，即從最寬的容器開始算。每次算完一種組合後，將指向較低的牆壁向內 (往另一個指標方向) 移動一格。(因為若移動較高的牆壁，新容器的高度仍為原較低的牆)
```cpp=
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](https://youtu.be/AXq38zDe_vw&t=280s)，interviewer表示希望時間複雜度在linear的時候，應該簡單介紹原本的時間複雜度之後盡快進入下一種方法，以免再interviewer不期望的approach上耗費時間。
- [11:40](https://youtu.be/AXq38zDe_vw&t=700s)，在進階問題的時候，有重新描述一次題目，但少了和intertviewer討論問題的環節。
- 在coding完之後，應該做一些簡單的驗證來證明自己的code。
### Interviewer
- 在進階問題的階段，應該做多一點討論，而不是interviewer自己coding然後就草草結束。
## 第三次作業 - 他評 2
### Interviewer
### 優點
* 題目講解的很清楚
* 有與面試者進行討論
### 缺點
* 第一個題目空間複雜度為 linear time 的優化解法完成後，沒有其他的評論就進到下一題了
* 第二題都是 interviewee 一直講， interviewer 缺乏互動
### Interviewee
### 優點
* 有完整 REACO 且有詢問題目的一些可能的限制條件
* 完整分析程式碼的時間複雜度，也有考慮到空間複雜度且優化
* 有完整解釋 hash_table 的使用
### 缺點
* [10:59](https://youtu.be/AXq38zDe_vw?t=659) 這邊寫完後可以加入 Test，舉個 Example 來驗證自己的程式碼
* [13:08](https://youtu.be/AXq38zDe_vw?t=788) 可以說因為有 $C_{n}^{2}$ 種可能，所以會是 string 個數的平方
* [19:39](https://youtu.be/AXq38zDe_vw?t=1179) 第二題解完後沒有任何的 Test 去驗證程式碼的正確性，也解釋時間複雜度的部分
## 第三次作業 - 他評 3
### Interviewer
### 優點
* 有清楚的描述題目需求，且 Interviewee 對第一個問題提出問題時有明確定義邊界與內容
### 缺點
* [4:33](https://youtu.be/AXq38zDe_vw?t=272) Interviewer 可以先問 Interviewee 會採用的 Sorting 演算法時間複雜等級為多少，再提出須要更快的方法
* [11:11](https://youtu.be/AXq38zDe_vw?t=662)不用明確表達要進到第二個問題，可直接給一個簡單的例子和 Interviewee 討論
### Interviewee
### 優點
* 第一題時有和 Interviewer 討論是否會有其他狀況發生
* 兩題都有做到 REAC，並且花在 Example 的時間不算太長
### 缺點
* Interviewee 完成題目時沒有做 Test 和 Optimization
## 第三次作業 - 他評 4
* [8:19](https://youtu.be/AXq38zDe_vw?t=499) 宣告已知大小的陣列時建議使用 `std::array<T, N>` 或 `T[N]`
* [16:17](https://youtu.be/AXq38zDe_vw?t=977) 變數命名應避免[與 std 衝突](https://en.cppreference.com/w/cpp/utility/hash)
* 第二題沒有兩方互動
## 第三次作業 - 他評 5
### Interviewer
### 優點
* 題目講解清楚
* 第一題有與 interviewee 做互動且給予回饋
### 缺點
* [4:35](https://youtu.be/AXq38zDe_vw?t=275) 「對演算法做優化或是加速」這句話可以改成 「時間上的優化」比較好
### Interviewee
### 優點
* 有做到 REACO，也有先詢問邊界和 constraint
* 有舉出例子和解說
### 缺點
* [13:06](https://youtu.be/AXq38zDe_vw?t=786) 這裡分析時間複雜度時花費的時間有點久，前面已經有說明了需要兩兩配對做比較，那只需要告訴 interviewer 其時間複雜度為 $O(n^2)$ ，字串長度為常數，不需要計算進去
* 沒有做 test
## 第三次作業 - 他評 6
### Interviewer
#### 優點：
* 不是以背題目的方式來說明題目。
* 題目設計第一題和第二題有連貫。
#### 可改進：
* 第二題的互動可以再多一點。
### Interviewee
#### 優點：
* 有完整做到 REACO。
* 口語表達流暢清晰。
#### 可改進：
* 可以做簡單的 Test 驗證自己的 Code。
# 第三次作業-他評7
> * 題目敘述完整，且清楚表達要求
> * 互動過程中有舉例及解釋，也有討論的行為
> * 選題有相關
## interviewer
* [00:15](https://youtu.be/AXq38zDe_vw?t=15) 解釋題目的時候很像在背題目，解釋題目時避開一些特定名詞可以避免interviewee背答案
## interviewee
* [1:00](https://youtu.be/AXq38zDe_vw?t=59) 馬賽克不見了@@
* [1:52](https://youtu.be/AXq38zDe_vw?t=111) 字有點小，看不太清楚
Sign in with Wallet
Connect another wallet