MediumRating 2037

1348. Tweet Counts Per Frequency

hash-tablestringbinary-searchdesignsortingordered-set

解題說明

Tweet Counts Per Frequency

題目描述：設計一個系統來記錄推文並能依據指定頻率（分鐘、小時、天）查詢某時間範圍內每個時間區間的推文數量。實現 recordTweet(tweetName, time) 記錄推文，以及 getTweetCountsPerFrequency(freq, tweetName, startTime, endTime) 回傳每個區間的推文計數。

解題思路：使用雜湊表（HashMap）儲存每個推文名稱對應的時間戳列表。查詢時，根據頻率計算區間大小（60、3600 或 86400 秒），然後遍歷該推文的所有時間戳，統計落在每個區間的數量。使用有序結構（如 set 或排序後二分搜尋）可以優化查詢效率。

C++ 解法

複雜度分析

時間複雜度：recordTweet 為 O(1)；getTweetCountsPerFrequency 為 O(t)，其中 t 為該推文名稱的時間戳總數

空間複雜度：O(n) — 其中 n 為所有推文記錄的總數

虛擬碼

1. Store tweets in a hashmap: tweetName -> list of timestamps
2. recordTweet: append time to the list for tweetName
3. getTweetCountsPerFrequency:
   a. Determine interval size based on freq (60, 3600, or 86400)
   b. Calculate number of buckets = (endTime - startTime) / interval + 1
   c. For each timestamp of tweetName in [startTime, endTime], increment bucket[(time - startTime) / interval]
   d. Return bucket counts

其他解法

方法二：有序集合（Sorted Set）+ 二分搜尋 使用 std::map 或 std::set 儲存時間戳，查詢時用 lower_bound/upper_bound 快速定位範圍內的推文。查詢時間複雜度可降低到 O(t' + log t)，其中 t' 為範圍內的推文數。插入變為 O(log t)。

方法三：分桶（Bucket）策略 預先依據最小頻率（分鐘）建立桶，查詢時將小桶合併為大桶。空間換時間，適合查詢遠多於插入的場景。

延伸思考

如果查詢非常頻繁但插入很少，你會如何優化資料結構？
如果需要支援刪除推文功能，設計會有什麼改變？
在分散式系統中，這個設計會遇到什麼挑戰？如何處理多台伺服器間的資料一致性？

Tweet Counts Per Frequency — CaffeCode