題目資訊

題目編號: 359
題目連結: Logger Rate Limiter
主題: Hash Table, Design, Data Stream

題目敘述

設計一個記錄器系統以接收消息流及其時間戳。每個唯一的消息最多只能每10秒打印一次（即在時間戳 $t$ 打印的消息將阻止其他相同消息在時間戳 $t + 10$ 之前被打印）。

所有消息將按時間順序到達。數個消息可能在同一時間戳到達。

實作 Logger 類別：

Logger(): 初始化記錄器對象。
bool shouldPrintMessage(int timestamp, string message): 如果消息應在給定的時間戳中打印則回傳 true，否則回傳 false。

範例 1:

輸入

["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]

輸出

[null, true, true, false, false, false, true]

解釋

Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");  // 回傳 true，"foo" 的下次允許時間戳是 1 + 10 = 11
logger.shouldPrintMessage(2, "bar");  // 回傳 true，"bar" 的下次允許時間戳是 2 + 10 = 12
logger.shouldPrintMessage(3, "foo");  // 3 < 11，回傳 false
logger.shouldPrintMessage(8, "bar");  // 8 < 12，回傳 false
logger.shouldPrintMessage(10, "foo"); // 10 < 11，回傳 false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11，回傳 true，"foo" 的下次允許時間戳是 11 + 10 = 21

約束條件：

$0 \leq \text{timestamp} \leq 10^9$
每個時間戳都將以非遞減順序（按時間順序）傳入。
$1 \leq \text{message.length} \leq 30$
最多将會進行 $10^4$ 次 shouldPrintMessage 的呼叫。

直覺

該問題需要設計一個系統，通過控制消息日誌記錄的頻率來防止在較短的時間範圍（此處為10秒）內打印重複消息。挑戰在於如何有效地管理消息的時間戳，使得每條相同的消息若在距上次打印不超過10秒內重複，就不會被打印。解法應能高效地跟蹤和更新消息的日誌時間戳，並判斷一條消息在給定的時間戳下是否可以被打印。

解法

解決此問題的方法涉及使用哈希表（在C++中為unordered_map）來維護每條獨特消息的最後打印時間戳。這樣可以實現插入、更新和查詢這些消息相關時間戳的常量時間複雜度操作。

初始化：
- 使用一個名為messageLastPrintedTime的無序映射作為哈希表，用於存儲每個獨特消息的最後日誌記錄時間戳作為鍵。
日誌檢查：
- 對於每個具有特定時間戳的傳入消息，系統會檢查該消息是否存在於哈希表中。如果存在，系統將進一步檢查該消息的上次日誌時間（從哈希表中檢索）是否在當前時間戳的10秒窗口內。如果在10秒窗口內，則該消息不應打印，且函數返回false。
- 如果該消息不存在於哈希表中，或其上次日誌時間不在10秒窗口內，則允許記錄該消息。
更新時間戳：
- 一旦確定一條消息可以打印，哈希表將被更新為當前時間戳作為該消息的新最後打印時間。
- 然後函數返回true，表示該消息已成功打印。

通過使用哈希表進行快速的更新和檢查，系統確保在符合約束條件下有效處理最多 $10^4$ 次調用，維持時間和空間複雜度的最佳性能。

程式碼

C++

class Logger {
private:
    // 用於儲存每個訊息最後一次被打印的時間的哈希表
    unordered_map<string, int> messageLastPrintedTime;

public:
    // 建構子，用於初始化 Logger 物件
    Logger() {
        // 在創建 Logger 物件時清空哈希表
        messageLastPrintedTime.clear();
    }
    
    // 檢查某訊息是否應在給定的時間戳被打印的函數
    bool shouldPrintMessage(int timestamp, string message) {
        // 檢查訊息是否存在於哈希表中，且是否在 10 秒窗口內
        if (messageLastPrintedTime.find(message) != messageLastPrintedTime.end() 
            && messageLastPrintedTime[message] > timestamp - 10) {
            return false;
        }

        // 將訊息的最後打印時間更新為目前的時間戳
        messageLastPrintedTime[message] = timestamp;

        // 允許訊息被打印
        return true;
    }
};

/**
 * 您的 Logger 物件將被如此實例化和呼叫：
 * Logger* obj = new Logger();
 * bool param_1 = obj->shouldPrintMessage(timestamp, message);
 */

Python

class Logger:
    # 用來儲存每個訊息最後被列印時間的哈希表
    def __init__(self):
        # 當 Logger 物件被創建時清除哈希表
        self.messageLastPrintedTime = {}

    # 檢查是否應該在給定的時間戳列印訊息的函數
    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        # 檢查訊息是否存在於哈希表中，且是否在10秒的時間窗內
        if message in self.messageLastPrintedTime and self.messageLastPrintedTime[message] > timestamp - 10:
            return False

        # 將訊息的最後列印時間更新為當前時間戳
        self.messageLastPrintedTime[message] = timestamp

        # 允許列印該訊息
        return True

# 你的 Logger 物件將被實例化並調用，如下所示：
# obj = Logger()
# param_1 = obj.shouldPrintMessage(timestamp, message)

複雜度分析

時間複雜度: $O(1)$。這是因為在 unordered_map（哈希表）中的查找和插入操作平均時間複雜度為 $O(1)$。因此，檢查消息是否存在以及更新消息的時間戳都在常數時間內執行。
空間複雜度: $O(m)$，其中 $m$ 是傳遞給 shouldPrintMessage 函數的唯一消息的數量。這部分空間是用於在 unordered_map 中儲存每個唯一消息與其最後打印時間戳的映射。在最壞的情況下，每次調用 shouldPrintMessage 都可能是針對一個唯一的消息，導致空間複雜度與唯一消息的數量成正比。

CS Note
En

Leetcode 359. Logger Rate Limiter

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析