Design Twitter
Understanding the Problem
We are building a simplified social media feed system. There are four operations: posting a tweet, following someone, unfollowing someone, and retrieving a news feed. The work concentrates in getNewsFeed, because it merges tweets from multiple users and returns the 10 most recent ones.
Each user has their own timeline of tweets, ordered by when they were posted. A call to getNewsFeed looks at the timelines of the user and everyone they follow, then picks the 10 most recent tweets across all those timelines. Since each user's timeline is already sorted by recency, this reduces to merging K sorted lists and taking the first 10 elements, where K is the number of users whose tweets matter.
Posting, follow, and unfollow are constant-time updates to a list or a set. The merge in getNewsFeed is the part where the algorithmic choice changes the running time.
Key Constraints:
1 <= userId, followerId, followeeId <= 500-> At most 500 users, so a follow set per user is cheap.0 <= tweetId <= 10^4-> Up to 30,000 total tweets, since every call could be apostTweet.At most 3 * 10^4 calls-> The timestamp counter tops out near 30,000, so a 32-bit integer holds it with no overflow. A feed that rescans every tweet from every followee can do up to 30,000 work pergetNewsFeed, even though we only need the 10 newest. The second approach avoids touching tweets we will never return.A user cannot follow himself-> The feed still includes the user's own tweets, but there is no self-follow edge to handle.
Approach 1: Brute Force (Collect and Sort)
Intuition
When getNewsFeed is called, gather every tweet from the user and everyone they follow into one list, sort that list by recency, and return the first 10.
The other operations are direct: postTweet appends to a user's tweet list, follow adds to a set, and unfollow removes from a set.
The cost lives in the sort. If a user follows many people who have each posted many tweets, every feed request sorts a potentially large list, even though only 10 of those tweets survive.
Algorithm
- Maintain a
Map<Integer, List<int[]>>where each user maps to their list of tweets. Each tweet is stored as[timestamp, tweetId]. - Maintain a
Map<Integer, Set<Integer>>for follow relationships. - Keep a global
timestampcounter, incremented on everypostTweetcall. - For
postTweet(userId, tweetId): append[timestamp, tweetId]to the user's tweet list. - For
follow(followerId, followeeId): addfolloweeIdtofollowerId's follow set. - For
unfollow(followerId, followeeId): removefolloweeIdfromfollowerId's follow set. - For
getNewsFeed(userId): collect all tweets from the user and everyone in their follow set into one list. Sort by timestamp descending. Return the first 10 tweet IDs.
Example Walkthrough
Code
- Time Complexity: O(1) for
postTweet,follow, andunfollow. O(T log T) forgetNewsFeed, where T is the total number of tweets from the user and all their followees. We collect all relevant tweets and sort them. - Space Complexity: O(U + T) where U is the number of users and T is the total number of tweets across all users.
The waste in getNewsFeed is that we collect and sort every tweet from the user and all their followees only to return 10. The next approach uses the fact that each user's tweets are already in chronological order to merge them without sorting everything.
Approach 2: Heap-Based Merge (Optimal)
Intuition
Each user's tweet list is already sorted by time, with the newest at the end since we append in order. So getNewsFeed is merging K sorted lists and returning the top 10 elements, which a max-heap (priority queue) handles directly.
We seed the heap with only the most recent tweet from each relevant user. Then we pop the most recent tweet overall, add it to the result, and push that user's next most recent tweet. We repeat until we have 10 tweets or the heap is empty.
This touches at most 11 tweets per user (one to seed, then one more each time that user's tweet is popped, up to 10 pops total across all users), not every tweet they have ever posted. Each heap operation costs O(log K), where K is the number of users in the feed.
The globally most recent unselected tweet is always one user's current frontier tweet. Within a single user, tweets are sorted by time, so a user's newest unselected tweet is more recent than all of that user's older ones. Across users, the heap holds exactly one frontier tweet per user, so its maximum is the most recent tweet not yet selected. After we pop a user's frontier and replace it with that user's next-older tweet, the invariant still holds. Repeating this 10 times yields the 10 most recent tweets in order.
Algorithm
- Maintain a
Map<Integer, List<int[]>>for tweets (each entry is[timestamp, tweetId]), aMap<Integer, Set<Integer>>for follow relationships, and a globaltimestampcounter. postTweet: append[timestamp++, tweetId]to the user's tweet list.follow: add followeeId to followerId's set.unfollow: remove followeeId from followerId's set.getNewsFeed:- Build a list of relevant users: the user themselves plus everyone they follow.
- For each relevant user who has tweets, push their most recent tweet into a max-heap. The heap entry is
[timestamp, tweetId, userId, index], where index points to the position in that user's tweet list. - Pop from the heap up to 10 times. Each time we pop, add the tweetId to the result, then push the same user's next most recent tweet (if it exists) into the heap.
Example Walkthrough
Code
- Time Complexity: O(1) for
postTweet,follow, andunfollow. O(K log K) forgetNewsFeed, where K is the number of users in the feed (the user + their followees). We push K items into the heap (each O(log K)), then pop at most 10 times (each O(log K)). Since we pop at most 10 times, this is O(K log K + 10 log K) = O(K log K). - Space Complexity: O(U + T + K) where U is the number of users, T is total tweets, and K is the heap size during
getNewsFeed(at most the number of followees + 1).