Design Twitter
Medium · Design · Hash Table · Linked List · Design · Heap (Priority Queue)
Problem
Design a small social network where users post tweets, follow each other and read a news feed of the latest tweets.
Implement the class Twitter:
- Twitter() creates the service.
- postTweet(userId, tweetId) has userId post a new tweet with the unique id tweetId.
- getNewsFeed(userId) returns the ids of the 10 most recent tweets posted by the user or by anyone they follow, most recent first (fewer if there are not 10).
- follow(followerId, followeeId) makes followerId follow followeeId. Following someone twice changes nothing.
- unfollow(followerId, followeeId) makes followerId stop following followeeId. Unfollowing someone not followed changes nothing.
Recency is the order in which postTweet was called, not the size of the tweet id.
Tests call the methods in sequence: ops[i] is a name and vals[i] its arguments; the first call creates the object. The answer is the list of return values, with None for methods that return nothing.
Examples
Input: Twitter(), postTweet(1,50), postTweet(2,7), follow(1,2), getNewsFeed(1), unfollow(1,2), getNewsFeed(1) Output: [null, null, null, null, [7, 50], null, [50]]
Tweet 7 was posted after 50, so it comes first. After the unfollow only user 1's own tweet is left.
Input: Twitter(), postTweet(3,4), getNewsFeed(2) Output: [null, null, []]
User 2 follows nobody and has posted nothing.
Input: Twitter(), postTweet(1,900), postTweet(1,5), getNewsFeed(1) Output: [null, null, null, [5, 900]]
Tweet 5 was posted last, so it is first even though its id is smaller.
Constraints
- 1 <= userId, followerId, followeeId <= 500
- 0 <= tweetId <= 10^4
- all tweet ids are unique
- at most 3 · 10^4 calls in total
- a user never follows themselves
Approaches
- Baseline: one global log, scan backwards — time post O(1); feed O(total tweets), space O(tweets + follows)
Follow-up
With millions of followers, merging at read time gets expensive for popular accounts, while pushing every tweet into each follower's stored feed at post time ("fan-out on write") gets expensive for accounts with many followers. Real systems mix the two: push for ordinary accounts, pull for the very popular ones at read time.
Related problems
Start free on Cariara · Coding problems · System design studio
