# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS11ooE4Rh)」作業 1
>貢獻者: 芋頭-Taro
> [video(英)](https://youtu.be/i6wuShAS-uQ)
> [video(漢)](https://youtu.be/6OA0AWZRfVM)
> 👨💻：interviewer
> 🦝：interviewee
## 筆記
### 面試官要點
* 面試官不要使用上對下的用詞，因為不確定對方上來的職位與自己的關係，有些企業會讓工程師面試他的主管
* 不要一開始透漏題目，這樣而外加題或是覺得對方步行要提早結束面試都方便
* 時間控管
### 面試者要點
* 關鍵提問
* 「我是否可以假設…」
* 對於商業目標的定義
* 期望結果的形式
* 資料缺失、或者雜訊
* 資料表之間的 JOIN 方式（Primary Key & Foreign Key）
* 極端情況
* 利用 Pseudo Code 與口頭描述提升溝通效率
* 先講解在打程式碼
* 滑鼠不要亂晃
* REACTO
* Repeat: 重複提問，確認自己理解原本的要求
* Examples: 針對題目條件，舉出符合的案例，不限於特例
* Approach: 說明自己打算採用的方案
* Code: 撰寫程式
* Test: 若不能實際測試，那說明驗證程式的方案
* 在寫出程式後，需要主動提出你寫的程式有哪些優劣勢、可以怎麼改進
* 用 Unit Test 說明程式可行性，以及因為面試時間太短沒有解完的是哪些 Edge Cases
* 說明此程式碼所做的權衡（Trade-off）：空間 v.s. 時間、可讀性 v.s. 效能、等等
* 提出 Coding Style 改進方向，例如哪裡值得 重構（Refactor）
### 企業面試概念
* 重點在溝通，而非閉嘴寫程式，企業寧願收會溝通程式70分的，也不要程式90但不溝通不知道她在幹嘛的
* 面試是種表演，要與面試官交流，相互面試
* Google recuirter 提供的準備文件會建議第一題花 10 - 15 分鐘，其中五分鐘確認題意，五分鐘思考並表達解法，最後五分鐘實作與測試；第二題花 20 - 25 分鐘，五分鐘確認題意，十分鐘想解法與表達，最後十分鐘實作與測試。其理由是第一題通常比較簡單而第二題會比較困難
* 一般自我介紹是拿來給面試者暖身用的，一般不太會太認真聽，時長大概一分鐘
* 自我介紹要準備 1 / 3 / 5 分鐘的版本
## [13. Roman to Integer](https://leetcode.com/problems/roman-to-integer/)
👨💻: 芋頭你好，我是 B ，我是【**自七七人**】的資深軟體工程師，我會給你一個題目，接著我們就可以開始了
🦝: 好的，沒問題
👨💻: 好，這個問題是:
>給你一串羅馬數字字串，其中包含('I', 'V', 'X', 'L', 'C', 'D', 'M')
>並且其大小範圍於 1~3999，請你將此字串轉換成 int 形式並回傳
🦝: OK 所以輸入一個由羅馬字母組成的字串，經處理後要回傳其 `int` 形式，像是輸入 XI 會回傳 11 這樣
👨💻: 沒錯
🦝: 好的 我的想法是將所有羅馬字母建立表格，利用 `map` 來實作，因為他在尋訪的時間成本較低，也很適合利用 `key` 來查詢 `value` ，在建完 table 後要找出羅馬字母的規則
🦝: (OS: 在字母右邊是加，而在左邊是減，但是要如何判定誰是被加減的數字呢? 不過在左邊的數最多只會有一個，還是要把個別檢查右邊的數是否比他大?...等等，右邊的數的大小，對阿，只要右邊的數的值比當前的大，當前的數勢必就是減)
🦝: …至於規則就是由最高位開始算，如果右側的數比當前的數大，就代表當前的數是用來減右側的數的，故將和減掉當前的數，反之右側的數小於等於就是將和加上當前的數
👨💻: 到目前聽起來還不錯，你可以把他用 code 寫出來嗎
🦝: 沒問題
```cpp
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](https://leetcode.com/problems/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*m)$
```cpp
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.
```cpp
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 logn)$ 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](https://leetcode.com/problems/3sum/description/)
👨💻: 好的，芋頭，歡迎來到【**自七七人**】的第二場面試，
🦝: 沒問題
👨💻: 如你所見，本公司有在研究組織培養，我們需要定期給予組織注入藥品以維持穩定，所以我們已經將各藥品的不同效果數值化，希望你可以就先單論單一效果，從所有藥品中取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--`
```cpp
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` 就可以查詢到對應的藥品
👨💻: 聽起來不錯，時間也差不多了，今天的面試就先到這邊，晚點你會收到我們討論的最終結果，辛苦了
🦝: 好的，謝謝，你也辛苦了
Sign in with Wallet
Connect another wallet