---
tags: info2023
---
# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 蔡中文-BadChinese
> 👨🏫：interviewer
> 👶：interviewee
## [1768. Merge Strings Alternately](https://leetcode.com/problems/merge-strings-alternately/description/?envType=study-plan-v2&envId=leetcode-75)
> [模擬面試錄影](https://www.youtube.com/watch?v=ZChpF6fim00)
### 模擬面試過程
👨🏫：感謝你的時間，接下來由我主持這場面試，可以幫我打開事先分享的 Google Docs ，我們來看一下這個問題，過程中你若有想法，就直接寫下便於後續討論。
：我們來看一下這個問題。給你兩個字符串 **`word1`** 和 **`word2`**，要求你通過交替添加字母的方式合併這兩個字符串，從 **`word1`** 開始，如果其中一個字符串比另一個長，就將多餘的字母附加到合併後的字符串的末尾。你可以告訴我你的解決方案嗎？
👶：這個問題是會有兩個字符串 **`word1`** 和 **`word2`**，並以交替方式合併。如果其中一個字符串比另一個長，將多餘的字母附加到合併後的字符串，這樣對嘛？
👨🏫：對
👶：好的，這題我們可以使用迴圈來實作。首先我們需要初始化一個空字串 `mergedResult` 來儲存合併後的結果。
：接下來，我們可以使用兩個指標 `i` 和 `j` 來遍歷兩個字串。初始值都為 0，然後我們可以進入一個迴圈，直到兩個字串都遍歷完畢。
：在每個迴圈中，我們從 `word1` 和 `word2` 中分別取出指標 `i` 和 `j` 所指向的字母，並將它們依序添加到 `mergedResult` 中。
：當迴圈結束後，我們就得到了合併後的字串。最後，我們只需要回傳 `mergedResult`。
### 暴力解法（2個指標）
```cpp
string mergeAlternately(string word1, string word2) {
int m = word1.size();
int n = word2.size();
string result = "";
int i = 0, j = 0;
while (i < m || j < n) {
if (i < m) {
result += word1[i];
i++;
}
if (j < n) {
result += word2[j];
j++;
}
}
return result;
}
```
👨🏫：很好，這個方案我們知道使用了兩個指標，分別是i和j。使用多個指標在閱讀程式，常常會花上更多時間，有什麼方法可以讓這個程式看起來更易閱讀，且不影響程式架構和時間複雜度呢？
👶：好的，如果想要使程式更精簡，我們可以只使用一個指標來完成。
：我們用一個指標遍歷兩個字串共同大小的部分。輪流將字串內容添加到 results 中。接著找出word1, word2中較大的字串。
：如果其中一個字串比另一個字串長，那麼在遍歷到較短字串的結尾後，我們只需要將剩餘的長度部分從較長字串中添加到 `mergedResult`中即可。
👨🏫：這想法蠻不錯的，可以嘗試著寫出來
### 利用一個指標，迴圈只跑共同大小的區間
```cpp
class Solution {
public:
std::string mergeAlternately(std::string word1, std::string word2) {
int length = min(word1.length(), word2.length());
int i = 0;
std::string mergedResult = "";
while (i < length) {
mergedResult += std::string(1, word1[i]) + std::string(1, word2[i]);
i++;
}
if (length == word1.length()) {
mergedResult += word1.substr(i);
} else if (length == word2.length()) {
mergedResult += word2.substr(i);
}
return res;
}
};
```
👶：時間複雜度：O(n) n 是最小的字串的大小
## [1679. Max Number of K-Sum Pairs](https://leetcode.com/problems/max-number-of-k-sum-pairs/?envType=study-plan-v2&envId=leetcode-75)
> [模擬面試錄影](https://youtu.be/5wI8Fv58Ssc)
### 模擬面試過程
👨🏫：還有一些時間，我們來看一下接下來這個問題。我會給你一個整數陣列 nums 和一個整數 k，希望你從陣列中挑選兩個數字，使它們的總和等於 k，然後把它們從陣列中移除。最後呢，返回可以在這個陣列上執行的最大操作次數。
👶：讓我理解一下題目，題目意思是會有一個陣列包含了數個整數，希望從這個陣列中選出兩個整數，使其相加等於K。最後呢，找出這個陣列中最多可以相加的次數對嘛？
👨🏫：對的
👶：好的，這個問題我們可以使用兩個迴圈加上指標來實作，嘗試陣列的每一種兩兩配對，來找出相加可以等於K值的所有組合。
：我們需要使用兩個迴圈，第一個迴圈從第一個位置開始，而第二個迴圈從第一個迴圈指標+1的位置開始，直到第一個迴圈執行到陣列的最後一個元素。這個方法可以找到陣列的所有組合。如果兩兩相加組合等於K的正確解，操作次數+1，並將相加等於K的元素修改成-1，避免再次使用到。
：這樣呢，當迴圈結束後我們就得到了最大操作次數。最後，我們只需要回傳最大操作次數。
### 直觀解(2個迴圈解法)
```cpp
class Solution {
public int maxOperations(int[] nums, int k) {
int count = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i] == -1) continue;
for(int j = i + 1; j < nums.length; j++){
if(nums[j] == -1) continue;
if(nums[i] + nums[j] == k){
count++;
nums[i] = -1;
nums[j] = -1;
break;
}
}
}
return count;
}
}
```
👨🏫：很好，這個是一個蠻直觀的解法。在開發上我們常常會需要寫蠻大量的程式碼，需要使用到蠻多記憶體空間，而裝置上的Ram不一定每次都夠大，所以我們需要盡可能的減少使用記憶體的空間。如果是你的話，有什麼方法可以讓這個程式減少記憶體空間用量，且不影響程式架構和時間複雜度甚至減少呢？
👶：好的，我有一個想法。如果一個陣列是排序過的，且是由小排到大，那我們只需要一次迴圈即可以找到所有配對組合。
：這個想法是使用 2 個指標，一個從陣列的頭開始，另一個從陣列的尾巴開始。向陣列的中間找尋兩兩相加=K的值
1. 如果 `sum` 等於目標值 `k`，代表找到目標，所以將 `head`往右移一位，以及tail左移一位。
2. 如果 `sum` 小於目標值 `k`，表示我們需要增加 `sum` 的值，所以將 `head`往右移一位。
3. 如果 `sum` 大於目標值 `k`，表示我們需要減少 `sum` 的值，所以將 `tail`往左移一位。
：這樣的時間複雜度則會下降至O(nlogn)，因為我們可以先使用sort()對整數陣列進行排序，這個排序操作的時間複雜度是O(n log n)。接著，我們使用兩個指針(head和tail)在排序後的陣列中進行搜索。這個搜索過程的時間複雜度是O(n)，因為head和tail最多會遍歷整個陣列一次。最後，整個解法的時間複雜度是O(n log n)3.
👨🏫：這想法蠻不錯的，可以試著把他寫出來
### 一個指標(減少指標使用數量)
```cpp
class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
Arrays.sort(nums);
int head = 0;
int tail = nums.size()-1;
int opts = 0;
while(head<tail){
int sum = nums[head] + nums[tail];
if(sum == k){
opts += 1;
head += 1;
tail -= 1;
}
else if(sum < k){
head += 1;
}
else if(sum > k){
tail -= 1;
}
}
return opts;
}
};
```
👶：時間複雜度：O(nlogn)＋O(n) = O(nlogn)
---
## [283. Move Zeroes](https://leetcode.com/problems/move-zeroes/description/?envType=study-plan-v2&envId=leetcode-75)
> [模擬面試連結](https://youtu.be/G1sDxDh_aAI)
### 模擬面試過程
👨🏫：Welcome to the interview! Today, we're gonna do a coding assessment. So, here's the deal: You will get an array called `nums`, and your task is to move all the zeros to the end of it while keeping the other elements in the same order.
👶：OK, let me clarify the objective of the assessment. We have an array of integers that may include both zeros and non-zero values, such as (1, 2, 3, 4). Our goal is to rearrange the array by moving all the zeros to the end while keeping the order of the non-zero integers.
For example, let's consider the following integer array: 1, 0, 0, 2, 3, 0, 4. Our objective is to shift the zeros to the end of the array. After performing some necessary actions, the array will be transformed into 1, 2, 3, 4, 0, 0, 0.
👨🏫：yes, you are right.
👶：OK, the first step of my approach is that we count the number of zeros in the array `nums`. This count will help us determine how many zeros need to be moved to the end.
👶: To count the number of zeros, I will iterate through the `nums`array and increment a counter variable whenever I encounter a zero.
👶: In the second step, we create a new vector called `ans`. We will use this vector to store the non-zero elements while keeping their relative order. So, We need to iterate through the original array `nums` and add the non-zero elements to `ans`.
👶: In the third step, we need to append the required number of zeros to the end of the `ans` vector. This number is based on the count of zeros we calculated in the first step.
👶: Finally, we copy the elements from **`ans`** back into the original array **`nums`** to complete the operation.
👶: The time complexity of the this approach is O(n)
👨🏫：That make sense, you can code it down.
### 使用二個Vector，一個用作暫存整數陣列
```cpp
void moveZeroes(vector<int>& nums) {
int n = nums.size();
// Count the zeroes
int numZeroes = 0;
for (int i = 0; i < n; i++) {
numZeroes += (nums[i] == 0);
}
// Make all the non-zero elements retain their original order.
vector<int> ans;
for (int i = 0; i < n; i++) {
if (nums[i] != 0) {
ans.push_back(nums[i]);
}
}
// Move all zeroes to the end
while (numZeroes--) {
ans.push_back(0);
}
// Combine the result
for (int i = 0; i < n; i++) {
nums[i] = ans[i];
}
}
```
👨🏫: In this approach you create two array to achieve the algorithm, But in the real world, we want to minimize the memory usage to keep program loading light. So, do you have any ideas on how we can reduce memory usage while maintaining the same time complexity?
👶: of-course. I have a idea to reduce memory usage but keep the same time complexity. we can just use one array to achieve this algorithm.
👶: First , We can initialize an integer variable to keep track of the index where the last non-zero element should be placed.
👶: Second, we can Iterate through the array using a for loop. If the current element **`nums[i]`** is not equal to 0, it means we have found a non-zero element. In this case, we copy this element to the **`lastNonZero`** position in the array and increment **`lastNonZero` position**
👶: In the third step, After processing all elements in the array, all non-zero elements are now at the beginning of the array, and poition of **`lastNonZero` pointer** is behind the last non-zero element.
👶: the final step, we complete the operation, iterate through the remaining elements in the array starting from **`lastNonZero`** position and set them to 0. This step ensures that all zeros are moved to the end of the array.
👶: that it, after conducting all the step we have a integer array that **satisfied the algorithm.**
### 僅使用一個Array(減少Array使用數量)
```cpp
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int lastNonZeroFoundAt = 0;
// If the current element is not 0, then we need to
// append it just in front of last non 0 element we found.
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != 0) {
nums[lastNonZeroFoundAt++] = nums[i];
}
}
// After we have finished processing new elements,
// all the non-zero elements are already at beginning of array.
// We just need to fill remaining array with 0's.
for (int i = lastNonZeroFoundAt; i < nums.size(); i++) {
nums[i] = 0;
}
}
};
```
👶: finally the time complexity is O(n), and the space complexity is Big O of (1)
### 初步檢討
* Interviewer講解題目時可以舉一個實際應用場景，避免直接照著LeetCode題目唸出來
* Repeat 問題時，Example可以多講幾個(講一個Base case, 例外Case等)
* [3:71](https://www.youtube.com/watch?v=ZChpF6fim00&t=371): 寫迴圈前可以先講這個迴圈的功能和結束條件，接著才講細節(Word1/Word2加入MergeResult的時間點)
* 說話卡卡的 (會重複講同一個兩個好幾次才講清楚 e.g., word1, word2講兩三次),
* test case 可以用兩個/以上(word1/word2同樣長度, word1/word2不同長度的情況等)
* 寫完程式碼&測試後要記得分析時間複雜度和空間複雜度
* 英文口說需要再加強
### 改善方法
* 事先先想好可以演算法應用場景，避免講出題目關鍵字
* 腦中如果沒有明確的想法，可以先講出一個關鍵字給予Interviewer反應，再適當的停頓想好再說。不慌張。
* 可以將先寫好整個程式的主要步驟的註解，讓Interviewer了解程式的主要區塊、功能，也方便自己分段講解程式
* 需要練習英文口說(自己寫程式時可以考慮碎碎念)。
## 第二次作業-他評 01
### 關於 interviewer
- [ ] 優點
* 在 interviewee 完成題目作答後有引導答題者精簡程式碼。
- [ ] 可改進的地方
* 可以將原題經過修飾改成情境題。
* [2:10](https://youtu.be/ZChpF6fim00?si=xJMUPVNyZPnOkzM9&t=70): 這邊應該對 interviewee 的問題做出回應。
### 關於 interviewee
- [ ] 優點
* 在實作完程式碼後，有再將先前舉的例子透過程式碼演示一遍。
- [ ] 可改進的地方
* 麥克風收音的部分需要調整，聲音整體偏小且偶有爆音。
* [2:28](https://youtu.be/ZChpF6fim00?t=208)：出現不必要的語句。
* 如果要藉由程式碼再將例子演示，可以舉更短的例子，使面試時間更為充裕。
# 第二次作業-他評02
## interviewer
### 優點:
* 說話語調舒服且穩定
* [00:03](https://youtu.be/ZChpF6fim00?t=3)開啟一個很好的面試開場，而不是只是考官與考生的關係。
### 可改善的地方:
* 在闡述題目時，可以包裝成另一情境來闡述，來更了解interviewee的理解能力和應變能力
* 可以多和interviewee溝通
## interviewee
### 優點:
* 有符合REACTO的步驟
* 有多和interviewer交流
### 可改善的地方:
* [03:28](https://youtu.be/ZChpF6fim00?t=209)可以再確認一下剪接時是否有地方沒有剪到
* 有些片段收音不太好，如[02:23](https://youtu.be/ZChpF6fim00?t=143)
* 邊講解邊寫程式時可以再加快打字速度
* [13:10](https://youtu.be/ZChpF6fim00?t=790)避免講過多的 "恩..."
Sign in with Wallet
Connect another wallet