---
# System prepended metadata

title: 2025 年「資訊科技產業專案設計」作業 2

---

# 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 的互動很重要。以前我講完就等下一題，現在會試著多觀察對方的反應並向對方確認理解程度，讓整個對話變得更自然。這樣不只是表現得比較放鬆，也能讓面試官感覺我真的在「溝通」，而不是在「背稿」。
另外，我有刻意練習自己的語調和肢體語言。比如講到有趣的應用時會讓表情自然一點、語氣有起伏。
## 在上課中
這堂課讓我收穫最多的一點，是有機會能直接和業界的學長姐交流。以前在上課時，常常覺得內容離實際工作很遠，但透過他們的分享，我開始更清楚這些底層知識在真實開發裡的重要性。比如他們講到在公司裡如何處理效能瓶頸、系統架構的取捨，讓我發現很多理論其實都能對應到實際情境，只是以前沒有機會那樣思考。
這門課讓我學會怎麼思考和提問問題」，未來在面試或職場上，這樣的能力會比單純背知識更有價值。