# 2022 年 「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022-homework1)」作業一
>貢獻者: 盤子 Plate Man
>[全面試影片](https://youtu.be/oxGYA2E5uBo)
🤵：interviewer 😀：interviewee
# 1528.[Shuffle String](https://leetcode.com/problems/shuffle-string/)
[第一題面試影片](https://youtu.be/oxGYA2E5uBo?t=0)
# 測驗說明與問答
🧍：ＯＫ，那我先來跟你解釋一下第一題，這題會給妳兩個資訊，一個是字串資訊、一個長度相同的整數 array 且此 array 代表的是前一個字串打亂的位置，請你幫我用相對快的方式出答案 並告訴我為什麼這樣做。
🙂：請問有甚麼限制嗎?
🧍：你可以先跟我說說你有甚麼想法。
🙂：好的，目前看到這款題目，如在不考慮記憶體用量的作法的話，應該會使用直接搜尋的方法，先見另一個儲存答案的陣列，之後利用FOR會圈依照後面的index陣列的位置放入到新的答案陣列中。
🧍：了解，那請問你知道這樣的寫法的時間複雜度是多少呢？
🙂：以這個解法來說的話，應該是 O(n)，因為他會直接走完完整的Array。
🧍：了解 那你可以實作看看嗎
🙂：沒有問題
```C++
string restore(string s,vector<int>& index){
string ans;
char strTemp[s.size()]={0};
for(int i=0;I < index.size();i++)
{
strTemp[index[i]]=s.at(i);
}
ans = strTemp;
return ans;
}
```
🧍：ok，那你剛剛有說，在不考慮記憶體的情況 可以這樣做，那如果考慮記憶體呢？
🙂：對的，剛剛那個作法的空間複雜度是 Ｏ(n) 如果今天在記憶體有限的情況下，可以用 swap 的作法，不在另外宣告一個 Array 讓時間複雜度變成 O(1)。
🧍：聽起來不錯，麻煩您幫我實作看看。
```C++
string restore(string s ,vector<int& index){
int n =s.size();
for(int i ; i<n ; i++)
{
while(index[i]!=1)
{
swap(s[i],s[index[i]])
swap(index[i],index[index[i]];
}
}
return s;
}
```
🙂：以上方法可以省去那記憶體，但時間複雜度變成O(n^2)，因為他使用swap，因此這部分可以 case by case 來選擇撰寫方式。
🧍：了解 這題你解的不錯 還從不同角度下手。
# 2325.[Decode the Message](https://leetcode.com/problems/decode-the-message/)
[第二題面試影片](https://youtu.be/oxGYA2E5uBo?t=597)
# 測驗說明與問答
🧍：那我們接下來來看第二題，第二題的要求是請你解密訊息，題目會給你一個字串的 key 與 message，請你回傳加密訊息的原文。
🧍：key 是由 26 個英文小寫字母第一次出現的順序作為替換表中的字母順序。比如我給你的 key 是 happy boy，則這就代表 ('h' -> 'a', 'a' -> 'b', 'p' -> 'c', 'y' -> 'd', 'b' -> 'e', 'o' -> 'f'，之後再請你用這個密碼表來對message做解密。
🙂：了解，那請問是否每個字母都會出現過呢？還是會有缺少的例外事件呢？並請問遇到空白是跳過處裡嗎？
🧍：不會的，此題遇到空白時直接跳過保持不變，並 key 中每個字母一定會至少出現一次。
🙂：那我了解題目了，以目前的想法來看，應該可以分兩部分來完成，第一步首先是先生成加密對照表，可以利用 Array 等結構，也可以 Map 來完成。第二步就可以利用對照表來解開訊息了。
🧍：了解，那麻煩您幫我實作看看。
```C++
string decodeMessage(string key, string message){
char table[6]={};
char k = ‘a’;
for(auto c:key){
if(c!=’ ‘&&table[c-‘a’]==0){
table[c-‘a’]=k++;
}
}
for(int i = 0 ; i < message.length();++i){
if(message[i]!=’ ‘ ){
message[i]=table[message[i]-‘a’];
}
}
return message;
}
```
🧍：ok 這看起來是沒問題 可以請你告訴我這解法的時間複雜度嗎。
🙂：是 O(m+n)
🧍：好，如果不使用 array 作為對照表，有其他的的解法嗎？
🙂：如果使用 unordered_map 也可以完成，並執行速度應該會更快。
🧍：聽起來這可行，方便也幫我使用此方法實作看看嗎？
```C++
string decode Message (string key , string message){
unordered_map<char,char> d;
d[‘ ’]=’ ‘;
int i = 0;
string lower = ‘abcdefghijklmnopqrstuvwxyz’
for(auto c : key){
if (d.count(c))continue;
d[c]=lower[i++];
}
string ans;
for (auto c:message ) ans.push_back(d[c]);
return ans;
}
```
🧍：ok,做得很好，這種做法之後在大量資料中，搜尋也會快蠻多的，那接下來就進入第三題摟。
# 2181.[Merge Nodes in Between Zeros](https://leetcode.com/problems/merge-nodes-in-between-zeros/)
[第三題面試影片](https://youtu.be/oxGYA2E5uBo?t=1514)
# 測驗說明與問答
🧍： Ok.then we going to the final problem,in this problem, You are given the head of a linked list, which contains a series of integers separated by 0's. The beginning and end of the linked list will have node's value is zero.
🧍： For every two consecutive zeros, merge all the nodes that are between them into one node whose value is the sum of all the merged nodes. The modified list should not contain any zeros. Returns the head of the modified list.
🙂： Ok, got it, so just caculate the sum of all the nodes's value between the beginning and end of the linked list have value is zero right?
🧍： Yes, just merge the node and return the answer list.
🙂： And will there be two consecutive nodes with value equal to 0?
🧍： This won't happen, there are no two consecutive nodes with node's value is 0.
🙂： Ok, and final question. Is the node value at the beginning and end of the linked list both 0? Or are there other exceptions that need to be handled?
🧍： Unnecessary. The beginning and the end nodes value are 0's in the linked list.
🙂： Got it, I think in this case, just need to determine the current value is 0 or not. If it is 0, then the sum of the numbers between the last 0 is stored in a modified link; if it is not 0, then the current value is added to the sum and we go on from there.
🧍： Ok, sounds good, can you finish the code?
🙂： Sure.
``` C++
Listnodes* mergenodes(Listnodes* head){
Listnode nodes;
head = head->next;
for(Listnode* prev = &nodes;head;head = head->next){
int sum = 0;
while(head->val != 0){
sum += head->val;
head = head->next;
}
prev-> next = head;
head-> val = sum;
prev = head;
}
return node.next;
}
```
🧍： Well done, can you tell me what the complexity is in this problem?
🙂： I think time complexity is O(n) and space complexity is O(1).
## 自我檢討
- 針對 interviewer 的檢討:
- 可以嘗試從不同角度的面向來做討論，而不是只有時間與空間複雜度而已
- 因為此次面試使用 Word 解題，沒有確認是否真的能夠執行，雖說可以理解，但畢竟是人，可能會有所疏失
- 在說明題目的時候可以在更完善點。
- 針對 interviewee 的檢討:
- 不要選擇使用 Word 來解題，不然會遇到自動修正的問題，使用 Notepad++ 等等編輯器較好，如果還是要使用 word 就要取消自動修正。
- 在面試中，如遇到邊打 Code 邊思考時，會卡住無法說話，這部分要在多多練習。
- 還不習慣使用英文來解釋寫法，容易造成語法錯誤與詞不達意的問題。
Sign in with Wallet
Connect another wallet