# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 霍夫曼-Mark Hoffman
> [英文模擬面試錄影-1](https://youtu.be/lyyr50FvWrc)
> [英文模擬面試錄影-1](https://youtu.be/xcuH1O02vsg)
> [英文模擬面試錄影-3](https://youtu.be/ubK1KXEYegE)
> 🧑🦳面試官
> 👦面試者 - Mark Hoffman (霍夫曼)
## 重點摘要：
### [LeetCode 268 - Missing Number](https://leetcode.com/problems/missing-number/)
🧑🦳: 給你一個長度為 n 的整數陣列，其中應該包含 [0, n] 所有整數，請你找出陣列中遺漏的數字。
👦: 我的作法是建立一個長度為 n+1 的整數陣列，在原始陣列的迭代過程中紀錄每一個數字的出現次數，最後再從新建的陣列中找出 0 並回傳索引值。
👦: ***程式實作***。
```cpp
class Solution {
public:
int missingNumber(vector <int> & nums) {
int n = nums.size();
vector <int> occurrences(n + 1, 0);
int i = 0;
for (; i < n; ++i) {
occurrences[nums[i]] += 1;
}
for (i = 0; i <= n; ++i) {
if (occurrences[i] == 0) {
return i;
}
}
return -1;
}
};
```
🧑🦳: However, this approach might have issues with overflow when dealing with very large ranges of numbers. Can you improve your code to handle all cases?
👦: 我可以把陣列的資料型態從「32位元的整數」改成「8位元的布林值」，這樣應該能節省一些空間。***程式實作***。
```cpp
class Solution {
public:
int missingNumber(vector <int> & nums) {
int n = nums.size();
vector <bool> occurrences(n + 1, false);
int i = 0;
for (; i < n; ++i) {
occurrences[nums[i]] = true;
}
for (i = 0; i <= n; ++i) {
if (!occurrences[i]) {
return i;
}
}
return -1;
}
};
```
🧑🦳: 你這樣確實能節省記憶體的使用量，但是效果有限，請你分析一下你的時間複雜度和空間複雜度。
👦: 由於程式共進行了兩次 O(n) 的迭代，故時間複雜度為 O(2n) = O(n)，而空間複雜度則是 O(n)，因為我們建立了一個長度為 n+1 的陣列。
🧑🦳: 分析得不錯！你說你的空間複雜度是 O(n)？我希望你把它降到 O(1)。
👦: 我想到一個更好的解法，因為每一個數字只會出現一次，他們的總和會是 1+2+3+...+n = (n+1)×n÷2，與其記錄出現次數，我們可以將所有數字加總起來，最後再與公式解相減，它們的差就會是漏掉的數字。
👦: ***程式實作***。
```cpp
class Solution {
public:
int missingNumber(vector <int> & nums) {
int n = nums.size();
int expect = (n + 1) * n / 2;
int actual = 0;
for (int i = 0; i < n; ++i) {
actual += nums[i];
}
int difference = expect - actual;
return difference;
}
};
```
### [LeetCode 387 - First Unique Character in a String](https://leetcode.com/problems/first-unique-character-in-a-string/)
🧑🦳: 給你一個只有小寫字母的英文字串，請你找出第一個只出現一次的字元。
👦: 我的作法是透過第一次的迭代記錄每一個字元的出現次數，並在第二次的迭代檢查其出現次數，如果次數為 1 就回傳索引值，如果最後沒有符合條件的字元就回傳 -1。
👦: ***程式實作***。
```cpp
class Solution {
public:
int firstUniqChar(string s) {
map <char, int> occurrences;
int n = s.length();
int i = 0;
for (; i < n; ++i) {
if (occurrences.find(s[i]) == occurrences.end()) {
occurrences[s[i]] = 1;
continue;
}
occurrences[s[i]] += 1;
}
for (i = 0; i < n; ++i) {
if (occurrences[s[i]] == 1) {
return i;
}
}
return -1;
}
};
```
🧑🦳: 請你分析一下你的程式的時間複雜度與空間複雜度。
👦: 程式碼有用到 map 這個結構，存取裡面的值為 O(log n)，但因為總共只有 26 個英文字母作為 key，因此其複雜度可視作 O(1)，而呼叫次數又為 n 次，故時間複雜度為 O(n)。空間複雜度則為 O(1)，原因同上（只有 26 個英文字母）。
🧑🦳: 你能不能讓你的程式跑得更快一點？
👦: 我可以把 map 換成一般的 C 陣列，這樣存取資料只要一個指令，而不是進行二分搜尋（Binary Search）。
👦: ***程式實作***。
```cpp
class Solution {
public:
int firstUniqChar(string s) {
constexpr int p = 123;
int n = s.length();
int occurrences[p];
int i = 97;
for (; i < p; ++i) {
occurrences[i] = 0;
}
for (i = 0; i < n; ++i) {
occurrences[s[i]] += 1;
}
for (i = 0; i < n; ++i) {
if (occurrences[s[i]] == 1) {
return i;
}
}
return -1;
}
};
```
### [LeetCode 16 - 3-Sum Closest](https://leetcode.com/problems/3sum-closest/)
🧑🦳: 給你一個整數陣列 nums 和一個整數 target，請你找出最接近 target 的三個數的和。
👦: 我的作法是用三層巢狀迴圈，找出陣列中所有可能三個數的和，並記錄最接近 target 的答案。
👦: ***程式實作***。
```cpp
class Solution {
public:
int threeSumClosest(vector <int> & nums, int target) {
int i, j, k, n = nums.size(), n_1 = n - 1, n_2 = n - 2;
int tmpSum, closestSum = INT_MAX / 2;
for (i = 0; i < n_2; ++i) {
for (j = i + 1; j < n_1; ++j) {
for (k = j + 1; k < n; ++k) {
tmpSum = nums[i] + nums[j] + nums[k];
if (std::abs(tmpSum - target) < std::abs(closestSum - target)) {
closestSum = tmpSum;
}
}
}
}
return closestSum;
}
};
```
🧑🦳: 我想請你分析你的程式碼的複雜度。
👦: 因為我用了三層的巢狀迴圈，而每一層都會進行 O(n) 的迭代，因此我的程式碼的時間複雜度是 O(n^3)。空間複雜度則是 O(1)。
🧑🦳: 你的時間複雜度是 O(n^3)？
👦: 是的，不過我想到了一個降低複雜度的方法。與其用三層的巢狀迴圈，我們可以先將陣列進行排序，再將最內層的迴圈改為二分搜尋。***程式實作***。
```cpp
class Solution {
public:
int threeSumClosest(vector <int> & nums, int target) {
int i, j, k, n = nums.size(), n_1 = n - 1, n_2 = n - 2;
int tmpSum, closestSum = INT_MAX / 2;
std::sort(nums.begin(), nums.end());
for (i = 0; i < n_2; ++i) {
for (j = i + 1; j < n_1; ++j) {
auto sectBegin = nums.begin() + j + 1;
int remain = target - nums[i] - nums[j];
auto found = std::lower_bound(sectBegin, nums.end(), remain);
if (found < nums.end()) {
tmpSum = *found;
if (found > sectBegin) {
if (std::abs(*(found - 1) - remain) < std::abs(tmpSum - remain)) {
tmpSum = *(found - 1);
}
}
}
else {
tmpSum = *(found - 1);
if (found < (nums.end() - 1)) {
if (std::abs(*(found + 1) - remain) < std::abs(tmpSum - remain)) {
tmpSum = *(found + 1);
}
}
}
tmpSum = tmpSum + nums[i] + nums[j];
if (std::abs(tmpSum - target) < std::abs(closestSum - target)) {
closestSum = tmpSum;
}
}
}
return closestSum;
}
};
```
🧑🦳: 不錯，那麼你的時間複雜度現在是多少？
👦: 兩層的巢狀迴圈加上一個二分搜尋的複雜度是 O(n^2 log n)。
🧑🦳: 你說你的時間複雜度是 O(n^2 log n)？你不覺得它還是有點慢嗎？你能讓它再快一點嗎？
👦: 你要我讓它再快一點？因為陣列已經排序過了，因此隨機三個數，靠左的數較小，而靠右的數較大。如果三數的和過大，就把最小值（左）換成更小的值；如果三數和過小，就把最大值（右）換成更大的值。這樣時間複雜度就會是 O(n log n)。***程式實作***。
```cpp
class Solution {
public:
int threeSumClosest(vector <int> & nums, int target) {
int i, j, k, n = nums.size(), n_1 = n - 1, n_2 = n - 2;
int tmpSum, closestSum = INT_MAX / 2;
std::sort(nums.begin(), nums.end());
for (i = 1; i < n_1; ++i) {
j = i - 1;
k = i + 1;
while ((j >= 0) && (k < n)) {
tmpSum = nums[i] + nums[j] + nums[k];
if (std::abs(tmpSum - target) < std::abs(closestSum - target)) {
closestSum = tmpSum;
}
if (tmpSum < target) {
k += 1;
continue;
}
if (tmpSum > target) {
j -= 1;
continue;
}
break;
}
}
return closestSum;
}
};
```
## 初步檢討：
1. REACTO 之 E 部分，應該更全面列舉例子，尤其是第三場面試。
2. 受試者及面試官說話之節奏過於單調，缺乏熱忱。
3. 受試者應盡可能一開始就提出最佳解，以免浪費時間。
4. 受試者與面試官應多互動，尤其是受試者，應該取得面試官的回饋。
5. 若遇到意外（第三場面試），受試者應立即修正錯誤，而非等面試官指點。
---
## 第二次作業-他評01
### 關於interviewer
* [ ] 可改進之處
* [4:51](https://youtu.be/ubK1KXEYegE?t=291): 就如同你上面說的，若是受試者在test階段發現錯誤時要請受試者修改程式碼。
### interviewee
- [ ] 優點
* 有在撰寫程式碼時適當加入註解讓 code 更明瞭
* REACTO各階段講的都蠻詳細的
- [ ] 可改進之處
* 因為是在leetcode上直接做編譯跟測資，但是我會比較想要受試者自己用測資帶入程式內部去做測試。
* 建議不要使用leetcode當作coding工具，受試者可能會看到leetcode題目當中關鍵字就容易想出解題方針。
## 第二次作業-他評02
### 關於interviewer
* 面試者提出$O(n^2)$ 可以適時的提點面試者，因為本來就會預期大概在submit階段過不了
* 提示不會太多也很剛好，很符合實際卡關時會面對的情況
### 關於interviewee
* 對暴力解的優化展現面試者對C++語言上操作的靈活性跟熟悉度。
* 整體上對於暴力解跟優化解法都給出很清楚的解釋
Sign in with Wallet
Connect another wallet