2023 年「資訊科技產業專案設計」作業 1

貢獻者: 芋頭-Taro
video(英)
video(漢)

👨‍💻：interviewer
🦝：interviewee

13. Roman to Integer

👨‍💻: 芋頭你好，我是 B ，我是【自七七人】的資深軟體工程師，我會給你一個題目，接著我們就可以開始了

🦝: 好的，沒問題

👨‍💻: 好，這個問題是:

給你一串羅馬數字字串，其中包含('I', 'V', 'X', 'L', 'C', 'D', 'M')
並且其大小範圍於 1~3999，請你將此字串轉換成 int 形式並回傳

🦝: OK 所以輸入一個由羅馬字母組成的字串，經處理後要回傳其 int 形式，像是輸入 XI 會回傳 11 這樣

👨‍💻: 沒錯

🦝: 好的 我的想法是將所有羅馬字母建立表格，利用 map 來實作，因為他在尋訪的時間成本較低，也很適合利用 key 來查詢 value ，在建完 table 後要找出羅馬字母的規則

🦝: (OS: 在字母右邊是加，而在左邊是減，但是要如何判定誰是被加減的數字呢? 不過在左邊的數最多只會有一個，還是要把個別檢查右邊的數是否比他大?..等等，右邊的數的大小，對阿，只要右邊的數的值比當前的大，當前的數勢必就是減)

🦝: …至於規則就是由最高位開始算，如果右側的數比當前的數大，就代表當前的數是用來減右側的數的，故將和減掉當前的數，反之右側的數小於等於就是將和加上當前的數

👨‍💻: 到目前聽起來還不錯，你可以把他用 code 寫出來嗎

🦝: 沒問題

map<char,int> m;

m['I'] = 1;
m['V'] = 5;
m['X'] = 10;
m['L'] = 50;
m['C'] = 100;
m['D'] = 500;
m['M'] = 1000;

int ans = 0;

for(int i = 0; i < s.length(); i++){
    if(m[s[i]] >= m[s[i+1]]){
        ans += m[s[i]];
    }
    else{
        ans -=m[s[i]];
    }
}

return ans;

🦝: 這樣應該就可以了，時間複雜度是

$O(n)$，因為總共要判斷輸入字串長度次的字母，至於空間複雜度是

$O(1)$

14. Longest Common Prefix

👨‍💻: welcome to the interview, I am the senior software engineer of facehook, you can call me jeff. I have sent you a problem, you can check it out.

🦝: well, let me see, “Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".”

🦝: so I should find the longest string amongst an array, like input bee and see should return ee right?

👨‍💻: no you only need to find out the “common prefix string”, if input floest and fluest will return fl rather than est.

🦝: oh, I see, thank for your remind, so…, My opinion is let first string compare with second string, find the common prefix string, and use that to compare with next string, until no more string or common prefix string not exist.

🦝: set array length is n and string length is m ,that time complexity is

$O(n\times m)$

string ans = strs[0];
int n = strs.size();

for(int i = 1; i < n; i++){
    string temp = "";
    for(int j = 0; j < min(strs[i].size(), ans.size()); j++){
        if(strs[i][j] != ans[j]){
        else
            temp += ans[j];
    }
    ans = temp;
}
return ans;

👨‍💻: well, that is the way, but do you think you could make it even faster?

🦝: yeah we can just sort the array by std::sort, after that the string will Sort by characters, so we can simple compare the first and last string to find the common prefix string.

👨‍💻: OK great, could you code it out

🦝: of course.

int n = strs.size();
string ans = "";
sort(strs.begin(),strs.end());
string first = strs[0], last = strs[n-1];

for(int i = 0; i < min(first.size(),last.size()); i++){
    if(first[i] != last[i]){
        return ans;
    }
    else{
        ans += first[i];
    }
}
return ans;

🦝: so in this case the time complexity is

$O(n\log n)$ cost by sort.

👨‍💻: well done A that is the interview for today, we will email you later to inform the result. Have a nice day.

🦝: thanks, you too.

15. 3Sum

👨‍💻: 好的，芋頭，歡迎來到【自七七人】的第二場面試，

🦝: 沒問題

👨‍💻: 如你所見，本公司有在研究組織培養，我們需要定期給予組織注入藥品以維持穩定，所以我們已經將各藥品的不同效果數值化，希望你可以就先單論單一效果，從所有藥品中取3種藥品並讓其效果相加為零

🦝: 所以就是單純先看其單一效果的數值，並且任取3種不重複的藥品，使其效果加起來為零嗎?

👨‍💻: 對，但要注意不可以有兩者內部數值組成都相同的結果，

🦝: 所以說輸入 [1,0,-1,-1] 只會回傳 [[1,0,-1]]而已，而不是[[1,0,-1] ,[1,0,-1]]

👨‍💻: 對的

🦝: 還有就是你們是用哪種資料型態去儲存藥品的各項數值呢?

👨‍💻: 至於資料型態你可以決定他要用哪種方法儲存，並說說你的看法

🦝: OK，至於資料型態我會用 map 作為儲存結構，可以利用 key 作為功能， value 作為數值，方便查找與閱讀。那本次的作法要利用此資料結構作為輸入嗎?

👨‍💻: 先不用沒關係，可以先簡單用整數陣列作為輸入

🦝: 好的，那我就開始了，我的想法是先將陣列從小到大排序，由於數組構成不能重複，所以利用 set 來存數組，最後再將其傳換成 vector 形式，隨後選定最小值作為起始值，再由其後方的數中選取兩數(分大值和小值)，因為是由小到大排序，所以選定小值 j = i + 1 和大值 k = n - 1，若三者合大於0，就讓大值由左側的值取代(也就是k )，反之就是讓小值由右側的值取代，當三者合為0時就將數組 push_back 進 vector 中，並且執行 j++ 與 k--

set<vector<int>> s;
vector<vector<int>> ans;
sort(nums.begin(),nums.end());
int n = nums.size();
int target = 0;

for(int i = 0; i < n - 1; i++){
    int j = i + 1;
    int k = n - 1;
    while (j < k) {
        int sum = nums[i] + nums[j] + nums[k];
        if(sum == target) {
            s.insert({nums[i], nums[j], nums[k]});
            j++;
            k--;
        }
        else if (sum < target)
            j++;
        else
            k--;
    }
}
for(auto triplets : s)
    ans.push_back(triplets);
return ans;

👨‍💻: 但是這樣會需要多做一次型態轉換，並且會需要花時間在相同的數組上，有甚麼方法可以避免或是優化嗎

🦝: 有的，只要在找到數組後，大小值也更新了，檢查新的 element 是否等於上個 element，大小值都要，當然也包括做為假定存在的起始值，若舊值等於新值就代表會造成相同數組結果，所以當遇到這樣的狀況就要跳到舊值不等於新值為止，這樣就可以直接用 vector 存取，並且省下了重複查找相同數組的時間。

👨‍💻: 這是個可行的辦法，那你能口述，如果輸入的是整數陣列，要如何用輸出的結果查詢到對應的藥品呢

🦝: 我會利用 map<vector<string>>，並用其對應的數值作為 key，這樣將輸出的數組帶入 map 就可以查詢到對應的藥品

👨‍💻: 聽起來不錯，時間也差不多了，今天的面試就先到這邊，晚點你會收到我們討論的最終結果，辛苦了

🦝: 好的，謝謝，你也辛苦了

---

第二次作業-他評 01

關於 interviewer

• 優點

• 4:03: 有上字幕讓觀賞影篇的人清楚知道題目內容，不錯。
• 4:03: 題目有轉換過問問題的方式而不是只照著leetcode原本題目來問。

• 可改進的地方

• 0:02: 避免說自己是"資深"的軟體工程師，因為我們不知道來面試的人未來位階是否比自己還大。
• 3:40: 此時提問的人應該可以再追問一些相關的問題，例如時間的優化等等。

關於 interviewee

• 優點

• 有適度的用手勢以及肢體去做動作。
• REACTO的部分都有cover到
• 1:00: 把腦海中在思考的內心話用剪片技巧顯現出來，很用心。

• 可改進的地方

• 講話可以再流暢一些。
• 螢幕上的code可以放大一點，看不清楚。
• 1:50: 通常面試應會在文字編輯器或是空白文件上打code，所以在開始打程式前應不會有打好任何程式在畫面上，也不會有自動縮排的功能。
• 0:15: 麥克風有怪聲音。

他評02

Interviewer

• 優點

• 有將題目變形，而不是 Leetcode 原題。

• 可改進的地方

• 可以與面試者的互動更多，像是問一些優化的問題，不一定要得到更好的程式碼，可以問問面試者的想法。

Interviewee

• 優點

• 內心獨白的部分表現得很好。

• 可改進的地方

• 01:00: 在獨白的部分，如果可以搭配例子，打在螢幕上效果應該更好。
• 07:59: while 迴圈的中止條件可以解釋一下為什麼會這樣設定。

他評03

Interviewee

• 可改進的地方

• 01:55: 避免說 size of the array，因為 sizeof 在 C/C++ 是保留字 (但 Java 裡頭不是)，考慮到英文面試時說話較慢，因此儘量一開始就避免講會讓人誤會的詞，可改說 "the length of the given array"。
• 特定的單音節的字，常用弱化母音 schwa 來唸，例如 to, at, for, can, of 等虛詞 (function words)。注意 of 要唸 /əv/，不唸為 /oʊf/

  推薦「英語兔」和「ST English」頻道

• 02:19: 程式碼 sort 出現於解說之前，應該避免，因為後者才是主體，程式碼只是產出的一環。後續可思考，如果不能呼叫標準函式庫的 sort，該怎麼做？

他評04

關於 interviewer

• 優點
• 造型很帥
• 題目有另外上字幕，很用心
• 講話通順，語氣自然
• (第二題)有把原始題目轉換過再提出
• 可改進的地方
• (第一題)可以觀察interviewee的code找出能優化的地方提問，或是提出延伸問題(REACTO的O)

關於 interviewee

• 優點
• 有加入interviewee的OS，把思考問題的想法表演出來，很有趣
• 講話通順，語氣自然
• 和interviewer有很多互動
• 可改進的地方
• 面試不會直接有LeetCode的介面可以打code，建議使用google document練習，function跟傳入的參數(輸入)也應該要是自己寫出來的
• (第一題)可以帶入實際例子測試code是否可行(REACTO的T)

他評05

關於 interviewer

• 題目變形的很漂亮，有和工作上做結合

關於 interviewee

• 心裡話的部分我覺得很有意思，蠻有拍片的感覺

在 11:46 中我發現你的 if(i>0 && nums[i]==nums[i-1]) 在 i=0 時，可能會造成非法記憶體存取，這一點可能要細心檢查一下

他評06

關於 interviewer

• 優點
• 有跟面試公司的工作相呼應舉例
• 可改進的地方
• 沒有

關於 interviewee

• 優點
• 有加入interviewee的os跟轉場，超棒，可以建頻道了
• 可改進的地方
• 15. 3Sum優化的code還是可以實作看看