Design Twitter
Design Twitter: design posting, following, unfollowing, and a news feed containing the ten newest visible tweet IDs.
- 1 <= userId, followerId, followeeId <= 500
- 0 <= tweetId <= 10⁴
- All the tweets have unique IDs.
- At most 3 * 10⁴ calls will be made to postTweet, getNewsFeed, follow, and unfollow.
- A user cannot follow himself.
Intuition
The direct way to build a feed is to collect every tweet written by the user and their followees, sort the whole collection by time, and take ten. That repeats a large sort even though each user's own tweets are already in chronological order and only ten results matter. Treat those per-user histories as sorted streams: place the newest tweet from each stream in a max-heap, remove the newest candidate, then expose only the previous tweet from that same user. This is the same k-way merge idea used for sorted lists, but performed from newest to oldest and stopped after ten pops. This is a system design twitter question: the interview version asks for the same feed merge at a smaller scale. Design Twitter is a system design interview question; the twitter system design at full scale fans out writes, while this version merges reads.
Design twitter as an LLD exercise: the output asks for only the newest few items drawn from several histories that are individually ordered. That shape is a bounded k-way merge: keep one frontier item per history in a heap and advance only the history that supplied the item you remove.
Approach
Before reading on: price up what enumerating every case costs here, then ask why only the extreme element matters and the rest need no ordering. Aim for O((F + 10) log F) per feed request time and O(T + R) space.
Give every posted tweet a comparable timestamp
Maintain one increasing counter and store (time, tweetId) in the posting user's list. The counter provides a total order even when several users post, while appending keeps every individual list sorted from oldest to newest. Follow relationships live in sets so duplicate follows do not create duplicate feed entries.
Seed the feed heap with one tweet per visible user
The user's feed includes their own tweets as well as tweets from followed accounts. For each such account with a non-empty history, push only its newest tweet into a max-heap, together with the user and index it came from. Older tweets from that account cannot beat its newest one, so pushing the entire history would add work without changing the next choice.
Merge backward and stop after ten tweets
Pop the newest heap entry, append its tweet ID, and if that user has an earlier tweet, push that predecessor. The heap therefore always contains the newest unconsumed tweet from every active history. Stop after ten results because anything left is older than every returned tweet and cannot affect the requested feed.
Solution & live demo
Common pitfalls
Pushing every historical tweet
for time, tweet_id in self.tweets[user]:
time, tweet_id = self.tweets[user][index]
Only the newest tweet from each user can be the next feed item. Adding entire histories makes a feed request grow with all stored tweets.
Forgetting the user's own posts
visible_users = self.following[userId]
visible_users = self.following[userId] | {userId}A user's feed always includes their own tweets even though following themselves is not required.
Returning more than ten items
while heap:
while heap and len(feed) < 10:
The contract limits the feed to ten tweets; continuing the merge wastes work and returns an invalid result.
Edge cases
No history contributes a heap entry, so the loop returns an empty feed.
The followee set stores that account once, preventing duplicate copies of its tweets in the feed.
Their ID is added explicitly to the visible-user set during feed construction, so their own tweets remain visible as required.