# 2025 年「資訊科技產業專案設計」作業 2
> 貢獻者 : ==摩斯 Morse==, Bella
> [面試錄影-1](https://www.youtube.com/watch?v=P0JelAEpZeQ)
> [面試錄影-2](https://youtu.be/_nYrw_m-H0o)
## Question 1
>E (Interviewee) : Bella
>R (Interviewer) : Morse
題目連結 : [7. Reverse Integer](https://leetcode.com/problems/reverse-integer/description/)
R ：你好！感謝你來參加今天的面試，我剛剛有傳一個Google文件的共用連結給你，等等想跟你討論一些關於程式的想法，你再幫我打在連結那份檔案內就好～有問題隨時跟我說！
E ：好的，謝謝！我已經打開連結了，目前沒問題～
R： 那這裡直接開始～
E： 好的！
R： 假設我們在處理一個老舊系統的日誌（log）資料，這些日誌中的序號都是 32-bit 帶號整數。由於系統設計上的需要，我們要將這些序號的位數反轉，作為新的索引。所以現在要寫一個函式，輸入是這個舊序號 x，回傳反轉後的新序號。關鍵要求是： 如果反轉後的數值超出了 32-bit 帶號整數的範圍，請回傳 0。而且我們假設環境不允許你使用 64-bit 整數來輔助檢查。
E： 那我確認一下我的理解：給定一個 32-bit 帶號整數 x，我們需要用數學方法將其位數反轉。核心挑戰是，在每一次 push 位數的操作前，我們必須主動檢查 Overflow，並確保整個過程只使用 32-bit 運算。如果溢位，就回傳 0，對嗎？
R： 完全正確！溢位檢查正是這題的重點～
E： 既然如此，我有幾個問題。第一個問題是，負號處理：如果輸入是負數（例如 −123），我們是保留負號，回傳 −321 嗎？第二個問題是：如果輸入是 120，反轉後是 21，我們會自動捨棄那個 0，對嗎？
R： 很好的問題！沒錯～負號保留，最後有零在反轉後會自動移除。
E： 謝謝，我知道了！那讓我來舉個例子：溢位極限輸入 (E）： 假設 INT_MAX=2147483647。如果輸入 x=1463847412，反轉後是 2147483641（仍在範圍內）。但任何會導致反轉後數值超過 2147483647 的輸入（如 2147483649），我們就必須回傳 0。
R： 沒錯，你的判斷正確，那要如何不用 64-bit 就進行安全的溢位檢查，分享一下你的想法～
E： 好的。我會寫一個 while 迴圈，用 x % 10 pop 末位數 digit，並透過 rev=rev∗10+digit push 到反轉結果 rev 中。核心技術點在於溢位檢查：我們必須在乘以 10 之前，檢查 rev 是否已經大於 INT_MAX/10，確保我們的 rev 乘以 10 之後不會衝破 INT_MAX 的邊界。
R： 你的方法很明確。請你直接開始寫程式碼。
E： 沒問題！這裡我使用的是 C 語言：
int reverse(int x) {
int rev = 0;
// 不允許使用 64-bit，我們必須使用 INT_MAX 和 INT_MIN 進行 32-bit 檢查
while (x != 0) {
// 核心溢位檢查：在乘以 10 之前檢查 rev 是否超過安全範圍
// rev > 214748364 或 rev < -214748364 時，下一輪必溢位。
if (rev > INT_MAX / 10 || rev < INT_MIN / 10) {
return 0;
}
int digit = x % 10;
x /= 10;
// 臨界點檢查 (處理 rev 剛好等於 INT_MAX / 10 的情況)
// rev == 214748364 時，若 digit > 7 則溢位。
if (rev == INT_MAX / 10 && digit > 7) return 0;
// rev == -214748364 時，若 digit < -8 則溢位。
if (rev == INT_MIN / 10 && digit < -8) return 0;
// 進行安全的推入操作
rev = rev * 10 + digit;
}
return rev;
}
E： 以上是我的code，在進入 Walkthrough 之前，先說明一下複雜度，因為每個位數只處理一次，所以時間複雜度是 O(log 10 ∣x∣)，這取決於輸入x的位數。只使用了幾個固定的整數變數，所以空間複雜度是 O(1)。
R： 你的溢位檢查邏輯很嚴謹，而且時間和空間效率都不錯，有更好的作法嗎？
E： 目前我想到的最好作法就是這個！
R： 了解～
E： 那我接下來以兩個例子來check是否正確，
負數案例 (x=−123)： 迴圈執行三次，rev 依序為 −3、−32、−321。 x 最終變為 0。回傳 −321。
極限溢位： 假設 rev 達到 214748364 (INT_MAX/10)，下一個 digit=8. 檢查 digit>7 成立，直接回傳 0。
R： 你的溢位檢查和 Walkthrough 非常到位，我這裡沒問題了～
### 初步檢討
- 面試時 `rev > INT_MAX / 10 || rev < INT_MIN / 10` 漏掉除以 10 了，而面試官也沒有注意到。
- 重新復述題目的時候也可以帶入使用場景。
## Question 2
>E (Interviewee) : Morse
>R (Interviewer) : Bella
R (Interviewer)： 歡迎參加今天的面試，那就直接進到我們的題目吧。
E (Interviewee)： 好的
R : 在虛擬記憶體管理中，當實體頁框（page frame）數量有限時，系統在載入新頁面時必須選擇淘汰一頁。這時候如果我們淘汰最不常用的 page 你知道這是什麼方法嗎 ？
E : LRU cache
R : 很好，那接下來我要你實做 LRU cache ，請你打開我剛才給你的檔案，裡面有一個骨架，請你使用它來完成。
E : 好的。我已經打開了。
R : 好的，我希望函式的一開始我可以呼叫 LRUCache 來做初始化，接著每次要將資料放入 Cache 內時我會呼叫 put ，我的 input 會是一個 key 跟 value 來表示要放進去的資料。最後當我呼叫 get 的時候，我可以得到對應 key 的 value。
E : 那我想確認一下我有正確理解每個 function 要做的事，首先我需要有一個 LRUCache 的 function 來初始化我的 Cache。接著有另一個 put 的 function 來把資料放入，因為是 LRU cache 所以如果超出容量我會需要把最少碰到的資料給踢出。最後，我會需要一個 get 的函式來取得輸入 key 的 value。
R : 沒錯 你的理解是正確的。
E : 好的，那我這邊想使用 Hash 搭配 double Linked list 來完成這題，因此我會需要先完成 Linked list struct 的部份。
R : 好的，沒問題。
```cpp
struct Node {
int value;
int key;
Node* next;
Node* prev;
Node(int v, int k) : value(v), key(k), next(nullptr), prev(nullptr) {}
};
```
E : 那這邊是我的 Linked list 的架構，我有使用到一個 constructor 來方便我建立 Node。 當我的 put 被呼叫的時候會需要把資料放到整個 list 的最後面，或是被 get 呼叫的時候也需要放到最後面。這樣當我容量滿需要移除的時候，list 的最前面就是 Least Recently used 的 Node 需要被移除。
E : 所以我需要先完成 insert remove 跟把目前節點移動到最後面的 function。此外，為了能夠取到最前跟最後面，我也會另外用兩個變數存 l 跟 r 當作 dummy head。
E : 至於查找的部份我使用 HashMap 來完成。
```cpp
unordered_map<int, Node*> hashMap;
int cap = 0;
int count = 0;
Node* l = nullptr;
Node* r = nullptr;
void insert(Node* newNode) {
// rp <-> r
r->prev->next = newNode;
newNode->prev = r->prev;
newNode->next = r;
r->prev = newNode;
}
void remove() {
// l <-> old <-> old_next
Node* oldNode = l->next;
l->next = oldNode->next;
oldNode->next->prev = l;
hashMap.erase(oldNode->key);
count--;
delete oldNode;
}
void detach(Node* deNode) {
deNode->prev->next = deNode->next;
deNode->next->prev = deNode->prev;
}
```
R : 看起來不錯，那要怎麼完成主要的 function 呢 ?
E : 首先 LRUCache 的部份就直接把 l r 跟 map 做初始化。接著 get 的時候直接用 hashmap 去找，如果找到的話就把 value 回傳並把對應的 Node 放回去到 List 的尾巴。在 put 的時候，則是做對應的操作。如果已經在裡面的話就更新數值並且放到最後面，如果不在裡面的話就確認容量還夠不夠，不夠則需要移除最左邊的，夠的話就直接放到最後面即可。
```cpp
LRUCache(int capacity) {
hashMap.clear();
cap = capacity;
count = 0;
l = new Node(0, 0);
r = new Node(0, 0);
l->next = r;
r->prev = l;
}
int get(int key) {
auto it = hashMap.find(key);
if (it != hashMap.end()) {
detach(it->second);
insert(it->second);
return it->second->value;
}
return -1;
}
void put(int key, int value) {
auto it = hashMap.find(key);
if (it == hashMap.end()) {
Node* newNode = new Node(value, key);
hashMap[key] = newNode;
if (count < cap) {
insert(newNode);
} else {
remove();
insert(newNode);
}
count++;
} else {
it->second->value = value;
detach(it->second);
insert(it->second);
}
}
```
E : 我的程式碼就到這邊，我舉個例子來當作範例。
```
["LRUCache", "put", "put", "get", "put", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2]]
```
初始化後給予兩個的 capacity，接著把 key 1 val 1 跟 key 2 val 2 放進去，這時候會是 `l <-> 1 <-> 2 <-> r` , 接著查 1 的時候會得到他的 value 1 ， 並把 1 移動到後面 `l <-> 2 <-> 1 <-> r` 。接著我再把 key 3 val 3 ，由於已經滿了，因此最後的 2 會被移除改為 3 ， `l <-> 1 <-> 3 <-> r` ，這時候再查詢 2 回傳便是 -1 了。
R : 看起來不錯，這樣時間複雜度如何呢 ?
E : 使用了 hashMap 做查找，且每次都是放在最左邊或是最右邊，因此時間複雜度為 O(1)。
R : 很好，今天的面試就到這裡，辛苦了。
### 初步檢討
- 後面程式碼的部份幾乎都只顧著自己說，沒有適度的和 interviewer 互動。
- 缺乏對於程式碼的分析，似乎只想著要把問題解決。
## 檢討自己至今的表現
#### 作業上
寫作業的時候目前還是都是先寫稿在直接演藝一次，但即使如此都還是會有需要重錄或是剪輯的部份，可見自己對於如何向他人說明自己的思路還需要多加練習。另一方面，練習的過程中發現自己在面試的時候很容易為了不緊張而想緩和氣氛，這樣有時候反而會有失專業，也是自己需要注意的部份。
在第二次面試練習的時候，因為題目的內容較長而沒有適度的和 interviewer 互動，也是需要檢討的部份，要注意面試的時候不要過於想表現自己反而劈哩啪啦的講不停。
#### 課堂上
上課學到最重要的事情便是要從 interviewer 或是企業方的角度去思考，對於我們來說往往很容易想表現自己對於工作很有熱忱，但忽略了公司方要找的是"可以解決問題的人"，熱忱反而不是最重要的，重要的而是自己的專業度。
另一方面，從學長姐的分享也可以了解到，他們為了進入心目中的公司付出了多少努力，而其中也不乏自己主動去爭取或是聯繫，也呼應了老師要我們主動去加 linkedin ，藉由上課的機會多多認識未來可能共事的夥伴。
## HW1 同儕互評
[小蚪-Yanbao](https://hackmd.io/@sysprog/BJbVKL0hgx)
[吉歐 Calala](https://hackmd.io/@sysprog/H1jISB03ll)
[粥餅倫-Bing](https://hackmd.io/@sysprog/SJto8qRnlx)
[勒芙蕾絲-Lovelace](https://hackmd.io/@sysprog/rygNaBkpgx)
[海帕提婭 Hypatia](https://hackmd.io/zrwJ8YK2TeiVtRP7bI1X6Q?both)
Sign in with Wallet
Connect another wallet