2024「資訊科技產業專案設計」HW1

櫻木滑倒
Sakuragi
🕵️‍♂️:Interviewer
🕶️:Interviewee
模擬面試錄影-1 (漢)
模擬面試錄影-2 (漢)
模擬面試錄影-3 (英)

LeetCode 69. Sqrt(x) : Easy

模擬面試過程

🕵️‍♂️: 你好，我是Jack，我是任職於Banana公司的面試官。

🕵️‍♂️: 我給你Google Doc的連結之後就可以開始了。

🕵️‍♂️: 在電腦圖學中，無論是在構建渲染環境還是設計遊戲，都經常需要計算物體之間的距離，而這種計算往往涉及平方根的運算。

🕵️‍♂️：假設今天給你一個介於

0

到

2^{31} - 1

的數值

x

，並要求在不使用任何函式庫的情況下，我們想求出

x

的平方根。

🕵️‍♂️：請問你對題目有疑問嗎？

🕶️：有，我想請問他的平方根不是整數的情況下如何表示答案？

🕵️‍♂️：往下取整數就可以了。

🕶️：好的，爲了確認我對題目的理解，我想用一個例子説明。

輸入： 10
輸出： 3

🕶️：請問我有理解錯題目嗎？

🕵️‍♂️：沒有，你可以開始寫你的程式了。

🕶️：在寫程式之前，我想先講一下我的想法。

🕶️：最直接的解法是使用一個迴圈，從輸入的值開始依次遞減，利用decision判斷當前數字的平方是否小於或等於輸入值。如果符合這個條件，則該數字就是輸入值的平方根。

暴力解法

class Solution {
public:
    int mySqrt(int x) {
        for(int i = x-1; i > 0; i--){
            int decision = i*i;
            if(decision <= x){
                return i;
            }
        }
        return 0;
    }
};

🕵️‍♂️：你用一個迴圈把所有可能的答案都判斷一次是可以解決我們的題目。但以實務層面來説，輸入資料十分大時，程式的效能會很差。請問你有其他更優秀的解法嗎？

🕶️：確實，之前的解法時間複雜度是

O (x)

。

🕶️：我的想法是利用二分搜尋法來解，這樣可以大幅度降低迴圈次數，將時間複雜度降到

O (\log x)

。具體來說，二分搜尋法的思路是每次將搜索範圍縮小一半，直到找到接近或等於輸入值平方根的整數。

🕶️：一開始判斷輸入是0或1的狀況，接下來開始實作二分搜尋法，最後再用一個判斷式來處理往下取整數的情況。

二分搜尋法

class Solution {
public:
    int mySqrt(int x) {
        if(x == 1 || x == 0) {
            return x;
        }
        int left = 1, right = x - 1;
        while(left < right){
            int mid = (left + right) / 2;
            int decision = mid * mid;
            if(decision == x){
                return mid;
            }
            else if(decision < x){
                left = mid + 1;
            }
            else if(decision > x){
                right = mid - 1;
            }
        }
        if(left == right){
            return left-1;
        }
        return 0;
    }
};

🕵️‍♂️：非常好，如果我們公司今天需要開發一款遊戲，且需要處理大量的平方根運算，而數值範圍是有限的，請問有沒有更快的解決方案呢？

🕶️：如果數值範圍是有限的，我們可以使用雜湊表來最佳化演算法。將系統中可能用到的平方根事先計算並存入雜湊表中，這樣在需要計算平方根時就可以直接查表，從而實現

O (1)

的時間複雜度。

🕵️‍♂️：非常好，櫻木滑倒先生。我們會再寄第二封的面試通知到你的信箱，祝你好運。

🕶️：非常感謝你，Jack先生。

初步檢討

針對 interviewer 的檢討:

講話太卡
咬字清晰點
少用助語詞(痾、然後)
可以更深入對演算法的空間複雜度做討論
應該對程式碼提出質問(因爲沒有測試過)

針對 interviewee 的檢討:

講話太卡
咬字清晰點
打程式碼中剪輯太多次
少用助語詞(痾、然後)
打程式有錯字
解釋程式碼須更清楚
視訊要照到鍵盤

第二次作業-他評 01

針對 interviewer 的檢討:

0:02: 不該自稱是「面試官」，這有「上對下」的隱含意思，大家日後可能會是同事，而且說不定應徵者一開始的職等就比自己高^{台灣很小，你永遠很難想像記仇會多久}，interview 是得知「相互」的「觀點」的途徑，不是讓你施展官威的場合。可改說「感謝你的時間，接下來由我主持這場面試」或「你好，從我手上這份簡歷，我感受到您對程式設計的熱情和專業，但在我們談及工作內容前，我想幫公司同仁先認識你在程式開發的想法和風格」
0:09: 注意 render 的翻譯，參見〈資訊科技詞彙翻譯〉
0:16: 在線性代數和工程數學中，相比單純的開平方根，常見 Frobenius Norm (還記得 SVD 分解嗎？)，不過在 LeetCode 原題中，使用整數開平方根，其應用領域就受限，於是該有其他案例。
0:24: 不用特別說「請問你有什麼疑問嗎？」這題在沒有變形的狀況下，不是難題，應該及早開始，可改說「請留意整數範圍限制，並在不使用任何函式庫的前提，進行程式開發，過程中我會斟酌加上一些限制」

針對 interviewee 的檢討:

1:19: 避免說「我想講一下」這種話，無助於溝通，用精簡的話 (注意未來可能是英語) 來確認和提問。
1:35: 避免說「如果有符合的話」，這顯得你很沒信心，可改說「就我所知」，或者直接推進 REACTO。以簡單題目開始，後續可能會有延伸題目，應該把時間保留在更多可展現自身經驗之處。
1:51: 不用將 public 這樣的關鍵字 (keyword) 唸出來，專注在程式碼的本體
2:05: 在 REACTO 的 Repeat 和 Approach 階段已有說明用的範例數值 (即 3 vs. 10) 和流程，稍早應該邊說邊紀錄，在 Coding 階段就可以重用，這樣不僅思緒更連貫，程式碼不用完整書寫，亦可增進討論
2:31: 在迴圈內有大量的乘法運算，在還沒開始 Coding，應當就討論如何減少運算，例如
$s q r t (1)$ ,
$s q r t (2)$ ,
$s q r t (3)$ 沒有運算的必要，直接檢查輸入 x 的數值，當
$x < 4$ 就返回
$1$
2:47: 變數 decision 的命名不精準，劍橋詞典的解釋: "a choice that you make about something after thinking about several possibilities"
3:45: 用「改進」取代「優化」，參見〈資訊科技詞彙翻譯〉，當提及二分搜尋法的時候，要有其效益分析 (時間複雜度、計算次數的比較)，避免說「大幅降低」這樣不精準的話語，理工人要用證據說話。
4:24: 避免說「我要開始打程式」這種顯而易見的話語。
考慮〈從 √2 的存在談開平方根的快速運算〉

119. Pascal's Triangle II : Easy

模擬面試過程

🕵️‍♂️: 你好，我是Jackson，我是任職於Grape公司的面試官。

🕵️‍♂️: 我給你Google Doc的連結之後就可以開始了。

🕵️‍♂️: 巴斯卡三角形能計算二項式係數，對於二項式展開至關重要。然後二項式展開在演算法的設計和機率統計中也有廣泛應用。

🕵️‍♂️：假設給定一個介於 0 到 33 之間的數字 rowIndex，表示巴斯卡三角形的第 rowIndex 層，最上方為第 0 層，我們的目標是求出該層的所有二項式係數。

🕵️‍♂️：請問你對題目有疑問嗎？

🕶️：沒有，但是爲了確認我對題目的理解，我想用一個例子説明。

輸入： rowIndex = 3
輸出： [1,3,3,1]

🕶️：請問我對於題目的理解上有任何錯誤嗎？

🕵️‍♂️：沒有，你可以開始寫你的程式了。

🕶️：在寫程式之前，我想先講一下我的想法。

🕶️：我的想法是先判斷初始條件，當輸入為 0 或 1 時，直接返回對應的結果。如果輸入大於 1，則使用雙重迴圈來計算巴斯卡三角形的值。第一層迴圈負責根據目標層數逐層更新，每次計算時創建一個 temp 來存放新一層的值。第二層迴圈負責根據目前的層數，兩兩相加計算巴斯卡三角形的係數，並將結果存入 temp。雙重迴圈完成後，將計算結果賦值給 answer。

🕶️：這樣的解法由於使用了雙重迴圈，因此時間複雜度為

O (r o w I n d e x^{2})

。同時，使用了 vector，最終會存放 rowIndex + 1 個元素，其他變數皆為常數級別，因此空間複雜度為

O (r o w I n d e x)

。

暴力解法 ( 雙重迴圈 )

下方程式碼的迴圈並非「對等」，不是「雙」。改稱「二層迴圈」。

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> answer = {1};
        if (rowIndex == 0){
            return answer;}
        answer.push_back(1);
        for(int x = 2; x <= rowIndex; x++){
            vector<int> temp = {1};
            for(int y = 0; y < x-1 ; y++){
                int insert = answer.at(y) + answer.at(y+1);
                temp.push_back(insert);
            }
            temp.push_back(1);
            answer = temp;
        }
        return answer;    
    }
};

🕵️‍♂️：做得非常好。但有個小問題，以實務層面來説，輸入資料十分龐大時，程式的效能會很差。請問你可以提出更優秀的演算法嗎?

🕶️：沒錯，之前的解法時間複雜度與 rowIndex 的平方成正比。

🕶️：我們可以直接利用二項式係數的性質來計算每一行的元素，以達到

O (r o w I n d e x)

的時間複雜度。

🕶️：具體的公式如下:

C (n, k) = \frac{n!}{k! (n - k)!}

🕶️：巴斯卡三角形第 n 行的每個元素是依據二項式係數直接計算出來的。

🕶️：我們這邊也使用到二項式係數的遞迴公式來計算目標層的每個元素:

C (n, k) = C (n, k - 1) \times \frac{n - k + 1}{k}

🕶️：這個演算法一樣使用了一個大小為 rowIndex + 1 的 vector 來存儲結果，因此空間複雜度仍然是 O(rowIndex)。

二項式係數

class Solution {
public:
    vector<int> getRow(int rowIndex){
        vector<int> answer(rowIndex + 1, 1); 
        for(int i = 1; i < rowIndex; i++){
            answer[i] = answer[i-1] * (rowIndex - i + 1) / i;
        }
        return answer;
    }
};

🕵️‍♂️：非常好，櫻木滑倒先生。我們會再寄第二封的面試通知到你的信箱，祝你好運。

🕶️：十分感謝你，Jackson先生。

初步檢討

針對 interviewer 的檢討:

講話太卡
咬字清晰點
少用助語詞(痾、然後)
可以更深入對演算法的空間複雜度做討論
應該對程式碼提出質問(因爲沒有測試過)
題目出得不夠好(優化的演算法只是公式，意義不大)

針對 interviewee 的檢討:

講話太卡
咬字清晰點
打程式碼中剪輯太多次
整個程式碼要打在同一頁(要調整Google Doc比例)
少用助語詞(痾、然後)
打程式有錯字
解釋程式碼須更清楚
二項式遞迴公式須解釋更清楚
第二個演算法意義不大
視訊要照到鍵盤

155. Min Stack : Medium

Simulated Interview Process

🕵️‍♂️: Hello, I am Johnson, the interviewer from Watermelon Company.

🕵️‍♂️: I'll send you the Google Doc link, and you can start once you're ready.

🕵️‍♂️: A stack is essential for managing function calls, expression evaluation, implementing undo features, and efficiently handling depth-first search (DFS) in graph or path exploration.

🕵️‍♂️: To design the MinStack, you need to ensure that all operations—push, pop, top, and getMin—run in constant time,

O (1)

. You'll be working within the constraints of integer values between

- 2^{31}

and

2^{31} - 1

, so your implementation should handle those boundaries. Additionally, you can assume that pop, top, and getMin will always be called on non-empty stacks, which simplifies the need for error handling around empty stacks. With up to 30,000 method calls, it's essential that your design remains efficient under heavy use.

🕵️‍♂️: Do you have any questions about the problem?

🕶️: Yes. So, does a MinStack simply have an extra function to track the minimum value in the stack compared to a regular stack?

🕵️‍♂️: You can say that again.

🕶️: One more thing, can I use the stack library to implement the code?

🕵️‍♂️: Yes, you can use the stack library.

🕶️: To make sure I understand the problem correctly, I'd like to explain it with an example.

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]

🕶️: Am I understanding the problem correctly?

🕵️‍♂️: Yes, you can start writing your code.

🕶️: Before writing the code, I'd like to explain my approach.

🕶️: My approach is straightforward. The pop, top, and getMin functions work similarly to a regular stack. The key difference is in the MinStack constructor: I use a stack where each element stores both its value and the minimum value of the stack up to that point.

🕶️: This solution is very simple, so the time complexity of each operation is simply

O (1)

Recording two value using one stack

class MinStack {
public:
    stack<pair<int, int>> minstack;
    MinStack() {}
    void push(int val) {
        if(minstack.empty()){
            minstack.push({val,val});
        }
        else{
            int peek = minstack.top().second;
            minstack.push({val,min(val,peek)});
        }

    }
    void pop() {
        minstack.pop();
    }
    int top() {
        return minstack.top().first;
    }
    int getMin() {
        return minstack.top().second;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

🕵️‍♂️: Excellent, Mr. Sakuragi! This is quite challenging, but it seems you’re the expert we’ve been searching for. We’ll send a follow-up interview notification to your email. Best of luck!

🕶️: Thank you very much, Mr. Johnson.

Initial Review

Feedback for the interviewer:

Speech was too choppy.
Enunciate more clearly.
Use fewer filler words (uh, then).
Could discuss the space complexity of the algorithm in more depth.
Should have questioned the code (since it wasn’t tested).
The question should be chosen more carefully (avoid selecting one with little room for improvement).

Feedback for the interviewee:

Speech was too choppy.
Enunciate more clearly.
Too many edits during the coding process.
Use fewer filler words (uh, then).
There were typos in the code.
Code explanations need to be clearer.
Make sure the keyboard is visible on camera.