# 資訊科技產業專案設計 HW1
###### tags: `資訊科技產業專案設計`
* Repeat: 重複提問，確認自己理解原本的要求
* Examples: 針對題目條件，舉出符合的案例，不限於特例
* Approach: 說明自己打算採用的方案
* Code: 撰寫程式
* Test: 若不能實際測試，那說明驗證程式的方案
* Opitmization: 優化程式碼
## 268. Missing Number
### 中文版
* 😈: 嗨！你好 那我們開始 code interview 吧
* 😈: 今天的題目是假如我給你一個整數 array 其中含有 n 個不同的數字， 而這些數字的範圍是從 0 ～ n, 在此範圍中有一個整數是不存在 array 裡的，請找出這個數字並回傳這個數字。
* 😬: 所以題目會提供一個 size 為 n 的整數 array, 然後 array 中的數字都在範圍 0 ~ n, 我需要做的事是找出一個數字在 0 ~ n 的範圍內, 但不存在這個 array 之中
* 😈: 沒錯
* 😬: 那假如題目給我一個陣列中 [0, 1, 3] 我要回傳 2, 如果給我的是 [0, 1, 2] 我要回傳 3
* 😈: 是的
* 😬: emmm ~ 我想我的做法會是建立一個 set, 然後遍歷這個 array 並將出現在 array 中的數字記錄於 set 中, 再檢查 0 ~ n， 如果某個數字不存在 set 中就 return 那個數字
* 😈: 聽起還不錯, 那開始 coding 吧
``` c++
// 首先我先建立一個 set 和變數 size
set<int> s;
int size = nums.size();
// 接著用一個 for loop 遍歷這個 array, 將這個 array ˊ中出現的數字存進 set 中
for(int i = 0; i < size; i++) {
s.insert(nums[i]);
}
// 接著在用一個 for loop 檢查數字 0 到 n - 1 如果不在 set 中代表此數字不存在 array 中, 返回此數字
for(int i = 0; i < size; i++) {
if(!s.count(i))
return i;
}
// 如果 0 ~ n - 1 都存在, 那 mssing number 就是 n
return size;
```
* 😬: 因為容器 set 的操作時間複雜度是 O($logn$), 所以在 for loop 中對 set 做操作其時間複雜度是 O($nlogn$)
* 😈: 那請你驗證你的程式碼
* 😬:
:::info
說明：
Ex: [0, 1, 3]
* initial:
* set<>
* 進入 1st for loop
* i = 0: 找到 0 寫入 set => set<0>
* i = 1: 找到 1 寫入 set => set<0, 1>
* i = 2: 找到 3 寫入 set => set<0, 1, 3>
* 進入 2st for loop
* i = 0: 0 有在 set 中 => continue
* i = 1: 1 有在 set 中 => continue
* i = 2: 2 不在 set 中 => 2 為 missing number 故回傳
:::
* 😈: 那有沒有不需要 set 的做法 ?
* 😬: emmm ~ 我想可以先算出 0 ~ n 的總和, 再以 for loop 遍歷 array 中的 element, 並將總和減去每一個 element, 最終留下的值即為 missing number
* 😈: 聽起可以, 那請以程式寫出來
``` c++
int sum = 0;
int size = nums.size();
// 以梯行公式將 0 ~ n 的總和算出來
sum = (1 + size) * size / 2 ;
// 遍歷整個 array 將總和減去 array 中的 element
for(int i = 0; i < size; i++){
sum -= nums[i];
}
return sum;
```
* 😬: 因爲在 for loop 中做的是時間複雜度為 O(1) 的操作, 所以此演算法的時間複雜度為 O(n)
* 😈: 那請你驗證你的程式碼
* 😬:
:::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
:::
* 😈: 讚 那我們今天的 interview 到此結束感謝你的參與！
#### 檢討
* 一開始把寫完程式寫完後沒有好好的 check, 再後來驗證程式碼時才找出錯誤並修改
* 影片中 interviewer 和 interviewee 白板程式碼畫面不一致, 因為是分開錄完再剪接, 導致畫面不一致, 下次會注意
### English version
* 😈: Hello！ Let's start our code interview
* 😈: today's problem is that if I give you an array contains n different numbers, and these numbers are in the range from 0 to n. Here is a number in this range and doesn't exist in this array, please find out and return it.
* 😬: So you'll give me array with size of n, and the element in this array is in the range 0 to n. what I need to do is finding out a number in this range and doesm't exist in the given array.
* 😈: exaltly
* 😬: So if the given array is [0, 1, 3], then I will return 2, if the given array is [0, 1, 2], then I will return 3
* 😈: yes
* 😬: Ok ~ my solution is I will build a integer set, and iterate the number in this array and record it in the set, then check the number from 0 to n, if the number is not recorded in set, I will return this number
* 😈: Sounds good. Let's code it up
``` c++
// first, I build a integer set and declare a variable size to store the size of array
set<int> s;
int size = nums.size();
// then use for loop to iterate the number in this array and record it in the set
for(int i = 0; i < size; i++) {
s.insert(nums[i]);
}
// then use another for loop to check the number from 0 to n - 1, if the number is not recorded in set, I will return this number
for(int i = 0; i < size; i++) {
if(!s.count(i))
return i;
}
// if all the number form 0 to n - 1 is recorded in set, it means the missing number is n
return size;
```
* 😬: beacuse the time complexity of the set operation is O($logn$) and I operate set in a for loop, the time complexity of this algorithm is O($nlogn$)
* 😈: Ok, please validate your code
* 😬:
:::info
Description：
Ex: [0, 1, 3]
* initial:
* set<>
* enter 1st for loop
* i = 0: I will find out 0 and record in set => set<0>
* i = 1: I will find out 1 and record in set => set<0, 1>
* i = 2: I will find out 3 and record in set=> set<0, 1, 3>
* enter 2st for loop
* i = 0: 0 is recorded in set => continue
* i = 1: 1 is recorded in => continue
* i = 2: 2 is not recorded in set => so 2 is missing number
:::
* 😈: Ok, and can you solve this without set ?
* 😬: emmm ~ I think I will compute the sum from 0 to n, then iterate the array and subtract each element from the sum. Finally, the remain sum value is missing number
* 😈: OK, please present your solution with code
``` c++
int sum = 0;
int size = nums.size();
// first, I compute the sum from 0 to n with trapezoid formula
sum = (1 + size) * size / 2 ;
// then I use foor loop to iterate the array and subtract each element from the sum.
for(int i = 0; i < size; i++){
sum -= nums[i];
}
So, the remain sum value is missing number and return it
return sum;
```
* 😬: Beacuse the operation in for loop is O(1), so the time complexity of this algorithm is O(n)
* 😈: Ok, please validate your code
* 😬:
:::info
說明：
Ex: [0, 1, 3]
* initial:
* sum = 0 + 1 + 2 + 3 = 6 (the sum form 0 to 3 is 6)
* 進入 for loop
* i = 0: 6 - 0 = 6 (6 substrat 0 is 6)
* i = 1: 6 - 1 = 5 (6 substrat 1 is 5)
* i = 2: 5 - 3 = 2 (6 substrat 3 is 2)
the remain number 2 is missing number
:::
* 😈: Great! Thank you for your participation and hope you have a nice day. byebye！
#### 檢討
## 242. Valid Anagram
### 中文版
* 😈: 嗨！你好 那我們開始 code interview 吧
* 😈: 今天的題目是假如給你兩個字串, 請檢察是否能透過重新排列字串一中的字元來形成字串二, 這些字元都是小寫的英文字母
* 😬: 所以我會拿到兩個字串, 然後去檢查這兩個字串所使用到的字元以及用到的字元的數量是否一樣, 如果是回傳 true, 否則回傳 false
* 😈: 沒錯
* 😬: 那假如他給我 "abc" 和 "cba" 我就回傳 true, 如果給我的是 "abb" 和 "cba" 我就回傳 false
* 😈: 是的
* 😬: emmm ~ 那我的作法是會先講兩個字串排序, 然後比較排序後的後的兩個字串是否相同, 如果一樣就回傳 true, 否則回傳 false
* 😈: 聽起可以, 那請以程式寫出來
``` c++
// 首先先將這兩個字串排序
sort(s.begin(), s.end());
sort(t.begin(), t.end());
// 接著比較排序好的字串是否相同, 如果相同則回傳 true
if(s == t)
return true;
// 不相同則回傳 false
return false;
```
* 😬: 由於 sort function 的時間複雜度是 O($nlogn$), 所以此演算法的時間複雜度是 O($nlogn$)
* 😈: 那請你驗證你的程式碼
* 😬:
::: info
說明
initial: s: "abc", t: "cba"
排序後 s: "abc", t: "abc"
因為 s == t 所以回傳 true
那假如
initial: s: "abb", t: "cba"
排序後 s: "abc", t: "abc"
因為 s != t 所以回傳 false
:::
* 😈: 那有沒有時間複雜度為 linear time 的方法
* 😬: emmm~ 我想我會以一個大小為 26 的 array 來記錄每個小寫字母在字串中的使用數量, 分別 trace 這兩個字串中的每個字元, 如果在第一個字串中出現, 我會把此字元對應到的 array element + 1, 如果在第二個字串中出現, 我會把此字元對應到的 array element - 1, 最後去 trace 這個 array, 如果全為 0 則回傳 true, 否則回傳 false.
* 😈: 聽起可以, 那請以程式寫出來
``` c++
// 先宣告一個 size 為 26 的 array 並初始化為 0
int count[26] = {0};
// 接著 trace 字串 s 中的每個字元, 把字元對應到的 array element + 1
for(int i = 0; i < s.length(); i++){
++ count[s[i] - 'a'];
}
// 然後 trace 字串 t 中的每個字元, 把字元對應到的 array element - 1
for(int i = 0; i < t.length(); i++){
-- count[t[i] - 'a'];
}
// 最後 trace array 中的每個 element, 如果有不為 0 的則 return false
for(int i = 0; i < 26; i++) {
if(count[i] != 0)
return false;
}
// 皆為 0 則 return true;
return true;
```
* 😬: 因為兩個 for loop 都是做 O(1) 的操作, 所以時間複雜度為 linear time
* 😈: 那請你驗證你的程式碼
* 😬:
::: info
說明
* initial: s: "abc", t: "cba" count: {0, 0, 0 ....}
* 進入 1st for loop
* i = 0: 找到 a 把對應的 element + 1 => count {1, 0, 0 ....}
* i = 1: 找到 b 把對應的 element + 1 => count {1, 1, 0 ....}
* i = 2: 找到 c 把對應的 element + 1 => count {1, 1, 1 ....}
* 進入 2st for loop
* i = 0: 找到 c 把對應的 element - 1 => count {1, 1, 0 ....}
* i = 1: 找到 b 把對應的 element - 1 => count {1, 0, 0 ....}
* i = 2: 找到 a 把對應的 element - 1 => count {0, 0, 0 ....}
* trace array => array 中的 element 皆為 0 所以回傳 true
那第二個 case
* initial: s: "abb", t: "cba" count: {0, 0, 0 ....}
* 進入 1st for loop
* i = 0: 找到 a 把對應的 element + 1 => count {1, 0, 0 ....}
* i = 1: 找到 b 把對應的 element + 1 => count {1, 1, 0 ....}
* i = 2: 找到 b 把對應的 element + 1 => count {1, 2, 0 ....}
* 進入 2st for loop
* i = 0: 找到 c 把對應的 element - 1 => count {1, 2, -1 ....}
* i = 1: 找到 b 把對應的 element - 1 => count {1, 1, -1 ....}
* i = 2: 找到 a 把對應的 element - 1 => count {0, 1, -1 ....}
* trace array => array 中的 i = 1 不為 0 顧回傳 false
:::
* 😈: 嗯 沒問題 那這邊想問你認為著個演算法會應用在什麼情況下
* 😬: 我想應該會應用在 hash table 中的 hash function 上, 假如有一個 hash table 他的 key value 是一個字串, 而對應的 bucket 存到是用到與 keyvalue 字串相同字元然後用到的數量也一樣的字串, 那 hash funciton 就是使用這演算法
* 😈: 那假如這些字元不是只有小寫英文字母呢？
* 😬: 那我會把 array 改成用 map 來存對應字元及其使用到的數量
* 😈: 讚 那我們今天的 interview 到此結束感謝你的參與！
#### 檢討
### English version
* 😈: Let's start our code interview
* 😈: today's problem is that I will give you 2 string, please check if the string two can be formed by rearanging the character in string one. all the character in string is lowercase letter
* 😬: So, you will give me two strings, then I will check if the character and its quanity is equal in these two strings, if so, return true, and if not, I will return false
* 😈: exactly
* 😬: So, if the given strings are "abc" and "cba", I will return ture, and if the given strings is "abb" and "cba", I will return false.
* 😈: yes
* 😬: emmm ~ my solution is sorting these two strings, then check if these two sorted strings are equal,if so, I will return true, if not, I will return false.
* 😈: Sound good! you can code it up
``` c++
// first, I will sort these two strings
sort(s.begin(), s.end());
sort(t.begin(), t.end());
// then check if the string one is equal to string two, if these two sorted strings is equal return true
if(s == t)
return true;
// and if not, return false.
return false;
```
* 😬: because the time complexity of sort function is O($nlogn$), the time complexity of this algorithm is O($nlogn$)
* 😈: OK! please validate your code
* 😬:
::: info
Desciption
initial: s: "abc", t: "cba"
sorting s: "abc", t: "abc" // after sorting
because s equal to t so return true
那假如
initial: s: "abb", t: "cba"
sorting s: "abb", t: "abc" // after sorting
because s is not equal to t, so return false
:::
* 😬: Right! and can you design another algorithm, and it just need linear time ?
* 😈: emmm~ I think I will use an array with size of 26 to record the using quanity of charater, then I will trace these two strings, if the charater show in string one, I will increase the corresponding element, and if the charater show in string two, I will decrease the corresponding element.
Finally, I will trace this array, if all the element in this array is zero, I will return true, if not, return false;
* 😈: Sounds good, you can code it up
``` c++
// I will declare an array with size of 26
int count[26] = {0};
// then trace all the character in string s and increase the corresponding element of array
for(int i = 0; i < s.length(); i++){
++ count[s[i] - 'a'];
}
// then trace all the character in string t and decrease the corresponding element of array
for(int i = 0; i < t.length(); i++){
-- count[t[i] - 'a'];
}
// Finally, I will trace all the element in the array, if the element in the array is not equal zero, I will return false
for(int i = 0; i < 26; i++) {
if(count[i] != 0)
return false;
}
// if all the elements are equal to zero, I will return true
return true;
```
* 😬: because the operation in these two for loops is constant time, so the time complexity of this algorithm is linear time.
* 😈: OK! Please validate your code
* 😬:
::: info
說明
* initial: s: "abc", t: "cba" count: {0, 0, 0 ....}
* enter 1st for loop
* i = 0: increase the corresponding element of 'a' => count {1, 0, 0 ....}
* i = 1: increase the corresponding element of 'b' => count {1, 1, 0 ....}
* i = 2: increase the corresponding element of 'c' => count {1, 1, 1 ....}
* enter 2st for loop
* i = 0: decrease the corresponding element of 'c' => count {1, 1, 0 ....}
* i = 1: decrease the corresponding element of 'b' => count {1, 0, 0 ....}
* i = 2: decrease the corresponding element of 'a' => count {0, 0, 0 ....}
* trace array => all the elements are equal to zero, return true
那第二個 case
* initial: s: "abb", t: "cba" count: {0, 0, 0 ....}
* enter 1st for loop
* i = 0: increase the corresponding element of 'a' => count {1, 0, 0 ....}
* i = 1: increase the corresponding element of 'b' => count {1, 1, 0 ....}
* i = 2: increase the corresponding element of 'b' => count {1, 2, 0 ....}
* enter 2st for loop
* i = 0: decrease the corresponding element of 'c' => count {1, 2, -1 ....}
* i = 1: decrease the corresponding element of 'b' => count {1, 1, -1 ....}
* i = 2: decrease the corresponding element of 'a' => count {0, 1, -1 ....}
* trace array => the index = 1 element is not equal to zero, so return false
:::
* 😈: emmm, no problem, but what situation you will apply this algorithm
* 😬: I think I will apply it in hash funtion, if the keyvalue of hash table is a string, the bucket store the string which can be formed by rearanging the character in keyvalue string
* 😈: OK! and if the character in these strings it not only lowecase letters, what would do?
* 😬: I think, I will modify array to map, the key of this map is character and value is using quanity
* 😈: Great! Thank you for your participation and hope you have a nice day. byebye！
#### 檢討
* interviewer 在介紹題目的時候沒有介紹清楚
* 先講完才寫 code, 沒有邊寫邊講
* 時間複雜度部分沒有講得很詳細
* 講解第二種做法及驗證程式碼時常常卡住, 也有文法講錯的部分
* 用英文講應用的時候講的不是很明白
# 資訊科技產業專案設計 HW2
###### tags: `資訊科技產業專案設計`
### Chinese version
* 😈: 同學你好 那我們就開始今天的 code interview
* 😈: 那首先可以請你解釋一下 STL 關聯容器 set 的概念嗎
* 😬: set 就是一個記錄表, 是用來記錄某個值是否有存在,
* 😈: 好 那今天的題目是假如我給你一個 size 為 n 的整數 array， 而存在 array 中的數字, 範圍都是從 0 ～ n, 請找出一個整數在此範圍中但是不存在 array 裡面
* 😬: 所以題目會提供一個 size 為 n 的整數 array, 然後 array 中的數字都在範圍 0 ~ n, 我需要做的事是找出一個數字屬於範圍 0 ~ n , 但不屬於這個 array
* 😈: 沒錯
* 😬: 那假如題目給我一個陣列中 [0, 1, 3] 我要回傳 2, 如果給我的是 [0, 1, 2] 我要回傳 3
* 😈: 是的
* 😬: 好 那我會用 set 來記錄這個 array 中的所有數字, 再從 0 trace 到 n, 哪個數字不在 set 中那個數字就是答案
* 😈: OK, 那請你開始 coding
``` c++
// 先宣告一個 function 好比說叫 finsNumber()
// 傳入的參數是一個 vector
findNumber(vector<int> &v)
// 首先我先建立一個 set
set<int> s;
// 接著用一個 for loop 遍歷這個 array, 將這個 array 中出現的數字存進 set 中
for(int i = 0; i < size; i++) {
s.insert(nums[i]);
}
// 接著在用一個 for loop 檢查數字 0 到 n - 1 如果不在 set 中代表此數字不存在 array 中, 返回此數字
for(int i = 0; i < size; i++) {
if(!s.count(i))
return i;
}
// 如果 0 ~ n - 1 都存在, 那答案就是 n
return size;
```
* 😬:
:::info
說明：
Ex: [0, 1, 3]
* initial:
* set<>
* 進入 1st for loop
* i = 0: 找到 0 寫入 set => set<0>
* i = 1: 找到 1 寫入 set => set<0, 1>
* i = 2: 找到 3 寫入 set => set<0, 1, 3>
* 進入 2st for loop
* i = 0: 0 有在 set 中 => continue
* i = 1: 1 有在 set 中 => continue
* i = 2: 2 不在 set 中 => 2 為 missing number 故回傳
:::
* 😬: 因為 STL 中的 set 的操作時間複雜度是 O($logn$), 所以在 for loop 中對 set 做操作其時間複雜度是 O($nlogn$)
* 😈: 那假如今天不能使用 set, 你會怎麼做?
* 😬: emmm ~ 那我會以一個 size 為 n 的 array 去模擬 set 的行為
``` c++
//宣告一個 size 為 n 的 array, array 用來記錄, 比如 index = 0 就代表 0 有沒有出現
int count[nums.size()] = {0};
// 接著用一個 for loop 遍歷這個 array, 將這個 array 中出現的數字對應的 index 設為 1
for(int i = 0; i < nums.size(); i++) {
count[nums[i]] = 1;
}
// 接著從 0 trace 到 n - 1, 如果在這個 index 對應 的 array element 值不為 1 則 return
for(int i = 0; i < nums.size(); i++) {
if(!count[i])
return i;
}
// 如果 0 ~ n - 1 都是1, 那答案就是 n
return size;
```
* 😬: 因爲在 for loop 中做的是時間複雜度為 O(1) 的操作, 所以此演算法的時間複雜度為 O(n)
* 😈: 好那假設今天沒有其他限制, 我會給你一個整數 array, 請你找出範圍從 array 中 minimum ~ array 中 maximum 之間不在 array 中的數字, 題目一開始不會給你範圍, 那你會怎麼處理
* 😬: 所以我會得到一個 array, 我要找出這範圍在這個 array 中的 minimum 到 maximum, 但不存在在 array 中的所有數字
* 😈: 是
* 😬: 那我會先將 array 排序, 然後用 set 來記錄這個 array 中的所有數字, 然後以 array 第一個 index 為 for 迴圈起點, 最後一個 index 為終點, 去 trace 哪些數字不在 set 中就 push 進 vector, 最後回傳
* 😈: OK, 那請用程式碼呈現
``` c++
vector<int> findNumbers(vector<int> &nums) {
// 一開始先排序這個 vector
sort(nums.begin(), nums.end());
// 接著宣告一個整數 set and vector as return vector
int set<int> s;
vector<int> ret;
// 將 vector 中出現的數字放進 set 中
for(int i = 0 ; i < nums.size(); i++) {
set.insert(nums[i]);
}
// 接著以 vector 第一個元素的值為起始, 然後跑到最後一個元素的值, 去看哪些值不在 set 中就把值放進 return vector
for(int i = num[0]; i <= nums[nums.size() - 1]; i++){
if(!s.count(i))
ret.push_back(i);
}
// 最後回傳這個 vector
return ret;
}
```
* 😈: 不錯不錯, 那接著下一題, 我今天有兩個字串, 要請你幫我比對能否將第一個字串中的字元重新排列來產生第二個字串, 那這兩個字串都只會包含小寫英文字母
* 😬: 所以我會得到兩個字串, 我要做檢查的是如果可以把第一個字串中的字元重新排列來生成第二個字串,就回傳 true, 不能就回傳 false
* 😈: 是的
* 😬: 那我應該會將這兩個字串排序, 然後比對這兩個字串排序後是否一樣, 如果一樣就回傳 true, 不一樣就回傳 false
* 😈: 這是一個可行的辦法, 但有沒有不使用排序的方法
* 😬: emmm~ 那我應該會去確認這兩個字串中使用到的字元及其使用數量, 如果使用到的字元跟使用數量都一樣就代表可以透過第一個字串中的字元重排成第二個字串
* 😈: OK, 那請用程式碼呈現
* 😬:
``` c++
// 假設這個 function 叫 isArrange 可否重新排列, 然後參數是兩個 string str1 和 str2
bool isRearrange(string str1, string str2) {
// 宣告一個 size 為 26 的 array, 全都初始化為 0
int arr[26] = {0};
// 接著 trace 字串 str1 中的每個字元, 把字元對應到的 array element + 1
for(int i = 0; i < str1.length(); i++){
++ count[str1[i] - 'a'];
}
// 然後 trace 字串 str2 中的每個字元, 把字元對應到的 array element - 1
for(int i = 0; i < str2.length(); i++){
-- count[str2[i] - 'a'];
}
// 最後 trace array 中的每個 element, 如果有不為 0 的則 return false
for(int i = 0; i < 26; i++) {
if(count[i] != 0)
return false;
}
// 皆為 0 則 return true;
return true;
}
```
* 😬: 因為兩個 for loop 都是做 O(1) 的操作, 所以時間複雜度為 linear time
* 😬:
::: info
說明
* initial: s: "abc", t: "cba" count: {0, 0, 0 ....}
* 進入 1st for loop
* i = 0: 找到 a 把對應的 element + 1 => count {1, 0, 0 ....}
* i = 1: 找到 b 把對應的 element + 1 => count {1, 1, 0 ....}
* i = 2: 找到 c 把對應的 element + 1 => count {1, 1, 1 ....}
* 進入 2st for loop
* i = 0: 找到 c 把對應的 element - 1 => count {1, 1, 0 ....}
* i = 1: 找到 b 把對應的 element - 1 => count {1, 0, 0 ....}
* i = 2: 找到 a 把對應的 element - 1 => count {0, 0, 0 ....}
* trace array => array 中的 element 皆為 0 所以回傳 true
那第二個 case
* initial: s: "abb", t: "cba" count: {0, 0, 0 ....}
* 進入 1st for loop
* i = 0: 找到 a 把對應的 element + 1 => count {1, 0, 0 ....}
* i = 1: 找到 b 把對應的 element + 1 => count {1, 1, 0 ....}
* i = 2: 找到 b 把對應的 element + 1 => count {1, 2, 0 ....}
* 進入 2st for loop
* i = 0: 找到 c 把對應的 element - 1 => count {1, 2, -1 ....}
* i = 1: 找到 b 把對應的 element - 1 => count {1, 1, -1 ....}
* i = 2: 找到 a 把對應的 element - 1 => count {0, 1, -1 ....}
* trace array => array 中的 i = 1 不為 0 顧回傳 false
:::
* 😈: 那如果今天字串中所包含的字元不止是小寫字母呢
* 😬:
``` c++
bool isRearrange(string str1, string str2) {
// 那我會把 array 改成用 map, key 代表字元及 value 代表使用數量
map<char, int> m;
// 接著 trace 字串 str1 中的每個字元, 把字元對應到的 array element + 1
for(int i = 0; i < str1.length(); i++){
++ m[str1[i]];
}
// 然後 trace 字串 str2 中的每個字元, 把字元對應到的 array element - 1
for(int i = 0; i < str2.length(); i++){
-- m[str2[i]];
}
// 最後 trace map 中的每個 key 對應的 value, 如果有不為 0 的則 return false
for(auto it = m.begin(); it != m.end(); it++) {
if(it->second != 0)
return false;
}
// 皆為 0 則 return true;
return true;
```
* 😈: 很好!! 那我們今天的 interview 到此結束感謝你的參與！
### English version
* 😈: Hello!! how are you today?
* 😬: I'm fine today!
* 😈: Good! Let's start our code interview
* 😈: First, please explain the concept of associative container set in STL briefly
* 😬: set is a record table and is used to record certain value is exist or not, if the value is exist, it would be inserted in set
* 😈: OK! and today's problem is that I will give you an array contains n different numbers, and these numbers are in the range from 0 to n. Here is a number in this range and doesn't exist in this array, please find out and return it.
* 😬: So you'll give me an array with size of n, and the element in this array is in the range from 0 to n. what I need to do is finding out a number in this range and doesn't exist in the given array.
* 😈: exaltly
* 😬: So if the given array is [0, 1, 3], then I will return 2, if the given array is [0, 1, 2], then I will return 3
* 😈: yes
* 😬: emmm ~ I will use an integer set to record all the number in the set, then check the number from 0 to n, if the number is not recorded in set, I will return this number
* 😈: OK. Let's code it up
``` c++
// firstly, I declare a function and I call it findNumber()
// its parameter is an integer vector
findNumber(vector<int> &v)
// then I declare an integer set
set<int> s;
// and use a for loop to record all the number in this vector into set
for(int i = 0; i < size; i++) {
s.insert(nums[i]);
}
// then, use another for loop to trace number from 0 to n - 1, if number is not recorded in set, I will return this number
for(int i = 0; i < size; i++) {
if(!s.count(i))
return i;
}
// if 0 to n - 1 is recorded in set, it means the answer is n
return size;
```
* 😬:
:::info
Description：
Ex: [0, 1, 3]
* initial:
* set<>
* enter 1st for loop
* i = 0: I will find out 0 and record in set => set<0>
* i = 1: I will find out 1 and record in set => set<0, 1>
* i = 2: I will find out 3 and record in set=> set<0, 1, 3>
* enter 2st for loop
* i = 0: 0 is recorded in set => continue
* i = 1: 1 is recorded in => continue
* i = 2: 2 is not recorded in set => so 2 is missing number
:::
* 😬: because time complexity of a set operation is O($logn$), so the time complexity of a for loop is O($nlogn$)
* 😈: OK! could you solve this problem without set?
* 😬: emmm ~ I will use an array with size of n to imitate the behavior of set
``` c++
// first, I declare an array with size of n to record whether the number exists in vector, if the number exist in vector, index = number would be set to one
int count[nums.size()] = {0};
// then, use a for loop to iterate vector, and set the corresponding element of array count to one
for(int i = 0; i < nums.size(); i++) {
count[nums[i]] = 1;
}
// then, trace the number from 0 to n - 1, if element is not equal to 1, return its index
for(int i = 0; i < nums.size(); i++) {
if(!count[i])
return i;
}
if index from 0 to n - 1 in array count are equal to one, it means the answer is n
return size;
```
* 😬: Beacuse the operation in for loop is O(1), so the time complexity of this algorithm is O(n)
* 😈: OK! if all limit are removed, I will give you an integer array, the range of number is from the maximum of this array to the minimum of this array, but you don't know this range, how you solve it
* 😬: So, if you give an array [2, 4, 6, 8], and it should return [3, 5, 7]
* 😈: yes
* 😬: is it sorted array
* 😈: No
* 😬: my solution is sorting this array first, and use a set to record all the numbers in this array. then, use a for loop to trace from index = minimum of this array to maximum od this array, any number is not recorded in set would be pushed into return vector
* 😈: OK, please code it up
``` c++
vector<int> findNumbers(vector<int> &nums) {
// firstly, sort this vector
sort(nums.begin(), nums.end());
// then, declare an integer set and integer vector as return vector
int set<int> s;
vector<int> ret;
// record all the numbers in this vector nums
for(int i = 0 ; i < nums.size(); i++) {
set.insert(nums[i]);
}
// because the first element in vector nums is minimum and the last element is maximum, so index from the first element to the last, any index value is not recorded in set would be pushed into return vector
for(int i = num[0]; i <= nums[nums.size() - 1]; i++){
if(!s.count(i))
ret.push_back(i);
}
// finally, return this vector
return ret;
}
```
* 😈: nice, next question, I will give you two strings, please chack that if the string two can be formed by rearranging the character in string one. all the character in strings are lowercase letter
* 😬: So, you will give me two strings, what I need to do is checking if I can rearrange characters in string one to form string two, return true, if not, return false.
* 😈: Yes.
* 😬: I think my solution is sorting these two strings, then check if these two sorted strings are equal,if so, I will return true, if not, I will return false.
* 😈: it is feasible, but do you have other solution.
* 😬: emmm~ I will use an array with size of 26 to record the using quantity of charater, if using quantity of these two strings are equal, the string two can be formed by rearranging string one.
* 😈: OK, show your code
* 😬:
``` c++
// first, I declare a function, maybe call it isArrange and its parameter is two string
bool isRearrange(string str1, string str2) {
// I will declare an array with size of 26
int count[26] = {0};
// then trace all the character in string s and increase the corresponding element of array
for(int i = 0; i < s.length(); i++){
++ count[s[i] - 'a'];
}
// then trace all the character in string t and decrease the corresponding element of array
for(int i = 0; i < t.length(); i++){
-- count[t[i] - 'a'];
}
// Finally, I will trace all the element in the array, if the element in the array is not equal zero, I will return false
for(int i = 0; i < 26; i++) {
if(count[i] != 0)
return false;
}
// if all the elements are equal to zero, I will return true
return true;
}
```
* 😬:
::: info
Description:
* initial: s: “abc”, t: “cba” count: {0, 0, 0 …}
* enter 1st for loop
* i = 0: increase the corresponding element of ‘a’ => count {1, 0, 0 …}
* i = 1: increase the corresponding element of ‘b’ => count {1, 1, 0 …}
* i = 2: increase the corresponding element of ‘c’ => count {1, 1, 1 …}
* enter 2st for loop
* i = 0: decrease the corresponding element of ‘c’ => count {1, 1, 0 …}
* => count {1, 0, 0 …}
* i = 2: decrease the corresponding element of ‘a’ => count {0, 0, 0 …}
* trace array => all the elements are equal to zero, return true
Case two:
* initial: s: “abb”, t: “cba” count: {0, 0, 0 …}
* enter 1st for loop
* i = 0: increase the corresponding element of ‘a’ => count {1, 0, 0 …}
* i = 1: increase the corresponding element of ‘b’ => count {1, 1, 0 …}
* i = 2: increase the corresponding element of ‘b’ => count {1, 2, 0 …}
* enter 2st for loop
* i = 0: decrease the corresponding element of ‘c’ => count {1, 2, -1 …}
* i = 1: decrease the corresponding element of ‘b’ => count {1, 1, -1 …}
* i = 2: decrease the corresponding element of ‘a’ => count {0, 1, -1 …}
* trace array => the index = 1 element is not equal to zero, so return false
:::
* 😬: because the operation in these two for loops are constant time, so the time complexity of this algorithm is linear time
* 😈: OK! but if today, the character in these strings not only lowecase letters, what would do?
* 😬:
``` c++
bool isRearrange(string str1, string str2) {
// I will modify array to map, key means charater and value means using quantity
map<char, int> m;
for(int i = 0; i < str1.length(); i++){
++ m[str1[i]];
}
for(int i = 0; i < str2.length(); i++){
-- m[str2[i]];
}
// Finally, trace all value in map, any value is not equal to zero would return false;
for(auto it = m.begin(); it != m.end(); it++) {
if(it->second != 0)
return false;
}
// all zero, return true;
return true;
```
* 😈: Great! Thank you for your participation and hope you have a nice day. byebye！
Sign in with Wallet
Connect another wallet