Design Twitter

The key idea

Problem

Design a simplified version of Twitter where users can post tweets, follow or unfollow another user, and see the 10 most recent tweets in their own news feed.

Implement the Twitter class with these methods:

- postTweet(userId, tweetId) composes a new tweet with id tweetId by the user userId. Each call uses a unique tweetId.
- getNewsFeed(userId) retrieves the 10 most recent tweet ids in the user's news feed. Each item must be posted by users the user follows or by the user themselves. Tweets must be ordered from most recent to least recent.
- follow(followerId, followeeId) makes the user followerId start following the user followeeId.
- unfollow(followerId, followeeId) makes the user followerId stop following the user followeeId.

Constraints

• 1 <= userId, followerId, followeeId <= 500
• 0 <= tweetId <= 10^4
• All tweet ids are distinct
• At most 3 * 10^4 calls in total across postTweet, getNewsFeed, follow, and unfollow
• A user cannot follow or unfollow themselves

Examples

Complexity

Time: O(F + k log F) Space: O(U + T)

More Design problems

• Binary Search Tree IteratorMEDIUM
• Design Circular QueueMEDIUM
• Design HashMapEASY
• Design HashSetEASY
• Detect SquaresMEDIUM
• Encode and Decode StringsMEDIUM
• Implement Queue using StacksEASY
• Implement Stack using QueuesEASY
• Insert Delete GetRandom O(1)MEDIUM
• LFU CacheHARD
• LRU CacheMEDIUM
• Maximum Frequency StackHARD