# 2025 年[「資訊科技產業專案設計」](https://hackmd.io/@sysprog/info2025-homework2)作業 2
Contributor: <`托爾斯泰-Tolstoy`>
## [LeetCode 450: Delete Node in a BST ](https://leetcode.com/problems/delete-node-in-a-bst/description/)
🧑🏻：
> 沒問題的話，那我們現在就開始code interview的部分
🧑🏼🎓：
> 好的
🧑🏻：
> 我們來做一到關於二元搜尋數Binary search Tree的題目
你需要製作一個函式叫做DeleteNode刪除節點
然後input式root樹根還有key，型態為int
請你實作刪除值為key的節點，並回傳新的根節點
若不存在這個key值的點，則回傳原本的root
若存在請根據BST的性質正確的刪除他
🧑🏼🎓：
> 了解了！我會想用遞迴的方法
> 首先排除root為空的情況
接著先討論如果當下看得節點(root)值不為key時
根據BST的性質，若key比較大則往右子樹遞迴，反之往左子樹遞迴
若找到了，也就是key等於當下root的值
> 這裡我在分為三種情況
第一種是左子樹為空，那就把右子樹的root回傳
第二種則是右子樹為空，那就把左子樹的root回傳
> 第三種是左右子樹都存在，那麼我就會把當下target點右子樹中最小的節點拉上來
這裡我會想用一個while loop來完成
並且做法是找到這一個右子樹最小的節點後，把他的值貼上來target節點
接著對右子樹呼叫deleteNode函式
因為這個右子樹最小的節點一定沒有左子樹，所以一定會解決
如此就能完成BST刪除節點的實作
> 我的想法講完了，接下來就來打我的code！
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root==NULL) return root;
else if(root->val<key) // 目標點在右子樹
root->right=deleteNode(root->right,key);
else if(root->val>key)
root->left=deleteNode(root->left,key);
else{ // 找到target node!
if(root->left==NULL)
return root->right;
if(root->right==NULL)
return root->left;
else{ // 左右子樹都在
TreeNode* rightsmallest=root->right;
while(rightsmallest->left!=NULL)
rightsmallest=rightsmallest->left;
root->val=rightsmallest->val;
root->right=deleteNode(root->right,rightsmallest->val);
}
}
return root;
}
};
```
🧑🏻：
> OK好，謝謝你的回答！
## [LeetCode 146: LRU Cache](https://leetcode.com/problems/lru-cache/)
**Interviewer**: 好，希望前面的講解能讓你更了解我們公司一點，那接下來就不免俗地來進行我們的code interview。那這一題我想要來考驗一下有關OS的能力，來做一個LRU Cache的實做。這一題我們希望你實做使用LRU，簡單版的cache，然後我的資料會是int，相對應的key值，需要你實做的有3個函式。
會有一個LRU class來實做，裡面有3個函式，第一個是建構子去建構LRU Cache，第二個是取得資料，第三個是把資料放進去。然後LRU的建構子會給你一個capacity，就是它的容量大小，超過容量大小的話，你應該知道要怎麼做，那接下來就交給你來實做。
**Interviewee**: LRU 是一種快取的淘汰策略，當快取滿了以後，我們會刪除「最久沒有被使用」的項目，以便騰出空間給新的資料。
為了達成這個目標，我們需要同時**滿足兩個條件**：
1. **能夠** O(1) **查找 key 是否存在**。
我們可以使用 `unordered_map`（也就是 Hash Map），讓我們能夠直接找到對應的node。
2. **能夠** O(1) **調整使用順序**。
這部分我們用 **Doubly Linked List** 來完成。每當有節點被使用時，就把它移到最前面。而當容量不足時，我們只要從尾端刪除最後一個節點，就是「最久沒被用」的項目。
我會在 linked list 的開頭與尾端各放一個虛擬節點（`head` 和 `tail`），這樣可以讓插入與刪除節點的操作更簡單，也不用處理太多邊界條件。
那接著我就開始實做。
> 我先從 linked list 開始
>
```cpp
#include <unordered_map> // include 給 hash map 的 library
class Node { // 我先定義一個 Node class
public: // 它會有 key、value、next、prev。
int key;
int value;
Node *next;
Node *prev;
Node(int k = 0, int v = 0) : key(k), value(v), next(nullptr), prev(nullptr) {}
// 另外我會提供兩個 utility function
void append(Node *target) { // 把target node接到current node後面。
this->next = target;
if (target)
target->prev = this;
}
void pull() { // 把node從linked list中拔出來。
if (next)
next->prev = prev;
if (prev)
prev->next = next;
}
};
```
> 接著我來實作 `LRUCache` class
```cpp
class LRUCache {
private:
// 我需要一個 unordered_map<int, Node*> 來記錄 key 對應的節點。
std::unordered_map<int, Node *> cache_map;
// 同時，我會有2個虛擬節點 head 和 tail 方便管理linked list。還有cache的空間。
Node *head;
Node *tail;
int capacity;
// 將節點移到最前面（最近使用）
void moveToFront(Node *node) {
node->pull(); // 拿出來
node->append(head->next); // 處理後面的節點
head->append(node); // 處理head節點
}
public: // Constructor
LRUCache(int capacity) : capacity(capacity) {
head = new Node();
tail = new Node();
head->append(tail);
}
```
接下來我實作 `get()`。
```cpp
int get(int key) {
// Cache miss: 如果 key 不存在，我直接回傳 -1。
std::unordered_map<int, Node *>::iterator it = cache_map.find(key);
if (it == cache_map.end()) {
return -1;
}
// Cache hit，如果存在，就把節點移到最前面，然後回傳它的值。
Node *node = cache_map[key];
moveToFront(node);
return node->value;
}
```
然後是 `put()`。
```cpp
void put(int key, int value) {
// 如果 key 已存在，更新值並移到最前面
std::unordered_map<int, Node *>::iterator it = cache_map.find(key);
if (it != cache_map.end()) {
Node *node = cache_map[key];
node->value = value;
moveToFront(node);
return;
}
// 創建新節點
Node *new_node = new Node(key, value);
cache_map[key] = new_node; // 登記到hash map中
// 檢查容量
if (capacity > 0) { // 如果足夠就capacity扣除1
capacity--;
} else {
// 容量不足，刪除最久未使用的節點，也是最後一個節點
Node *discard = tail->prev; // 可以用tail的前一個節點表示
if (discard != head) { // 排除掉 empty list 的可能性
discard->pull(); // 從 cache 移除
cache_map.erase(discard->key); // 從 hash map 中移除
}
}
// 將新節點加到最前面
new_node->append(head->next);
head->append(new_node);
}
};
```
最後我做簡單的測試來驗證：
```cpp
#include <iostream>
// 測試程式
int main() {
LRUCache *cache = new LRUCache(2); // 容量為2的cache
// 接著插入1和2
cache->put(1, 1);
cache->put(2, 2);
// 存取1，這樣一來2就是Least Recently Used cache
printf("Get 1: %d\n", cache->get(1));
// 插入3，然後2會被替換
cache->put(3, 3);
// 看看2是不是cache miss並回傳-1
printf("Get 2: %d\n", cache->get(2));
// 我們再試著插入4，1是LRU會被替換
cache->put(4, 4);
printf("Get 1: %d\n", cache->get(1));
printf("Get 3: %d\n", cache->get(3));
printf("Get 4: %d\n", cache->get(4));
return 0;
}
```
整體的思路是透過 map 快速找到節點位置，再用雙向鏈結串列維持 LRU 順序。所有操作都在 O(1) 時間內完成。
---
**Interviewer**: 不好意思我想要看一下你`get()`那邊的程式碼
看到了，程式碼完成度滿高的，有一點點小錯誤但你有找到那個==，然後看到你有少一個分號之類的，但是沒有關係，程式整體是存在的，code interview就到這邊，感謝你的用心講解。
# 自評
## Interviewee
- 有發現自己的`!=`沒有打好
- 可以省去程式碼比較繁複的步驟，因為沒有真的要實際執行，所以像 linked list 的部分可以假設有宣告就好
## Interviewer
- 能問 interviewee 的問題不足，比如可以問複雜度等等的問題。
# 檢討自己至今的表現
## 在作業上
最近在練習模擬面試的時候，我開始更注重表達和互動節奏。以前準備面試時，我只會背答案，結果一緊張就容易忘。現在我會先整理自己的想法，用框架去幫助自己講得更自然，比如先說背景、再講做法、最後補上結論。即使臨場被問到沒準備的題目，也能靠著邏輯去組織出一個有方向的回答，而不是卡住。
我也開始注意到和 interviewer 的互動很重要。以前我講完就等下一題，現在會試著多觀察對方的反應並向對方確認理解程度，讓整個對話變得更自然。這樣不只是表現得比較放鬆，也能讓面試官感覺我真的在「溝通」，而不是在「背稿」。
另外，我有刻意練習自己的語調和肢體語言。比如講到有趣的應用時會讓表情自然一點、語氣有起伏。
## 在上課中
這堂課讓我收穫最多的一點，是有機會能直接和業界的學長姐交流。以前在上課時，常常覺得內容離實際工作很遠，但透過他們的分享，我開始更清楚這些底層知識在真實開發裡的重要性。比如他們講到在公司裡如何處理效能瓶頸、系統架構的取捨，讓我發現很多理論其實都能對應到實際情境，只是以前沒有機會那樣思考。
這門課讓我學會怎麼思考和提問問題」，未來在面試或職場上，這樣的能力會比單純背知識更有價值。
Sign in with Wallet
Connect another wallet