Design Twitter
Medium · Heap / Priority Queue
Build a tiny social feed service. It supports posting a tweet by a user, having one user follow or unfollow another, and fetching a user's news feed which must contain the ids of the 10 most recent tweets from the user themselves and everyone they follow, ordered from newest to oldest. Tweets are identified by ever-increasing recency: later posted tweets always count as more recent than earlier ones. Unfollowing a user who was never followed should be harmless, and a user is always considered a source of their own tweets even without an explicit follow.
Examples
Input: postTweet(1, 5); getNewsFeed(1)
Output: [5]
Why: User 1 posted tweet 5 and hasn't followed anyone else, so the feed just shows their own tweet.Input: postTweet(1, 5); follow(2, 1); postTweet(2, 6); getNewsFeed(2)
Output: [6, 5]
Why: User 2 sees their own tweet and user 1's tweet, newest first.Input: postTweet(1, 5); follow(2, 1); unfollow(2, 1); getNewsFeed(2)
Output: []
Why: After unfollowing user 1, user 2 no longer sees user 1's tweet and has posted none themselves.Constraints
1 <= userId, followerId, followeeId <= 500, 0 <= tweetId <= 10^4, all tweetId values are unique, postTweet and follow/unfollow calls total at most 3*10^4, at most 10^4 calls to getNewsFeed
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Design Twitter. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.