---
tags: info2022-homework
---
# 資訊科技產業專案設計 作業 1
contributed by <`魏昇芷 - tissue`>
## 答題流程
* Repeat: 重複提問，確認自己理解原本的要求
* Examples: 針對題目條件，舉出符合的案例，不限於特例
* Approach: 說明自己打算採用的方案
* Code: 撰寫程式
* Test: 若不能實際測試，那說明驗證程式的方案
* Opitmization: 優化程式碼
## [268. Missing Number](https://leetcode.com/problems/missing-number/)
### 中文版
* 😈: 嗨！很高興你來參加我們的面試，那我們就開始 code interview 吧。
* 😈: 請你打開這份 google document，那今天第一題的敘述如畫面所示，題目會給你一個整數陣列，這個陣列含有 n 個不同的數字，而這些數字的範圍是從 0 ～ n，另外，在這個陣列中，所有的數字都是唯一的。而在這個範圍中會有一個整數是不存在陣列裡，請你找出這個數字並回傳這個數字。
* 😈: 比如說題目給你陣列 [0, 1, 2, 3, 4, 6]，你必須回傳 5
* 😬: 好，所以題目會提供一個 size 為 n 的整數陣列，然後陣列中的每個數字都落在範圍 0 ~ n，因為範圍 0 ~ n 總共有 n + 1 個數字，但陣列的大小為 n，所以會有一個數字不在這個陣列中，我需要做的是找出這一個在 0 ~ n 的範圍內，但不存在陣列之中的數字。
* 😈: 沒錯。
* 😬: 好，那舉例來說，假如題目給我一個陣列是 [0, 1, 3]，我要找到範圍在 0 ~ 3 中且不存在在這個陣列中的數字，也就是 2，而如果給我的陣列是 [0, 1, 2] 我要回傳 3。
* 😈: 是的。
* 😬: emmm ~ 那我的做法會是建立一個 set，然後逐一走訪這個陣列並將出現在陣列中的數字記錄於 set 中，再檢查範圍 0 ~ n，如果某個數字不存在 set 中就回傳那個數字。
* 😈: 這個方法聽起來是可行的，不過你這樣是不是需要配置額外的記憶體空間呢？
* 😬: 是的，我必須額外建立的一個 set，空間複雜度會是 O(n)，因為配置給 set 的空間大小正比於陣列的 size。
* 😈: 那有沒有不需要配置額外空間的做法?
* 😬: emmm ~ 我想可以先利用梯形公式算出 0 ~ n 的總和，再以 for loop 逐一走訪陣列中的元素，並將總和減去每一個元素，最終留下的值即為 missing number，而這樣的做法只需要新增一個變數，不需要額外配置記憶體。
* 😈: 好，那請以程式把剛剛的想法寫出來。
* 😬:
``` c++
// 那我先定義一下這個 function prototype 為
int findMissingNumber(vector<int> *v) {
int sum = 0;
int size = nums.size();
// 以梯行公式將 0 ~ n 的總和算出來
sum = (1 + size) * size / 2 ;
// 逐一走訪整個陣列將總和減去陣列中的元素
for(int i = 0; i < size; i++){
sum -= nums[i];
}
return sum;
}
```
* 😈: 那請你舉例來驗證你的程式碼。
* 😬:
:::info
說明：
Ex: [0, 1, 3]
* initial:
* sum = 0 + 1 + 2 + 3 = 6
* 進入 for loop
* i = 0: 6 - 0 = 6
* i = 1: 6 - 1 = 5
* i = 2: 5 - 3 = 2
剩餘的 2 即為 missing number
:::
* 😈: 好，那這邊想請問你，這題有沒有辦法不額外配置記憶體空間，且不使用任何加減乘除運算來得到答案？
* 😬: 我想這題可以利用 xor operation 的特性，當數字 x ^ x 的時候會得到 0，所以我只要將 0 ^ 1 ^ .. ^ n 的結果去對陣列中的每個元素做 xor operation，因為 x ^ x 相消，所以最後留下的數字即為 missing number。
* 😬:
:::info
說明：
Ex: [0, 1, 3]
* initial:
* res = 0 ^ 1 ^ 2 ^ 3
* iterate array
* i = 0: 0 ^ 1 ^ 2 ^ 3 ^ 1 = 1 ^ 2 ^ 3 ^ ~~0 ^ 0~~
* i = 1: 1 ^ 2 ^ 3 ^ 1 = 2 ^ 3 ^ ~~1 ^ 1~~
* i = 2: 2 ^ ~~3 ^ 3~~ = 2
剩餘的 2 即為 missing number
:::
* 😈: 好，那你的作法已經達到我要的目的，我們可以開始下一題
## [2. Add Two Numbers](https://leetcode.com/problems/add-two-numbers/)
* 😈: 那今天第二題的敘述如 google document 所示，題目會給你兩條用來儲存數字 singly-linked list，而數字會以倒序的方式存於其中，一條 list 代表一串數字，如下方 `'342'` 會以 `2`->`4`->`3` 存於 singly-linked list 中，而每個 node 所存的數字範圍為 0 ~ 9，請你將兩條 list 中的所存的數字相加，並回傳儲存相加結果的 list。
:::info
ListNode 的結構體:
```c
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
```
:::
* 😬: 好！所以題目會給我兩條 singly-linked list，這兩條 list 各以倒敘的方式存了兩個數字，我需要把這兩個數字相加，一樣以倒序的方式將相加後的結果存於 singly-linked list 中。
* 😈: 沒錯！
* 😬: 好，那舉例來說，假如題目給我一條 singly-linked list 是 `2`->`4`->`3`，和另一條 `5`->`6`->`4`，那代表要將數字 342 加上 465，結果為 807，並將結果 807 以 `7`->`0`->`8` 存於 singly-linked list 中。
* 😈: 是的。
* 😬: emmm ~ 那我的做法會是先利用迴圈逐一走訪兩條 list 中的節點，將節點的值相加並存於新的 list 中，另外，必須考慮進位的問題還有節點是否為空的問題，因為兩條 list 的長度可能不同。
* 😈: 這個想法是可行的，那請開始 coding 吧。
* 😬:
```clike
// 我先定義一下這個 function prototype 為 ListNode* addTwolist(ListNode* l1, ListNode* l2)
ListNode* addTwolist(ListNode* l1, ListNode* l2)
{
// 先判斷 l1 或 l2 是否為空
if (!l1)
return l2;
if (!l2)
return l1;
int carry = 0, res = 0;
ListNode* newHead = NULL, *cur;
while(1) {
// 設定 l1 和 l2 的中止條件
if(!l1 && !l2)
break;
int val1 = 0, val2 = 0;
// 檢查 l1 是否已經走訪完畢
if (l1) {
val1 = l1->val;
l1 = l1->next;
}
// 檢查 l2 是否已經走訪完畢
if (l2) {
val2 = l2->val;
l2 = l2->next;
}
// 算出總和後，計算 carry 以及以 mod 10 使結果只留下個位數
res = val1 + val2 + carry;
carry = res / 10;
res %= 10;
// 將結果存於新建的 ListNode 中
if (!newHead) {
newHead = new ListNode(res);
cur = newHead;
} else {
cur->next = new ListNode(res);
cur = cur->next;
}
}
// 最後回傳新建的 list head
return newHead;
}
```
* 😈: 那請你驗證你的程式碼。
* 😬:
:::info
說明：
Ex: 342 + 465
* initial:
l1: 2 -> 4 -> 3
l2: 5 -> 6 -> 4
* 進入 for loop
* node1: 2 + 5 + 0 -> res = 7, carry = 0
* node2: 4 + 6 + 0 -> res = 0, carry = 1
* node3: 3 + 4 + 1 -> res = 8, carry = 0
回傳 7 -> 0 -> 8
:::
* 😈: 不過你的程式碼目前是存在問題的，無法滿足所有的情形。
* 😬: 不好意思，我確認一下。
* 😈: 你可以試試看 99 + 1 這筆測資。
* 😬: 喔！我少檢查了一種情況是 l1 和 l2 都走訪完但還有進位的情況，比須在檢查中止條件的部分多檢查 carry。
```clike
ListNode* addTwolist(ListNode* l1, ListNode* l2)
{
if (!l1)
return l2;
if (!l2)
return l1;
int carry = 0, res = 0;
ListNode* newHead = NULL, *cur;
while(1) {
// 在中止條件補上 carry
if(!l1 && !l2 && !carry)
break;
int val1 = 0, val2 = 0;
if (l1) {
val1 = l1->val;
l1 = l1->next;
}
if (l2) {
val2 = l2->val;
l2 = l2->next;
}
res = val1 + val2 + carry;
carry = res / 10;
res %= 10;
if (!newHead) {
newHead = new ListNode(res);
cur = newHead;
} else {
cur->next = new ListNode(res);
cur = cur->next;
}
}
return newHead;
}
```
:::info
說明：
Ex: 99 + 1
* initial:
l1: 9 -> 9
l2: 1
* 進入 for loop
* node1: 9 + 1 + 0 -> res = 0, carry = 1
* node2: 9 + 0 + 1 -> res = 0, carry = 1
* node3: 0 + 0 + 1 -> res = 1, carry = 0
回傳 0 -> 0 -> 1
:::
* 😈: 程式部分都沒問題了，這邊想請問你一下，請你設想一個情境，而這個情境是適何應用這個演算法。
* 😬: 好，我認為假如今天要做大數運算的時候，也就是數字超過 64 bit 可表示的範圍，我們先以字串的形式來儲存數字，要運算時，先將原本以字串儲存的數字改以倒序的方式存於 singly-linked list 中，再用到剛剛的演算法把結果存於另一條 list，最後將 list 中的數字再轉以字串儲存。
* 😈: 其實一定也不轉成 singly-linked list 直接用字串算的方法，那你覺得妳多了轉成 list 的成本，那轉成 list 的優勢在哪？
* 😬: 我覺得差別會在元素位移的彈性，因為字串是以字元陣列來存，舉剛剛 99 + 1 的情形來說，當以字串做運算式，我需要把元素 0 和 1 都往後移一位，才能將進位的 1 放入元素 0，而且還要確保一開始分配的字串有足夠的空間讓我們做位移。相較之下，用 singly-linked list 做元素位移和分配額外空間就方便許多。
::: info
說明：
Ex: 99 + 1
* char a = "99"
* char b = "1"
1. step 1 : "90", carry = 1
2. step 2 : "00", carry = 1
3. step 3 : 先位移成 "X00" 接著放入 carry 變為 "100"
:::
* 😈: 假如我今天想以 multi-thread 的方式來加速你上述的演算法，你覺得須要考慮到的議題有哪些？請簡單從你的程式碼中指出。
* 😬: 我認為第一點就是 carry 的問題， carry 要在前面的 node 完成計算後才會傳給後面的 node，因此 carry 的部分會讓運算難以平行化。
* 😬: 第二點是我們會建立 new list 來回傳兩條 list 相加後的結果，假如 thread 不能按照順序完成任務，那在這條記最終結果的 new list 中，node 的順序會與我們想要的結果不同，比如第二個 thread 比第一個 thread 先完成計算，這樣第二個 node 和第一個 node 順序就會對調。
* 😈: 那今天我還是想用 multi-thread 的方式，你會利用怎樣的方式來保證順序?
* 😬: 我會設定 thread 的優先權，做越前面計算的 thread 優先權越高，比如說有三個 thread，優先權 thread 1 > thread 2 > thread 3，接著會利用到 condition variable，先把三個 thread 都卡在上面，然後這個 condition variable 跟 signal 機制必須特別設計過，就是我每次 signal 都是喚醒優先權最高的那個 thread，所以我的 main thread 會先喚醒 thread 1，接著 thread 1 完成任務後會接著喚醒 thread 2，thread 2 完成任務後會接著喚醒 thread 3，這樣就可以做到讓 thread 按我想要的順序來完成任務。
* 😈: OK 很好!! 那我們今天的 interview 到此結束感謝你的參與！
### [26. Remove Duplicates from Sorted Array (English)](https://leetcode.com/problems/remove-duplicates-from-sorted-array/)
* 😈: Hello! Welcome to our interview.
* 😈: OK! So, please open this google document. Today's problem is that I'll give you an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once and return the number of unique elements. The relative order of the elements should be kept the same and the range of the elements from `-100` to `100`.
* 😈: You can place the result in the first part of the array nums without changing the array size. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
* 😈: For example, if the array is [1,1,2], you jsut need to change array to [1,2,X] and return 2, because you have 2 unique element. It does not matter what X really is.
* 😬: OK~ You'll give me an integer array contains duplicates and the elements of array is sorted in non-decreasing order. Suppose that there is kth unique elements in array. What I need to do is put these unique elements in first kth elements and return k.
* 😈: Right!
* 😬: OK~ my solution is that I'll build a integer set and an integer to record the number of unique number, then iterate the numbers in this array. I'll check whether the number exist in the set or not. If the number does not exist in the set, I will put it to the first part. Otherwise, I'll ignore it.
* 😈: Your solution is feasible, but this solution would allocate extra memory. Could you figure out another solution without allocating extra memory?
* 😬: emmm~ This array is sorted in non-decreasing order. So, I think I can use this feature. I just need to declare two integer, one is for record the number of unique numbers, another is record number I iterate previously. When iterating array, I'll check whether the number is equal to the number I iterate previously. if number is not equal to the number I iterate previously, I will put it to the first part of array. Otherwise, I'll ignore it, In the end, return the integer for record the number of unique numbers.
* 😈: Sounds good. you can code it up
* 😬:
``` c++
// first, I declare the function prototype
int removeDuplicates(vector<int>& nums) {
// then I declare two integer, one is for record the number of unique numbers, another is record number I iterate previously. Because the elements' range from -100 to 100, I set this integer to 101 from conflict.
int count = 0, cur = 101;
// iterate the array
for (int i = 0; i < nums.size(); i++) {
// check whether the number is equal to the number I iterate previously
if (cur != nums[i]) {
// if number is not equal to the number I iterate previously, I will put it to the first part.
cur = nums[i];
nums[count] = cur;
count++;
}
}
// return the integer for record the number of unique numbers
return count;
}
```
* 😈: OK~ Please use some examples to validate your code.
* 😬:
::: info
* initial: [1,1,2]
* Iterate array
* i = 0, [1,1,2] count = 1
* i = 1, [1,1,2] count = 1
* i = 2, [1,2,2] count = 2
return 2
* initial: [0,0,1,1,1,2,2,3,3,4]
* Iterate array
* i = 0, [0,0,1,1,1,2,2,3,3,4] count = 1
* i = 1, [0,0,1,1,1,2,2,3,3,4] count = 1
* i = 2, [0,1,1,1,1,2,2,3,3,4] count = 2
* i = 3, [0,1,1,1,1,2,2,3,3,4] count = 2
* i = 4, [0,1,1,1,1,2,2,3,3,4] count = 2
* i = 5, [0,1,2,1,1,2,2,3,3,4] count = 3
* i = 6, [0,1,2,1,1,2,2,3,3,4] count = 3
* i = 7, [0,1,2,3,1,2,2,3,3,4] count = 4
* i = 8, [0,1,2,3,1,2,2,3,3,4] count = 4
* i = 9, [0,1,2,3,4,2,2,3,3,4] count = 5
return 5
:::
* 😈: OK~ But the momory usage is important issue. Can you figure out some method to clean useless data and only leave the unique data.
* 😬: I will subtract the number of unique data from the size of original array, the result is the number of useless data. For example, the number of useless data in [1,2,2] is 1, so I pop one data from the back. The other example is [0,1,2,3,4,2,2,3,3,4], total size 10 - the number of unique data 5 is 5, so the number of useless data in [0,1,2,3,4,2,2,3,3,4] is 5, so I need to pop five data from the back.
* 😈: Great! Thank you for your participation and hope you have a nice day. Byebye！
Sign in with Wallet
Connect another wallet