DSA problem
Design Twitter
Design a simplified Twitter-style social graph that supports four operations: postTweet(userId, tweetId) records a new tweet; getNewsFeed(userId) returns the 10 most recent tweet ids posted by the user or by anyone they follow, in reverse chronological order; follow(followerId, followeeId) and unfollow(followerId, followeeId) adjust the follow graph. Each user can follow many others, and a user implicitly follows themselves so their own tweets always appear in their feed.
The state we keep is small but pointed. For each user maintain a list (or deque) of (timestamp, tweetId) records, appended in order; the timestamp is a monotonic counter incremented on every post so global order is unambiguous across users. For each user also maintain a set of followee ids. The four mutation operations are all O(1) — push to a list, add or remove from a set, increment a counter.
The interesting routine is getNewsFeed. Naively concatenating all followee tweets and sorting is O(F · T · log) per feed, which is wasteful when most tweets are old. The textbook solution is a k-way merge with a max-heap: initialize the heap with the latest tweet from each of the user's followees (including themselves), then repeatedly pop the most recent, and after popping push the popper's next-most-recent tweet. Stop after 10 pops.
This gives O(F + K · log F) per feed where F is the number of followees and K = 10 is the feed size — an order of magnitude better than the sort-everything approach when users follow hundreds of accounts. The same pattern is what real timeline systems use under the hood, except they shard the per-user tweet lists and the heap operates over inbox shards rather than user accounts.
Examples
postTweet(1, 5); getNewsFeed(1)[5]postTweet(1, 5); follow(1, 2); postTweet(2, 6); getNewsFeed(1)[6, 5]follow(1, 2); unfollow(1, 2); postTweet(2, 6); getNewsFeed(1)[]Constraints
- 1 <= userId, followerId, followeeId <= 500
- 0 <= tweetId <= 10^4
- All the tweets have unique IDs.
- At most 3 * 10^4 calls will be made to postTweet, getNewsFeed, follow, and unfollow.
- A user cannot follow themselves more than once and cannot follow a user that does not exist.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.