Loading problem…

226. Design Twitter

MediumDesign

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see the 10 most recent tweets in the user's news feed. Implement the Twitter class: - Twitter() Initializes your twitter object. - void postTweet(int userId, int tweetId) Composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId. - List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user's news feed. Each item must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent. - void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId. - void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.

Examples

Example 1

Input: operations = ["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"], arguments = [[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]

Output: [null,null,[5],null,null,[6,5],null,[5]]

Explanation: User 1 posts tweet 5 and sees [5]. After following user 2, who posts tweet 6, user 1's feed shows [6,5] (newest first). Once user 1 unfollows user 2, tweet 6 disappears and the feed is [5] again.

Example 2

Input: operations = ["Twitter","postTweet","postTweet","getNewsFeed"], arguments = [[],[1,5],[1,3],[1]]

Output: [null,null,null,[3,5]]

Explanation: User 1 posts tweet 5 and then tweet 3. The feed lists the newest first: [3,5].

Example 3

Input: operations = ["Twitter","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"], arguments = [[],[1,5],[5,10],[1],[1,5],[1]]

Output: [null,null,null,[10],null,[]]

Explanation: User 1 follows user 5, so tweet 10 from user 5 appears in user 1's feed. After unfollowing, user 1 has no visible tweets, so the feed is [].

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 himself.

How to solve Design Twitter: approach and complexity

Timestamped Tweets + Merge Recent: O(T log T) feed time, O(N) space.

Stamp every tweet with a global increasing time. A news feed is the 10 most recent tweets among the user and everyone they follow — gather those tweets and pick the newest ten.

Watch it run step by step

226. Design Twitter

MediumDesign

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see the 10 most recent tweets in the user's news feed. Implement the Twitter class: - Twitter() Initializes your twitter object. - void postTweet(int userId, int tweetId) Composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId. - List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user's news feed. Each item must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent. - void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId. - void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.

Examples

Example 1

Input: operations = ["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"], arguments = [[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]

Output: [null,null,[5],null,null,[6,5],null,[5]]

Explanation: User 1 posts tweet 5 and sees [5]. After following user 2, who posts tweet 6, user 1's feed shows [6,5] (newest first). Once user 1 unfollows user 2, tweet 6 disappears and the feed is [5] again.

Example 2

Input: operations = ["Twitter","postTweet","postTweet","getNewsFeed"], arguments = [[],[1,5],[1,3],[1]]

Output: [null,null,null,[3,5]]

Explanation: User 1 posts tweet 5 and then tweet 3. The feed lists the newest first: [3,5].

Example 3

Input: operations = ["Twitter","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"], arguments = [[],[1,5],[5,10],[1],[1,5],[1]]

Output: [null,null,null,[10],null,[]]

Explanation: User 1 follows user 5, so tweet 10 from user 5 appears in user 1's feed. After unfollowing, user 1 has no visible tweets, so the feed is [].

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 himself.

How to solve Design Twitter: approach and complexity

Timestamped Tweets + Merge Recent: O(T log T) feed time, O(N) space.

Stamp every tweet with a global increasing time. A news feed is the 10 most recent tweets among the user and everyone they follow — gather those tweets and pick the newest ten.

Watch it run step by step