# 2024「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2024/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Finfo2024-homework1)」HW1
> 櫻木滑倒
> Sakuragi
>🕵️♂️:Interviewer
>🕶️:Interviewee
> [模擬面試錄影-1 (漢)](https://youtu.be/KYOUfnXouMA)
> [模擬面試錄影-2 (漢)](https://youtu.be/4gbTHgfwdnc)
> [模擬面試錄影-3 (英)](https://youtu.be/3szsZ7jYolg)
## LeetCode 69. [Sqrt(x)](https://leetcode.com/problems/sqrtx/description/) : Easy
### 模擬面試過程
🕵️♂️: 你好，我是Jack，我是任職於Banana公司的面試官。
🕵️♂️: 我給你Google Doc的連結之後就可以開始了。
🕵️♂️: 在電腦圖學中，無論是在構建渲染環境還是設計遊戲，都經常需要計算物體之間的距離，而這種計算往往涉及平方根的運算。
🕵️♂️：假設今天給你一個介於 $0$ 到 $2^{31}-1$ 的數值$x$，並要求在不使用任何函式庫的情況下，我們想求出$x$的平方根。
🕵️♂️：請問你對題目有疑問嗎？
🕶️：有，我想請問他的平方根不是整數的情況下如何表示答案？
🕵️♂️：往下取整數就可以了。
🕶️：好的，爲了確認我對題目的理解，我想用一個例子説明。
輸入： `10`
輸出： `3`
🕶️：請問我有理解錯題目嗎？
🕵️♂️：沒有，你可以開始寫你的程式了。
🕶️：在寫程式之前，我想先講一下我的想法。
🕶️：最直接的解法是使用一個迴圈，從輸入的值開始依次遞減，利用decision判斷當前數字的平方是否小於或等於輸入值。如果符合這個條件，則該數字就是輸入值的平方根。
---
### 暴力解法
```cpp
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的狀況，接下來開始實作二分搜尋法，最後再用一個判斷式來處理往下取整數的情況。
---
### 二分搜尋法
```cpp
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](https://youtu.be/KYOUfnXouMA?t=2): 不該自稱是「面試官」，這有「上對下」的隱含意思，大家日後可能會是同事，而且說不定應徵者一開始的職等就比自己高^台灣很小，你永遠很難想像記仇會多久^，interview 是得知「相互」的「觀點」的途徑，不是讓你施展官威的場合。可改說「感謝你的時間，接下來由我主持這場面試」或「你好，從我手上這份簡歷，我感受到您對程式設計的熱情和專業，但在我們談及工作內容前，我想幫公司同仁先認識你在程式開發的想法和風格」
* [0:09](https://youtu.be/KYOUfnXouMA?t=9): 注意 render 的翻譯，參見〈[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)〉
* [0:16](https://youtu.be/KYOUfnXouMA?t=16): 在線性代數和工程數學中，相比單純的開平方根，常見 [Frobenius Norm](https://youtu.be/Gt56YxMBlVA) (還記得 SVD 分解嗎？)，不過在 LeetCode 原題中，使用整數開平方根，其應用領域就受限，於是該有其他案例。
* [0:24](https://youtu.be/KYOUfnXouMA?t=24): 不用特別說「請問你有什麼疑問嗎？」這題在沒有變形的狀況下，不是難題，應該及早開始，可改說「請留意整數範圍限制，並在不使用任何函式庫的前提，進行程式開發，過程中我會斟酌加上一些限制」
- [ ] 針對 interviewee 的檢討:
* [1:19](https://youtu.be/KYOUfnXouMA?t=79): 避免說「我想講一下」這種話，無助於溝通，用精簡的話 (注意未來可能是英語) 來確認和提問。
* [1:35](https://youtu.be/KYOUfnXouMA?t=95): 避免說「如果有符合的話」，這顯得你很沒信心，可改說「就我所知」，或者直接推進 REACTO。以簡單題目開始，後續可能會有延伸題目，應該把時間保留在更多可展現自身經驗之處。
* [1:51](https://youtu.be/KYOUfnXouMA?t=111): 不用將 `public` 這樣的關鍵字 (keyword) 唸出來，專注在程式碼的本體
* [2:05](https://youtu.be/KYOUfnXouMA?t=125): 在 REACTO 的 Repeat 和 Approach 階段已有說明用的範例數值 (即 3 vs. 10) 和流程，稍早應該邊說邊紀錄，在 Coding 階段就可以重用，這樣不僅思緒更連貫，程式碼不用完整書寫，亦可增進討論
* [2:31](https://youtu.be/KYOUfnXouMA?t=151): 在迴圈內有大量的乘法運算，在還沒開始 Coding，應當就討論如何減少運算，例如 $sqrt(1)$, $sqrt(2)$, $sqrt(3)$ 沒有運算的必要，直接檢查輸入 x 的數值，當 $x < 4$ 就返回 $1$
* [2:47](https://youtu.be/KYOUfnXouMA?t=167): 變數 `decision` 的命名不精準，劍橋詞典的[解釋](https://dictionary.cambridge.org/dictionary/english/decision): "a choice that you make about something after thinking about several possibilities"
* [3:45](https://youtu.be/KYOUfnXouMA?t=228): 用「改進」取代「優化」，參見〈[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)〉，當提及二分搜尋法的時候，要有其效益分析 (時間複雜度、計算次數的比較)，避免說「大幅降低」這樣不精準的話語，理工人要用證據說話。
* [4:24](https://youtu.be/KYOUfnXouMA?t=264): 避免說「我要開始打程式」這種顯而易見的話語。
* 考慮〈[從 √2 的存在談開平方根的快速運算](https://hackmd.io/@sysprog/sqrt)〉
---
## 119. [Pascal's Triangle II](https://leetcode.com/problems/pascals-triangle-ii/description/) : Easy
### 模擬面試過程
🕵️♂️: 你好，我是Jackson，我是任職於Grape公司的面試官。
🕵️♂️: 我給你Google Doc的連結之後就可以開始了。
🕵️♂️: 巴斯卡三角形能計算二項式係數，對於二項式展開至關重要。然後二項式展開在演算法的設計和機率統計中也有廣泛應用。
🕵️♂️：假設給定一個介於 0 到 33 之間的數字 rowIndex，表示巴斯卡三角形的第 rowIndex 層，最上方為第 0 層，我們的目標是求出該層的所有二項式係數。
🕵️♂️：請問你對題目有疑問嗎？
🕶️：沒有，但是爲了確認我對題目的理解，我想用一個例子説明。
輸入： `rowIndex = 3`
輸出： `[1,3,3,1]`
🕶️：請問我對於題目的理解上有任何錯誤嗎？
🕵️♂️：沒有，你可以開始寫你的程式了。
🕶️：在寫程式之前，我想先講一下我的想法。
🕶️：我的想法是先判斷初始條件，當輸入為 0 或 1 時，直接返回對應的結果。如果輸入大於 1，則使用雙重迴圈來計算巴斯卡三角形的值。第一層迴圈負責根據目標層數逐層更新，每次計算時創建一個 temp 來存放新一層的值。第二層迴圈負責根據目前的層數，兩兩相加計算巴斯卡三角形的係數，並將結果存入 temp。雙重迴圈完成後，將計算結果賦值給 answer。
🕶️：這樣的解法由於使用了雙重迴圈，因此時間複雜度為 $O(rowIndex^2)$。同時，使用了 vector，最終會存放 rowIndex + 1 個元素，其他變數皆為常數級別，因此空間複雜度為 $O(rowIndex)$。
---
### 暴力解法 ( <s>雙重迴圈</s> )
:::danger
下方程式碼的迴圈並非「對等」，不是「雙」。改稱「二層迴圈」。
:::
```cpp
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(rowIndex)$ 的時間複雜度。
🕶️：具體的公式如下: $$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)。
---
### 二項式係數
```cpp
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](https://leetcode.com/problems/min-stack/description/) : 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
```cpp
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.
Sign in with Wallet
Connect another wallet