Design Twitter

DiffPush Tier Heaps · Hard Problems O(F + P log P) per feed · O(U + P)

The Newsroom Wire Service

A press agency runs an internal wire: reporters post dispatches stamped with sequence numbers, reporters can shadow other reporters, and each reader's digest shows the ten freshest dispatches from everyone they shadow (themselves included). Shadowing can be revoked. Replay a command log and record every digest the system produces.

Input: A list of operations: ["postTweet", userId, tweetId], ["getNewsFeed", userId], ["follow", followerId, followeeId], or ["unfollow", followerId, followeeId].

Output: Return the list of feeds produced by every getNewsFeed operation, each feed holding at most 10 tweet ids ordered newest first.

Constraints

1 <= number of operations <= 3 * 10^4
0 <= userId, tweetId <= 10^5 (ids are per-user sequential)
getNewsFeed returns at most 10 tweets, most recent first
Every user follows themselves by default

Examples

Example 1

Input: {"operations":[["postTweet",1,5],["getNewsFeed",1],["follow",1,2],["postTweet",2,6],["getNewsFeed",1],["unfollow",1,2],["getNewsFeed",1]]}
Output: [[5],[6,5],[5]]
Following reporter 2 adds their dispatch to the digest; unfollowing removes it again.

Example 2

Input: {"operations":[["postTweet",1,1],["postTweet",1,2],["getNewsFeed",1],["follow",2,1],["getNewsFeed",2]]}
Output: [[2,1],[2,1]]
Feeds read newest-first; a new follower immediately sees the shadowed reporter's history.

Solve this in your browser →

Also on LeetCode ↗