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

貢獻者: 月前龍馬-lonmu
模擬面試: 漢-1
模擬面試: 漢-2
模擬面試: 英

Repeat
Example
Approach
Code
Test
Opmization

🧔 : interviewer 👶：interviewee

🧔 : 您好 今天由我來主詞這場面試，然後這邊有個問題想要請你解一下，題目敘述為
.
. / / 測驗說明與問答 如下面各題所示
.
🧔 : 方法大致沒問題 那你可以開始 implement 剛剛討論的方法了
👶 : coding. . . finished 帶入example 解釋code沒問題
🧔 : ok 那可以分析一下 你寫的程式 他的時間複雜度如何
👶 : explain time complexity 是否有更好的方法
🧔 : 好 那今天就先到這邊 稍待與主管和人資討論 再連絡你 謝謝

20. Valid Parentheses(漢1 easy)

🧔:給予一段字串，請判斷此字串之括號是否相匹配，合法請傳回true，不合法回傳false，你可以假設所有輸入之字串僅包含，括號、中括號、大括號這三種，且字串長度至少為1，小於104。

👶:好的我可以理解為 輸入字串僅有合法括號，題目為判斷此字串之合法性，簡單帶個例子 '()[]{}' -> true , '[{]}'-> false.

那我先大致敘說目前想到的方法，我會使用stack儲存character，然後使用iterator iterate input string s 的第一個element 到最後一個element，其中每輪當遇到左括號push至stack，若非左括號則檢查stack是否為空，不為空則檢查其右括號與stack top elment是否相匹配，匹配pop出來完成該次iterate，否則回傳false.

當所有character皆檢查完後，再檢查stack是否為空，若為空則代表input為valid回傳true，反之不為空則為invalid回傳false.

bool isValid(string s) {
    stack<char> st;
    for(char c:s){
        if(c==’(’ || c==’{’ || c==’[’){
            st.push(c);
        }
        else{
            if(st.empty() 
            || c==’)’&&st.top()!=’(’ 
            || c==’}’&&st.top()!=’{’ 
            || c==’]’&&st.top()!=’[’){
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}

50. Pow(x,n) (漢2 medium)

測驗說明與問答
🧔: 給予一 double x and int n，請計算其冪次 x 的 n 次方，你可以假設 -100.0<x<100.0 ， 而 n 於[-2^31 , 2^31-1]之間，n為非0整數，且x的n次其值落於-10的4次方與10的4次方之間.

👶: 舉個例子 2^10 = 1024, 2^-2 = 0.25.

直觀的做法為直接將x相乘n次 若n為負 則使用1/(x的n次)即可，
假設|x|: d, |n|=N; 則此方法的時間複雜度為O(N)，但考量時間複雜度有更優解 故不這麼做.

可以使用 recursion 將N以2進制的方式做考慮
2^10 = 2^(0b1010) = 1* 2^2 * 2^8
2^-2 = 1/2 ^ 2 = 0.5 ^(0b10) = 0.5 ^ 2 = 0.25
但是這樣比起iterate的方式多出 遞迴函式所占用的stack空間 O(log N) 所以我想用iterator的方式

用while把 n為0 作為終止條件 若n對2取模數(module 2)不為0時 則將結果先乘起來 之後x取平方 n除等於2

double myPow(double x, int n) {
    if(n<0) x = 1/x;
    double result =1;
    while ( n ! =0){
        if (n%2!=0){
            result *= x;
        }
        x *= x;
        n/=2;
    }
    return result;
}

1. Two Sum(英 easy)

🧔:Hello, welcome to the interview, there is a problem on the
google docs

The problem is to find two numbers in an integer array, 'nums,' that add up to a given 'target.' We need to return the indices of these two numbers.

👶:I think a suitable approach for this problem is to use a hash map. We can iterate through the array once, storing each element's value and its index in the hash map. Then, during the second pass, we check if the complement of the current element (target minus the current number) exists in the hash map. If it does, we've found our pair.

🧔:Do you think there's any room for optimization in your code?

👶:I believe this solution is already quite efficient. The hash map allows us to find the complement in constant time, making the overall time complexity O(n), where n is the length of the array. I don't see any further optimization needed for this problem.

🧔:Excellent! Your solution looks solid, and you've demonstrated a good understanding of the problem-solving process. Thank you for going through the REACTO framework with us. Is there anything else you'd like to add or any questions you have?

👶:No, I think we've covered everything. Thank you for this opportunity.

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int,int> hm;
    vector<int> ans;
    for(int i=0; i<nums.size(); i++){
        if(hm.find(target-nums[i]) == hm.end()){
            hm[nums[i]] = i;	
        }
        else{				
            ans.push_back(i);					
            ans.push_back(hm[target-nums[i]]);
            break;
        }
    }
    return ans;

}

初步檢討

• 影片沒注意剪輯成1.5倍速了
• 英文口說溝通需再加強
• Valid Parentheses(漢1) 影片程式碼有小部分錯誤
• interview方面，缺少互動交流，比較偏向interviewee單方面敘說方法及實作
• 題目方面直接考leetcode題目，缺少真實面試靈活多變的情況

改善方法

• 多練習英文口說及英聽
• 多練習思考題目背後想考的觀念及想法
• 多加嘗試與interviwer交流

---

第二次作業-他評01

關於 interviewer

• 優點

• 題目和條件都解釋得很清楚，語速也很順暢自然。

• 可改進的地方

• 面試者發現括號錯誤，可以提醒，增加互動性。

關於 interviewee

• 優點

• 寫完時有針對example的部分做test。

• 可改進的地方

• 00:56: for example是 e.g.，EX 則有其他意涵。

第二次作業-他評02

關於 interviewer

• 優點

• 題目說明清楚。

• 可改進的地方

• 題目應該適度包裝一下而非直接照抄leetcode上面的題目。

關於 interviewee

• 優點

• 4:39: 有搭配例子做test的部分很好。

• 可改進的地方

• 字有點小看不太清楚。
• 2:27: 這邊可以講一下話避免尷尬。

第二次作業-他評03

關於 interviewer

• 優點

• 題目敘述清晰

• 可改進的地方

• 題目可以改成情境題，而非直接使用leetcode原題，也可以比照實際面試狀況去變化題型測驗應試者反映
• 模擬面試錄影(漢1): interviewer 自稱面試官 不過其他影片有改進這個問題

關於 interviewee

• 優點

• 確實執行REACTO
• 1:10: 英文影片中 implement 方法時，先寫下方法概要的註解，是一個不錯的方式，也可以減少在寫程式時出錯的機會
• pow(x,n)(漢2)的影片，闡述方法的概念時，說明得很清楚!

• 可改進的地方

• 英文有些字詞發音聽不太清楚，需要在注意

第二次作業-他評04

interviewer

• 優點

• 題目敘述得相當清楚而且也直接把constraint加進去，這樣可以省去很多跟測資有關的疑問發生。

• 可改進的地方

• 應該避免直接複製leetcode的題目包裝一下，這樣有可能interviewee已經看到題目就在想解，根本沒在聽。

interviewee

• 優點

• 完全有按照REACTO的步驟來演出自己的程式功力，也能夠分析自己的複雜度。

• 可改進的地方

• 在建構程式碼的過程中途有時候都沒講話有點小尷尬，如果能夠一邊講解自己的code的話可以讓互動性更高一點。