# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者 : 孟宗竹-Bamboo
> LeetCode : 13. Roman to Integer
> [錄影: Problem1](https://www.youtube.com/watch?v=CnOwGRUJ5qA)
> LeetCode : 3. Longest Substring Without Repeating Characters
> [錄影: Problem2](https://www.youtube.com/watch?v=XDMrC7ThHjU)
> LeetCode : 20. Valid Parentheses
> [錄影: Problem3](https://www.youtube.com/watch?v=8Pgv-CL4hik)
> [Document Link](https://docs.google.com/document/d/12DHUrmUF2fhkPF-uNe_WnLTz8F4ix-u2J5QPDFGelVg/edit)
>
> **:man: : Interviewer**
> **:baby: : Interviewee**
## [13. roman-to-integer](https://leetcode.com/problems/roman-to-integer/)
> [錄影: Problem1](https://www.youtube.com/watch?v=CnOwGRUJ5qA)
### 測驗說明與問答
:man: : 同學您好，歡迎來參加我們公司的面試。請先自我介紹一下。
:baby: : 謝謝，我很高興能參加這個面試。我是孟宗竹bamboo，擁有計算機科學學士學位，並在過去的三年中在一家軟體開發公司工作。我在軟件開發領域有豐富的經驗，並且對數據結構和算法有一定的了解。
:man: : 我們公司非常注重技術能力，等下我會傳送一份文件給您，裡面會有一些您需要回答的問題。請問您有收到文件了嗎?
:baby: : 有，我有收到了。
:man: : 好第一個問題是我希望你能跟我說如何將羅馬符號轉為相對應的數字。羅馬數字由七個不同的符號表示：I、V、X、L、C、D 和 M。
| 符號 |值 |
| -------- | -------- |
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
羅馬數字通常從左到右，從最大到最小的順序書寫。然而如果符號並非由大到小，則表示發生了減法 : 共有六種情況下會使用減法：
(1). I 可以放在 V（5）和 X（10）的前面。
(2). X 可以放在 L（50）和 C（100）的前面。
(3). C 可以放在 D（500）和 M（1000）的前面。
希望你能夠回答 數字2 跟 4 以及49 分別用羅馬符號該如何表示 ?
:baby: : 好，那接下來我就來回答數字2 跟數字 49 該如何用羅馬符號表式。
數字 2 用羅馬數字表示為 II，只是兩個 1 相加在一起。
由上述的規則可以看到 : 數字 4 用羅馬數字表示不是為 IIII，應該是為IV，由此可以看到一個重複的符號不會出現超過4次以上，最多出現3次。因為如果需要出現4次，便可以透過減法的方式去表示。
數字 49 用羅馬數字表示便為 XXXIX ，不是IL，這裡也可以看到剛剛得到的小結論一個重複的符號不會出現超過3次以上。
:man: : 好那現在希望你能夠通過程式碼將羅馬符號，將其轉換為整數。
:baby: : 好，那接下我會用程式將羅馬符號轉為數字，我先將我的想法透過步驟的方式描述出來
我先用兩個範例說明 :
第一個範例是XIX，他會轉化為數字19。
一開始會將所有羅馬符號跑過一次，那在跑的過程中會將羅馬符號轉化為相對應的數字。
轉化完對應的數字後，會去檢查對應的數字是否有比下個數字小，也就是符合上述的規則，那這樣這個數字就是會用減法。
如果沒符合，那這個數字就用加法。當看到最後一個數字時因為後面沒有數字則用加法。
```
XIX
10 1 10 -> +10 -1 +10 -> 19
```
接下來用XCVIII說明，他會轉化為數字98。
```
XCVIII
10 100 5 1 1 1 -> -10 + 100 +5 +1 +1 +1 -> 98
```
接下來我會用步驟描述剛剛將羅馬符號轉為數字的過程
```
step 1 : run input string 跑過羅馬符號的input string
step 2 : map roman to number 跑的過程將符號轉為整數
step 3 : test if the number is smaller than next number 轉完後，檢查數字是否小於下一個數字
step 4 : if true : minus this number 如果小於下一個數字就會將他減掉這個數字
step 5 : if false : add this number 如果大於等於下一個數字就會將他加上這個數字
最後我們就可以得到答案了
```
:baby: : 接下來我將想法轉為程式碼
```cpp
int MAPPING(char symbol){
switch(symbol){
case ‘I’ : return 1;
case ‘V’ : return 5;
case ‘X’ : return 10;
case ‘L’ : return 50;
case ‘C’ : return 100;
case ‘D’ : return 500;
case ‘M’ : return 1000;
}
}
int main(string input){
int ans = 0;
for(int i=0;i<input.length()-1;i++){
int number = MAPPING(input[i])
if(number < MAPPING(input[i+1])) ans -= number;
else ans += number;
}
ans += MAPPING(input[input.length()-1]);
return ans;
}
```
:baby: : 接下來我用上述的例子來驗證程式碼是否正確
```
XIX 10 1 10 -> +10 -1 +10 = 19
XCVIII 10 100 5 1 1 1 -> -10 + 100 +5 +1 +1 +1 = 98
step 1 : input string
step 2 : string’s char -> number ?
step 3 : number < next number -> number -> -number
number >= next number -> number -> number
return ans
XIX len= 3 for (0-> 2)
i=0 number = 10 next_number = 1 ans += 10
i=1 number = 1 next_number = 10 ans -= 1
i= 2 ans += 10
return 19
XCVIII len = 6 for (0->5)
i=0 number = 10 next_number = 100 ans -= 10
i=1 number = 100 next_number = 5 ans += 100
i=2 number = 5 next_number = 1 ans += 5
i=3 number = 1 next_number = 1 ans += 1
i=4 number = 1 next_number = 1 ans += 1
i=5 ans += 1
return 98
hash I -> index X map[X] = 1
hash V -> index Y map[Y] = 5
```
:man: : 想請問同學針對這個程式碼的複雜度有甚麼想法?
:baby: : 針對這個程式的複雜度來說。
main函數的for 迴圈跑的次數取決於字串input的長度。
因為每次都要執行Mapping函數，而因為Mapping函數最多只有7個，則複雜度為常數級別的。
接下來在迴圈中的幾行，都是常數級別的操作。
因此，可以得知最後整體的複雜度將會是O(N) * O(1) = o(N) 線性複雜度
```cpp
int MAPPING(char symbol){ # O(1)
switch(symbol){
case ‘I’ : return 1;
case ‘V’ : return 5;
case ‘X’ : return 10;
case ‘L’ : return 50;
case ‘C’ : return 100;
case ‘D’ : return 500;
case ‘M’ : return 1000;
}
}
int main(string input){
int ans = 0;
for(int i=0;i<input.length()-1;i++){ # O(N)
int number = MAPPING(input[i])
if(number < MAPPING(input[i+1])) ans -= number;
else ans += number;
}
ans += MAPPING(input[input.length()-1]);
return ans;
}
```
:man: : 好，非常謝謝同學這題的回答。
## [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)
> [錄影: Problem2](https://www.youtube.com/watch?v=XDMrC7ThHjU)
### 測驗說明與問答
:man: : 好同學您好，接下來是第二個問題。第二個問題是會輸入一個字串 s，找出其中不包含重複字元的最長子串的長度。
**例子 1：**
> 輸入：s = "abcabcbb"
> 輸出：3
> 解釋：答案是 "abc"，長度為 3。
>
**例子 2：**
> 輸入：s = "bbbbb"
> 輸出：1
> 解釋：答案是 "b"，長度為 1。
>
**例子 3：**
> 輸入：s = "pwwkew"
> 輸出：3
> 解釋：答案是 "wke"，長度為 3。
這就是為第二題問題的描述。
:baby: : 好我接下來會解這一到題目有關於一個字串找出其中不含重複字元的連續子字串的長度，我一開使聽到就會想到可以使用set 這個結構來裝出現的字元因為我只需要在意他是否曾經出現過，並不需要特別在乎順序性，也就是這個字元在子字串的位置在哪。
用個例子舉例 "abcabcbb" 為什麼不用在乎順序 :
abc bca cab abc cb b -> max 3
set 不存在重複的字元
set{a,b,c}
如果字元存在該集合，那我們就應該在該集合的字元(含)以前的全部去掉，不用做更新。
再把新的字元加入這個字串，同時也去看是否需要更新這個字串的最長長度。
經過這一系列的過程，就可以在掃的過程中得到字串的長度。
:man: : 好那現在希望你能夠通過程式碼解決這一題。
:baby: : 好那麼首先我會將我的想法思路用步驟描述出來，再將她轉為程式碼。
```
step 1 : 先掃過這個input string
step 2 : 檢查每個字元是否出現過
step 3 : 如果出現過，就把從start開始到出現重複的字元(含)的字元刪掉，並且跟新start
step 4 : 沒有出現過 ，將字元加入現在的substring，同時更新
```
接下來將這段寫成程式碼 :
在這裡我用unordered_set來解決問題，而不用set，因為undored_set不考慮順序性，而是用雜湊表(hash table)實作的，做資料插入和查詢的時間複雜度很低，為常數級別O(1)。
而set是用紅黑樹實作的，雖然他因為紅黑相隔的關係來讓整棵樹能比較平衡，但即便平衡，他的複雜度仍不是常數級別的。
```cpp
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> S;
int n = s.length();
int max_len = 0;
int start = 0;
for(int i = 0;i< n;i++){
while(S.count(s[i]) > 0){
S.erase(s[start]);
start++;
}
S.insert(s[i]);
max_len = max(max_len,i - start+1);
}
return max_len;
}
};
```
:baby: : 接下來我會用上述的例子做驗證。
```
pwwkew
length = 6
start =0
i = 0 : , Map ={(p,0)} max_len = 1
i = 1 : , Map={(p,0),(w,1)} max_len =2
i = 2 : Map={(p,0),(w,2)} start = 2
i = 3 : Map={(p,0),(w,2),(k,3)} max_len = 2
i = 4 : Map={(p,0),(w,2),(k,3),(e,4)} max_len = 3
i = 5 : Map= {(p,0),(w,5),(k,3),(e,4)} start = 3 max_len = 3
```
:man: : 想請問同學有沒有辦法將這段程式碼進行優化?
:baby: : 我接下來會將他優化。
```cpp
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> S;
int n = s.length();
int max_len = 0;
int start = 0;
for(int i = 0;i< n;i++){
if(S.find(s[i])!= S.end() && S[s[i]] >= start){
start = S[s[i]]+1;
}
S[s[i]] = i;
max_len = max(max_len,i - start+1);
}
return max_len;
}
};
```
:man: : 同學想請問你覺得這個題目你可能會在處理甚麼專案主題時會用到?
:baby: : 關於我可能會在哪些專案主題會用到，雖然這一題只是要找出最長的字串其中不重複的字元的長度。但可以把每個字元看成是一個keyword，所以現在題目變成一整串keywords中不重複的連續keywords. 那這樣最常的子字串多任何一個keyword就會又重複了，那這樣就可以變成一個keyword經過多少個其他的keywords才會又在撞見自己，因為那代表我再往左多一個keyword跟再往又多一個keyword便會重複出現keyword。那這樣就變成一個計算頻率的問題。像這種計算keywords頻率的問題，可能會時常出現在搜尋引擎的透過keyword搜尋的問題上，可以透過這個出現的頻率來說這篇文章比較接近使用者query的問題或是資料庫處理資料上。
:man: : 好，謝謝同學，看來你對處理文本問題有一些認識，非常開心今天能夠參與您的面試。
## [20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)
> [錄影: Problem3](https://www.youtube.com/watch?v=8Pgv-CL4hik)
### 測驗說明與問答
:man: : Welcome to our company's interview. Our company places a strong emphasis on technical skills.Thus, In the upcoming interview process, I will ask you a question and I hope you can solve it.
:baby: :OK, I am glad to sovle this problem.
:man: : Then, the question is the following :
Students are usually careless when they calculate their math oepration, for example they forget to add some parentheses when they do their homework.
parentheses may be small parentheses,"(", ")",big parentheses "{", "}" and middle parentheses '[' and ']'.
You are their teacher, in order to help them avoid this mistakes. Can you give them some tips?
:baby:: Sure. I can give some rules to my students.
First, students can check hether the number of parentheses is odd or even? If the number of parentheses is odd. Then, it must be incorrect.After checking the number, student can draw a line. Then write every former parentheses they see on the line.When they see every back parentheses, they can check whether the last parenthese on the line is its according parenthese. It it is, student can erase its according parenthese on the line. If yes, then it is incorrect.
Finally, after they see all the parentheses, there are still some aprenthese on the paper. It is regarded as incorrect.
> First, they can check the number of the parentheses is odd or even
> if the number of parentheses is even -> correct and need to do more check
> otherwise, it will be incorrect
>
> Second, they can a draw a line
> when they see former parentheses , push on the line
> when they see back parentheses, they need to check whether the last parentheses on the line is its former parentheses. > and if it is, then students can erase it.
> if it is not , it will be incorrect
>
> Finally, if the line they draw has still some parentheses . empty -> correct
not empty -> incorrect.
```
These are my tips to students
:man:: It sounds like a good idea. Can you program your thoughts into a program?
:baby:: Sure. I can program my thoughts into a program.
```
Step 1 : check the number of parentheses
Step 2 : have a loop to run the input string of parentheses
Step 3 :
check the parentheses is belong to former "(", "[" ,"{"
* if yes :then push it into stack
* otherwise : check if the top parentheses in the stack is its former parentheses.
* if it is not -> invalid
* if it is its former parenthese pop the stack;
Step 4 : check stack is empty or not.
Then, we can change these steps into program.
During programmin, I will give the reason why I choose to implement above thoughts with stack.
```cpp
class Solution {
public:
bool isValid(string s) {
stack<char> st;
unordered_map<char,char> mapping;
mapping[')'] = '(';
mapping[']'] = '[';
mapping['}'] = '{';
if(s.length() % 2 == 1) return false;
for(int i=0;i<s.length();i++){
if(s[i] == ')' || s[i] == ']' || s[i] == '}'){
if(st.empty()== false && st.top() == mapping[s[i]]){
st.pop();
}
else{
return false;
}
}
else{
st.push(s[i]);
}
}
if(st.empty() == false ) return false;
return true;
// Optimization
// return st.empty()
}
};
```
Then, I will test the correctness of my program by given some examples.
```
( ( [ }
( ( [ } return false;
```
When we see "}" and check the top of the stack, the top of the stack is not its according former parentheses. Thus, it return false.
```
( ( return false;
```
We only see foremer parentheses. Hence, in every step I push the former parentheses.
After we ran all the parentheses in the string, we check whether the stack is empty or not. We see stack is not empty. So, we will return false and it will be invalid.
We pass program by these two examples.
:man::Okay, thank you bamboo. I am very happy to participate in your interview today.
## 總體初步檢討
針對 interviewer 的檢討 :
* 提問時，避免只拋出「時間複雜度是什麼等級？」這樣的問題，這樣對話欠缺上下文，可能 interviewee 憑藉猜測或背誦做答，從而喪失鑑別度 (注意對話時間，儘量讓問答有效率)，可改為一併要求 interviewee 解釋並簡介對應到現有程式碼該怎麼展現
* 應該要對interviewee給出的答案再坐進一步的詢問，讓原先的問題更有意義。
* 第二題例子講太久
* 這、就是、那的語助詞太多
* 第三題的英文太差了
* 第三題的題目描述舉的差強人意
針對 interviewee 的檢討:
* input的發音t太重。
* 這、就是、那的語助詞太多
* 說n的複雜級別，應該說線性的複雜級別
* 第二題說明set用紅黑樹實做複雜度較低，可以直接明確的說明紅黑樹的複雜度為多少。
* 第三題的英文太差了
* former parentheses 與 back parentheses 應該要用更專業的說法，如果面是當下不知道應該要先說明自己定義的former parentheses & back parentheses為甚麼。
* 講話常常會用「我們」 e.g., 「我們接下來就可以得到...」、「我們可以透過..」
* 很多單字都忘記複數了
---
## 他評01
### interviewer
- [ ] 優點
* 咬字清晰，語速均衡
- [ ] 可改進的地方
* 文件的畫面佔幅太小
* 英文口說不熟練
### interviewee
- [ ] 優點
* 自我介紹更有帶入感
* 撰寫與解說程式條理分明
- [ ] 可改進的地方
* REACTO缺少R
Sign in with Wallet
Connect another wallet