首先，idempotency 的意思就是一個動作做一次跟做很多次的結果是一樣的，譬如 HTTP POST & PUT 的比較，PUT 是 idempotent 的，POST 不是，因為它每次都會產生新東西。

Idempotency Key 據說是 Stripe 發明的詞，為了要讓一些操作可以避免重複執行，以 HTTP request 為例，會讓 client 產生一個 unique 的 key, 並在 HTTP header 帶上這個 key, server 端會 maintain idempotency key 和 result 的對應，如果發現已經有了，就直接回傳結果不處理，如果沒有，代表還沒做過，就執行操作並把 key & result 存起來。

Idempotency Key 也可以由 server 產生，不過必須要是這個操作是由 server 發起的。簡單來說，是由操作的發起者產生這個 key。

參考：Idempotency Key：原理與實測

簡介

這是分散式系統中很常用到的技巧，譬如你有個 redis cluster for caching, 就可以用 consistent hashing 來決定資料要放到哪個 redis instance, 優點是當增加或減少 redis node 時，可以最大化的減少資料的搬移

用 ChatGPT 查了下 redo log 是怎麼用在 database crash or power loss 後的 recovery 裡，這邊做個小筆記統整一下：

• 進行交易時，會依序進行以下步驟：
  1. 寫 redo log, 裡面記錄準備要做的改變，並記錄這個 transaction 的狀態為 in progress
  2. 把 redo log 紀錄的那些改變實際寫入 database files
  3. 把 redo log 的 transaction 狀態改為 committed
  4. 回傳 OK

題目
思路：

1. 可以找到最小可重複動作嗎？
   • 題目的 method 要傳入 first node, 回傳它的 clone
   • 最小可重複動作可設定為：給定一個 node, 回傳 its clone
2. DFS: 先寫 recursive case
3. Base case: method 收到已 clone 過的 node
   • Use a dict to record nodes been cloned.
4. 須注意傳入 cloneGraph 的 node 有可能是 None

題目
思路：

• 要找的點是可到達的點的距離在 threshold 裡的那些點，所以要找的是最短距離，因為只要最短距離可以在 threshold 內，那它就是可到達的點
• 用 Floyd-Warshall’s algorithm 找到所有點之間的最小距離
  • k 是 i 到 j 之間的任意點。比較 i -> j 經過所有 k 的距離，最小的即為 i -> j 的最短距離。
  • Question:
    if the path is i -> 2 -> 1 -> j and the iteration consider k == 1 first. But the dist[i][1] not yet populated and still have value of float('inf'). It will have the actual value until k == 2.

題目
最直覺的作法就是先排序，取出最重的兩個撞擊後，把剩下的放回去，然後重複以上步驟：

1
2
3
4
5
6
7
8

def lastStoneWeight(self, stones: List[int]) -> int:
    while len(stones) > 1:
        stones.sort()
        s1 = stones.pop()
        s2 = stones.pop()
        if s1 != s2:
            stones.append(s1 - s2)
    return stones[0] if stones else 0

但這樣的時間複雜度為 O(n^2 * log n)，太大了，有沒有其他方法？

題目
這邊記錄自己答案的演變和檢討，有需要的也可以直接跳到最後的 O(1) space complexity 解答

一開始的思路：用遞增的 index 同時 go through 這兩個字串，按照裡面的 backspace hint build 出兩個新的字串再來看看是否相等

題目
思路：怎麼判斷兩個字串是不是 anagram?

• 可以把兩個字串都做排序，再看看是否相等，但這樣每次都要多花 O(n) 時間
• 可以計算每個字母出現的頻率，再看看兩個字串的計算結果是否相等。雖然單獨算也是要 O(n)，但假如搭配 sliding window 移動的時候一個個字母加入計算，就不會有額外的時間複雜度

題目
紀錄一下一開始的思路，檢討錯誤，再整理最後的答案。一開始的想法：

1. 這應該可以分解成最小可重複動作，用遞迴解看看
2. 覺得可以用原本的 method 當遞迴函式，把 image, color 照樣傳入，sr, sc 為該點的座標
3. 最小可重複動作：從當下這點擴散到周圍四個點

題目
思路

1. 樹的問題會先從遞迴來想比較直觀，首先找出最小可重複動作來作為 recursive case
2. 先假設我們可以用題目給的 method 直接當作遞迴的函式，也就是說我們遞迴函式的回傳，是 preorder 排序的 node values
3. 最小可重複動作：對於我這個 node 來說，回傳 preordered values

1
2
3
4
5
6
7

def preorder(self, root: 'Node') -> List[int]:
    if not root:
        return []
    result = [root.val]
    for child in root.children or []:
        result.extend(self.preorder(child))
    return result