題目描述:設計一個簡化版推特系統,支援以下操作:
postTweet(userId, tweetId):使用者發推文。getNewsFeed(userId):回傳使用者自己及其追蹤者最新的最多 10 則推文(按時間由新到舊)。follow(followerId, followeeId):追蹤功能。unfollow(followerId, followeeId):取消追蹤。解題思路:getNewsFeed 是此題難點——需要合併多個使用者的推文串流並取前 10 筆,這是**多路合併(K-way merge)**問題,以最小堆實作最有效率。
資料設計:
tweets:unordered_map<int, vector<pair<int,int>>>,userId → [(timestamp, tweetId), ...],每個使用者的推文按時間遞增存放(vector 尾端是最新的)。following:unordered_map<int, unordered_set<int>>,userId → 追蹤的人的集合。timer 記錄發推順序。getNewsFeed 流程:
堆中每個元素記錄:(timestamp, tweetId, userId, indexInVector),方便回溯找下一筆。
時間複雜度:postTweet O(1),follow/unfollow O(1) 平均(雜湊表);getNewsFeed O(F log F + 10 log F) = O(F log F),其中 F 為追蹤人數(加上自己共 F+1 個串流)。建堆初始化需要對每個串流各做一次 push O(F log F),之後最多取 10 次,每次 heap 操作為 O(log F),合計 O(F log F)。
空間複雜度:O(T + U²),其中 T 為總推文數,U 為使用者數。tweets 儲存 O(T) 筆推文,following 最壞情況 O(U²)(每個使用者追蹤所有其他人)。getNewsFeed 的堆最多容納 F+1 個元素,為 O(U) 臨時空間。
1. postTweet(userId, tweetId): append (globalTimer++, tweetId) to tweets[userId].
2. follow(followerId, followeeId): add followeeId to following[followerId] (skip self-follow).
3. unfollow(followerId, followeeId): remove followeeId from following[followerId].
4. getNewsFeed(userId):
a. Collect all relevant users: {userId} ∪ following[userId].
b. For each user u, push their most recent tweet (last element) as (timestamp, tweetId, u, lastIndex) into a max-heap.
c. While feed has < 10 tweets and heap is not empty:
- Pop (ts, tid, u, idx) from heap → add tid to feed.
- If idx-1 >= 0, push (tweets[u][idx-1].ts, tweets[u][idx-1].tid, u, idx-1) into heap.
d. Return feed.暴力合併排序 O(T log T):對 userId 及其追蹤者的所有推文合併成一個大陣列,直接按 timestamp 排序後取前 10。實作簡單,但需掃描所有歷史推文,當推文總量 T 很大時效率低落,而堆方法只需存取每個串流的最新端。
每次 getNewsFeed 預先排序快取:在 follow/unfollow/postTweet 時標記 feed 為 dirty,在 getNewsFeed 時重新生成並快取。適合讀多寫少場景(Twitter 的實際使用模式),但快取失效策略複雜,且快取本身需要 O(U * 10) 空間。
LinkedList + 時間戳指針:每個使用者的推文用雙向鏈結串列儲存,各串流維護當前讀取指針,實現真正的 O(1) 移動到下一筆。與本解的堆方法類似,但鏈結串列在 cache 效率上不如連續的 vector。